Edit Distance (Levenshtein)

Measuring how different two words are

When you type “recieve” a spell checker suggests “receive”. It finds the closest word by counting the fewest single-letter edits:

• insert a letter,
• delete a letter,
• replace one letter by another.

The minimum number is the edit distance (or Levenshtein distance). KITTEN → SITTING needs 3: replace K with S, replace E with I, insert G.

The dynamic-programming idea

Let dp[i][j] be the edit distance between the first i letters of A and the first j letters of B.

• dp[i][0] = i (delete everything) and dp[0][j] = j (insert everything).
• If the last letters match: dp[i][j] = dp[i−1][j−1] (no cost).
• Otherwise: dp[i][j] = 1 + min(dp[i−1][j], dp[i][j−1], dp[i−1][j−1]), corresponding to delete, insert and replace.

for i in 1..m:
    for j in 1..n:
        if A[i] == B[j]:  dp[i][j] = dp[i−1][j−1]
        else:             dp[i][j] = 1 + min(delete, insert, replace)
answer = dp[m][n]

Reading the table

Each cell depends on its left, upper and upper-left neighbours, so you can fill it row by row. Starting at the bottom-right corner and always stepping to the neighbour that explains the value gives the edit script. A diagonal step with the same value is a match, a diagonal step with +1 is a replacement, a step up is a deletion and a step left is an insertion.

It is the same table-filling pattern as the longest common subsequence; LCS only allows inserts and deletes.

Code

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

print(edit_distance("kitten", "sitting"))   # 3

Where is it used?

Spell checkers and autocorrect, DNA sequence alignment, plagiarism detection, diff tools, search with typos, and speech or OCR error measurement.

Common mistakes

• Forgetting the base row and column, which must count 0, 1, 2, …
• Adding 1 even when the letters match.
• Using min(left, up) only and forgetting the diagonal (replace).
• Confusing the table index (1-based, with an extra row and column) with string index (0-based).