Norvig Spellchecker
Explore the Norvig spellchecker algorithm to understand how it uses candidate selection, language, and error probability models for spelling correction. Learn the mathematical foundation including Bayes' theorem and implement a basic spellchecker with over 75% accuracy.
We'll cover the following...
Overview
The Norvig spellchecker is a spelling correction algorithm created by Peter Norvig, a computer scientist and AI researcher at the Stanford Institute for Human-centered AI. His justification behind creating his spellchecker was to create a simple and expandable way to teach his colleagues how spelling correctors like Google work. This example is not meant to be as accurate as a modern method but attains a respectable accuracy of >75%.
The spellchecker uses probability theory to determine which word to suggest as a correction. It selects the candidate that maximizes the conditional probability , where is the original word. Mathematically we can write it as follows:
...