Skip to content
Tutorials Center
My learning

Topics

Lesson 216 of 225 ยท Projects

Project: Spell Checker

Build a spell checker in stages. Start with a hash set, add edit distance, generate candidate edits, speed up search with a BK-tree, and test every version.

When your phone underlines "stroy" in red and offers "story", three separate data structure problems have just been solved in a few milliseconds. First, the program decided that "stroy" is not a word, which is a membership question. Second, it found real words that are close to the typo, which is a similarity search. Third, it chose which suggestion to show first, which is ranking.

In this project you build a spell checker in stages. You start with a hash set for the "is this a word?" question, add edit distance to measure closeness, try two ways of finding candidates (scanning everything and generating edits), then replace the scan with a BK-tree that skips most of the dictionary. At the end you test all versions against each other. Each stage is a complete program you can run.

The specification

The checker works on lowercase English words and has two jobs:

  • is_known(word): is the word in the dictionary?
  • suggest(word, k): return up to k dictionary words within edit distance 2 of the word (distance 1 for words of three letters or fewer, otherwise almost every short word matches), best first. "Best" means a smaller distance first, then the more frequent word, then alphabetical order (so results are deterministic).

Our dictionary is a small vocabulary where each word has a frequency, standing in for how often people use it. It is deliberately full of look-alike words (still, stall, spill, spell, shell, small) because that is where spell checkers get interesting.

The edit distance (Levenshtein distance) between two words is the smallest number of single-character edits that turns one into the other. An edit is an insertion, a deletion or a substitution. For example spel to spell takes 1 edit (insert an l), and stroy to story takes 2 (substitute r with o, then o with r).

Stage 1: is the word known?

The first stage is just a dictionary lookup. We split text into words with a regular expression and test each one against a dict:

Python Stage 1: membership with a dict

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A hash lookup is O(1) on average, so checking a whole document costs time proportional to its length. Note that nights is flagged: our toy dictionary has night but not its plural. Real checkers add rules for suffixes (or just use a bigger word list). The interesting part starts now: what do we suggest for the unknown words?

Edit distance is a classic dynamic programming problem. Let D[i][j] be the distance between the first i letters of a and the first j letters of b. Deleting, inserting or substituting the last letter gives the recurrence:

TEXT
D[i][j] = min( D[i-1][j]   + 1                    # delete a[i]
             , D[i][j-1]   + 1                    # insert b[j]
             , D[i-1][j-1] + (a[i] != b[j]) )     # substitute, or free match

The first row and column are D[0][j] = j and D[i][0] = i (turning a prefix into nothing). The table below makes the idea visible for a pair of short words:

Python The edit distance table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The bottom-right cell is the answer. Filling the table costs O(len(a) * len(b)) time. Because each row only needs the previous one, a production version keeps two rows and uses O(min(len(a), len(b))) extra space. We use that version from now on.

Now the brute-force corrector: compute the distance to every dictionary word and keep those within 2. We also report how many distance computations that takes:

Python Stage 2: scan the whole dictionary

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

It works, and with a few dozen words it is instant. But every query computes one full table per dictionary word. With 200,000 words and a 30-character typo, that is millions of cell updates for one underlined word. We need to avoid looking at words that cannot possibly be close.

Sorting tuples (distance, -frequency, word) is a handy trick: Python compares tuples element by element, so the smallest distance wins, then the largest frequency (negated), then alphabetical order.

Stage 3: generate the edits instead of scanning

Flip the problem around. Instead of asking "which dictionary words are close to the typo?", generate every string that is one edit away from the typo, and ask the hash set which of them are real words. Lookups are O(1), so the dictionary size no longer matters:

TEXT
"spel"  --delete-->   pel, sel, spl, spe
        --replace-->  apel, bpel, ... sael, sbel, ... spea, speb, ...
        --insert-->   aspel, bspel, ... spela, spelb, ... (spell is in here!)

For a word of length n there are n deletions, 26n replacements (one of which keeps the same letter) and 26(n+1) insertions: about 53n + 26 strings, fewer after removing duplicates. Distance 2 means applying the function twice, to every one of those strings:

Python Stage 3: generate edits and look them up

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This version is the one many tutorials stop at, and it is fine for short words. Its cost depends on the word length and the alphabet size, not on the dictionary: for distance 2 you generate on the order of (53n)^2 strings, which grows quickly with n and explodes at distance 3. It is also tied to a 26-letter alphabet: add accents, digits or another language and LETTERS grows.

Stage 4: a BK-tree

The brute-force scan wasted work because it treated the dictionary as an unordered pile. A BK-tree (Burkhard-Keller tree) organises words by their distance to each other, so a search can discard whole groups at once.

Build it like this. The first word is the root. To insert a new word, compute its distance d to the current node; if the node has no child on an edge labelled d, the word becomes that child, otherwise move down that edge and repeat. Each edge label is a distance to the parent:

TEXT
            the
        /    |     \       edge label = distance to parent
      1/    2|      \3
    they    tee     three...
   1/  \2
 then  them ...

