Spell Correction & Suggestions

Users mistype. A search engine that returns nothing for recieve is bad UX.

Edit distance (Levenshtein): how many single-character insertions/deletions/substitutions to transform A into B?

levenshtein("kitten", "sitting") = 3
  kitten -> sitten (substitute k -> s)
         -> sittin (substitute e -> i)
         -> sitting (insert g)

Standard DP algorithm; O(|A|*|B|).

For suggestions: index your dictionary terms. On query, if a term has zero results AND its edit distance to a known term is ≤ 2, suggest the known term.

Symmetric Delete (SymSpell) is fast: precompute deletions of each indexed term up to distance N. Then, lookup is O(1) per candidate (compare deletions of query against indexed deletion sets).

Practical tweaks:

• Frequency-aware: prefer suggestions that appear MORE OFTEN in the corpus
• Phonetic (Soundex, Metaphone): "knight" and "night" should be near-equivalent
• Keyboard distance: 'q' and 'w' are adjacent; treat single-key swaps preferentially
• N-best candidates: show "Did you mean X / Y / Z?"

Google's spell corrector also uses noisy-channel models trained on real query logs (clicked-corrections data is gold).

For this lesson: classic Levenshtein + suggest-if-distance-<=2.