FINDING NEEDLES · CHAPTER 11

Query understanding

People type two or three words, often misspelled, in their own vocabulary. Fix, expand, and route the query before any retriever sees it.

~14 min read7 booksTested Python

What you'll learn

  • How edit distance plus a popularity count fixes a misspelled word
  • How a synonym table turns zero results into the right books
  • How a few routing rules send a query to the right tool
  • How a prefix trie ranked by past searches does autocomplete

Before you start

The clerk who hears what you meant

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.

typingautocomplete
→
fixspelling
→
expandsynonyms
→
routeisbn · author · search
→
searchchapter 10

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.

IdTitleAuthorTagsSearches
1The Lantern KeeperMara Quillfantasy140
2Lantern Light RecipesTom Ashbycooking30
3Habits of the HeronInes Varganature55
4The Habit EngineDev Raoself-help90
5Starship OrchardLena Holtscience fiction, children’s70
6Robots in the AtticSam Okoroscience fiction, children’s45
7The Last LighthouseMara Quillfantasy60

The nearest real word, then the most searched

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

MANIM Query understanding rewrites intent before retrieval.

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.

TypedNearest words (distance)Fixed to
lanturnlantern (1)lantern
keperkeeper (1)keeper
habitzhabit (1, 90 searches), habits (1, 55 searches)habit
lantrenlantern (2)lantern
xyzzyashby (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.

Say it the way the catalogue says it

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.

As typed

kids, scifi

0 books

Expanded

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.

Expanding with a made-up answer (HyDE)

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.

Not every query is a search

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.

QueryRule that firesRoute
978-0-00-000000-113 digits once hyphens are removedisbn lookup
Mara Quillmatches a known author exactlyauthor filter
lanturn keperneitherhybrid 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”.

Answer before the shopper finishes typing

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.

PrefixTop completions (searches)
tthe lantern keeper (140), the habit engine (90), the last lighthouse (60)
the lathe lantern keeper (140), the last lighthouse (60)
hahabits of the heron (55)
llantern 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.

The whole pipeline in one file

query_pipeline.pylanturn keper → lantern keeper
"""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)}

Mistakes learners make

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.

What to remember

  • Spelling: smallest edit distance, then most searched. “lanturn keper” becomes “lantern keeper”. “habitz” ties at 1 and the count picks habit (90 over 55).
  • Expansion: “kids scifi” finds 0 books. In the catalogue’s words it finds books 5 and 6.
  • Routing: an ISBN goes to a lookup, an author name to a filter, everything else to hybrid search. Route before you fix.
  • Autocomplete: a prefix trie ranked by searches. “the la” gives the lantern keeper (140), then the last lighthouse (60).

Check yourself

1. What is the edit distance from “keper” to “keeper”?

1. Insert one e.

2. Why does “lantren” cost 2 and not 1?

Plain edit distance has no swap. Swapping r and e is two substitutions.

3. Why route before spell-fixing?

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.

4. Why does the prefix “l” not suggest The Lantern Keeper?

The trie holds “the lantern keeper”, which starts with t. A prefix walk from “l” never reaches it.

Go to the source

Keep going