Query understanding — from raw string to structured intent

The funnel from lesson 40 starts with a string the user typed. Before a single posting list is touched, that string is normalized, tokenized, corrected, expanded, segmented, and tagged. Every one of those transforms trades recall against precision — your job is to name the trade for each.

The one engineering line to carry through every section: each transform either widens the set of documents that can match (recall) or narrows it toward the user's true intent (precision), and a senior engineer can state which, and the failure mode, for every stage. Normalization and expansion buy recall; phrase detection and tagging buy precision; spelling correction and segmentation are recall-then-precision in one move. Get the direction wrong and you either return nothing or return everything.

The analysis pipeline, in order

Analysis (the IR term) is the deterministic transform from a raw query (and, symmetrically, from each document at index time) into the sequence of terms that the index keys on. The cardinal rule: the query analyzer and the document analyzer must agree. If the index stored running stemmed to run but the query analyzer leaves running alone, the term never matches and recall silently dies. Most production bugs in this layer are an asymmetry between the two paths.

1 · Unicode normalization

A user typing café on a Mac and another pasting café from a PDF can produce different byte sequences for the same visible string: one is the precomposed code point U+00E9, the other is e + a combining acute accent U+0301. Byte-equality fails; the term won't match. NFKC (Normalization Form KC — Compatibility Composition) is the standard fix: it canonicalizes composed/decomposed forms and folds compatibility variants (full-width ＡＢＣ → ABC, the ligature fi → fi, ① → 1). Then casefold (a more aggressive lowercase that also handles e.g. German ß → ss) and optional diacritic folding (café → cafe, naïve → naive).

The trade. Every fold is a recall-for-precision swap. Diacritic folding lets resume match résumé — great for English users who skip accents. But in French, marché (market) and marche (walks/step) are different words; fold them and you inject ambiguity. Failure mode: a blanket accent-strip applied to a French or Vietnamese corpus collapses distinct words and tanks precision. The senior move is to make folding locale-aware, not global.

2 · Tokenization

Tokenization splits the normalized string into tokens. Three regimes you must distinguish:

The trade. Aggressive splitting (hyphens, dots) raises recall (node.js finds docs that wrote node js) but lowers precision (C++ queries match every doc containing a bare c). CJK segmentation is recall-vs-precision in the cut itself: under-segmenting keeps long phrases (precise, low recall), over-segmenting into characters maximizes recall but matches noise.

3 · Stopwords — why modern BM25 mostly keeps them

Stopwords are extremely frequent function words (the, a, of, to). Classic IR dropped them: in a 1990s memory-and-disk-constrained index, the posting list for the covers ~every document and costs a fortune to store and intersect, while contributing almost nothing to ranking. So dropping them was a pure win on cost.

Modern systems mostly keep stopwords. Two reasons. First, BM25 (lesson 42) already down-weights them automatically via IDF — a term in every document has near-zero inverse document frequency, so it barely moves the score even if present. The cost-saving motivation is gone now that storage is cheap and skip-lists make long posting lists fast. Second, dropping them destroys phrase queries and changes meaning: to be or not to be becomes empty; the office (the show) becomes office; vitamin a loses the a that is the query. Failure mode of dropping: the query flights to paris and flights from paris become identical. The senior position: keep stopwords for matching, rely on IDF to neutralize their weight, and special-case them only inside phrase detection.

4 · Stemming vs lemmatization

Both collapse morphological variants so run matches running/ran/runs — a recall move. They differ in how, and in what they cost.

The trade. Stemming over-merges, hurting precision: a query for universe retrieves university docs because both became univers. Lemmatization is precise but pays POS-tagging latency on every query and needs per-language resources. The pragmatic default in web/e-commerce search is a light stemmer (Porter or KStem, which is more conservative) for high-recall languages, and skipping stemming entirely where precision dominates (legal, code, exact-SKU). Whatever you pick, apply the identical transform at index time — the asymmetry bug again.

Spelling correction — the noisy-channel model

Roughly 10–15% of web queries contain a typo. Correcting them is a large recall lever (the misspelled term has an empty or wrong posting list). The standard framing is the noisy-channel model: the user intended a correct word c but a noisy channel (fat fingers, bad spelling) emitted the observed string w. We invert it with Bayes:

