Spelling Correction and Phonetic Matching

A user types retreival. The dictionary of the index contains retrieval but not retreival, so an exact lookup returns nothing. The two strings differ by two swapped letters. Measured by the standard edit distance, they are two operations apart, or one if swapping two adjacent letters counts as a single operation. Deciding that the user meant retrieval, quickly and without proposing retrial or reversal, is the problem of spelling correction. A related problem arises with names: Muller and Mueller, or Chebyshev and Tchebycheff, are the same name spelled differently, and matching them requires knowing how they sound rather than how they are written.

These techniques belong with text processing because they extend normalization to cases rules cannot anticipate. They usually operate at query time, comparing query terms with the index's dictionary rather than changing the index. This article follows Manning, Raghavan, and Schütze (2008, §§3.3–3.4).

Two principles

Correction rests on two principles:

1. Prefer the nearest alternative. Among dictionary terms, choose those closest to what was typed, by some measure of distance between strings.
2. Among equally near alternatives, prefer the more common one. If board and bored are both one edit from bord, choose the one that occurs more often, in the collection or in the query log, which reflects what people actually search for but can underrepresent rare and specialized terms.

These principles give a strict order, distance first and frequency second. The noisy channel model described below combines the two into one probability, so a slightly farther but much more likely word can win. A system can also correct a term even when it is in the dictionary, since a valid word can still be the wrong one, as discussed under context-sensitive correction below.

Edit distance

The edit distance, or Levenshtein distance (Levenshtein, 1966), between two strings is the minimum number of single-character insertions, deletions, and substitutions that transform one into the other. Cat and cut are at distance 1 (one substitution). Kitten and sitting are at distance 3: substitute s for k, substitute i for e, and insert g.

The distance is computed by dynamic programming. Let $D[i][j]$ be the distance between the first $i$ characters of string $a$ and the first $j$ characters of string $b$. Then $D[i][0] = i$, $D[0][j] = j$, and

$$D[i][j] = \min \begin{cases} D[i-1][j] + 1 & \text{(delete } a_i\text{)} \\ D[i][j-1] + 1 & \text{(insert } b_j\text{)} \\ D[i-1][j-1] + [a_i \ne b_j] & \text{(substitute, free if equal)} \end{cases}$$

where $[a_i \ne b_j]$ is 1 if the characters differ and 0 if they are equal.

The recurrence follows from asking what the last operation of a cheapest edit sequence could be. Consider turning $a_1 \dots a_i$ into $b_1 \dots b_j$, and look at the final characters $a_i$ and $b_j$. Either $a_i$ was deleted, in which case the rest of the work turned $a_1 \dots a_{i-1}$ into all of $b_1 \dots b_j$, at best $D[i-1][j]$, plus one for the deletion. Or $b_j$ was inserted at the end, leaving $a_1 \dots a_i$ to become $b_1 \dots b_{j-1}$, at best $D[i][j-1]$, plus one. Or neither, in which case $a_i$ ended up as $b_j$, either unchanged, for free, or by one substitution, and the prefixes were matched at best for $D[i-1][j-1]$. Those cases cover every possibility, so the cheapest of the three is the distance. The first row and column are the cases where one prefix is empty: turning $i$ characters into nothing takes $i$ deletions. Each cell depends only on the cells above, to the left, and diagonally above-left, so filling the table row by row, left to right, always has the needed values ready.

For kitten and sitting:

The bottom-right cell gives the distance, 3. The computation fills a table of $(|a|+1)(|b|+1)$ cells, so it takes time proportional to the product of the lengths.

Take one cell to see the rule at work. The cell for kitte against sitti (row e, column for the second i) holds 2. Its three neighbours are 2 above (kitt against sitti), 2 to the left (kitte against sitt), and 1 diagonally (kitt against sitt). Since e and i differ, the candidates are $2 + 1$, $2 + 1$, and $1 + 1$, and the minimum is 2.

The table also records how to achieve the distance. Starting at the bottom-right cell and repeatedly stepping back to a neighbour that produced its value recovers an optimal sequence of edits, a backtrace. For kitten, the path runs along the diagonal from the top-left corner to row n, column n, and then one step right. Along the diagonal the value increases twice, at k against s and at e against i, which are the two substitutions. The final rightward step from 2 to 3 is the insertion of g. Spelling correction usually needs only the distance, but the alignment explains to a reader, or to a weighted error model, which edits were made.

The figure below shows the tables for the opening example. With Levenshtein distance, the swapped e and i of retreival cost two substitutions. With transpositions allowed, as described next, the same swap costs one.

