Card 05/ 09
Compute the Edit Distance Between Two Words
Each entry is the cheapest of deleting, inserting or substituting the last letter, or keeping it free when it matches.
The edit distance between two words is the fewest single-letter edits that turn one into the other, where an edit inserts a letter, deletes one or substitutes one for another. It is also called the Levenshtein distance. This walkthrough fills the edit distance table for CART and CHAT, reads the distance from the last cell, and walks back to name the edits.
Entry (i, j) holds the fewest edits that turn the first i letters of CART into the first j letters of CHAT. When the last letters of the two prefixes match, they cost nothing and the entry copies its diagonal. Otherwise the entry is 1 plus the smallest of three neighbours, one for each edit: above means deleting the last letter of CART's prefix, left means inserting the last letter of CHAT's prefix, and the diagonal means substituting one for the other.
Before the table: how many edits turn CART into CHAT?
- C and T stay, and the two middle letters are each substituted: A becomes H and R becomes A. The table below reaches the same number.
Filling the edit distance table for CART (rows) and CHAT (columns)
Row C
Row 0 counts insertions: building C, CH, CHA and CHAT from nothing costs 1, 2, 3 and 4. Column 0 counts deletions in the same way. C matches C, so that entry copies its diagonal, 0. The rest of the row is 1 more than the entry to its left, one insertion per letter of CHAT.
| Prefix | Empty | C | H | A | T |
|---|---|---|---|---|---|
| Empty | 0 | 1 | 2 | 3 | 4 |
| C | 1 | [0] | 1 | 2 | 3 |
Row A
Against H, A is 1 plus the smallest of above, 1, left, 1, and diagonal, 0: one substitution. A matches A, so that entry copies its diagonal, the C and H entry, which holds 1.
| Prefix | Empty | C | H | A | T |
|---|---|---|---|---|---|
| Empty | 0 | 1 | 2 | 3 | 4 |
| C | 1 | 0 | 1 | 2 | 3 |
| A | 2 | 1 | 1 | [1] | 2 |
Row R
R matches nothing in CHAT, so every entry is 1 plus its smallest neighbour. Against A, the diagonal holds 1, so the entry is 2: CAR becomes CHA with two substitutions.
| Prefix | Empty | C | H | A | T |
|---|---|---|---|---|---|
| Empty | 0 | 1 | 2 | 3 | 4 |
| C | 1 | 0 | 1 | 2 | 3 |
| A | 2 | 1 | 1 | 1 | 2 |
| R | 3 | 2 | 2 | 2 | 2 |
Row T
T matches the final T, so the last entry copies its diagonal, the R and A entry, which holds 2.
| Prefix | Empty | C | H | A | T |
|---|---|---|---|---|---|
| Empty | 0 | 1 | 2 | 3 | 4 |
| C | 1 | 0 | 1 | 2 | 3 |
| A | 2 | 1 | 1 | 1 | 2 |
| R | 3 | 2 | 2 | 2 | 2 |
| T | 4 | 3 | 3 | 3 | [2] |
The distance is the last cell, 2, which a run confirmed. To name the edits, walk back from that cell and, at each step, move to a neighbour that explains the entry's value. T matches and its diagonal holds the same 2, so T is kept free. The R and A entry is 1 more than its diagonal, so R is substituted with A. The A and H entry is 1 more than its diagonal, so A is substituted with H. C matches with a diagonal of 0, so C is kept. Read forwards, the edits are keep C, substitute A with H, substitute R with A, keep T, as the run printed.
Row 0 and column 0 are where edit distance differs from the longest common subsequence: they are not zeros but the cost of building or erasing a prefix, one edit per letter. Leave them as zeros and every distance comes out too small.
← → move through sections and cards