Edit-Distance Candidate Generation for Query Spelling Correction

A query that misses because of a typo returns nothing, and a user who gets nothing usually leaves rather than respells. The corrective layer therefore sits on the critical path, and it has to decide three things per query term: whether the term is a mistake at all, which of the many strings within a small edit distance is the intended one, and whether to rewrite the query or merely to offer the alternative.

The middle decision is where the machinery lives. Enumerating candidates is a bounded search over the vocabulary; ranking them is a probabilistic model; and deciding to act is a threshold on the margin between the best candidate and the original.

Candidate generation is a search over a trie

The vocabulary is a finite set of strings, usually the index’s term dictionary. Finding all entries within edit distance 1 of a query term by comparing against every entry is $O(|V| \cdot L^2)$ with dynamic programming, which for a million-term vocabulary and an average term length of eight is far too slow for the serving path.

Two structures make it tractable. The first is a trie or a finite-state transducer over the vocabulary, traversed with a Levenshtein automaton: a state machine that accepts exactly the strings within distance $k$ of the query. Traversal prunes branches as soon as the automaton reaches a dead state, so the cost is proportional to the size of the accepted set plus the shared prefixes on the way to it, not to the vocabulary. For $k=1$ on English text, the accepted set for a typical term is small.

The second is deletion neighbourhoods, the SymSpell approach. For each vocabulary entry, every string obtained by deleting up to $k$ of its characters is precomputed and stored in a hash map keyed by the reduced string. To find candidates for a query term, the same deletions are generated for the query and looked up. Any two strings at edit distance $k$ share a common subsequence reachable from each by at most $k$ deletions, so every true candidate is found; but a shared key only proves that the pair is within $2k$ deletions of each other, which is why the surviving candidates are verified with an exact distance computation before use.

The index cost per term is the number of distinct deletion variants, $\sum_{d=0}^{k}\binom{L}{d}$, which is about $L^2/2$ for $k=2$ and a term of length $L$. For a vocabulary of a million terms of average length eight, that is tens of millions of keys, so the structure is memory-resident and built once. The lookup side is a hash probe per generated variant, which is a few dozen probes for the same parameters.

A third option is phonetic hashing, mapping both the vocabulary and the query into a coarse sound code and looking up by code. It catches misspellings that preserve sound, which is a real class, and misses every misspelling that does not. It is cheap enough to run in addition to the others.

Distance itself needs care. Plain Levenshtein charges 1 for insertion, deletion, and substitution. Damerau-Levenshtein adds transposition, which matters because adjacent-character swaps are among the most common typing errors and a model without transposition charges 2 for them. Weighted variants charge less for substituting keys that are adjacent on the keyboard or for characters that sound alike, which reduces the candidate set to plausible typos at the cost of a keyboard-layout table.

Ranking is a noisy channel

Given candidates $c$ and an observed query term $t$, the noisy-channel formulation asks for the $c$ maximizing $P(c) \cdot P(t \mid c)$: the prior probability that the user meant $c$, times the probability that $c$ would be typed as $t$.

The prior comes from term frequency in the collection or from query logs. This is the single most important term. It is what makes receive beat recieve and their beat thier: both are within one edit, but one is a word people write and the other is not. Frequency also handles the case where two candidates are both real words: form and from are one transposition apart, and the prior decides.

The channel probability is a model of typing. A simple version assigns each edit operation a probability from a confusion matrix estimated over character pairs, so ie and ei swaps, doubled letters, and adjacent keyboard keys all get distinct weights. More elaborate versions condition on position in the string, since errors are more common at the ends of long words than in the middle, and on the surrounding characters.

The product is then compared against the probability of the original term, and the ratio decides. If $P(c) \cdot P(t \mid c) / P(t) > \theta$, rewrite. The threshold $\theta$ is not a modelling parameter but a policy one: it trades false corrections against missed ones, and the two errors have different costs. A false correction on a rare but correctly spelled technical term is worse than a missed correction on a typo, because the first silently returns results for a different query.

Terms that must not be corrected

The single largest source of damage in deployed correctors is correcting terms that are not misspellings.

Rare terms in a specialized corpus are the first class. A product code, a surname, a species name, or a gene identifier has low frequency in the general vocabulary and high importance to the user. A prior built from general frequency will happily rewrite it to the nearest common word. The standard defence is a protected set drawn from the index itself: if the term appears in the collection at all, even once, the threshold for rewriting it rises sharply or the rewrite is disabled.

Terms that are in-vocabulary but unusual are the second class. definately is not in the vocabulary and is corrected; defiantly is in the vocabulary, is one character away, and is a different word. Because it is in-vocabulary, a corrector that only rewrites out-of-vocabulary terms leaves it alone, which is the right default. The mistake is to also rewrite in-vocabulary terms when the surrounding query suggests otherwise; that path requires more context than a single term provides.

Short terms are the third class. Every three-letter string is within one edit of many common words, so the candidate set is dense and the prior differences are small. Corrections on terms of one or two characters should be suppressed outright.

def levenshtein(a: str, b: str, limit: int) -> int:
    """Banded DP; returns limit+1 as soon as the distance provably exceeds limit."""
    if abs(len(a) - len(b)) > limit:
        return limit + 1
    prev = list(range(len(b) + 1))
    for i, ca in enumerate(a, 1):
        cur = [i] + [0] * len(b)
        for j, cb in enumerate(b, 1):
            cur[j] = min(prev[j] + 1,                    # deletion
                         cur[j - 1] + 1,                  # insertion
                         prev[j - 1] + (ca != cb))        # substitution
        if min(cur) > limit:                              # whole row over budget
            return limit + 1
        prev = cur
    return prev[-1]

The band check is what makes the routine usable in a filter: most vocabulary entries can be rejected after a few rows rather than after the full $O(L^2)$ computation.

Whole-query correction and the join problem

Term-by-term correction fails on errors that span a space. new york typed as ne wyork produces two terms, neither of which is a plausible typo of a single word. The fix is to correct over the query as a string, or to consider merges and splits of adjacent terms as candidate operations, which is the same candidate-generation problem with an extra operation class.

The split case is common in languages that compound: data base should be database, and a term-level corrector sees two valid words and changes nothing. The merge case appears in English with dropped spaces. Both are handled by generating candidates for the concatenation of adjacent term pairs and checking whether the concatenation is in the vocabulary.

Phrase-level correction needs a phrase prior, which is where query logs help: a correction is accepted if the resulting phrase appears in the logs above a count threshold. That is also how the corrector learns that new york is a unit, which is the same information that query segmentation uses for a different purpose.

Presentation versus rewriting

Rewriting silently is the fastest path to a result and the least transparent. The alternative is to return results for the original query and offer the correction, which requires that the original query returns something: if it returns nothing, there is no results page to attach a suggestion to.

The usual compromise is conditional: rewrite automatically when the original returns fewer than a small number of results and the correction’s margin exceeds the threshold; otherwise show results for the original with a suggestion. That keeps rare-but-correct queries intact, because they return results, and rescues typos, because they do not. The threshold on result count is a policy choice that has to be set against the collection’s size, and it interacts with the expansion behaviour described in synonym expansion, since a query that returns nothing may be returning nothing because its terms were never expanded, not because they were misspelled. Running correction before expansion and expansion before the empty-result check is the ordering that avoids confusing the two.