How a diff checker works

Reading the graph

Put the original text across the top and the changed text down the side. Every route from the top-left corner to the bottom-right corner is one way of turning the first into the second:

• a step right deletes a unit of the original (costs 1 edit);
• a step down inserts a unit of the changed text (costs 1 edit);
• a diagonal step keeps a unit that's the same in both (free). Diagonals exist only where the letter across matches the letter down.

So the best diff is the route that uses the most free diagonals and the fewest right-and-down steps. Runs of diagonals are called snakes.

Myers' idea: try 0 edits, then 1, then 2…

Checking every route would be hopeless for real documents. Eugene Myers' 1986 insight was to grow the search by edit count. With D edits, a route can only end on a few diagonals of the grid, and for each one you only need to remember how far along it you got. At each step, every path spends one more edit (right or down), then slides down any snake for free. The first path to reach the corner has, by construction, the fewest edits possible.

Because the work depends on the number of edits, comparing two drafts that differ by a few sentences is nearly instant even when they're long. Two texts with nothing in common are the slow case, which is why textdiff stops after a few seconds on huge, unrelated inputs rather than freezing your tab.

Same edit, three granularities

Diff tools line texts up by line first. What you see next depends on the unit used inside a changed line:

Why two tools can disagree

There are often several shortest routes. In ABCABBA → CBABAC above, more than one script has 5 edits. Myers' algorithm prefers deletions before insertions when there's a tie, which is why diffs tend to show the red line above the green one. Git's patience and histogram options first anchor on lines that occur only once in each file, which often gives more natural results for code with many repeated lines like }. None of them detect moved blocks: a moved paragraph is a deletion plus an insertion.

A diff can show you precisely what differs between two versions, but never why it differs. Chasing the why is what ahaboo's narrated explainers do, for questions like why the Moon cycles through its phases.

Ready to use it? Compare two texts, or try string compare to see character mode with hidden characters named.