To search for words within tol of a query q: compute d = distance(q, node). If d <= tol, the node is a result. Now the key idea: the triangle inequality says that for any child c reached by an edge labelled e, the distance from q to c is at least |d - e|. So a child can only contain a match if d - tol <= e <= d + tol. Every other edge is skipped without computing a single distance:

Python Stage 4: a BK-tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With a tiny dictionary the savings are modest (the output above shows roughly a third of the distance computations saved for stroy); with thousands of words they are larger. How well pruning works depends on the tolerance (small is much better) and on how spread out the distances are. At tolerance 2 on a dictionary where most words are within four or five edits of each other, a BK-tree may still visit a sizable fraction of the nodes. It is a heuristic with a guaranteed-correct answer, not a guaranteed speedup.

The pruning argument needs the distance to be a true metric: non-negative, symmetric, zero only for equal words, and obeying the triangle inequality. Plain Levenshtein is a metric. A distance that breaks the triangle inequality can make the BK-tree silently skip real matches.

Stage 5: put it together

Now package the pieces into one class. The BK-tree finds all words within the tolerance, and a sort ranks them by the specification: smaller distance, then higher frequency, then alphabetical:

Python Stage 5: the SpellChecker class

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the behavior against the specification: a known word returns itself, an unknown word returns up to three close words, and a word with nothing close returns an empty list. Notice that correct_text leaves a token alone when no suggestion exists, which is safer than inventing a replacement. The reduced tolerance for very short words matters: without it, the one-letter word a is only two edits from tea and would be "corrected" into it. Also note that nights became night, because the plural is one deletion away from a known word.

Stage 6: test it against the simple versions

How do you know the BK-tree did not drop a real match? The same trick as in the autocomplete project works: compare it with the slow, obviously correct version. We have three independent implementations of "all words within distance 2": the full scan, the edit generator and the BK-tree. If they agree on hundreds of mutated words, we can trust the fast one.

Python Stage 6: differential testing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three methods should return identical sets. If you ever change the distance function (for instance to a weighted one), this test tells you at once whether your pruning is still valid.

Going further: transpositions and real-world tweaks

The most common typing error is swapping two neighbours: teh for the. Under Levenshtein that costs 2 (two substitutions), so teh ranks the no better than a word two edits away. The Damerau-Levenshtein distance counts an adjacent swap as one edit. In the generate-edits approach it is a one-line addition:

Python Adding transpositions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Real spell checkers also add: a much larger dictionary; word forms (plurals, -ing, -ed); keyboard-aware costs (substituting a neighbouring key is cheaper); context from the previous word (their vs there); and a personal dictionary. Another popular speedup is the delete-only index (the SymSpell idea): precompute all deletions of every dictionary word and store them in a hash map, so a query only deletes characters from the typo and looks up the matches. It trades memory for very fast lookups and works with any alphabet.

Complexity summary

Strategy Query time Extra memory Notes
Scan every word O(N * n * m) none N words of length m, query length n
Generate edits (distance 2) about O(n^2 * 26^2) set lookups the generated sets independent of N, needs a fixed alphabet
BK-tree between O(log N) and O(N) distance calls O(N) nodes depends on tolerance and data
Delete-only index O(n^2) lookups at distance 2 large index fast queries, big memory

Common mistakes

  • Using a distance that is not a metric with a BK-tree, which makes pruning drop correct answers.
  • Forgetting the exact-match case: a correct word must be returned as itself, not "corrected" to a more popular neighbour.
  • Sorting suggestions without a tie-break, which produces results that change between runs.
  • Generating distance-3 edits by repeating the edit function: the set grows by a factor of about 53n each time.
  • Mutating the dictionary while iterating over it when you add words at runtime.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the edit distance between two words measure?

    Levenshtein distance counts the cheapest sequence of single-character edits. Length difference and position-by-position mismatches are only bounds or special cases.
  2. 2. Why does the generate-edits approach not depend on the dictionary size?

    The work is proportional to the number of generated strings, which depends on the word length and alphabet, not on how many words are stored.
  3. 3. In a BK-tree search with tolerance t, a node at distance d from the query may have matches only under edges labelled e where

    By the triangle inequality, a child under an edge labelled e is at least |d - e| away from the query, so only labels within t of d can lead to matches.
  4. 4. Why can a BK-tree return wrong answers if the distance function breaks the triangle inequality?

    Pruning is justified only by the triangle inequality. Without it, a skipped subtree can still contain words within the tolerance.
  5. 5. How does the project make suggestion order deterministic?

    Sorting on a tuple orders by distance first, then by higher frequency, then alphabetically, so equal candidates always appear in the same order.

Summary

  • A spell checker is three problems: membership (hash set), closeness (edit distance) and ranking (distance, then frequency).
  • Levenshtein distance is a DP table filled in O(n * m); two rows are enough.
  • Scanning the dictionary costs one distance per word; generating edits costs about 53n + 26 strings per level and ignores dictionary size.
  • A BK-tree uses the triangle inequality to skip subtrees; it requires a true metric and works best with small tolerances.
  • Compare fast and slow implementations on many generated inputs: differential testing is the cheapest way to trust an optimization.
  • Real systems add transpositions, bigger dictionaries, word forms, and context.

Next: Project: Real-time Leaderboard