From exact matches to edits
Exact string matching asks where a pattern occurs unchanged. A different question is how much work it takes to transform one string into another. Fix a finite sequence of symbols for each string; for text, agree on the symbol representation before applying the algorithm, since bytes, Unicode code points and displayed characters need not coincide.
Definition 6.2.1
(Edit distance)
Let and be finite sequences of symbols. An edit script transforms into by a finite sequence of operations, each inserting, deleting or substituting one symbol at cost one; keeping a symbol unchanged costs zero. The edit distance is the minimum total cost of such a script. The empty script has cost zero, and transposing two adjacent symbols is not a single allowed operation in this model.
Alignments and the recurrence
Definition 6.2.2
(Alignment and its cost)
An alignment of and places the symbols of and in two rows, preserving the order in each row. A column may pair two symbols, or pair one symbol with a gap; it cannot contain two gaps. Equal paired symbols cost zero; unequal pairs and single-gap columns cost one. The cost of an alignment is the sum of its column costs.
For example, aligning with can be written as
with cost two: substitute by , then insert .
Why should minimizing alignment cost give the edit distance? The next result says that it does, and the proof shows how to move between the two descriptions.
Theorem 6.2.3
(Alignment cost equals edit distance)
For all finite sequences and , the minimum cost of an alignment of and equals the edit distance .
Proof
(From alignments to scripts and back)
An alignment gives a script of the same cost: scan left to right, keep or substitute paired symbols, delete an upper symbol paired with a gap, and insert a lower symbol paired with a gap. Hence the minimum alignment cost is at least .
Conversely, follow symbol identities through any edit script: substitution preserves an identity, deletion ends it, and insertion creates one. The original symbols that survive into the final string remain in their original order, since no allowed operation swaps them. Pair each such original with its final descendant; pair each deleted original and each final inserted symbol with a gap. Between consecutive surviving pairs, before the first pair and after the last pair (or over the entire sequence if there are no surviving pairs), list deleted originals in their original order and inserted final symbols in their final order; the two lists can be placed one after the other without changing either row order.
Every unequal surviving pair required at least one substitution, each deleted original at least one deletion, and each final inserted symbol at least one insertion. These required operations are distinct, so the alignment costs no more than the script. This argument also permits extra edits that later undo one another; they cannot make the script cheaper than the alignment. The two minima are equal.
Definition 6.2.4
(Prefix table of alignment costs)
Write and . For and , let be the minimum alignment cost for the first symbols of and the first symbols of . For put if and otherwise.
Theorem 6.2.5
(Prefix recurrence for edit distance)
With the notation above, and , and for
Consequently .
Proof
(Removing and appending the final column)
Boundary: if one prefix is empty, every symbol of the other must pair with a gap, and each such column costs one. So and .
Now let . Upper bound: for each of the three candidates, take an optimal alignment of the smaller prefixes and append the matching final column, namely against a gap, a gap against , or against . Each result is an alignment of the two longer prefixes whose cost is the candidate value, so is at most the minimum of the three.
Lower bound: take an optimal alignment of the two prefixes. Its final column has exactly one of the three forms, since two gaps are not allowed. Removing it leaves an alignment of the appropriate smaller prefixes, whose cost is at least the corresponding table entry, and the removed column costs , or respectively. So is at least the candidate for that form, hence at least the minimum. Induction on applies the same argument to the smaller entries, and the boundary values start it. Finally by the previous theorem.
Proof X-ray
Why the last column is enough
The key move is to look only at the final column of an optimal alignment. There are exactly three forms because a column with two gaps is forbidden; this is where the definition of alignment is used. Removing the column leaves an alignment of smaller prefixes, and the cost is additive over columns, so no information is lost; that additivity is what lets a table of prefix costs replace a search over all alignments.
The argument closes by induction on , since every candidate refers to an entry with smaller index sum. The upper bound uses optimal sub-alignments, the lower bound uses an optimal whole alignment; both directions are needed. If a cost depended on neighboring columns, for example a cheaper opening of a long gap, removing one column would not leave an independent subproblem and this recurrence would fail.
The same table also has a second, equivalent description as a shortest-path computation.
Concept lensCombinatorial
Alignments are paths in a grid
Place the entries at the points of a grid. A down step from to is a column pairing with a gap, a right step is a gap against , and a diagonal step pairs with at cost . Alignments of and correspond exactly to monotone paths from to , and the alignment cost is the path length. The recurrence is then the usual shortest-path equation on this acyclic grid, and is the shortest distance from to .
A table and a witness
Worked example 6.2.6
(The table for CAT and CUTS)
For and , fill each row from left to right, starting with the empty-prefix boundaries:
| prefix / prefix | empty | C | CU | CUT | CUTS |
|---|---|---|---|---|---|
| empty | 0 | 1 | 2 | 3 | 4 |
| C | 1 | 0 | 1 | 2 | 3 |
| CA | 2 | 1 | 1 | 2 | 3 |
| CAT | 3 | 2 | 2 | 1 | 2 |
For instance, the entry for against is , where the diagonal candidate adds because . The entry for against is , because makes the diagonal step free. The bottom-right value proves that two edits are optimal; the alignment displayed earlier supplies a matching witness.
To reconstruct an optimum in general, start at and select any predecessor that attains the recurrence minimum, recording its column. A diagonal step records a match or substitution, an upward step a deletion, and a left step an insertion. At continue left, and at continue up, until reaching ; reverse the recorded columns. Ties can produce different optimal alignments, so an implementation needing deterministic output must specify a tie rule. Reading backwards without reversing gives the columns in the wrong order.
Theorem 6.2.7
(Traceback gives an optimal alignment)
Starting at , repeatedly move to a predecessor that attains the minimum in the recurrence (and along the boundary when or ), recording each column. Reversing the recorded columns gives an alignment of and of cost , hence an optimal one.
Proof
(Each step peels one column of an optimal prefix alignment)
Claim: the columns recorded from a cell down to , once reversed, form an alignment of the first and symbols of cost . Induct on . At the alignment is empty and costs . On the boundary the only move is up, each column deletes one symbol, and the cost is ; the case is symmetric.
Otherwise the chosen predecessor attains , where is the cost of the column recorded for the step. By hypothesis the reversed columns from form an alignment of cost , and appending the recorded column gives an alignment of the longer prefixes of cost . At this is an optimal alignment of and .
Worked example 6.2.8
(Reading the CAT and CUTS table backwards)
Start at , with value . The diagonal predecessor gives and the upward one gives , but the left one gives , so record an insertion of . At the diagonal predecessor gives , which attains the value, so record the match . At the diagonal gives and the other two give , so record the substitution . At the diagonal gives , so record the match , and we reach .
Reversing the recorded columns gives , , , , which is the alignment displayed earlier. Here no tie occurred at any step, so this is the only optimal alignment.
Worked example 6.2.9
(Ties and an edge case: AB against BA)
For and the table is
| prefix / prefix | empty | B | BA |
|---|---|---|---|
| empty | 0 | 1 | 2 |
| A | 1 | 1 | 1 |
| AB | 2 | 1 | 2 |
At the corner all three candidates equal two: up gives , left gives , and the diagonal gives . Each choice leads to an optimal alignment: two substitutions , ; or the columns , , ; or the columns , , . All have cost two. In particular the swap costs two in this model, and the table shows that no script with one operation exists, since .
The explorer below fills the table cell by cell, lists the three candidates and the attaining predecessors for each, and reads an optimal alignment back under a chosen tie rule.
Cost, memory and model choices
There are entries, each computed in constant time, so the full table costs time and space. If only the distance is needed, the recurrence needs the previous row and the current row, reducing working storage to ; a full stored table supports the simple backtrack above. Recovering an alignment with less memory needs extra work, not merely discarding all previous rows and then backtracking as before.
Changing operation costs changes the recurrence and may change its mathematical properties. In particular, a one-step adjacent swap is not included above: to has distance two in this model, even though a separate swap operation would cost one. The dynamic program returns a minimum edit cost, not a semantic judgment about whether two sentences mean the same thing.
Counterexample mode
Insertions and deletions alone give a different distance
A plausible claim is , where LCS is the length of a longest common subsequence. For and the longest common subsequence is , of length two, because does not occur in . The formula gives , but the table gives , witnessed by substituting by and inserting . The formula is the distance in the model with insertions and deletions only, where a substitution has to be simulated by a deletion and an insertion at cost two. With unit-cost substitution allowed, the recurrence above must be used.
Common mistakes
Common mistake
(Initializing the empty-prefix boundary to zero)
Setting says that turning the empty string into a string of length is free. For and the corrupted table gives , although and the true distance is one (insert ). The boundary records that each of the symbols of must be inserted.
Common mistake
(Comparing the wrong symbols on the diagonal)
The diagonal candidate at uses , which compares with , the last symbols of the two prefixes. If an implementation indexes from zero and compares with in a table indexed by prefix length, it is off by one. For and at it would compare with , giving instead of the correct .
Exercises
Quick check
(Compute the distance from to and exhibit an optimal script.)
Compare the lengths of the two strings first.
Solution · Answer
The distance is one. The script that deletes the final symbol turns into at cost one. No script of cost zero exists because the strings differ, so one is optimal.
Quick check
(Explain why the empty-prefix boundary is necessary. What goes wrong if it is initialized to zero?)
Ask what an empty prefix of can be paired with.
Solution · Answer
An empty prefix has no symbol to pair with the first symbols of , so every one of them is paired with a gap, at cost one each; hence . With zero initialization the table claims that insertions into the empty string are free. For and it then reports , although the strings differ and the true distance is one.
Quick check
(Suppose two transition candidates attain the minimum at . Must an optimal alignment of those prefixes exist ending with each of the two choices? Explain why a tie at a cell that lies on no optimal backtrack from need not give two optimal alignments of the full strings.)
For the second part, try and at the cell for and .
Solution · Answer
Yes. If a candidate attains the minimum, an optimal alignment of the smaller prefixes with the matching final column appended is an alignment of cost , hence optimal, and it ends with that column. So both endings occur.
A tie at a cell does not make that cell part of an optimal alignment of the full strings. In the table for and , the cell has value two reached both from above () and diagonally (). Both give optimal alignments of with . But completing either to must still insert and , for a total of at least , which exceeds . The cell is on none of the optimal backtracks from .