How does a computer know what changed?

What is a diff?

A diff is the smallest list of changes that turns one text into another. These two shopping lists are nearly identical — one line differs.

A − means removed, a + means added, everything else stayed put. The real question is the interesting one: how does a computer decide that this is one substitution rather than deleting five lines and writing five new ones?

How it works, in three steps

No mathematics in this part. This is the whole idea.

1. 1

   Lay it out as a grid

   The old text runs across the top, the new text runs down the side. Every point on the grid means "used this many old lines and this many new ones". The change becomes a question of finding a route from the top-left corner to the bottom-right.

2. 2

   Find the cheapest route

   Stepping right deletes one old line. Stepping down inserts one new line. Running along a diagonal is free — those are the lines that are identical on both sides. The best diff is the route with the fewest paid steps.

3. 3

   Read the route back

   The winning route is translated back into the list of − and + lines you are used to seeing. Right becomes a deleted line, down becomes an inserted one, diagonal becomes a line left alone.

If you want the detail

Given sequences A (length N) and B (length M), build an edit graph: a grid of (N+1) × (M+1) points, where point (x, y) means "consumed x elements of A and y of B". A diff is a path from (0,0) to (N,M). The shortest edit script is the path with the fewest non-diagonal moves.

Why k, and why that is what makes it fast

Look at the last column. A diagonal step raises x and y together, so k = x − y does not change — free, and still on the same diagonal. Only a paid step moves k, by exactly one, left or right. Which means: after d edits only the diagonals from −d to +d are reachable at all, and on each of them there is just one number worth keeping — the furthest point reached. That is where an (N+1)×(M+1) grid collapses into a single row of at most 2d+1 numbers, and why the search is O((N+M)·D) rather than O(N·M). Myers §2.

One search, with the numbers

The two shopping lists from earlier, run to completion. No controls in this part — just the values the algorithm actually produces at each level of d.

1. d = 0

   (2, 2)

   Start at (0,0). "milk" and "eggs" are the same on both sides, so both are taken for free down the diagonal, as far as (2,2). Nothing paid for yet, two lines already accounted for.

   V afterwardsk0 x 2

2. d = 1

   One edit allowed, so two diagonals open from (2,2). Going right deletes "sugar" and lands on (3,2); going down inserts "salt" and lands on (2,3). Nothing matches after either, so neither slides, and neither has reached (5,5).

   V afterwardsk-1 x 2k0 x 2k1 x 3

3. d = 2

   (5, 5)

   Two edits. From (3,2), a step down inserts "salt" and lands on (3,3) — where "bread" and "coffee" match, so both are free through to (5,5). Done.

   V afterwardsk-2 x 2k-1 x 2k0 x 5k1 x 3

D = 2: one line deleted, one inserted, four left alone. That is the diff you read at the top of this page.

Glossary

The algorithm terms are deliberately left in English so you recognise them again in the paper and in real source code. Here they are in plain language.

diff

The list of changes between two texts — what was removed, what was added.

edit script

The sequence of steps that turns A into B. It is the answer being searched for.

edit graph

The grid the search happens on. One axis is the old text, the other is the new one.

D

How many paid steps the answer takes — lines deleted plus lines inserted. Smaller is tighter.

snake

A run of lines that are identical on both sides, travelled for free. It shows up as a diagonal.

frontier

How far the search has reached so far. It expands one step at a time — it is the part that moves.

diagonal k

Which diagonal of the grid you are on, k = x − y. The algorithm’s way of saying "which slanted lane".

the V array

A small note of the furthest point reached on each diagonal. It is the only data the algorithm really keeps.

backtrack

The second phase. Once the search reaches the corner, the route is read back out of the recorded V — that is what turns "the distance is 2" into the actual list of lines.

tie-breaking

What happens when two moves are equally good. The rule is arbitrary but fixed — and it is that rule, not any judgement, that decides which of several equally short diffs you are shown.

hunk

One block of nearby changes in a diff, with a few lines of context around it. The same diff can come out as one hunk or several; fewer is usually easier to read.

tokenize

Turning text into a list of numbers before comparing it — one number per line, word or character. What counts as an "element" is your choice, and the choice changes the answer.

O(...)

Shorthand for how the cost grows as the input grows, ignoring constants. O(N·M) means "proportional to the two lengths multiplied"; O((N+M)·D) means "proportional to their sum times the size of the change" — far smaller when the change is small.