Two refinements are common. Damerau–Levenshtein distance also counts the transposition of two adjacent characters as a single operation (Damerau, 1964), since swapped letters are among the most common typing errors. Under it, retreival is at distance 1 from retrieval rather than 2. The restricted version described below needs one more case in the recurrence: when $a_{i-1} a_i = b_j b_{j-1}$, the two characters swapped, $D[i][j]$ may also be $D[i-2][j-2] + 1$. In the right-hand table above, that case applies at row i, column e: ei in the typed string is ie reversed, so the cell takes $D[4][4] + 1 = 0 + 1 = 1$ instead of the 2 that substitutions give. Two versions are in use. The restricted version, also called optimal string alignment, never edits a substring more than once and can give a larger distance than the unrestricted one: ca and abc are at distance 3 under the restricted version and 2 under the unrestricted one. Weighted edit distance assigns different costs to different operations. Substituting a letter with one next to it on the keyboard, such as m for n, can cost less than substituting a distant one, so that the measure reflects which errors people actually make.

Finding candidates with a k-gram index

Computing the edit distance from a query term to every term in a dictionary of millions is too slow. The usual solution is a cheap filter that finds a small set of plausible candidates first.

A k-gram index maps each sequence of $k$ characters to the dictionary terms that contain it. With $k = 2$ and $ marking the start and end of a word, the term board contains the bigrams $b, bo, oa, ar, rd, and d$. To correct bord, take its bigrams, $b, bo, or, rd, and d$, retrieve the terms that share many of them, and measure the overlap with the Jaccard coefficient, the size of the intersection divided by the size of the union:

Terms above a threshold, say 0.4, are kept. Only they are compared by edit distance: board, bored, and lord are at distance 1 from bord, and border is at distance 2. The remaining tie among board, bored, and lord is broken by frequency, following the second principle. The threshold is a heuristic, not a guarantee: a correct term that shares few k-grams with the typo, as often happens with short words, falls below it and is never considered. The k-gram index is built once, from the dictionary, and it is small, because it indexes terms rather than documents. The same structure also supports wildcard queries such as bo*d. Intersecting the postings of the k-grams the pattern requires, here $b, bo, and d$, yields candidates such as board, bold, and bored. The candidates must then be checked against the pattern itself, since a term can contain all the required k-grams without matching it. Billboard begins with b, contains bo, and ends with d, so it has all three k-grams, but it does not begin with bo (Manning, Raghavan, and Schütze, 2008, §3.2).

On a real dictionary

The table above uses a handful of hand-picked words. A real dictionary is less tidy. The vocabulary of Reuters-21578 (Lewis, 1997), 29,187 terms from 10,788 news stories, lowercased and split into runs of letters as in term statistics, gives a bigram index in which 6,031 terms share at least one bigram with bord. Of those, 33 have a Jaccard coefficient of at least 0.4. The highest-scoring ones:

Two of the three best candidates, borad and baord, are themselves typing errors that occur once each in the newswire, and ord, brd, and bor are fragments and abbreviations. All five tie with board on distance. Only frequency, the second principle, separates them, and it does so decisively: board occurs 1,159 times, these five rivals at most 17 times each. Any dictionary built from real text contains its own misspellings, as the long tail of hapax legomena showed, which is why frequency, not mere membership in the dictionary, is the evidence that a word is correct.

The filter can also fail. The transposition exprot shares only the bigrams $e, ex, xp, and t$ with export, a Jaccard coefficient of exactly 0.4, because swapping two letters breaks three bigrams at once. With a slightly stricter threshold, export, which occurs 1,067 times in the collection, would never reach the edit-distance stage. Short words and transposed letters are where k-gram filters most often lose the right answer.

Context-sensitive correction

Isolated-term correction cannot fix an error that produces a real word. In flew form Heathrow, every word is correctly spelled, and the error is that form should be from (Manning, Raghavan, and Schütze, 2008, §3.3.5). Correcting it requires context: among the variants of each query word, find the combination that is most common as a phrase in the collection or the query log. Flew from Heathrow is far more frequent than flew form Heathrow.

The noisy channel model gives this reasoning a probabilistic form. Kernighan, Church, and Gale (1990) applied it to isolated misspelled words; with a language model over phrases rather than single words, the same formula takes context into account. Treat the typed query $q$ as the output of a noisy channel applied to an intended query $w$, and choose the $w$ that maximizes

$$P(w \mid q) \propto P(q \mid w)\, P(w),$$

