Course contentsShow
← System Design
Lesson 1774 of 1,91942. Real-World System: Search and TypeaheadFree lesson

Spell Correction and Query Expansion

Using edit distance algorithms and synonym dictionaries to handle typos and broaden search coverage.

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:

  1. Calculate edit distance between the query term and dictionary terms (or frequent search terms from your inverted index)
  2. Suggest corrections with distance ≤ 2
  3. 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.