Edit distance¶

How many single-letter changes (insert a letter, delete a letter, replace a letter) turn one word into another? This number, the Levenshtein distance, is found with a table over the two prefixes.

Time	Extra space	Output
\(O(nm)\) for lengths \(n\) and \(m\)	\(O(nm)\), or \(O(\min(n, m))\) for the number alone	the distance and the list of edits

The idea¶

kitten becomes sitting in 3 edits: replace k with s, replace e with i, insert g. No way with 2 exists.

As with the longest common subsequence, look at the last letters. To turn the first \(i\) letters of \(a\) into the first \(j\) letters of \(b\), the last edit was one of:

keep (if \(a_i = b_j\)) or replace \(a_i\) by \(b_j\): then turn \(a_1..a_{i-1}\) into \(b_1..b_{j-1}\);
delete \(a_i\): then turn \(a_1..a_{i-1}\) into \(b_1..b_j\);
insert \(b_j\) at the end: then turn \(a_1..a_i\) into \(b_1..b_{j-1}\).

\[D[i][j] = \min\big(D[i-1][j-1] + [a_i \ne b_j],\; D[i-1][j] + 1,\; D[i][j-1] + 1\big)\]

with \(D[i][0] = i\) (delete everything) and \(D[0][j] = j\) (insert everything). \([a_i \ne b_j]\) is 1 when the letters differ and 0 when they are equal.

How it works¶

Fill row 0 with \(0, 1, 2, \dots, m\) and column 0 with \(0, 1, \dots, n\).
Fill the rest row by row with the rule above.
\(D[n][m]\) is the distance. To list the edits, walk back from the corner, at each cell choosing a neighbour that gives its value.

Code¶

PythonJavaC++

def edit_distance(a, b):
    """The fewest single-letter inserts, deletes and replacements that turn a into b (Levenshtein distance).
    Returns the distance and the list of steps."""
    n, m = len(a), len(b)
    D = [[0] * (m + 1) for _ in range(n + 1)]   # D[i][j] = distance from a[:i] to b[:j]
    for i in range(n + 1):
        D[i][0] = i                             # delete all i letters
    for j in range(m + 1):
        D[0][j] = j                             # insert all j letters
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            same = 0 if a[i - 1] == b[j - 1] else 1
            D[i][j] = min(D[i - 1][j] + 1,          # delete a[i-1]
                          D[i][j - 1] + 1,          # insert b[j-1]
                          D[i - 1][j - 1] + same)   # keep or replace
    steps, i, j = [], n, m
    while i > 0 or j > 0:                       # walk back to list the steps
        if i > 0 and j > 0 and D[i][j] == D[i - 1][j - 1] + (a[i - 1] != b[j - 1]):
            if a[i - 1] != b[j - 1]:
                steps.append(f"replace {a[i - 1]} with {b[j - 1]}")
            i -= 1; j -= 1
        elif i > 0 and D[i][j] == D[i - 1][j] + 1:
            steps.append(f"delete {a[i - 1]}"); i -= 1
        else:
            steps.append(f"insert {b[j - 1]}"); j -= 1
    return D[n][m], steps[::-1]


if __name__ == "__main__":
    for a, b in [("kitten", "sitting"), ("sunday", "saturday"), ("mars", "stars")]:
        d, steps = edit_distance(a, b)
        print(a, b, d, "; ".join(steps))

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class EditDistance {
    static List<String> steps = new ArrayList<>();

    /** The fewest single-letter inserts, deletes and replacements that turn a into b (Levenshtein distance).
     *  Returns the distance; the list of steps is left in steps. */
    static int editDistance(String a, String b) {
        int n = a.length(), m = b.length();
        int[][] D = new int[n + 1][m + 1];            // D[i][j] = distance from a[:i] to b[:j]
        for (int i = 0; i <= n; i++) D[i][0] = i;     // delete all i letters
        for (int j = 0; j <= m; j++) D[0][j] = j;     // insert all j letters
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                int same = a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1;
                D[i][j] = Math.min(Math.min(D[i - 1][j] + 1,    // delete a[i-1]
                                            D[i][j - 1] + 1),   // insert b[j-1]
                                   D[i - 1][j - 1] + same);     // keep or replace
            }
        steps = new ArrayList<>();
        int i = n, j = m;
        while (i > 0 || j > 0) {                      // walk back to list the steps
            if (i > 0 && j > 0 && D[i][j] == D[i - 1][j - 1] + (a.charAt(i - 1) != b.charAt(j - 1) ? 1 : 0)) {
                if (a.charAt(i - 1) != b.charAt(j - 1)) steps.add("replace " + a.charAt(i - 1) + " with " + b.charAt(j - 1));
                i--; j--;
            } else if (i > 0 && D[i][j] == D[i - 1][j] + 1) {
                steps.add("delete " + a.charAt(i - 1)); i--;
            } else {
                steps.add("insert " + b.charAt(j - 1)); j--;
            }
        }
        Collections.reverse(steps);
        return D[n][m];
    }

    public static void main(String[] args) {
        String[][] pairs = {{"kitten", "sitting"}, {"sunday", "saturday"}, {"mars", "stars"}};
        for (String[] p : pairs) {
            int d = editDistance(p[0], p[1]);
            System.out.println(p[0] + " " + p[1] + " " + d + " " + String.join("; ", steps));
        }
    }
}

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

