Edit Distance

#How does it work?

Edit distance (Levenshtein distance) is the fewest single-letter operations that turn one word into another. The allowed operations are replacing, deleting or inserting a letter. KITTEN → SITTING has distance 3: K→S, E→I and adding G at the end.

dp[i][j] is the cheapest way to turn X's first i letters into Y's first j letters. If the last letters match, no edit is needed and the diagonal is copied. Otherwise the cheapest of three options wins: replace (diagonal), delete the letter from X (above) or insert Y's letter (left), each plus 1.

It is shaped just like LCS: LCS maximises what is shared, edit distance minimises the difference. Walking the table back from the bottom right lists the edits.

#Try it yourself

#Step by step

1. 01First row dp[0][j] = j (insert j letters), first column dp[i][0] = i (delete i letters).
2. 02If the letters match, dp[i][j] = dp[i − 1][j − 1].
3. 03Otherwise dp[i][j] = 1 + min(diagonal, above, left).
4. 04dp[m][n] is the distance; walk back from the bottom right to read the edits.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def edit_distance(x: str, y: str) -> int:
    m, n = len(x), len(y)
    # dp[i][j] = cheapest way to turn x[:i] into y[:j].
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i  # delete everything
    for j in range(n + 1):
        dp[0][j] = j  # insert everything
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # no edit needed
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],  # replace
                                   dp[i - 1][j],      # delete
                                   dp[i][j - 1])      # insert
    return dp[m][n]


print(edit_distance("KITTEN", "SITTING"))   # K->S, E->I, +G
print(edit_distance("SUNDAY", "SATURDAY"))

#Complexity

Each cell is filled in constant time. If only the distance is needed, two rows are enough. If the question is whether the distance is below some small k, only a band around the diagonal is needed, bringing it to O(k · n).

#When to use it?

Spell checking and "did you mean?" suggestions, fuzzy matching in search engines, comparing DNA sequences, correcting OCR and speech recognition output, and diff tools all use edit distance.

#Practice

Log in to answer questions and save your progress.