Tile the prefix grid with dynamic programming to find shortest paths through the alignment lattice.
- Watch a single insertion shift downstream characters into false mismatches
- Fill the recurrence table across diagonal matches and orthogonal edits
- Trace the backpointers to reconstruct the minimal diff script
After thisYou can power diff engines, spell-checkers, and genomic sequence aligners using dynamic programming.
Short on timeThe DPHeatmap interactive grid in §5
Eight Mismatches, Two Moves
3 minthe hook
Every diff tool you have run fills this table, and the obvious rival fails on the first insertion: count the columns that disagree. Take the pair emotions and demotion, and stack them:
e m o t i o n s
d e m o t i o n
Every one of the eight columns disagrees, because the inserted d shifts every later column by one. A reader who scores columns answers eight; a reader who is allowed to edit does better. Insert a d at the front, delete the trailing s, and the first word has become the second in two moves.
Position by position, all eight characters of emotions and demotion disagree. What is the edit distance — the fewest unit edits that turn one word into the other?
Eight apparent differences, two real edits. That gap is the whole page: edit distance is the price of a path, not the size of a difference.
Keep the tiled staircase in view: a grid with one tile for every pair of prefixes, and a path that steps from the empty pair at the top left to the full pair at the bottom right. Each tile holds the cheapest cost of reaching its pair, and the path through the tiles is the alignment.
NextWhy does a single shifted byte produce eight false mismatches in naive diffs?
The Mirage of Column Comparison
2 minthe trap
Operationally you are handed two strings and asked for one number — the fewest unit edits that turn the first into the second. Three moves count as a single edit each: delete a character, insert a character, replace a character. (Damerau 1964 would later add a fourth, the adjacent swap.)
“Count the characters that differ” is a different question, and a worse one. It is undefined when the lengths differ, and it is wrong even when they agree, as the two words above show. The strings never arrive with an alignment attached; choosing the alignment is part of the problem.
NextHow does the alignment problem map to finding the shortest path in a grid DAG?
The Infinite Graph of Words
2 minthe invariant
Fix a finite alphabet . The vertices are all finite strings : every word, every prefix, the empty string , every piece of garbage you can type. Join two strings with an edge when one is the other with a single character inserted, deleted, or replaced.
Every edge is one unit edit, so edit distance is graph distance:
The graph is infinite, and you never build it: you ask for one shortest path between two of its vertices. That is what makes a geodesic — the length of the shortest route through a space where “nearby” means “one typo away”.
The framing is not decoration. Graph distance is a metric, so inherits the triangle inequality for free, and that one property is what makes nearest-word search and error correction work. Levenshtein 1965 built the distance for exactly that purpose.
NextHow do substitution, insertion, and deletion costs determine the diagonal path?
Three Edge Types, One Metric Geodesic
2 minthe algebra
The table you drive below is this infinite graph, cut down to the two strings in hand.
The product graph, and the recurrence. Write for the prefix of of length , and likewise. A node stands for the pair of prefixes ; the node is and the node is the pair . To reach , the last edit was one of exactly three moves, and each is an edge of :
with and . This is the recurrence of Wagner and Fischer 1974, and its three terms are the three arrows that light up when you hover a cell. No fourth term exists: those three moves exhaust the ways one string can be a single edit from another.
A path is an alignment. A monotone walk from to selects matched pairs with both coordinates strictly increasing. Each unpaired index on the -side is a deletion, each unpaired index on the -side is an insertion, and a matched pair costs one when its two characters disagree:
The distance is the minimum of that cost over all matchings — the alignment view of Needleman and Wunsch 1970. You do not compare column by column; you thread the two strings together and pay for every unthreaded character and every mismatched pair. Needleman and Wunsch wrote the same recurrence for amino-acid sequences, with a general score per pairing.
Insert and delete only, and the longest common subsequence. Drop substitution. A matched pair is now free and each unmatched position costs one, so you match as many as you can. With the length of a longest common subsequence,
This is a derived identity — put into the alignment cost above — and it is the honest answer to the next prompt. For the two words on this page (the shared emotion), so : removing substitution changes nothing here, because the optimal script was already one insertion and one deletion.
1 minboss round
Ban substitutions entirely, allowing only insertions and deletions. How does the minimum edit distance between emotions and demotion change?
The metric axioms, and how the costs decide them. Three properties make a metric.
- Identity: , along the diagonal that matches every character, and forces .
- Symmetry: . Every edge has an inverse of the same weight — an insertion undone by a deletion — so reversing a script preserves its cost.
- Triangle inequality: . Run the script for , then the script for ; concatenating them is a script for (Levenshtein 1965).
Change the costs and the axioms change with them, because the metric is a property of the operations, not of the strings. Give deletion weight 1 and insertion weight 2 and symmetry dies — an insert can no longer undo a delete at equal cost.
Raise substitution to weight 2, the price of a delete plus an insert, and it is never worth using; the metric collapses back to . Unit costs for insertion, deletion, and substitution balance strictly between those two extremes.
Two bounds you can read off the picture. Each edit changes the length of a string by at most one, so , and padding the shorter string with substitutions and insertions costs at most , so . For emotions and demotion that sandwich is , and the alignment bound makes it exact at 2.
NextHow does Unix diff reconstruct version histories from the dynamic programming matrix?
Carving the Minimum Path
2 minthe simulation
Hover or click a cell: its predecessor cells light up and the exact recurrence that filled it appears here. Or press play to walk the fill order(81 cells in dependency order).
dp[i][j] = dp[i−1][j−1] if a[i]=b[j], else 1 + min( dp[i−1][j] (delete), dp[i][j−1] (insert), dp[i−1][j−1] (substitute) ).
Levenshtein edit distance of "emotions" and "demotion".
Hover any cell to light its incoming edges: delete from above, insert from the left, substitute from the diagonal. Press play to fill the 81 cells in dependency order, then Trace solution to walk the winning script back from the corner.
Watch the three arrows that light up when you hover a cell — delete from above, insert from the left, substitute from the diagonal — then press Trace solution and check that the chosen arrows form one monotone path through the tiled staircase; that single path is the alignment, not a column-by-column comparison.
The top-left cell is , and the top row and left column are pure insertions and deletions, so they read 1, 2, 3, … across and down. Every interior cell is its cheapest predecessor plus one, unless the two characters agree, in which case the diagonal is free and the cell copies its upper-left neighbour.
For your two words the bottom-right cell reads 2. Turn on Trace solution and the highlighted path through the tiled staircase walks the script out: the path steps right once along the top row (insert d), runs seven diagonal cells through the shared emotion, then drops one cell down the last column (delete s). The eight column mismatches never mattered, because the optimal path never steps on the diagonal through them.
Watch which cells the trace avoids. A shortest path leaves the main diagonal only by paying, and every step away costs an edit; the further off-diagonal a cell sits, the more edits already spent reaching it. That observation becomes the band in section 6.
NextWhat Strong Exponential Time Hypothesis barrier prevents sub-quadratic string comparison?
From Genome Assembly to Git Diffs
2 minsystems
Four tools run on this one number.
- Error-correcting codes. Levenshtein 1965 asked how far apart binary codewords must be when insertions and deletions are the enemy. A code with minimum distance corrects up to errors, and the proof is the triangle inequality: balls of that radius around the codewords are disjoint, so a corrupted word has at most one nearest codeword.
- Spelling and diff. The correction of a misspelling is the dictionary word at least edit distance away;
diffandgit blamerun the same DP over lines, and Myers’ walk (1986) makes the cost track the size of the change rather than the size of the files. - Sequence alignment. Needleman and Wunsch 1970 align proteins with this recurrence and a substitution matrix; Smith and Waterman 1981 relax the requirement to span both sequences and align locally. Every alignment score in bioinformatics is this table.
- Record linkage and near-duplicates. Comparing a name, an address, or a product title across two databases is a small edit distance with character-dependent costs, which is exactly where the operation weights start to matter.
Ukkonen’s Corridors and the SETH Barrier
The table has cells, so it costs time and space. Two consequences are worth carrying away.
A bounded-distance test needs only a band. Suppose you do not want itself but only the answer to “is ?” for a small . Every step of a path changes by at most one, and the path starts at , so any node on a path of cost at most must satisfy . Cells outside that diagonal band already carry a cost above , so a bounded-distance search can ignore them (Ukkonen 1985).
For equal lengths the band holds cells — , not . The chart below counts them for the full table and three fixed thresholds; the counts are exact arithmetic on that formula.
Cells a distance-≤-k test must fill — exact counts, band |i − j| ≤ k
The full table grows like and the bands grow like : at the full grid is over a million cells and the width-2 band is under six thousand. Myers 1986 sharpens the same idea to by walking the diagonals greedily, where is the answer itself — the algorithm inside diff.
You cannot in general beat the quadratic. Computing edit distance on length- strings has no known algorithm, and if one existed the Strong Exponential Time Hypothesis would fail (Backurs and Indyk 2015; Bringmann and Künnemann 2015). State that at the strength it deserves: this is a conditional lower bound, not a proof that no fast algorithm exists. It is why the quadratic table has stood for fifty years.
Lineage & Attributions
- Levenshtein 1965 — Binary codes capable of correcting deletions, insertions, and reversals: defines the distance and its metric property, motivated by error-correcting codes.
- Needleman and Wunsch 1970 — A general method applicable to the search for similarities in the amino acid sequence of two proteins: the alignment recurrence and the global-alignment lineage.
- Wagner and Fischer 1974 — The string-to-string correction problem: the dynamic program that computes the distance.
- Damerau 1964 — A technique for computer detection and correction of spelling errors: adds the adjacent transposition as a fourth edit.
- Ukkonen 1985 — the diagonal-band cutoff for bounded-distance search.
- Myers 1986 — the greedy diagonal algorithm, the engine inside
diff. - Smith and Waterman 1981 — local sequence alignment, the same table without the requirement to span both sequences.
- Backurs and Indyk 2015 · Bringmann and Künnemann 2015 — conditional quadratic lower bounds for edit distance under the Strong Exponential Time Hypothesis.
- Deza and Deza 2009 — Encyclopedia of Distances: the metric-space framing of edit distance among string metrics.