Edit distance (Levenshtein distance)

Type recieve and your phone suggests receive. It knows you were close because the two words are only a couple of edits apart. Measuring that closeness, the edit distance, is a classic job for dynamic programming.

A table with one word down the side and another along the top, numbers in its cells, and an orange path of edits from the top left to the bottom right corner
A table with one word down the side and another along the top, numbers in its cells, and an orange path of edits from the top left to the bottom right corner

The problem

An edit changes a word by one letter: insert a letter, delete a letter, or replace one letter with another. The edit distance between two words is the fewest edits that turn one into the other. Cat and cut are 1 apart, cat and cast 1, and cat and act 2. It is also called the Levenshtein distance, after the Soviet mathematician Vladimir Levenshtein, who studied it in 1965.

The table

Let d[i][j] be the edit distance between the first i letters of one word and the first j letters of the other. Turning a word into nothing takes one delete per letter, so d[i][0] = i, and building a word from nothing takes one insert per letter, so d[0][j] = j. If letter i equals letter j, d[i][j] = d[i − 1][j − 1]. Otherwise d[i][j] = 1 + the smallest of d[i − 1][j − 1] (replace), d[i − 1][j] (delete) and d[i][j − 1] (insert).

An example

For kitten and sitting the table has 7 rows and 8 columns. The bottom right cell is 3, and reading back from it gives: replace k by s, keep i, t and t, replace e by i, keep n, and insert g. Kitten, sitten, sittin, sitting: three edits, and the table proves that no shorter list exists.

Reading the edits back

Start at the bottom right cell and ask which neighbour its value came from. If the letters match and the cell equals its upper left neighbour, the letter was kept: step diagonally. If it is one more than the upper left neighbour, it was a replace; one more than the cell above, a delete; one more than the cell to the left, an insert. Several paths can tie, and each gives a shortest list of edits.

History and uses

Levenshtein introduced the distance in 1965 while working on codes that correct errors. The table method was published by several people, most famously by Robert Wagner and Michael Fischer in 1974, so it is often called the Wagner–Fischer algorithm. Today edit distances rank spelling suggestions, match names with typos in databases, compare DNA and protein sequences, and score speech recognition.

Explore it

Open the app and press Step. The two letters being compared light up in the headings; equal letters copy the blue cell up and to the left, and different letters read all three blue neighbours and add one to the smallest. At the end the orange path runs back from the corner, and the edits appear under the table.

Frequently asked questions

Is edit distance a metric?

Yes. It is never negative, it is 0 only for equal words, it is the same in both directions, and going through a third word can never make it shorter: d(a, c) ≤ d(a, b) + d(b, c). That makes it useful for searching for close matches.

What is the Damerau–Levenshtein distance?

The edit distance with one extra edit: swapping two neighbouring letters. Frederick Damerau found in 1964 that insert, delete, replace and swap together cover more than 80 percent of spelling errors. With swaps, recieve and receive are 1 apart instead of 2.

Can edit distance be computed faster than O(m·n)?

Not by much. In 2015 Arturs Backurs and Piotr Indyk showed that a method taking O(n^(2 − ε)) time for some ε > 0 would break the strong exponential time hypothesis, which most researchers believe. For words that are close, though, only a narrow band around the diagonal of the table is needed.

How is edit distance used in DNA comparison?

Biologists use the same table with scores instead of counts: matches earn points, and replacements and gaps cost points that depend on the letters. That is the Needleman–Wunsch algorithm of 1970 for whole sequences, and the Smith–Waterman algorithm of 1981 for the best matching pieces.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try edit distance