Spelling Correction and Query Segmentation

Roughly one in ten web queries contains a misspelling, and a lexical index matches nothing for most of them. Correction is therefore not a nicety; it is the difference between a result page and an empty one. The engineering difficulty is not in proposing corrections but in knowing when to apply them, because search queries are full of strings that look like errors and are not.

The noisy channel model

The standard framing treats the user as having intended \(c\) and typed \(q\) through a noisy channel. The best correction maximises

\(P(c)\) is a language model over queries, capturing which strings people actually search for. \(P(q\mid c)\) is an error model, capturing which typos are likely: adjacent-key substitutions, transpositions, phonetic confusions, and the systematic errors of a particular input method. The two do genuinely different work, and neglecting either produces a recognisable failure: a weak \(P(c)\) corrects toward common but wrong terms, a weak \(P(q\mid c)\) accepts corrections requiring implausible edits.

Candidate generation is a solved engineering problem. A trie or BK-tree over the vocabulary retrieves everything within edit distance 2; symmetric delete indexing precomputes deletions and turns lookup into a hash join, which is fast enough for interactive use over large vocabularies.

The hard part: when not to correct

Search queries are dense in strings that are not misspellings. Product codes, gene names, package identifiers, brand names with deliberate spellings, non-English words in a mixed-language corpus, and new terms that predate the language model. Correcting pytorch to python, or a serial number to a dictionary word, produces results that are worse than the empty page.

Two mechanisms carry most of the weight. Corpus-conditioned correction only corrects toward terms that exist in the index, which prevents proposing a dictionary word that no document contains. Result-conditioned correction checks whether the original query returns results: if it does, correction is at most a suggestion, and if it returns nothing, correction can be applied automatically.

That split is the standard product pattern. "Showing results for X, search instead for Y" applies the correction while preserving the escape hatch; "Did you mean X?" leaves the original results in place. Choosing between them is a decision about confidence, not a UI preference.

The single strongest training signal is behavioural: users who search, get nothing, and immediately search again with a small edit have labelled a correction pair. Query reformulation logs produce correction models that outperform dictionary-based approaches on exactly the tail terms dictionaries lack.

Segmentation and compounds

Related and less discussed: deciding where the words are. "newyorkhotels" needs splitting; "new york" needs joining into a phrase for retrieval to treat it as a unit. Both matter more in some languages than in English, and both are handled by the same machinery, scoring candidate segmentations by a language model over the corpus. German compounds, agglutinative languages, and any language written without spaces make segmentation a precondition for indexing rather than a query-time refinement.

When it breaks

Correction compounds with other query processing. Correcting a term and then expanding the correction can drift a long way from the original intent in two steps, each individually reasonable. Ordering and confidence thresholds between stages need designing as a pipeline, not per stage.

Multilingual queries break single-language models. A query mixing two languages will be "corrected" toward whichever the model was trained on. Language identification on a three-word query is itself unreliable, so the failure compounds.

The tail has no evidence. Behavioural signals need traffic, and the rarest queries, where correction matters most because there is no other route to results, have none. This is the same head-tail problem that afflicts every behavioural feature in search.

Aggressive correction hides recall failures. If a query returning nothing is silently rewritten into one that returns something, the logs record a successful query and the underlying coverage gap never surfaces. Logging the original alongside the correction is what keeps that visible.