How to Write a Spelling Corrector

I couldn't help but read this and think about all the "coding" initiatives I've seen in K-12 and shake my head. What Norvig is doing is what we should be teaching. He is tackling this seemingly REALLY hard problem by thinking about it methodically, translating some intuition into code, carefully constructing an argument about how to solve it, and ways that it could be extended. This is what actual engineers look like. Everything I've seen around "coding" though has become…

I know a spelling corrector is not the same thing as a spelling checker, but this is too good an opportunity to pass to promote Martha Snow's hilarious poem 'Spell Chequer': Eye halve a spelling chequer It came with my pea sea It plainly marques four my revue Miss steaks eye kin knot sea. Eye strike a quay and type a word And weight four it two say Weather eye am wrong oar write It shows me strait a weigh…

Interesting that the shortest (and among the most readable) is the 15-line version written in old-school AWK: http://pacman.blog.br/wiki/index.php?title=Um_Corretor_Ortog... A surprise is that the Perl implementation weighs in at 63 lines. I would have expected much less. I expect a much shorter version is possible, relying on idiomatic constructs at the expense of readability.

This is posted here about every three months. Norvig's approach assumes a very small fixed vocabulary (so it won't scale well to the basic multilingual plane), and can only recover errors with an edit distance of two or less. If you are interested in a vastly superior yet still very intuitive approach to spelling correction, I recommend the classic paper on noisy channel model corrector by Kernighan, Church, and Gale, which fuses the probability distribution the distribution over possible errors…