Edit distance

Type «балконский», a misspelling of the surname Bolkonsky. The speller below knows the 47,585 words of the Russian original of “War and Peace” and within a few milliseconds suggests «болконский»: one substitution of a letter away. To claim that, it must know that all the other words are further, that is, it must somehow compare the typo with each of them. Next to it is the table with which two words are compared, under it the alignment, and further down at what distance the typo is from each word of the dictionary. Try your own typos and a different limit on edits.

Look at the lower graph. Of the novel's 47,585 words only five are within two edits of «балконского»: «болконский», «волконский» and three more forms of the surname Bolkonsky. The rest are far away, most often nine edits. So almost all of the speller's work goes into making sure that a word does not fit. A full table for every word is 4,017,020 cells per typo. The speller computes 353,105, eleven times fewer, and the answer is still exact. How it does this we will see once we understand the table itself.

The idea

The edit distance, or Levenshtein distance, between two strings is the fewest edits by which one turns into the other. An edit is inserting a letter, deleting a letter or replacing one letter with another. From «балконский» to «болконский» is one substitution, from «одьютант» to «адъютант» (misspelled and correct “adjutant”) two, from “kitten” to “sitting” three.

Look at what became of the last letter of the first word. It was either deleted, or replaced with the last letter of the second word (perhaps for free, if they coincide), or it stayed, and the last letter of the second word was inserted at the end. In each case the same problem remains for shorter beginnings of the words. So the distances between all beginnings can be written into a table and filled row by row: each cell is the minimum of three neighbouring ones plus the cost of the last edit.

The table and paths through it

Let a have length m and b length n. The cell D[i][j] of the table is the distance between the first i letters of a and the first j letters of b:

The edges are clear: i letters turn into the empty string by i deletions, the empty string into j letters by j insertions. Here is the table for «одьютант» and «адъютант» from the listing below:

        а  д  ъ  ю  т  а  н  т
     0  1  2  3  4  5  6  7  8
  о  1  1  2  3  4  5  6  7  8
  д  2  2  1  2  3  4  5  6  7
  ь  3  3  2  2  3  4  5  6  7
  ю  4  4  3  3  2  3  4  5  6
  т  5  5  4  4  3  2  3  4  5
  а  6  5  5  5  4  3  2  3  4
  н  7  6  6  6  5  4  3  2  3
  т  8  7  7  7  6  5  4  3  2

The table is conveniently read as a map. From each cell one can step down, deleting a letter of the first word; right, inserting a letter of the second; or diagonally, keeping a letter if it matches or replacing it. Each way of turning one word into the other is a path from the top left corner to the bottom right, and its cost is the sum of the steps. The distance is the cost of the cheapest path, and on this map it could be found with Dijkstra's algorithm. But the graph here is special: all steps lead down and to the right, so the cells can simply be visited row by row, and for each cell all its predecessors are already ready.

A path written out in columns is called an alignment: two strings one under the other, with hyphens in place of the inserted and deleted letters. It is recovered from the corner of the table back to the start like this: each cell is asked from which neighbour it got its value.

The distance is a true metric: it is zero only for equal strings, symmetric (an insertion and a deletion can be swapped), and it obeys the triangle inequality: d(a, c) ≤ d(a, b) + d(b, c), because the edits from a to b and from b to c together turn a into c. The last property will come in handy when we build an index.

The cost of edits and the alignment

Nothing prevents edits from costing differently. Illumina sequencers confuse letters more often than they lose them, so for them a substitution is cheaper than a gap; for nanopore ones it is the other way round. A person at a keyboard more often hits a neighbouring key, so replacing one letter with its neighbour on the keyboard is cheaper than with a distant one. The formula stays the same, only costs replace the ones. Change them below and watch how the cheapest path changes.

When a substitution costs 1, the alignment of GCATGCG and GATTACA is four substitutions at cost 4. Set the substitution cost to 3: replacing has become dearer than deleting a letter and inserting another, and the path leaves the diagonal in a staircase, three deletions and three insertions, cost 6. With a substitution at 2 or more it is not needed at all, and the distance becomes m + n − 2 · LCS, where LCS is the length of the longest common subsequence: everything not in the common part is deleted from one word and inserted from the other.

The shaded cells are those through which at least one cheapest path passes, and there are often many paths. The distance is unique, but there may be dozens of alignments, and a program picks one by the rule of in what order it checks the neighbours. In the listing the diagonal comes first, then deletion, then insertion; text comparison utilities choose in their own way, which is why two programs can show the same edit differently.

Code

The full table and the path back from the corner. The demo has the table from the start of the article, alignments of several pairs and an alignment with an expensive substitution: in the middle row | is a match, * a substitution, a space an insertion or deletion.

Note «войнаимир» (“warandpeace” run together): the nearest word of the novel is «войнами» (“by wars”), two edits away. Spaces are not counted as a typo: for the speller «войнаимир» is one word that does not exist, not three words without spaces. Splitting a string into words is a separate problem.

Now the speller. It reads the novel from the server where the code runs, builds a dictionary with counts and for each typo looks for words no more than two edits away. The output columns are how many words passed the length filter, how many cells of the table were actually computed, and how many full tables against every word would take:

How not to compare with everything

The speller has three tricks, and all three rest on one thing: we do not need the exact distance to words further than k. It is enough to know that they are further.

