Edit distance

The edit distance between two strings, also called the Levenshtein distance, is the fewest single-letter insertions, deletions and replacements that turn one string into the other. Spell checkers use it to suggest the dictionary words closest to what was typed. Dynamic programming finds it with a grid over the prefixes of the two strings in $O(nm)$ time.

Explanation

Someone typed HOUSE but meant HORSE. Write one word above the other, letter under letter. Only the third column differs, U against R, so replacing one letter is enough, and the answer is 1.

Fig. 1. The top row is the word we change, the bottom row is the word we want. Each column is one place, and a coloured column is an edit.

Now turn SPORT into PARTY. Letters can also be deleted and inserted, and after a deleted or inserted letter every later letter moves one place.

Put the words letter under letter, as for HOUSE, and replace every letter that differs. S stands over P, P over A, O over R, R over T and T over Y. All five columns differ, so that is 5 replacements, the red columns in Fig. 2. Now delete the S instead, and the other letters slide one place to the left. PORT against PART differs in one place, so replace O by A, then insert Y at the end. That is 3 edits, the blue columns.

Fig. 2. Left: comparing place by place replaces every letter, 5 edits (red). Right: deleting S first lines the words up, 3 edits (blue).

So the question is which letter stands against which. Look at the last column. Whatever the edits are, the last column is one of three things. T stands against Y: T is replaced by Y, or kept if the letters were equal. T stands against nothing: T is deleted. Or nothing stands against Y: Y is inserted. Each case leaves the same question on shorter words, plus that one edit:

• T is replaced by Y: turn SPOR into PART, which takes 3 edits, plus 1 is 4;

• T is deleted: turn SPOR into PARTY, 4 edits, plus 1 is 5;

• Y is inserted: turn SPORT into PART, 2 edits (delete S, replace O by A), plus 1 is 3.

Fig. 3. The last column is a letter over a letter, a letter over a gap, or a gap over a letter. What is left before it is the same question on shorter words.

We don't know which case is best, so we try all three and take the smallest, 3. That is the third case, the blue answer. Each shorter question is solved the same way, and every question that comes up turns a prefix of SPORT (its first few letters) into a prefix of PARTY. Each word has 6 prefixes, from 0 to 5 letters, so there are only 6 × 6 = 36 questions, and their answers fit in a grid.

This is dynamic programming over pairs of prefixes, on the same grid as the longest common subsequence. SPORT runs down the left and PARTY across the top, and each cell holds the fewest edits that turn one prefix into the other. A cell is built from three neighbours: from the cell above by deleting the row's letter, from the cell to the left by inserting the column's letter, and from the cell up-left by keeping or replacing a letter. The row and the column marked ∅ are the empty prefixes.

Row ∅ and column ∅ are the empty prefixes: turning i letters into nothing takes i deletions, and turning nothing into j letters takes j insertions.

S and P are different: the smallest of 1 + 1, 1 + 1 and 0 + 1 is 1.

S and A are different: the smallest of 2 + 1, 1 + 1 and 1 + 1 is 2.

S and R are different: the smallest of 3 + 1, 2 + 1 and 2 + 1 is 3.

S and T are different: the smallest of 4 + 1, 3 + 1 and 3 + 1 is 4.

S and Y are different: the smallest of 5 + 1, 4 + 1 and 4 + 1 is 5.

P and P are equal, so keeping P adds nothing: the smallest of 1 + 1, 2 + 1 and 1 + 0 is 1.

P and A are different: the smallest of 2 + 1, 1 + 1 and 1 + 1 is 2.

P and R are different: the smallest of 3 + 1, 2 + 1 and 2 + 1 is 3.

P and T are different: the smallest of 4 + 1, 3 + 1 and 3 + 1 is 4.

P and Y are different: the smallest of 5 + 1, 4 + 1 and 4 + 1 is 5.

O and P are different: the smallest of 1 + 1, 3 + 1 and 2 + 1 is 2. It comes from above: O is deleted.

O and A are different: the smallest of 2 + 1, 2 + 1 and 1 + 1 is 2.

O and R are different: the smallest of 3 + 1, 2 + 1 and 2 + 1 is 3.

