Edit distance and spelling correction

Intermediate

Introduction

Spell checkers, search engines that ask "did you mean ...?", DNA comparison and fuzzy matching of names in databases all ask the same question: how different are two strings? Edit distance answers it by counting the smallest number of small edits that turn one string into the other. It is one of the classic dynamic-programming algorithms, and with a dictionary of word frequencies it becomes a working spelling corrector.

How it works

Three edits are allowed in Levenshtein distance, each costing 1:

  • Insert a character ("cat" to "cart").
  • Delete a character ("cart" to "cat").
  • Substitute one character for another ("cat" to "cut").

"kitten" becomes "sitting" in 3 edits: k to s, e to i, then insert g.

To compute the minimum, fill a table D where D[i][j] is the distance between the first i characters of a and the first j characters of b:

  • D[i][0] = i (delete everything) and D[0][j] = j (insert everything).
  • D[i][j] = the minimum of D[i − 1][j] + 1 (delete), D[i][j − 1] + 1 (insert) and D[i − 1][j − 1] + cost, where cost is 0 if a[i] equals b[j] and 1 otherwise.

The answer is in the bottom-right cell. Each row only needs the row above it, so two lists are enough. The work is len(a) × len(b) cells.

Variants: operations can have different costs (some textbooks use 2 for a substitution, so it equals a deletion plus an insertion). The Damerau variant adds a transposition of two neighbouring characters for cost 1: "teh" to "the" is then 1 edit instead of 2. It looks two rows back, D[i − 2][j − 2] + 1, when the last two characters are swapped.

A spelling corrector combines distance with word frequency. For an unknown word, consider dictionary words within a small distance (1 or 2), and pick the closest; among equally close words, pick the most frequent. This is a simple version of the noisy channel model: choose the word w that maximizes P(w) × P(typo given w), where P(w) is how common w is and P(typo given w) is how likely that particular mistake is.

Example

def distance(a, b, swaps=False):
    older, prev = None, list(range(len(b) + 1))
    for i in range(1, len(a) + 1):
        cur = [i]
        for j in range(1, len(b) + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            d = min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + cost)
            if swaps and i > 1 and j > 1 and a[i - 1] == b[j - 2] and a[i - 2] == b[j - 1]:
                d = min(d, older[j - 2] + 1)
            cur.append(d)
        older, prev = prev, cur
    return prev[-1]


print("kitten -> sitting:", distance("kitten", "sitting"))

counts = {"the": 500, "ten": 40, "tea": 30, "eh": 5}


def correct(word, swaps):
    scored = [(distance(word, w, swaps), -counts[w], w) for w in counts]
    d, _, best = min(scored)
    return best, d


for swaps in (False, True):
    best, d = correct("teh", swaps)
    print(f"swaps={swaps}: teh -> {best} (distance {d})")
Open in compiler

Line by line

  1. prev starts as the first row, 0 to len(b). Each new row cur starts with i, the cost of deleting i characters.
  2. Each cell takes the cheapest of delete, insert and substitute (or keep, when the characters match).
  3. With swaps=True, a pair of swapped neighbours may also come from two rows back (older) at cost 1.
  4. "kitten" to "sitting" costs 3, as worked out above.
  5. Without swaps, "teh" is 2 edits from "the" but only 1 from "ten", "tea" and "eh"; the most frequent of those, "ten", wins. With swaps, "the" is 1 edit away and, being by far the most frequent word, it wins.

Expected result

kitten -> sitting: 3
swaps=False: teh -> ten (distance 1)
swaps=True: teh -> the (distance 1)

In the real world

Phone keyboards weigh edits by the keyboard layout (hitting a neighbouring key is a likely typo), search engines learn corrections from the queries people retype, and modern correctors use language models to pick the word that fits the sentence ("their" or "there"). Peter Norvig's well-known 21-line corrector generates every string one or two edits away and keeps those in the dictionary. Bioinformatics uses weighted edit distances to align DNA and protein sequences, and databases use them to match "Jon Smith" to "John Smith".

Common mistakes

  • Off-by-one errors between table positions and string positions: D[i][j] compares a[i − 1] with b[j − 1].
  • Forgetting the first row and column, which hold the cost of inserting or deleting whole prefixes.
  • Ignoring frequency, so a rare word beats a common one at the same distance.
  • Correcting words that are already in the dictionary.

Best practices

  • Test with known pairs: kitten and sitting is 3, flaw and lawn is 2, identical strings are 0.
  • Keep only two rows (or three with transpositions) to save memory.
  • Limit candidates to a small distance and, for speed, to words of similar length.
  • Use a frequency list from text like the one you are correcting.

Summary

Edit distance is the minimum number of insertions, deletions and substitutions that turn one string into another. Dynamic programming computes it by filling a table of prefix distances, one row at a time. Adding transpositions handles swapped letters. A spelling corrector picks the dictionary word with the smallest distance, preferring frequent words, which is a simple noisy-channel model.

Quick check

1. What is the Levenshtein distance between 'cat' and 'cut'?
2. What does cell D[i][j] of the edit-distance table hold?
3. Why does plain Levenshtein give 2 for 'teh' and 'the'?
4. Two dictionary words are both 1 edit from a typo. Which should a corrector choose?

Key takeaways

  • Edit distance fills a table where each cell is the distance between two prefixes.
  • Plain Levenshtein counts a swap of two letters as two edits; adding transpositions fixes the most common typo.
  • A good corrector combines closeness (edit distance) with how common each candidate word is.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.