Motivation
Two strings can differ because a character was inserted, deleted, or substituted. Counting mismatched positions is not enough: an insertion near the beginning shifts every later position, yet may require only one edit. Edit distance asks for the smallest number of permitted operations that transforms one string into another. It is useful whenever we need a precise comparison based on these operations, but its value depends on the cost model we choose.
The dynamic program works on pairs of prefixes. Its central idea is to classify the last column of an alignment, which relates an optimal global transformation to smaller prefix problems. The table is both a way to compute the distance and a record from which an optimal transformation can be reconstructed.
Definitions
Definition 2.10.1
(Edit operations and alignments)
Let and be finite strings over the same alphabet. A permitted operation inserts one character, deletes one character, or substitutes one character for a different character; each costs one. All intermediate strings are allowed. Let be the minimum cost of transforming into . Empty prefixes have length zero.
An alignment places the characters of the two strings into columns, in their original orders, allowing a gap in either row but not gaps in both rows. A column with two equal characters costs zero, a column with two different characters costs one, and a column with one gap costs one. The cost of an alignment is the sum of its column costs.
Theorem 2.10.2
(Edit sequences and alignments)
For any two finite strings, the minimum number of unit-cost insertions, deletions and substitutions equals the minimum cost of an alignment of those strings.
Theorem 2.10.3
(Prefix recurrence)
The boundary values are and . For ,
where the bracket is one if the two characters differ and zero otherwise. Filling the table in increasing row and column order computes in time and space, with constant-time character comparison.
Proof: why alignments capture edits
Proof
(Edit sequences correspond to alignments)
An alignment gives an edit sequence of the same cost. Scan its columns from left to right. If a column has the same character in both rows, leave that character unchanged. If it has different characters, substitute the upper one by the lower one; if its lower row is a gap, delete the upper character; if its upper row is a gap, insert the lower character. The order of columns ensures that the operations can be applied from left to right while preserving the unprocessed suffix. Hence the minimum edit cost is at most the minimum alignment cost.
For the other direction, consider any edit sequence and track each character in the current string back to its original character, if it has one. Inserted characters have no original ancestor; substitutions preserve a character's ancestry and deletions remove it. Operations never reorder the surviving ancestors. In the final string, align every surviving original ancestor with its final descendant. Align a deleted original character with a gap, and an inserted final character with a gap. Place these unmatched characters in their original and final orders between consecutive matched ancestors.
Each original character aligned to a different final descendant must have been substituted at least once. Each deleted original character must have been deleted, and each final character with no original ancestor must have been inserted. These are distinct operation charges; intermediate insertions later deleted and repeated substitutions only increase the sequence's cost. Thus the resulting alignment costs no more than the edit sequence. Taking minima proves equality. This ancestry argument permits arbitrary intermediate edits; it does not assume in advance that an optimal sequence has a convenient last operation.
Proof: the prefix recurrence
Proof
(The prefix recurrence from the last column)
For an empty target, every source character must be deleted; for an empty source, every target character must be inserted. This proves the boundary values. Now consider a minimum-cost alignment of two nonempty prefixes. Its last column is exactly one of three kinds: above a gap, a gap above , or above . Removing that column leaves an alignment of the corresponding smaller prefixes. Its cost is the cost of that column plus at least the optimum for those prefixes. This yields a lower bound by the displayed minimum.
Conversely, append each of the three possible final columns to an optimal alignment for the corresponding smaller prefixes. The resulting alignment is valid and attains the associated candidate cost. The minimum candidate is therefore achievable, proving equality. By the alignment theorem, this is also the minimum number of edits.
Every entry depends only on the entry above, the one to its left and the one diagonally above-left. Filling row by row from the initialized top row and left column makes all three available. There are entries and constant work per entry under the stated model, giving the time and space bounds. If only the distance is needed, keeping the preceding row and the part of the current row already filled uses space; swapping the roles of the strings gives space. This reduced-space calculation alone does not retain a complete backtracking table.
Proof X-ray
The last alignment column
The three cases are exhaustive and disjoint: delete the final source character, insert the final target character, or align the two final characters. The equal-character case has zero cost; the unequal case is a substitution. The proof compares complete alignments rather than guessing which literal edit occurred last in an arbitrary edit script.
Worked examples
Worked example 2.10.4
(A shifted suffix)
Transform cat into cart by inserting r between a and t. An alignment is
and has cost one. The strings are different, so zero edits cannot suffice. Their distance is exactly one, despite the shifted position of the final t.
Worked example 2.10.5
(A complete small table)
For source ab and target ac, the prefix-distance table is
The bottom-right entry is one: align the two a characters and substitute b by c. At that cell the diagonal candidate is , while deletion and insertion each give two.
Worked example 2.10.6
(Multiple optimal scripts)
For ab and ba, two substitutions give cost two. Deleting the first a and inserting an a at the end also costs two. One operation cannot produce the target: a substitution changes only one position, and an insertion or deletion changes the length. The optimum is two, and backtracking ties may return different optimal alignments.
Worked example 2.10.7
(Empty strings)
The distance from the empty string to dog is three: insert its three characters. No operation inserts more than one character, so fewer cannot suffice. The first row of the table records this reasoning for every target prefix.
Reconstructing an edit sequence
Start at . At each non-boundary cell choose a predecessor that achieves the recurrence minimum: above for a deletion, left for an insertion, or diagonal for a match or substitution. On a boundary, take the only possible moves along that boundary. Every move decreases , so the process stops at after at most steps.
The backtracking moves describe alignment columns in reverse order. Reverse the recorded list, then scan its columns from left to right to apply the operations as in the first proof. Tie-breaking may be arbitrary: equality with the table entry guarantees that the sum of recorded column costs equals . Writing operations in the reverse backtracking order without adjusting indices can produce the wrong script, so the alignment provides a stable intermediate representation.
For example, from the bottom-right entry of the ab versus ac table, a diagonal move records the substitution , and the next diagonal move records the match . Reversing the recorded columns gives the match followed by the substitution. The resulting edit script changes the second character once.
Concept lensStructural
The table as a shortest-path problem
Take the grid graph on vertices with and . Give the edge cost one, the edge cost one, and the edge cost . Then is the least cost of a path from to , and each path from to is an alignment, column by column. Optimal alignments are exactly the shortest paths, and backtracking walks one shortest path in reverse.
Common mistakes
Counterexample mode
Hamming distance is not edit distance
The equal-length strings abc and bca differ in all three positions, but deleting the first a and inserting it at the end uses only two edits. Position-by-position mismatch count can overestimate edit distance because deletions and insertions change the alignment.
Common mistake
(Reusing the unit-cost table for another cost model)
The recurrence depends on the permitted operations and their costs. If a substitution costs two rather than one, the diagonal candidate must add two for a mismatch. Otherwise a to b would get distance one, whereas the cheapest script now is a deletion plus an insertion, of cost two. If transposition is an allowed single operation, a different recurrence and proof are needed. A table computed for one model should not silently be interpreted as the distance for another.
Common mistake
(Reading the distance as an edit script)
A distance alone is also not a particular edit script. To output a script, retain enough predecessor information or recompute it with a separately justified method. Rolling rows save memory for the numerical answer but discard the complete table used by the simple backtracking procedure above.
Distance properties and their limits
The unit-cost distance is symmetric: reverse an edit sequence, replacing each insertion with the corresponding deletion, each deletion with the corresponding insertion, and each substitution by its reverse. This creates a sequence of the same cost in the opposite direction. Applying the argument in both directions proves .
It also satisfies the triangle inequality. Concatenate an optimal edit sequence from to with one from to . This gives a valid, though not necessarily optimal, sequence from to , so . The distance is nonnegative and is zero exactly when the strings are equal. Together these facts make the unit-cost edit distance a metric on finite strings.
The concatenated script can contain edits that cancel. For instance, transforming a to ab and back to a costs two in total, while directly transforming a to itself costs zero. The triangle inequality is therefore an inequality, not an assertion that passing through a chosen intermediate string is always optimal.
Choosing a table orientation
The rows and columns may be swapped for this symmetric model. If one string is much shorter, use it for the stored row in the reduced-space calculation. For instance, comparing a thousand-character string with a ten-character string still takes time proportional to their length product, but the row buffer needs only eleven entries. The arithmetic model assumes entries and indices fit the stated constant-time operations; representing unusually long strings may require an additional bit-cost analysis.
Space-saving and script reconstruction are different design goals. The full table makes it easy to follow a predecessor at each step and verify its equality with the stored value. A rolling-row implementation should promise only the distance unless it also implements and proves a reconstruction method. This distinction prevents a complexity claim for the numerical answer from being silently applied to a full explanation of the chosen edits.
Summary
Alignment columns provide the bridge between arbitrary edit scripts and a recurrence on prefixes. The three possible last columns give deletion, insertion and match-or-substitution candidates. The completed table gives the optimum, and predecessor choices reconstruct an optimal alignment and edit sequence.
Exercises
Quick check
(Compute the edit distance from a to b and justify the answer.)
Solution · Answer
Substitute a with b for cost one. The strings differ, so zero operations cannot work; the distance is one.
Quick check
(Compute the edit distance from ab to a and give an optimal script.)
Solution · Answer
Delete the final b for cost one. Since the input and output lengths differ, at least one operation is necessary.
Exercise 2.10.8
(Give an alignment of abc and bca with cost two. Why is the distance not one?)
Foundation
Solution(3)
- 1
Exhibit an alignment of cost two
Align
awith a gap, thenbwithbandcwithc, then a gap with the finala. The cost is .Because: A column of two equal characters costs zero, and each column with a gap costs one.
- 2
Rule out a single edit
Key step
One edit is a substitution, an insertion or a deletion. A substitution changes only one position, but the strings differ in all three. An insertion or deletion changes the length, but both strings have length three.
- 3
Conclude that the distance is two
Zero edits would force the strings to be equal, and one edit is impossible, so the distance is at least two. The alignment shows it is at most two. Hence the distance is exactly two, and in particular not one.
Quick check
(For aa and a, list two distinct one-edit scripts and explain how ties arise in backtracking.)
Solution · Answer
Delete either the first or the second a. Both produce a at cost one. At the relevant table cells, different minimum-cost predecessor paths align the target a with different occurrences in the source. Repeated characters make these alignments distinct even though the resulting string is the same.