O and T are different: the smallest of 4 + 1, 3 + 1 and 3 + 1 is 4.

O and Y are different: the smallest of 5 + 1, 4 + 1 and 4 + 1 is 5.

R and P are different: the smallest of 2 + 1, 4 + 1 and 3 + 1 is 3.

R and A are different: the smallest of 2 + 1, 3 + 1 and 2 + 1 is 3.

R and R are equal: the smallest of 3 + 1, 3 + 1 and 2 + 0 is 2.

R and T are different: the smallest of 4 + 1, 2 + 1 and 3 + 1 is 3. It comes from the left: T is inserted.

R and Y are different: the smallest of 5 + 1, 3 + 1 and 4 + 1 is 4.

T and P are different: the smallest of 3 + 1, 5 + 1 and 4 + 1 is 4.

T and A are different: the smallest of 3 + 1, 4 + 1 and 3 + 1 is 4.

T and R are different: the smallest of 2 + 1, 4 + 1 and 3 + 1 is 3.

T and T are equal: the smallest of 3 + 1, 3 + 1 and 2 + 0 is 2.

T and Y are different: the smallest of 4 + 1, 2 + 1 and 3 + 1 is 3. The corner holds the answer, 3.

1/26

Fig. 4. The grid filled row by row. Step through it with the buttons or the arrow keys. The blue arrows come from the cell above, the cell to the left and the up-left cell, and the framed one gives the smallest number (up-left wins ties, then above, then left).

Every cell is an answer too: turning SPORT into PAR takes 3 edits.

Walking back to the edits

The corner says 3 but not which edits. To find them, start in the corner and step back to the neighbour its number came from. A step up-left keeps the letter if the two letters are equal and replaces it if not. A step up deletes a letter, and a step left inserts one. Fig. 7 shows the walk for SPORT and PARTY. The walk finds the edits from the end, so read them backwards: delete S, keep P, replace O by A, keep R, keep T, insert Y.

Fig. 5. The walk back from the corner. +Y inserts Y, = keeps a letter, O→A replaces O by A, −S deletes S.

At a cell where several neighbours give the same number, any of them is right, and the strings have several shortest lists of edits. For example, AB turns into BA by two replacements, or by deleting A and inserting A at the end. The walk takes one of them, depending on which neighbour it checks first.

Implementation

The first string is a with n letters, the second is b with m letters. The grid is a vector of vectors f with n + 1 rows and m + 1 columns. The five steps of dynamic programming, and restoring the edits, are:

1. State: f[i][j] is the fewest edits that turn the first i letters of a into the first j letters of b.

2. Base case: f[i][0] = i (delete all i letters) and f[0][j] = j (insert all j letters).

3. Order: i from 1 to n, and inside it j from 1 to m, so each cell comes after the cells above, to the left and up-left.

4. Transition: f[i][j] is the smallest of f[i - 1][j] + 1 (delete a[i - 1]), f[i][j - 1] + 1 (insert b[j - 1]) and f[i - 1][j - 1] + (a[i - 1] != b[j - 1]) (keep the letter if they are equal, replace it if not). Letter i of a is a[i - 1], because a string counts places from 0. For example, f[3][2] (O against A) is the smallest of 2 + 1, 2 + 1 and 1 + 1, which is 2.

5. Answer: f[n][m].

6. Restoring: walk back from (n, m). At each cell the program checks up-left first, then up, then left, and moves to the first neighbour the number came from.

Each step of the walk is one column of Fig. 2. A printed edit needs a position. The edits are applied from left to right, and each position counts letters in the string as it is at that moment. When the edits have reached cell (i, j), the string is the first j letters of b followed by the last n - i letters of a. So the edit that leads into (i, j) replaces or inserts at position j (up-left or left), or deletes at position j + 1 (up), counting from 1. On the main example, the edit into (1, 0) deletes position 1 (SPORT becomes PORT), the edit into (3, 2) replaces position 2 (PORT becomes PART), and the edit into (5, 5) inserts Y at position 5 (PART becomes PARTY).

The input is the two strings, separated by a space or on two lines. The program prints the edit distance and then one edit per line: delete p, replace p c or insert p c, where p is the position and c the new letter. For the main example the input is:

SPORT
PARTY

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();

    // state: f[i][j] = fewest edits that turn the first i letters of a into the first j letters of b
    vector<vector<int>> f(n + 1, vector<int>(m + 1));

    // base case: delete all i letters, insert all j letters
    // other costs: f[i][0] = i * (cost of a deletion), f[0][j] = j * (cost of an insertion)
    for (int i = 0; i <= n; i++) f[i][0] = i;
    for (int j = 0; j <= m; j++) f[0][j] = j;

    // order: row by row, each row left to right
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // transition: letter i of a is a[i - 1], letter j of b is b[j - 1]
            // other costs: use each edit's own cost instead of 1, here and in the walk back
            int del = f[i - 1][j] + 1;                              // delete a[i - 1]
            int ins = f[i][j - 1] + 1;                              // insert b[j - 1]
            int rep = f[i - 1][j - 1] + (a[i - 1] != b[j - 1]);     // keep or replace
            f[i][j] = min({del, ins, rep});
        }
    }

    // answer
    cout << f[n][m] << "\n";

    // restoring: walk back from (n, m); remove this block if you only need the distance
    vector<string> edits;
    int i = n, j = m;
    while (i > 0 || j > 0) {
        // the string is now b[0..j) followed by the rest of a
        if (i > 0 && j > 0 && f[i][j] == f[i - 1][j - 1] + (a[i - 1] != b[j - 1])) {
            if (a[i - 1] != b[j - 1])
                edits.push_back("replace " + to_string(j) + " " + b[j - 1]);
            i--;   // up-left: keep or replace
            j--;
        } else if (i > 0 && f[i][j] == f[i - 1][j] + 1) {
            edits.push_back("delete " + to_string(j + 1));
            i--;   // up: delete
        } else {
            edits.push_back("insert " + to_string(j) + " " + b[j - 1]);
            j--;   // left: insert
        }
    }
    reverse(edits.begin(), edits.end());   // the edits were found from the end
    for (const string& e : edits) cout << e << "\n";
}

The grid has (n + 1)(m + 1) cells, each filled in constant time, so the program takes $O(nm)$ time and memory (see time complexity). The walk back adds O(n + m) steps. For two strings of 5000 letters that is 2.5 \cdot 10^7 cells, well within a second by the rule of thumb of about 10^8 simple steps per second.

Only the distance, with two rows

As in the LCS article, row i reads only row i - 1 and itself, so when only the distance is needed, prev can hold row i - 1 and cur row i. For two strings of 10 000 letters the two rows take 80 KB. The walk back still needs the whole grid. The one new line is cur[0] = i at the start of each row.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();

    vector<int> prev(m + 1), cur(m + 1);        // rows i - 1 and i
    for (int j = 0; j <= m; j++) prev[j] = j;   // row 0: insert all j letters
    for (int i = 1; i <= n; i++) {
        cur[0] = i;                             // column 0: delete all i letters
        for (int j = 1; j <= m; j++) {
            cur[j] = min({prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + (a[i - 1] != b[j - 1])});
        }
        swap(prev, cur);   // row i becomes the row above
    }
    cout << prev[m] << "\n";
}

Other costs

Some problems give each edit its own cost. Then each + 1 in the transition becomes the cost of that edit, a replacement of different letters costs the replacement price, and the base case becomes i deletions and j insertions at their prices, as the comments in the main program say. For example, if deleting is free and inserting costs 1, column ∅ holds only zeros, row ∅ holds 0, 1, 2, …, and a step up adds nothing. If a replacement costs more than a deletion and an insertion, the grid still picks the cheaper pair. The walk back must use the same costs. Replacements must cost the same for every pair of letters, or at least never more than going through a third letter (see the end of the proof).

Searching for a word with mistakes in a text

To find the place in a long text where a short word appears with the fewest mistakes, put the word down the left and the text across the top. A match may start anywhere in the text, so row ∅ is all zeros: skipping the text before the match costs nothing. Column ∅ stays 0, 1, 2, … as before. The cell f[n][j] is then the fewest edits for a match that ends at letter j of the text, and the answer is the smallest number in the last row. For the word PART in the text SPORTY the last row is 4, 4, 3, 3, 2, 1, 2, and the smallest, 1, belongs to PORT.

