How spell checkers work: dictionaries, edit distance and suggestions
Every spell checker does two separate jobs: detection (is this word wrong?) and correction (what was meant?). The first is mostly a data problem, the second mostly a search problem.
A very short history
Spell checking is one of the oldest text-processing tasks in computing. Fred Damerau's 1964 paper in Communications of the ACM already described automatic detection and correction based on the observation that most errors are a single insertion, deletion, substitution or transposition. Vladimir Levenshtein's 1965 paper (published in English in 1966) defined the edit distance that still bears his name. Ralph Gorin's SPELL, written at Stanford in 1971 for the PDP-10, is often cited as the first spell checker for general English text. The Unix spell command followed in the 1970s, and since the 1990s the open-source lineage of Ispell, Aspell and Hunspell has supplied the checkers inside many browsers, office suites and operating systems. Hunspell, for example, is used by LibreOffice and Firefox.
Detection: the word list
The simplest detector is a set of known words. If a token is not in the set, it is flagged. Everything then depends on the list:
- Too small, and correct but uncommon words are flagged constantly, which teaches users to ignore the underlines.
- Too large, and rare words hide common typos. A list that contains calender (a pressing machine) will never warn you about a misspelled calendar.
That is why curated, graded lists exist. SCOWL splits English into size levels so that each project can choose its own balance; its author recommends the "60" level for spell checking and warns against the largest ones. The Letterbench checker uses levels up to 50, about 72,000 entries.
Storing every inflected form is simple but wasteful for languages with rich morphology. Hunspell instead uses two files: a .dic file of stems, each tagged with flags, and an .aff file of affix rules that say which prefixes and suffixes each flag allows and how the stem changes. A single entry such as walk/DGS can stand for walk, walked, walking, walks. For English this mainly saves space; for Hungarian, Finnish or Turkish, where one stem can have hundreds of forms, it is what makes a checker possible at all. The hunspell(5) manual page documents the format.
Correction: generating candidates
Once a word is flagged, the checker needs plausible replacements. Three families of method dominate.
1. Edit distance
The edit distance between two strings is the minimum number of single-character operations needed to turn one into the other. With Levenshtein's definition the operations are insertion, deletion and substitution; the Damerau–Levenshtein variant adds transposition of two adjacent characters, which matters because swapped letters (teh, recieve) are among the commonest typing errors. Our step-by-step implementation in JavaScript shows both.
There are two ways to use it. You can compare the bad word against every dictionary word and keep the closest, which is simple but slow for large lists. Or you can generate every string within distance 1 or 2 of the bad word and keep those that are in the dictionary. Peter Norvig's essay How to Write a Spelling Corrector popularized the second approach with a famously short Python program, and it is what the Letterbench checker does in JavaScript. For a word of length n over an alphabet of 26 letters there are 54n+25 strings at distance 1, so distance 2 runs to tens or hundreds of thousands of lookups: fine for one word on demand, too slow for checking a whole book interactively.
2. Symmetric delete
Wolf Garbe's SymSpell algorithm makes the generate approach much faster by using only deletions. In advance, it stores every dictionary word together with all the strings obtained by deleting up to k of its characters. At lookup time it generates only the deletions of the misspelled word, which is a far smaller set than all edits, and matches them against the precomputed table. Insertions, substitutions and transpositions are all covered, because they correspond to deletions on one side or both. The cost is memory: the precomputed table is many times larger than the word list. The algorithm and benchmarks are described in the SymSpell repository.
3. Sound-alike keys
Typing errors are near-misses on the keyboard; spelling errors by people who do not know a word are near-misses in sound: fone, nolij, sircumstance. These can be several edits away from the target. Phonetic algorithms reduce each word to a key that approximates its pronunciation, so that words that sound alike share a key. Soundex, patented in 1918 and used for the US census, is the classic; Lawrence Philips's Metaphone (1990) and Double Metaphone (2000) handle English spelling far better. GNU Aspell combines edit distance with a sounds-like comparison, which is why it is good at phonetic misspellings.
Ranking: which candidate first?
Generating candidates is the easy half. For acress, the candidates actress, across, acres, access, caress are all one edit away. Which did the writer mean? A principled answer comes from the noisy channel model, applied to spelling correction by researchers at AT&T Bell Labs around 1990: choose the candidate c that maximizes P(c) × P(typed word | c), where P(c) is how common the word is (the language model) and P(typed | c) is how likely that particular error is (the error model). Real systems estimate both from large corpora and from logs of actual corrections; a substitution of neighbouring keys such as s for a, for example, is far more likely than one between distant keys.
Simple checkers approximate this with rules. Letterbench sorts by edit distance, then by SCOWL frequency level, then by whether the first letter matches; others add keyboard adjacency or phonetic similarity. Good ranking matters more than people expect: users usually click the first suggestion.
Context: the next level
Everything above looks at words one at a time, so it cannot catch real-word errors such as their for there or form for from (see homophones spell checkers miss). Detecting those requires looking at the surrounding words. Early approaches used confusion sets (lists of commonly confused words) with n-gram statistics: if over there is far more frequent than over their, flag the latter. Modern grammar checkers and word processors increasingly use neural language models trained on very large corpora, which handle context much better, at the cost of size and, often, sending text to a server for processing.
Practical design choices
- Where it runs. A browser-side checker keeps text private and works offline; a server-side one can use huge models. Browsers' built-in checkers are local by default, but some offer optional cloud-enhanced modes.
- Tokenizing. Decide what a word is: apostrophes, hyphens, accented letters, numbers, URLs and code identifiers all need explicit rules.
- Case. Store names with capitals and accept lower-case words in capitalized or all-caps form, not the other way round.
- User dictionary. Every checker needs an "add word" function; nobody's vocabulary matches a general list.
For a concrete example of all these choices in under two hundred lines of code, see the Letterbench spell checker documentation.