1. A length filter. Each insertion or deletion changes the length by one, a substitution does not, so d(a, b) ≥ |m − n|. Words whose length differs by more than k need not be looked at. For «балконского», 25,713 of the 47,585 words remain.
2. A band. For the same reason D[i][j] ≥ |i − j|: cells further than k from the main diagonal are certainly greater than k, and there is no point computing them. What remains is a band of width 2k + 1; in the scene these are the framed cells, and the speller does not compute the grey numbers outside it. The work per word falls from m · n to (2k + 1) · m.
3. Early stopping. Any path to the bottom right corner passes through every row of the table, and the cost only grows along the way. So if all the numbers in the current row are greater than k, the result is greater than k too, and the word can be dropped. On words unlike the typo the rows overflow after three or four letters: for «балконского» the speller computes 14 cells per word on average instead of 84 in the full table.

Together this is 353,105 cells instead of 4,017,020, 11 times fewer. In the browser the scene spends a few milliseconds on this, while the histogram below, which needs exact distances to all the words, has to compute full tables. But a scan is still a scan: every word of the dictionary is touched at least once. To avoid touching most words at all, an index is needed.

• A BK-tree (Burkhard and Keller, 1973) arranges the dictionary by distances from node words. If the query is at distance d from node x, then by the triangle inequality only the subtrees of words whose distance to x lies in [d − k, d + k] are of interest, and the rest are discarded whole. Details are in the article on the BK-tree.
• A Levenshtein automaton. For a query and a limit k a finite automaton is built that accepts exactly the strings no further than k, and it is run over a trie of the dictionary, cutting off branches where the automaton has died. This is how fuzzy search has worked since version 4.0 in Lucene, on which Elasticsearch and Solr stand; search became more than a hundred times faster than before. Lucene allows no more than two edits.
• Symmetric deletion. For each word of the dictionary all strings obtained by deleting up to k letters are written out in advance, and the word is put into a hash table under each of them. Two strings at distance at most k necessarily share such a string, so the candidates for a query are found with a few lookups in the table. Try it in the problem about a dictionary of typos.

What it costs

Hirschberg's technique (1975) is needed when the strings are long and the whole alignment is wanted: the table is computed from the start to the middle row and from the end to the same row, the place where the best path crosses the middle is found, and the two halves are solved separately. The square of m·n cells is never held in memory.

A measurement: two versions of a random DNA string of length n, with a different letter in every hundredth position. The full table against a band 17 cells wide (k = 8).

The slope of the full table is 2: twice as long a string, four times as many cells. The slope of the band is 1. On strings of 800 letters the band in Python is 62 times faster, and the gap grows with length. But the band works only if the limit k is known in advance. If it is not known, it is doubled, 1, 2, 4, …, until the distance falls within the band, and the total work is still O(d · n), where d is the answer. Computing only the band and widening it until the answer fits was proposed by Esko Ukkonen in 1985.

Variants

Transpositions. Fred Damerau in 1964, studying typing errors, found that more than 80 % of typos come down to one insertion, one deletion, one substitution or a transposition of two neighbouring letters. By Levenshtein a transposition is two edits: «кнзяь» is two away from «князь» (“prince”), from «князя» (“of the prince”) and from «казнь» (“execution”) alike. Turn on “swapping neighbours is one edit” in the first scene: a fourth transition is added to the table, from the cell two diagonal steps back, and «князь» pulls ahead. This version is called the optimal string alignment distance. It is simple, but no longer a metric: “CA” and “AC” are at distance 1, “AC” and “ABC” at 1, while “CA” and “ABC” are at 3, and the triangle inequality is violated. The full Damerau–Levenshtein distance, where transposed letters may then be edited further, is computed in a more complicated way (Lowrance and Wagner, 1975).

Weights. Real spellers price edits by probability: neighbouring keys, unstressed vowels («карова» for «корова», “cow”), doubled consonants. The formula is the same, the prices change.

Alignment in biology. In protein and DNA sequences substitutions of some letters by others also have different costs, and a gap of several letters in a row is cheaper than as many scattered ones. This is the Needleman–Wunsch algorithm (1970) for aligning whole sequences and Smith–Waterman (1981) for finding the most similar piece; both are in the article on sequence alignment. Try it yourself in the problem about sequencer errors.

Comparing files. diff compares the lines of files, not letters, and allows only insertions and deletions. It is the same table, but Eugene Myers in 1986 found a way to traverse it in O((m + n) · d), where d is the number of differences: this is how git works. More in Myers's diff.

History

The distance was invented several times, in different sciences and for different needs. Vladimir Levenshtein introduced it in 1965 in “Doklady Akademii Nauk”, when looking for codes that correct not only distorted symbols but also dropped and inserted ones; the story of this work is told in detail in the course chapter on dynamic programming. A year earlier Fred Damerau of IBM published a way of finding and correcting typos in which a transposition of neighbouring letters counted as one error. The table for computing it was found independently: by Taras Vintsyuk in 1968 for speech recognition, by Saul Needleman and Christian Wunsch in 1970 for comparing proteins, and by Robert Wagner and Michael Fischer in 1974 for correcting strings, and in computer science it is often called by their names. In 1983 David Sankoff and Joseph Kruskal gathered these discoveries into one book, “Time Warps, String Edits, and Macromolecules”, and showed that speech, texts and molecules are compared with one and the same table.

Problems

In the first problem the edits have different costs, and the shortest alignment stops being the cheapest. In the second no table is needed at all: find all the words of a dictionary one edit away from a query faster than comparing it with each of them.