FINDING NEEDLES · CHAPTER 11
People type two or three words, often misspelled, in their own vocabulary. Fix, expand, and route the query before any retriever sees it.
A shopper walks up to a bookshop counter and mumbles “lanturn keper”. A good clerk does not say “no such book”. They hear The Lantern Keeper. Another shopper asks for “kids scifi”. The shelves say “children’s” and “science fiction”, and the clerk knows that is the same thing.
A search bar has no clerk. Every retriever in this series so far takes the query as typed. If the words are wrong, BM25 matches nothing and even a dense encoder gets a noisy vector. Query understanding is the small set of steps that play the clerk.
Retrieval can only find what the query asks for. A cheap fix to the query often beats an expensive fix to the ranker, because it runs once per search and helps every stage after it.
The shop has seven invented books. Each has a count of how often it was searched last month. That count stands in for a query log and breaks ties all through this chapter.
| Id | Title | Author | Tags | Searches |
|---|---|---|---|---|
| 1 | The Lantern Keeper | Mara Quill | fantasy | 140 |
| 2 | Lantern Light Recipes | Tom Ashby | cooking | 30 |
| 3 | Habits of the Heron | Ines Varga | nature | 55 |
| 4 | The Habit Engine | Dev Rao | self-help | 90 |
| 5 | Starship Orchard | Lena Holt | science fiction, children’s | 70 |
| 6 | Robots in the Attic | Sam Okoro | science fiction, children’s | 45 |
| 7 | The Last Lighthouse | Mara Quill | fantasy | 60 |
Edit distance counts the fewest one-letter changes that turn one word into another. A change is an insert, a delete, or a substitution. “lanturn” becomes “lantern” with one substitution, u to e. So the distance is 1.
meant · rewrite · entities · input
the cost to match the first i letters of a with the first j letters of b is the cheapest of: delete a letter, insert a letter, or keep/substitute the last letter (free if they already match).
The vocabulary is every word in a title or author name. Each word gets the searches of the books it appears in. “lantern” is in books 1 and 2, so it carries 140 + 30 = 170. To fix a word, take the vocabulary word with the smallest distance. If two tie, take the more searched one. Give up if the best is more than 2 edits away.
| Typed | Nearest words (distance) | Fixed to |
|---|---|---|
| lanturn | lantern (1) | lantern |
| keper | keeper (1) | keeper |
| habitz | habit (1, 90 searches), habits (1, 55 searches) | habit |
| lantren | lantern (2) | lantern |
| xyzzy | ashby (4) | left alone |
“habitz” is one edit from both “habit” and “habits”. The count picks “habit”, because The Habit Engine is searched more than Habits of the Heron. It may be the wrong guess. That is why real search bars say “Showing results for habit. Search instead for habitz.”
“lantren” swaps two letters. Plain edit distance charges that as 2, not 1. A variant that counts a swap of neighbours as one edit fits typing errors better. Real spellers also use the words around the typo and a much larger query log.
Both words in “kids scifi” are spelled fine. They are just not the shop’s words. A tag filter for “kids” and “scifi” finds 0 books. A small synonym table maps kids to children’s and scifi to science fiction. The same filter now finds books 5 and 6.
kids, scifi
0 books
children’s, science fiction
2 books: Starship Orchard, Robots in the Attic
Here the table replaces the word. Many engines instead add the synonym next to the original, with a lower weight, so a book that really says “kids” still ranks first. Dense retrieval from chapter 7 already closes some of this gap on its own. A synonym table is still cheaper, easier to audit, and works on the BM25 side and on filters, where vectors do not help.
A short question and a long passage do not look alike, even to an encoder. One fix asks a language model to write a fake answer first, then embeds that fake answer and searches with it. The fake answer may be wrong in its facts, but it is written in the vocabulary and shape of a real passage, so its vector lands nearer the real ones. It costs one model call per query, so it suits slow, hard questions, not a shop search bar.
Some queries name one exact thing. Sending them through BM25 and an encoder wastes time and can rank the exact match below a near miss. A router looks at the shape of the query and picks a tool.
| Query | Rule that fires | Route |
|---|---|---|
| 978-0-00-000000-1 | 13 digits once hyphens are removed | isbn lookup |
| Mara Quill | matches a known author exactly | author filter |
| lanturn keper | neither | hybrid search |
The order matters. Routing looks at the raw query first, so an ISBN is never “spell-fixed”. Only a query bound for search goes through the speller and the synonym table. “lanturn keper” leaves the pipeline as “lantern keeper”, routed to hybrid search.
Three hand-written rules are enough to show the idea. A large shop trains a small classifier on its query log instead, with labels such as “looking for one title”, “browsing a topic”, or “asking a question”.
Autocomplete runs on every key press, so it must be fast. A trie stores past queries one letter per node. Typing “the la” walks six nodes down. Everything below that node is a completion. Sort those by searches and show the top 3.
| Prefix | Top completions (searches) |
|---|---|
| t | the lantern keeper (140), the habit engine (90), the last lighthouse (60) |
| the la | the lantern keeper (140), the last lighthouse (60) |
| ha | habits of the heron (55) |
| l | lantern light recipes (30) |
Look at the last row. A shopper who types “l” for The Lantern Keeper sees only the cookbook. A prefix trie only matches from the first letter, and the title starts with “the”. Real systems also index each title from every word, or drop a leading “the”.
Interactive · Walk the trie
Each key press moves one node down. Which completions survive?
This walk visits every query under the prefix. With millions of past queries, a real engine stores the top few completions at each node ahead of time, so a key press is one lookup.
"""Query understanding for a small bookshop search bar.
Four steps run before any retriever sees the query:
autocomplete (while typing), spelling fix, synonym expansion, routing.
The books are invented. "searches" is how often each title was searched
last month; it stands in for a real query log.
"""
import re
BOOKS = [
{"id": 1, "title": "The Lantern Keeper", "author": "Mara Quill", "tags": ["fantasy"], "searches": 140},
{"id": 2, "title": "Lantern Light Recipes", "author": "Tom Ashby", "tags": ["cooking"], "searches": 30},
{"id": 3, "title": "Habits of the Heron", "author": "Ines Varga", "tags": ["nature"], "searches": 55},
{"id": 4, "title": "The Habit Engine", "author": "Dev Rao", "tags": ["self-help"], "searches": 90},
{"id": 5, "title": "Starship Orchard", "author": "Lena Holt", "tags": ["science fiction", "children's"], "searches": 70},
{"id": 6, "title": "Robots in the Attic", "author": "Sam Okoro", "tags": ["science fiction", "children's"], "searches": 45},
{"id": 7, "title": "The Last Lighthouse", "author": "Mara Quill", "tags": ["fantasy"], "searches": 60},
]
# What shoppers type, mapped to the words the catalogue uses.
SYNONYMS = {"kids": "children's", "scifi": "science fiction", "sf": "science fiction"}
# ---- 1. Spelling: edit distance, then popularity breaks ties ----
def edit_distance(a, b):
"""Levenshtein: fewest single-letter inserts, deletes, or substitutions."""
prev = list(range(len(b) + 1))
for i, ca in enumerate(a, start=1):
row = [i]
for j, cb in enumerate(b, start=1):
row.append(min(prev[j] + 1, # delete ca
row[j - 1] + 1, # insert cb
prev[j - 1] + (ca != cb))) # keep or substitute
prev = row
return prev[-1]
def vocabulary():
"""Every title and author word, weighted by the searches of its books."""
weight = {}
for book in BOOKS:
for word in (book["title"] + " " + book["author"]).lower().split():
weight[word] = weight.get(word, 0) + book["searches"]
return weight
def correct_word(word, max_distance=2):
"""Known words stay. Otherwise: smallest distance, then most searched.
Synonym keys count as known, or "sf" would be "fixed" to "of".
"""
vocab = vocabulary()
if word in vocab or word in SYNONYMS:
return word
scored = [(edit_distance(word, w), -vocab[w], w) for w in vocab]
best = min(scored)
return best[2] if best[0] <= max_distance else word
def correct(query):
return " ".join(correct_word(w) for w in query.lower().split())
# ---- 2. Expansion: say it the way the catalogue says it ----
def expand(query):
return [SYNONYMS.get(w, w) for w in query.lower().split()]
def match_tags(terms):
"""Books whose tags contain every term. A stand-in for a filtered search."""
return [b["id"] for b in BOOKS if all(t in b["tags"] for t in terms)]
# ---- 3. Routing: pick the right tool for the query ----
def route(query):
digits = re.sub(r"[\s-]", "", query)
if re.fullmatch(r"\d{13}", digits):
return "isbn lookup"
authors = {b["author"].lower() for b in BOOKS}
if query.lower().strip() in authors:
return "author filter"
return "hybrid search"
# ---- 4. Autocomplete: a prefix trie ranked by searches ----
class Trie:
def __init__(self):
self.root = {}
def insert(self, text, count):
node = self.root
for ch in text:
node = node.setdefault(ch, {})
node["$"] = count # "$" marks the end of a whole query
def complete(self, prefix, k=3):
node = self.root
for ch in prefix:
if ch not in node:
return []
node = node[ch]
found, stack = [], [(node, prefix)]
while stack: # walk everything under the prefix
node, text = stack.pop()
for ch, child in node.items():
if ch == "$":
found.append((child, text))
else:
stack.append((child, text + ch))
found.sort(key=lambda pair: (-pair[0], pair[1]))
return [(text, count) for count, text in found[:k]]
def build_trie():
trie = Trie()
for book in BOOKS:
trie.insert(book["title"].lower(), book["searches"])
return trie
def understand(raw):
"""The whole pipeline once the shopper presses enter."""
fixed = correct(raw) if route(raw) == "hybrid search" else raw
return {"fixed": fixed, "terms": expand(fixed), "route": route(fixed)}
Spell-fixing words the speller has never seen. “sf” is one edit from “of”. If the synonym keys are not in the speller’s list of known words, “sf” becomes “of” before expansion can turn it into science fiction.
Fixing a query that was not a typo. ISBNs, part numbers, and rare names look like misspellings. Route first. Fix only what is bound for text search, and always offer the original query.
Expanding too far. Every synonym brings in more books, and some of them are wrong. Expanding “habit” to “habits” would pull in Habits of the Heron, a nature book, for a shopper who wanted the self-help one. Expand with a short, checked table, or at a lower weight.
Ranking autocomplete by text order, not by searches. Sorted alphabetically, “t” would show the habit engine before the lantern keeper, though the lantern keeper is searched 140 times to 90. The count is the ranking.
1. Insert one e.
Plain edit distance has no swap. Swapping r and e is two substitutions.
An ISBN or exact name is not a typo. A speller would change it to the nearest word and the exact lookup would never happen.
The trie holds “the lantern keeper”, which starts with t. A prefix walk from “l” never reaches it.