Minimum edit distance: alignments and search

A speech recognizer hears "turn on the kitchen light" and writes "turn on a kitchen light please". A spell checker sees "acress". An OCR engine reads the two letters "rn" as an "m". In each case there is a string we have and a string we want, and the question is the same: how much editing separates them?

The answer is the Minimum edit distance: the minimum total cost of the editing operations that turn a source string into a target string. Three operations are allowed. An insertion adds one symbol, a deletion removes one, and a substitution replaces one with another. Each operation has a cost, most often 1, and the distance is the cheapest way of getting from source to target, not the first way you happen to find. With every operation at cost 1 (and a substitution of a letter by itself at cost 0) this quantity is the Levenshtein distance, after the 1966 paper that introduced it for error correcting codes. Nothing in the definition says the symbols must be letters. Take words as the symbols and the same definition measures how far a recognized sentence is from its transcript, which is exactly how speech recognition uses it.

The spelling application is older than most of NLP. Damerau found in 1964 that a single wrong, missing, extra or transposed letter accounts for about 80 percent of spelling errors, which is why candidate generation at edit distance 1 works so well: Kernighan, Church and Gale's spelling corrector lists exactly the six one-edit candidates for "acress" shown in the table and then picks among them with a probabilistic model. Approximate matching generalizes the search direction: instead of comparing two whole strings, you look for places in a long text that a pattern would match after at most k edits.

Word error rate, computed

The Word error rate (WER) is edit distance applied to words. Align the recognizer's hypothesis to the human reference at the word level, count the insertions, substitutions and deletions on that alignment, and divide by the number of words in the reference. The denominator is the reference, never the hypothesis, and because insertions are counted the rate can exceed 100 percent.

SLP3's own CallHome example has 6 substitutions, 3 insertions and 1 deletion over 13 reference words, a WER of 76.9 percent. The standard scorer is NIST's sclite in the SCTK toolkit, which does the alignment and the arithmetic for you but reports exactly these counts.

Lay the two words on top of each other as on slide 82, with a star for a gap, and read the ten columns from left to right: I over a star, N over E, T over X, E over E, a star over C, N over U, and then T I O N over T I O N. The row underneath, d s s _ i s, names the columns that cost something: delete I, substitute N by E, substitute T by X, insert C, substitute N by U. Five operations, and five is the minimum edit distance.

What you just read is an Alignment: a correspondence between the two strings that says, for every symbol, what it lines up with. A column with the same letter top and bottom is a match and costs nothing. A column with two different letters is a substitution. A letter over a gap is a deletion (the source letter is consumed without producing anything), and a gap over a letter is an insertion. The cost of an alignment is the sum of its column costs, and the minimum edit distance is simply the cost of the cheapest alignment. The practical half of the story is that the dynamic programming table does not just give the number, it stores a Backpointer in each cell, and following those pointers back from the last cell recovers one cheapest alignment. Part 11 does that recovery by hand.

Two cost conventions, and the same words come out as 5 or 8

Here is the trap this lecture sets, and the reason this section exists. Slides 85 and 86 define the Substitution cost as 1 for two different letters. The filled table you will meet in part 11 (slides 89 and 91) is copied from SLP3, and SLP3 fills it with a substitution cost of 2. Levenshtein proposed both: in his second version insertions and deletions cost 1 and substitutions are simply not allowed, and since any substitution can be written as a deletion followed by an insertion, that is the same as allowing it at cost 2. Both are legitimate cost functions. They give different numbers, and they can disagree about which alignment is best.

Read the totals again: 1 + 1 + 1 + 0 + 1 + 1 = 5 under unit costs and 1 + 2 + 2 + 0 + 1 + 2 = 8 with substitutions at 2. Both describe the same alignment. If an exam asks for the distance from intention to execution and you answer 8 without saying why, the grader who has the slide 85 recurrence in mind will mark it wrong, and the reverse is also true.

Try it: label the columns yourself

The editor below shows three alignments of intention and execution, with the four trailing matches already labeled. Label every remaining column, watch the two totals update, and then compare the presets. The third one pairs the letters position by position with no gaps at all: five substitutions. Under unit costs it ties the slide alignment at 5. With substitutions at 2 it costs 10 and loses to 8. The cost function does not only change the total; it changes which alignments are optimal.

The obvious algorithm is search. Start at intention and try one edit: delete a letter and you get ntention, insert a letter and you get intecntion, substitute a letter and you get inxention. Those are three of the children. Count all of them for a 26-letter alphabet: 9 possible deletions, 26 × 10 = 260 insertions and 25 × 9 = 225 substitutions, which is 494 children for one step. A blind search that needs five steps to reach execution touches on the order of 494^5, about 3 × 10^13 strings. SLP3 puts it plainly: the space of all possible edits is enormous, so we cannot search naively.

