Minimum Edit Distance

This builds on Regular Expressions and Text Normalization, which turned a raw character stream into clean tokens. That gave us strings to work with; this lesson gives us a way to compare two of them.

Measuring string similarity

Much of language processing needs to measure how similar two strings are. A speller seeing graffe should rank giraffe (one insertion away) above grail (several edits away). A coreference system, deciding whether Stanford President Marc Tessier-Lavigne and Stanford University President Marc Tessier-Lavigne name the same person, uses the fact that the strings differ by a single word. Minimum edit distance quantifies both intuitions: it counts the smallest number of one-character edits that turn one string into the other, so a small distance means the strings are close.

The clearest way to see a distance is as an alignment — a correspondence between the characters of the two strings, with a symbol under each column recording the operation. For intention → execution, one minimum alignment uses five operations (one deletion, three substitutions, one insertion); under the substitution-cost-2 Levenshtein it costs $8$.

The dynamic-programming algorithm

How do we find the minimum? Naively, the space of edit sequences is enormous — but most sequences pass through the same intermediate strings, so the work collapses. That overlap is what dynamic programming exploits: solve the big problem by combining stored solutions to overlapping sub-problems. Minimum edit distance is one of the field's canonical DP algorithms, alongside Viterbi decoding and CKY parsing; if you have met DP in a string-algorithms course, this is the same table-driven method, applied to language.

Let $X$ be the source string of length $n$ and $Y$ the target of length $m$. Define $D[i,j]$ as the edit distance between the first $i$ characters of $X$ and the first $j$ characters of $Y$. The answer is $D[n,m]$. The base cases are the distances from the empty string: turning $i$ characters into nothing takes $i$ deletions, so $D[i,0]=i$; the reverse takes $j$ insertions, so $D[0,j]=j$. Each interior cell is the cheapest of the three moves that reach it — a deletion from above, an insertion from the left, or a substitution (or match) from the diagonal:

The three cases are the three ways the last characters can be handled:

• Deletion: align $X$'s first $i-1$ characters against all $j$ of $Y$'s, then delete $X[i]$
• Insertion: align all $i$ against the first $j-1$, then insert $Y[j]$
• Substitution or match: align the first $i-1$ against the first $j-1$, then substitute $X[i]$ for $Y[j]$, or pay nothing if they already match

The cell keeps the cheapest of the three.

Under the Levenshtein weighting — insertion and deletion cost $1$, a substitution costs $2$ except that matching a letter to itself is free — this specializes to

Fill the table row by row from the bottom-left corner: initialize the border, then sweep every interior cell, taking the running minimum.

A worked table

For $X=\text{intention}$ and $Y=\text{execution}$ under the substitution-cost-2 Levenshtein, the completed matrix reads $D[9,9]=8$ in the top-right corner. The source runs up the left edge, the target across the bottom; each cell holds the minimum edit distance between the two prefixes meeting at it.

The backtrace

The distance alone gives the cost of the best alignment; with one extra bookkeeping step, the same table also recovers the alignment itself. While filling the matrix, store in each cell a backpointer to the neighbor (or neighbors) that supplied its minimum: a left arrow for an insertion, a down arrow for a deletion, a diagonal for a substitution or match. After the table is full, backtrace from the top-right cell, following pointers back to the origin. The path of cells you walk is a minimum-cost alignment — a diagonal step aligns two characters, a horizontal step is an insertion, a vertical step a deletion.

Walk the intention → execution table concretely. Starting from the answer cell $D[9,9]=8$, at each step you look at the three neighbors that could have produced the cell and step to whichever one the recurrence used. The path recovered is a diagonal at every column except one deletion near the start and one insertion in the middle, and reading the operations off the path in source order gives:

Adjusting for the one deletion and one insertion in the full alignment, the operation tally is one deletion, one insertion, and three substitutions that touch distinct characters, plus four free matches on the shared suffix tion. Under the substitution-cost-2 weighting that is $1+1+3\cdot 2=8$, matching the corner cell exactly. The alignment is what a downstream task consumes: a speller uses it to say which letters to change, and a diff tool uses the same path to show insertions and deletions between two files.

Drawn on the real matrix, the path is not the schematic diagonal but a concrete staircase through the actual cells. It leaves the answer $D[9,9]=8$, walks the free suffix tion straight down the diagonal at constant cost $8$, drops one cell for the $n\to u$ substitution, takes one horizontal insertion of c, matches e, then two substitutions and a single vertical deletion of the leading i land it at the origin. Each arrow points from a cell to the predecessor that supplied its minimum, so the whole path is read from top-right to bottom-left; reversing it recovers the edit sequence in source order.

That extra step generalizes. Allow arbitrary operation costs — say, cheaper substitutions between letters adjacent on a keyboard — and the same table becomes a spelling-correction engine. Replace minimum cost with maximum probability and the recurrence becomes the Viterbi algorithm, used throughout sequence labeling and speech recognition. The DP table filled for intention → execution is the same machinery, reused across the subject.¹

Weighted edits and the cost of the alignment

The Levenshtein weighting charges every substitution the same, but the framework does not require it. Replace the constant sub-cost with a per-pair cost — a confusion matrix — and the same table computes a distance tuned to a real error model. For spelling correction the natural costs come from how often one letter is mistyped for another: substituting e for a (adjacent readings, common typo) should cost less than substituting e for q. For biological sequence alignment the costs come from substitution matrices estimated from evolution, and the identical DP, run with a gap penalty and those costs, is the Needleman–Wunsch algorithm. Nothing in the recurrence changes; only the three cost functions do. This is why edit distance is a template rather than a single algorithm: fix the costs and you fix the notion of similar.