Two factors, each with a name and a job:

• P(c) — the prior / language model. How likely is c to be a query at all? Estimated from the query log: frequent past queries get high prior. This is what makes the beat teh and makes domain-specific terms self-correct (a shoe site's log makes nike a high-prior correction for nkie).
• P(w | c) — the error / channel model. Given the user meant c, how likely were they to type w? Driven by weighted edit distance: fewer/cheaper edits ⇒ higher probability.

Weighted edit distance: Damerau-Levenshtein, worked

Plain Levenshtein distance counts the minimum insertions, deletions, and substitutions to turn one string into another. Damerau-Levenshtein adds a fourth operation — transposition of two adjacent characters — because swapping neighbours (teh→the) is one of the most common real typos and Levenshtein would charge it as two edits. Keyboard-adjacency weighting further says a substitution of two physically-adjacent keys (s↔d) is cheaper than distant keys (s↔p), because the former is a far more probable slip.

Worked example: distance from typed teh to candidate the.

Plain Levenshtein teh→the = 2 (substitute position 2 e→h, substitute position 3 h→e). With the transposition rule, the adjacent pair eh↔he is a single operation, so Damerau-Levenshtein = 1. That single-edit candidate gets a much higher P(w|c) than any 2-edit alternative — which is exactly why transposition matters: teh should correct to the (1 edit, transposition), not to tea (1 substitution) once the prior is folded in.

Ranking candidates with a query-log language model

Concretely: user types teh. Candidate generator (all dictionary/log words within Damerau distance ≤ 2, via a BK-tree or a deletion-index like SymSpell) yields the, tea, ten. Toy numbers — channel probability from edit cost, prior from query-log frequency (per million queries):

Even though tea and ten are also single edits, the wins by ~150× — almost all of it from the prior (the is enormously more frequent in the log than tea/ten). This is the key intuition: the channel model narrows to plausible typos; the query-log prior picks the winner. A spelling corrector with no prior corrects nkie to a dictionary word like nice; a corrector with a shoe-store query-log prior corrects it to nike. The prior is where your domain lives.

Query expansion — buy recall, watch the drift

Expansion adds terms to the query so documents that used different words can still match. It is the single biggest recall lever and the single biggest precision risk. The terms are added as optional (SHOULD) clauses with lower weight, not mandatory ones, so they boost recall without forcing every expansion to appear.

Classic expansion

• Synonym dictionaries / thesauri. Hand-curated or mined: laptop ⇒ notebook, nyc ⇒ new york city, tv ⇒ television. Precise, controllable, but static and expensive to maintain across domains and languages.
• Pseudo-relevance feedback (PRF) / Rocchio. Assume the top-k documents from a first-pass search are relevant (hence pseudo — no human said so), then reweight the query vector toward their terms. This automatically discovers corpus-specific expansions.

Rocchio reweighting, worked

In the vector-space view a query is a weighted term vector q. Rocchio moves it toward the centroid of (pseudo-)relevant docs and away from non-relevant ones:

Toy worked numbers. Original query jaguar speed over a 4-term vocabulary {jaguar, speed, animal, car}. Initial q = (1, 1, 0, 0). PRF: the top-2 returned docs (treated as relevant) happen to be about the car, with term vectors d₁ = (1, 1, 0, 1) and d₂ = (1, 0, 0, 1); one non-relevant doc (about the animal) d₃ = (1, 0, 1, 0). Use α = 1, β = 0.75, γ = 0.25.

The query learned to add car (weight 0.75) and suppress animal — it disambiguated jaguar toward the car sense because the first-pass results leaned that way. That is also the danger: if the first-pass top-k were actually about the animal, Rocchio would amplify the wrong sense. PRF amplifies whatever bias the first pass had — query drift.

Neural expansion

• Embedding nearest-terms. Use a term/word embedding (or the dense query embedding from lesson 43) to pull semantically near terms: sneaker ≈ trainer, running shoe. Captures synonymy no thesaurus listed, but neighbours include co-occurring-but-wrong terms (sneaker ≈ sock), so it drifts more than a curated dictionary.
• doc2query / docTTTTquery. Flip the problem: at index time, a seq2seq model generates the queries each document would answer and appends them to the doc. The expansion lives in the index, not the query — zero query-time latency, and it bridges vocabulary mismatch from the document side. Effectively a learned, document-conditioned synonym set.

Query segmentation & phrase detection

A bag-of-terms analysis throws away word order. For many queries that is fine; for some it is fatal. new york times as three independent terms (new AND york AND times) matches a document about "the new times in York" — wrong. The query means the newspaper, a single concept. Query segmentation groups adjacent tokens into phrases (multi-word expressions) so they are matched as a unit.

Why it matters for the inverted index (lesson 42): a phrase match requires positional postings — the index must store where in each document a term appears, so new york times only matches when the three terms are adjacent and in order. That is more expensive than a plain term match, so you only promote high-confidence phrases. Detection signals: query-log co-occurrence / pointwise mutual information (the trigram appears together far more than chance), a known-entities gazetteer, or a learned segmenter. The trade: phrase matching is a precision tool — it shrinks the matching set to documents with the exact adjacency, raising precision but risking recall if the document phrased it slightly differently (the New York Times vs NY Times). The standard hedge is to issue both: the phrase as a strong-weighted optional clause plus the loose AND, so the phrase match floats to the top without excluding the rest.

Intent classification, NER, and structured tagging

Everything above operated on words. This stage operates on meaning: classify what the user wants and extract the structured fields a backend can act on.

Intent classification — the Broder types

From lesson 40, the classic taxonomy of web-search intent (Broder 2002):

• Navigational — go to a specific known destination (facebook login, chase bank). One right answer; do not expand or diversify; precision is everything.
• Informational — learn about a topic (how does bm25 work). Many good answers; expansion and diversity help.
• Transactional — do something / buy something (cheap iphone charger, book flight to paris). Triggers commerce ranking, price/availability signals.

Intent is usually a lightweight classifier (logistic regression / small transformer) over the query plus log features. It gates the rest of the pipeline: a navigational query turns off expansion and diversity; a transactional one turns on price sorting and inventory filters. Misclassifying navigational as informational is the classic precision failure — the user wanted exactly one site and you handed them a topic page.

Named-entity recognition & entity linking

NER tags spans with types: in cheap iphone charger, iphone is a PRODUCT/BRAND span. Entity linking then resolves the span to a canonical entity in a knowledge base / catalog: the surface form iphone → entity Apple iPhone (brand=Apple, product-line=iPhone). Linking is what lets iphone, i-phone, and apple phone all resolve to the same node — disambiguation against a catalog, not string matching.

Structured tagging → facets

For e-commerce especially, the goal is to decompose the query into the catalog's structured fields. Worked: cheap iphone charger →

Those fields are exactly the facets that structured / e-commerce search exposes — the filter-and-sort controls in lesson 47. Query understanding is what auto-populates them from free text, so cheap iphone charger behaves like the user had clicked Brand: Apple, Category: Chargers, Sort: price-low-to-high. The trade: every extracted facet that you turn into a hard filter trades recall for precision — tag cheap as a hard price ≤ p25 filter and you exclude the $9 charger priced at p26. Senior practice is to apply tags as ranking boosts/soft-sorts rather than hard filters unless the field is unambiguous (a confidently-linked brand is safe to filter; a fuzzy modifier like cheap is safer as a sort signal).

The LLM era — rewrite power, latency tax

An LLM (lesson 26) can do much of this pipeline in one shot and better: query rewriting (chrgr for iphn → iPhone charger, fixing spelling, expanding abbreviations, and normalizing all at once), conversational rewriting (resolving and a cheaper one? against prior turns), and semantic expansion (generating intent-faithful synonyms and related terms with far less drift than embedding-neighbour expansion, because the model reasons about sense). It can also emit the structured tags directly as JSON.

One query through every stage

Putting it together — the user types café RUNNING-shose nyc (note the typo shose):

Trace the recall/precision ledger: normalization, spelling, stemming, and expansion all widened the matchable set (recall up); segmentation of nyc and the location/category facets narrowed toward intent (precision up). Every arrow had a direction, and a senior can name it.

Interactive · query-understanding pipeline

Type a query (or pick an example) and watch it transform stage by stage. The lexicon, synonym map, and typo model below are a small built-in toy — deterministic, no network — so the exact corrections are illustrative, but the stages and their order are real.

Interview prompts you should be ready for