The visual shows the observation that rescues the problem. Delete the i of intention and then substitute t by x and you reach nxention. Substitute t by x first and then delete the i and you reach nxention again. Two paths, one state, and once you know the cheapest way to reach a state there is no reason to explore any other route into it. SLP3 states the idea directly: many distinct edit paths end up in the same string, so rather than recomputing all those paths we can remember the shortest path to a state each time we see it. Remembering subproblem answers and combining them is Dynamic programming, Bellman's table-driven method from 1957.

Why only prefix pairs matter

Remembering strings is still too many states. The step that makes the table small is to notice which states can matter at all. Suppose exention lies on an optimal path from intention to execution. Then the part of the path from intention to exention must itself be optimal, because if a shorter way to exention existed we could splice it in and shorten the whole path, a contradiction. This is the Optimal substructure argument in SLP3, and it means the only thing worth remembering about a partial solution is how much of the source it has consumed and how much of the target it has produced: the pair (i, j). For two 9-letter words there are only (m + 1)(n + 1) = 10 × 10 = 100 such pairs. Put as a picture: edits are moves in a grid from (0, 0) to (m, n), each move is one operation, and dynamic programming finds the best path efficiently.

A path from the top-left corner to the bottom-right corner that uses only these three moves is an alignment: each step is one column. Reading the slide 82 alignment as moves gives down, diagonal, diagonal, diagonal, right, then five diagonals, which is the staircase in the figure. Wagner and Fischer showed in 1974 that filling the grid solves the problem in time proportional to the product of the two lengths, O(mn) time and, with backpointers stored, O(mn) space. Each cell is filled once with three comparisons.

Three small questions give you the whole initialization. What is the distance from int to the empty string? You must delete i, n and t, so 3. From the empty string to ex? Insert e and x, so 2. From empty to empty? Nothing to do, 0. Write those as D[3, 0] = 3, D[0, 2] = 2 and D[0, 0] = 0 and you have the first row and column of every table you will ever fill.

Slide 85 sets the notation. The source x has length m, the target y has length n, and D[i, j] is the minimum edit distance between the prefix x[1..i] and the prefix y[1..j]. The answer to the whole problem is the last cell, D[m, n]. The Edit distance recurrence says how to fill every other cell from three neighbors.

Each line is one possible last column of an optimal alignment of the two prefixes. Either the last column is x_i over a gap, in which case the rest is an optimal alignment of x[1..i-1] with y[1..j] and we pay a deletion; or it is a gap over y_j, the rest aligns x[1..i] with y[1..j-1] and we pay an insertion; or it is x_i over y_j, the rest aligns the two shorter prefixes and we pay the substitution cost, which is zero when the letters agree. There is no fourth shape a column can take, so the minimum over these three is exact. That is the optimal substructure of the previous concept written as an equation.

Now the exam favorite: why is D[i, 0] = i? The target prefix is empty, so every one of the i source letters has to disappear, and the only operation that removes a source letter is a deletion. No insertion can help, since it would produce a target letter where none is wanted, and no substitution can help, since it leaves a letter in place. At one unit per deletion the cost is exactly i. The mirror argument gives D[0, j] = j. In the general form of SLP3's pseudocode the border is built incrementally, D[i, 0] = D[i-1, 0] + del(x_i), which reduces to i when deletions cost one.

A table you can fill in one minute

Before the 10 × 10 table of part 11, fill a tiny one under unit costs: cat to cats. The first row and column are the initialization. Every other cell is the minimum of the cell above plus one, the cell to the left plus one, and the diagonal cell plus zero or one.

What the cost function can encode

Slide 86 spells out the unit Substitution cost: sub(a, b) = 0 if a = b, else 1. It also says the cost can be weighted, and this is where edit distance stops being a counting exercise and becomes a model. SLP3's caption to its pseudocode notes that costs can be specific to the letter, and its text adds that for spelling correction substitutions are more likely between letters that are next to each other on the keyboard. Kernighan, Church and Gale estimated four confusion matrices (deletion, addition, substitution and reversal counts) from the typos in 44 million words of 1988 AP newswire and used them as the channel probabilities of a noisy-channel spelling corrector; their top candidate agreed with the majority of three human judges in 87 percent of 329 cases. Set a substitution cost to the negative log of such a probability and the cheapest alignment becomes the most probable one.

A cost function can also grow a fourth operation. Damerau's 1964 study listed transposition of two adjacent letters as one of the four single-error types. The simplest extension adds a fourth line to the Wagner-Fischer table, D[i-2, j-2] + cost, that applies when x_{i-1} = y_j and x_i = y_{j-1}; this restricted form is often called optimal string alignment distance, and it can overcount when a transposed pair is edited again. Lowrance and Wagner's 1975 algorithm handles that general case, and both are commonly labelled Damerau-Levenshtein distance. The typo teh for the costs 2 with the three classic operations (delete one letter, insert it elsewhere) but only 1 with transposition. The slide recurrence does not include this move; treat it as an optional fourth line you can add when the application calls for it.