// The fewest single-letter inserts, deletes and replacements that turn a into b (Levenshtein distance).
// Returns the distance; the list of steps is put in steps.
int editDistance(const string& a, const string& b, vector<string>& steps) {
    int n = a.size(), m = b.size();
    vector<vector<int>> D(n + 1, vector<int>(m + 1, 0));   // D[i][j] = distance from a[:i] to b[:j]
    for (int i = 0; i <= n; i++) D[i][0] = i;        // delete all i letters
    for (int j = 0; j <= m; j++) D[0][j] = j;        // insert all j letters
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int same = a[i - 1] == b[j - 1] ? 0 : 1;
            D[i][j] = min({D[i - 1][j] + 1,          // delete a[i-1]
                           D[i][j - 1] + 1,          // insert b[j-1]
                           D[i - 1][j - 1] + same}); // keep or replace
        }
    steps.clear();
    int i = n, j = m;
    while (i > 0 || j > 0) {                         // walk back to list the steps
        if (i > 0 && j > 0 && D[i][j] == D[i - 1][j - 1] + (a[i - 1] != b[j - 1] ? 1 : 0)) {
            if (a[i - 1] != b[j - 1]) steps.push_back(string("replace ") + a[i - 1] + " with " + b[j - 1]);
            i--; j--;
        } else if (i > 0 && D[i][j] == D[i - 1][j] + 1) {
            steps.push_back(string("delete ") + a[i - 1]); i--;
        } else {
            steps.push_back(string("insert ") + b[j - 1]); j--;
        }
    }
    reverse(steps.begin(), steps.end());
    return D[n][m];
}

int main() {
    vector<pair<string, string>> pairs = {{"kitten", "sitting"}, {"sunday", "saturday"}, {"mars", "stars"}};
    for (auto& p : pairs) {
        vector<string> steps;
        int d = editDistance(p.first, p.second, steps);
        cout << p.first << " " << p.second << " " << d << " ";
        for (size_t k = 0; k < steps.size(); k++) cout << (k ? "; " : "") << steps[k];
        cout << "\n";
    }
}

Output:

kitten sitting 3 replace k with s; replace e with i; insert g
sunday saturday 3 insert a; insert t; replace n with r
mars stars 2 insert s; replace m with t

When to use it¶

Spelling correction: suggest dictionary words at distance 1 or 2 from what was typed.
Fuzzy search and matching of names with typos, OCR errors, or different spellings.
Biology: counting mutations between DNA sequences (with weights, sequence alignment).
Comparing versions of short texts, or measuring how well a speech recognizer did (word error rate is edit distance on words).

Common mistakes¶

Forgetting the first row and column: they are not zero but \(0, 1, 2, \dots\)
Mixing up which neighbour is insert and which is delete: up (\(D[i-1][j]\)) uses up a letter of \(a\) (delete); left (\(D[i][j-1]\)) produces a letter of \(b\) (insert).
Treating swaps as one edit: plain Levenshtein counts ab → ba as 2; Damerau–Levenshtein adds transposition as one edit.
Memory on long strings: keep only two rows if the edits are not needed.

Going deeper¶

Each part below starts closed; open the ones you want.

Sample walkthrough: kitten → sitting

	∅	s	i	t	t	i	n	g
∅	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3

Two cells explained:

Row k, column s: k ≠ s; replace from \(D[0][0] = 0\) gives 1, delete from \(D[0][1] = 1\) gives 2, insert from \(D[1][0] = 1\) gives 2. So 1.
Row e, column i (the second i): e ≠ i; replace from \(D[4][4] = 1\) gives 2.

Walk back from 3 (row n, column g): insert g (from 2); n = n, keep (from 2); e ≠ i, replace (from 1); t, t, i kept along the diagonal; k ≠ s, replace (from 0). Three edits.

The math: it is a true distance, and how fast it can be

Correctness. Any sequence of edits can be rearranged to work from left to right, so the edits that touch the last letters can be taken to be last; the three cases above are all the possibilities for them, and the rest must itself be optimal. Hence the minimum over the three cases.

A metric. Edit distance satisfies \(D(a, a) = 0\); \(D(a, b) > 0\) when \(a \ne b\); \(D(a, b) = D(b, a)\) (each edit has an opposite edit of the same cost); and the triangle inequality \(D(a, c) \le D(a, b) + D(b, c)\) (do the edits one after the other). This is what lets search structures such as BK-trees prune.

Bounds. \(|n - m| \le D(a, b) \le \max(n, m)\). With only insertions and deletions allowed, \(D = n + m - 2\,\text{LCS}(a, b)\).

Time. \((n+1)(m+1)\) cells, \(O(1)\) each. Backurs and Indyk (2015) showed that a truly subquadratic algorithm, \(O(n^{2-\varepsilon})\), would refute the Strong Exponential Time Hypothesis. If the distance \(d\) is known to be small, only a band of width \(2d + 1\) around the diagonal is needed: \(O(d \cdot \min(n, m))\) (Ukkonen, 1985).

Watch it step by step

Orange is the cell the new value came from; green means the letters matched (keep), red means an edit was needed. The last frame shows one cheapest path in purple.

Variations and related ideas

Weighted edits: different costs for each operation or each pair of letters (for example, keys next to each other on a keyboard cost less).
Damerau–Levenshtein: also allows swapping two neighbouring letters as one edit.
Hamming distance: for equal lengths, only replacements; just count the differing positions in \(O(n)\).
Needleman–Wunsch (global) and Smith–Waterman (local) alignment in biology use the same table with scores and gap penalties.

References¶

V. I. Levenshtein, "Binary codes capable of correcting deletions, insertions, and reversals", Soviet Physics Doklady 10(8), 1966.
R. A. Wagner and M. J. Fischer, "The string-to-string correction problem", Journal of the ACM 21(1), 1974.
E. Ukkonen, "Algorithms for approximate string matching", Information and Control 64, 1985.
A. Backurs and P. Indyk, "Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)", STOC 2015.

	∅	s	i	t	t	i	n	g
∅	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3

	∅	s	i	t	t	i	n	g
∅	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3