Spell Correction and Query Expansion
What You'll Learn
You'll learn how search engines recover from user typos and broaden queries to improve coverage using edit distance algorithms and synonym dictionaries.
The Problem
Users make typos. They search for "appke" instead of "apple" or "programing" instead of "programming." Without correction, you'd return zero results and lose them. Similarly, searching "laptop" should also consider "notebook" or "portable computer" to avoid missing relevant documents.
Spell Correction: Edit Distance Algorithms
Edit distance measures how many single-character operations (insert, delete, substitute) transform one word into another. "appke" → "apple" requires one substitution, so the edit distance is 1.
When a query returns few or zero results, you:
- Calculate edit distance between the query term and dictionary terms (or frequent search terms from your inverted index)
- Suggest corrections with distance ≤ 2
- Optionally auto-correct if confidence is high (one dominant match)
Think of edit distance like a spell-checker suggesting "Did you mean...?"
Query Expansion: Synonym Dictionaries
Query expansion rewrites or augments queries with synonyms. Instead of just searching for "laptop," you internally expand to (laptop OR notebook OR portable_computer).
You maintain synonym dictionaries—either curated manually or learned from:
- Click-through data (users who search "laptop" click the same results as those searching "notebook")
- Co-occurrence patterns in documents
Expansion improves recall (finding more relevant documents), though it may slightly reduce precision.
Integration Point
Both techniques sit in your query processing flow (step 1738), before executing term intersection against your inverted index. You transform the raw query → corrected/expanded query → then retrieve posting lists.
Key Takeaway:
Spell correction uses edit distance to fix typos, while query expansion uses synonym dictionaries to broaden search coverage—both significantly improve user experience by handling imperfect input gracefully.