A Simplified Version of Google's Spell Checker

Peter Norvig explains a spell checker in 20 lines of Python that works almost as well as Google’s “did you mean” corrections for one-word errors. It reads a text file, counts word frequencies, generates possible corrections by edit distance, and picks the most frequent candidate.

Reading notes

#

• It uses holmes.txt, a Project Gutenberg collection of Sherlock Holmes stories, as the training text.
• The words are converted to lowercase before counting, so “the” and “The” are treated the same.
• The error model gives edit distance 1 candidates much higher probability than edit distance 2 candidates, and both are less likely than an exact match.
• The post lists the four edit operations: deletion, transposition, alteration, and insertion.
• Norvig’s tests gave correct answers in more than 80% of cases.
• The post notes that Google can improve on this because it has much more data, including web queries and refinements.