A spelling corrector in a few lines of Python
Summary
Peter Norvig builds a small probabilistic spelling corrector and uses it to explain the language model, error model, candidate search and honest evaluation. The corpus contains 1,115,504 words and 32,192 distinct entries. The development set reached 75 percent correct results.
Ideas
- A word frequency model estimates the probability of possible corrections.
- Deletion, transposition, replacement and insertion generate candidates at edit distance one.
- Only known words limit the very large set of candidates.
- Bayes conceptually separates word probability from typo probability.
- A separate test set prevents unconscious tuning to development examples.
- Context from neighbouring words resolves ambiguities of individual words.
Insights
- Small models explain complex systems better than opaque production implementations.
- Explicit simplifications show both how a model works and where its limits are.
- More training data only helps if the model and error assumptions fit.
- Evaluation turns a convincing demonstration into a verifiable claim.
Facts
- The separate test set reached 68 percent correct results.
- A word with eight letters generates 442 candidates with one edit step.
Recommendations
- Keep training, development and test data strictly separate.
- Start with an explainable model and document every simplification.
- Profile first before optimising the implementation for speed.
References
Links to the original source and the Web Archive open in a new tab.