When a search engine suggests «did you mean…», when a spell checker proposes the right word or when a version control tool shows the lines changed between two versions of a file, the same question lies behind it: how different are two sequences, and what is the cheapest way to turn one into the other? The classic answer is the edit distance, and the way to compute it is one of the most elegant examples of dynamic programming.
The Levenshtein distance
The Levenshtein distance between two strings is the minimum number of elementary operations needed to turn the first into the second. Three operations are allowed, each costing 1:
- insertion of a character;
- deletion of a character;
- substitution of one character with another.
From «cat» to «hat» a single substitution is enough: distance 1. From «cast» to «coast» a single insertion is enough: distance 1. From «kitten» to «sitting» three operations are needed: two substitutions (k → s, e → i) and one insertion (the final g).
The recurrence
Let D(i, j) be the distance between the first i characters of A and the first j characters of B. Look at the last characters of the two prefixes:
- if they are equal, nothing needs to be done: D(i, j) = D(i − 1, j − 1);
- otherwise, choose the best of three options:
- substitute: 1 + D(i − 1, j − 1);
- delete the last character of A: 1 + D(i − 1, j);
- insert the last character of B: 1 + D(i, j − 1).
The base cases are intuitive: D(i, 0) = i, because reaching the empty string means deleting everything; D(0, j) = j, because starting from empty means inserting everything.
An example with the table
Let us compare «sole» and «sale». The table has one row for each prefix of «sole» and one column for each prefix of «sale»:
| ε | s | a | l | e | |
|---|---|---|---|---|---|
| ε | 0 | 1 | 2 | 3 | 4 |
| s | 1 | 0 | 1 | 2 | 3 |
| o | 2 | 1 | 1 | 2 | 3 |
| l | 3 | 2 | 2 | 1 | 2 |
| e | 4 | 3 | 3 | 2 | 1 |
The bottom-right cell is 1: substituting the «o» with an «a» is enough. By following backwards the choices that produced each cell, you also rebuild the sequence of operations, that is, the alignment between the two strings.
The code
def levenshtein(a, b):
prev = list(range(len(b) + 1))
for i, ca in enumerate(a, 1):
curr = [i]
for j, cb in enumerate(b, 1):
if ca == cb:
curr.append(prev[j - 1])
else:
curr.append(1 + min(prev[j - 1], prev[j], curr[j - 1]))
prev = curr
return prev[-1]
Time is proportional to the product of the lengths, |A| · |B|. Since each row depends only on the previous one, memory shrinks to two rows. If you need to rebuild the alignment, however, you must keep the whole table or use more sophisticated techniques such as Hirschberg's, which recovers the alignment in linear memory by splitting the problem in half.
Useful variants
- Different weights: in a keyboard-aware spell checker, substituting a letter with an adjacent one can cost less than with a distant one. You only need to change the costs in the recurrence.
- Transpositions: the Damerau-Levenshtein distance counts swapping two adjacent characters as a single operation, the most common typing error («teh» instead of «the»).
- Maximum threshold: if you only need to know whether the distance is at most k, it is enough to compute a diagonal band 2k + 1 wide in the table. This is how you search quickly among many candidates.
- Biological sequence alignment: the Needleman-Wunsch (global alignment) and Smith-Waterman (local alignment) algorithms are the same idea with scores for matches, mismatches and gaps.
The longest common subsequence
A related problem is the longest common subsequence (LCS): the longest sequence of elements that appear in both strings in the same order, not necessarily consecutively. For «ABCBDAB» and «BDCABA» an LCS has length 4, for example «BCBA».
The recurrence is similar: if the last elements match, add 1 to the solution for the shorter prefixes; otherwise take the maximum of removing an element from one sequence or the other. If only insertions and deletions are allowed, the edit distance equals |A| + |B| − 2 · LCS.
How a diff works
Tools that compare text files apply the same logic, treating lines as elements instead of characters: the lines of the LCS are the unchanged ones, the others are marked as added or removed. For long files the full table would be too large, and real tools use more efficient algorithms, such as Myers', which work well when the differences are few compared with the length of the files. This is the typical case of source code changes.
In document analysis, comparing two versions of a contract or a web page with a line diff and then a word diff makes changes obvious that would escape the naked eye.
In short
- The Levenshtein distance counts the minimum insertions, deletions and substitutions between two strings.
- It is computed with a dynamic programming table in |A| · |B| time.
- Walking back through the table yields the alignment, that is, the sequence of edits.
- Weights, transpositions and thresholds adapt the algorithm to spell checkers and approximate search.
- The longest common subsequence is the basis of file diff tools.