where $P(w)$, the language model, measures how likely the intended query is, estimated from query logs or text, and $P(q \mid w)$, the error model, measures how likely the typed string is as a corruption of the intended one, estimated from observed pairs of errors and corrections. Brill and Moore (2000) improved the error model by allowing edits of multi-character substrings, such as ph typed as f. Web search engines can estimate both models from their query logs, as the web search article describes, which lets them correct names and new terms that no fixed dictionary contains, once enough users have searched for them.

A worked noisy-channel example

The formula's behaviour is easiest to see with deliberately simple models. For the language model, take each word's share of the Reuters-21578 text, $P(w) = \mathit{cf}_w / T$. For the error model, assume that each edit happens independently with a small probability $\varepsilon$, so that $P(q \mid w) = \varepsilon^{d(q, w)}$, where $d$ is the edit distance, and an intended word is typed correctly, $d = 0$, with probability about 1. Real error models are learned and give different edits different probabilities. This one has a single parameter, the typist's error rate.

The query goverment makes a good test, because the misspelling occurs 8 times in the collection and so is in the dictionary. Its main rival is government, with 1,730 occurrences, one edit away. The posterior odds between them are

$$\frac{P(\textit{government} \mid q)}{P(\textit{goverment} \mid q)} = \frac{\varepsilon^{1} \times 1730}{\varepsilon^{0} \times 8} = 216.25\,\varepsilon.$$

The correction wins when this exceeds 1, that is, when $\varepsilon > 1/216.25 \approx 0.0046$. Normalizing over all the dictionary terms within two edits of the query:

(Probabilities rounded to three decimals; other candidates share the remaining 0.001 or less.) The same typed string is corrected under one assumption about how often people mistype and left alone under the other. That is the trade-off the two principles at the start of the article expressed as a strict order, and the noisy channel turns it into a threshold that can be estimated from data, by measuring how often real users mistype.

Phonetic matching and Soundex

Names are often misspelled in ways that preserve their sound: Smith and Smyth, Herman and Hermann. Phonetic algorithms map strings to codes intended to give names that sound alike the same code. The match is approximate: similar-sounding names can receive different codes, and different names can share one. The oldest is Soundex, patented by Robert Russell in 1918 and used for decades to index United States census records. The common American version works as follows:

1. Keep the first letter.
2. Replace the remaining letters with digits: b, f, p, v → 1; c, g, j, k, q, s, x, z → 2; d, t → 3; l → 4; m, n → 5; r → 6. Vowels, h, w, and y get no digit.
3. Merge adjacent letters with the same digit into one, including when they are separated only by h or w. A vowel between them keeps them separate. A letter with the same digit as the first letter is also merged into it.
4. Keep the first letter and the first three digits, padding with zeros if necessary.

Some results, computed with this procedure:

The failures show the algorithm's assumptions. Soundex keeps the first letter, so variants that differ in their first letter, such as Chebyshev and Tchebycheff, can never match. It also knows nothing about silent letters, so the gh in Leigh separates it from Lee. More elaborate algorithms such as Metaphone apply many more pronunciation rules. Zobel and Dart (1996), comparing methods for matching personal names, found that on their data phonetic codes alone performed worse than string-distance measures, and proposed a measure combining the two. For retrieval, phonetic matching is mainly useful as an additional source of candidates for name searches, not as a replacement for edit distance.

Where correction fits

Spelling correction usually runs on queries, leaving the index unchanged: query terms not found in the dictionary, or found only rarely, are checked for close alternatives. How the result is presented is a separate decision. The system can suggest a correction, rerun the query with it and say so, or apply it silently, as described in the web search article. Correction is applied to documents mainly when they contain systematic errors, such as text produced by optical character recognition, where the same confusions, such as rn read as m, recur throughout a collection.

References

• Brill, E., and Moore, R. C. (2000). An improved error model for noisy channel spelling correction. In Proceedings of ACL 2000, 286–293.
• Damerau, F. J. (1964). A technique for computer detection and correction of spelling errors. Communications of the ACM, 7(3), 171–176.
• Kernighan, M. D., Church, K. W., and Gale, W. A. (1990). A spelling correction program based on a noisy channel model. In Proceedings of COLING 1990, 205–210.
• Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 10(8), 707–710.
• Lewis, D. D. (1997). Reuters-21578 text categorization test collection, distribution 1.0.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, sections 3.2–3.4. Cambridge University Press.
• Russell, R. C. (1918). U.S. Patent 1,261,167. Index.
• Zobel, J., and Dart, P. (1996). Phonetic string matching: Lessons from information retrieval. In Proceedings of SIGIR 1996, 166–172.