Correctness proof

First, why a list of edits can always be drawn as two rows in columns, as in Fig. 2. Such a picture is an alignment: each column is a kept letter, a replaced letter, a letter over a gap (deleted) or a gap over a letter (inserted), and the letters keep their order in both rows. A shortest list of edits never touches the same letter twice: inserting a letter and deleting it later, replacing a letter twice, or replacing an inserted letter wastes an edit. So every letter of the first string is kept, replaced once or deleted, every inserted letter stays, and the result is an alignment whose number of edit columns is the number of edits.

Write f_{i,j} for f[i][j], a_i for letter $i$ of the first string and b_j for letter $j$ of the second. Take a cell $(i,j)$ and assume every cell above it and to its left holds the fewest edits for its prefixes. The base cases are right: an empty string can only be reached by deleting every letter, and built from nothing only by inserting every letter.

Each option the transition compares is the number of edits in a real list: a list for shorter prefixes plus one more edit, or plus a kept letter. So the fewest edits are at most f_{i,j}. They are also at least f_{i,j}. Take a shortest list of edits for the two prefixes and its alignment. Its last column is one of the three cases of Fig. 3:

• a_i over b_j: the other columns align the first i - 1 letters with the first j - 1, so they hold at least f_{i-1,j-1} edits, and the last column adds 1 if a_i \ne b_j;

• a_i over a gap: the rest aligns i - 1 letters with $j$, at least f_{i-1,j} edits, plus 1;

• a gap over b_j: the rest aligns $i$ letters with j - 1, at least f_{i,j-1} edits, plus 1.

In each case the shortest list has at least as many edits as one of the three options, so the smallest option is the fewest edits.

The first step needs each kind of edit to have one price. If replacements are priced per pair of letters and a detour is cheaper, a shortest list may replace a letter twice, and the grid is wrong. With A→B costing 10, A→C and C→B costing 1 each, and deleting and inserting 5 each, the grid gives 10 for A to B, but replacing A by C and then C by B costs 2.

Common mistakes

• Using a shortcut instead of the grid. Comparing letters in the same places gives 5 for SPORT and PARTY instead of 3, and is right only when nothing is inserted or deleted. The LCS length $L$ doesn't help either: \max(n, m) - L gives 1 for AB and BA, but the answer is 2.

• Printing each edit's position in the original string, or printing the edits in the order the walk finds them. After S is deleted from SPORT, the O is at position 2, not 3, and replace 3 A turns PORT into POAT. Reverse the list and use the position j in the string being built.

• Keeping one row and overwriting it in place. When cell j reads d[j - 1] as its up-left value, d[j - 1] already holds row i, so the value from row i - 1 is lost, and A and A give 1 instead of 0. Keep two rows, or save the old d[j - 1] in a variable before overwriting it.

• Adding swaps of two neighbouring letters as one more option, f[i - 2][j - 2] + 1 when the last two letters are swapped. The state (i, j) doesn't record that a swapped pair may be edited again, so ant to neat gives 3, while swapping to nat and inserting e takes 2. Such problems need the full Damerau–Levenshtein distance.

Similar algorithms

The longest common subsequence uses the same grid over prefixes, but counts kept letters and takes a maximum, while edit distance counts edits and takes a minimum. With only insertions and deletions, the edit distance is n + m - 2L, where $L$ is the length of the LCS.

The Damerau–Levenshtein distance adds a fourth edit, swapping two neighbouring letters, for typos like TEH for THE.

The grid is also a state graph. The cells are vertices, the moves right, down and diagonally down-right are edges of cost 0 or 1, and the edit distance is the shortest path from the top-left cell to the bottom-right one. Every edge goes right or down, so filling the grid in order finds that path without a shortest-path algorithm.

Wildcard matching fills the same grid over prefixes of a pattern and a word, but each cell holds yes or no: does this prefix of the pattern, where ? stands for one letter and * for any run of letters, match this prefix of the word?

Practice