The author makes a factual error regarding Norvig's version. He writes: > Peter Norvig approaches the problem using a different way of thinking. He first store

The author makes a factual error regarding Norvig's version. He writes: > Peter Norvig approaches the problem using a different way of thinking. He first stores his dictionary in a hash-table for fast lookup. Then he goes through hundreds, or even thousands of combinations of spelling mutations of the target word and checks if each one is in the dictionary. This system is clever, but breaks down quickly if you want to find words with an error greater than 1. Norvig writes [1]: > The literature on spelling correction claims that 80 to 95% of spelling errors are an edit distance of 1 from the target. As we shall see shortly, I put together a development corpus of 270 spelling errors, and found that only 76% of them have edit distance 1. Perhaps the examples I found are harder than typical errors. Anyway, I thought this was not good enough, so we'll need to consider edit distance 2. That's easy: just apply edits1 to all the results of edits1: I wrote some code for this a few months ago and tried tries, which ultimately rejected in favor of a fast Levenshtein implementation. On a side note the author misses one other possible avenue, which is a family of algorithms using bit Vector operations [2] [3] to measure edit distance. Anyway IIRC my code went the opposite way. It traversed the word then looked in the trie for matches. This quickly broke down as edit distance increased and I suspect this is what the author is observing in the other implementation. The author's approach of going the other way is uninteresting idea and I might retrofit that to my code to see how it performs. [1]: http://norvig.com/spell-correct.html http://norvig.com/spell-correct.html [2]: http://portal.acm.org/citation.cfm?id=846095 http://portal.acm.org/citation.cfm?id=846095 [3]: http://www.odinlake.net/papers/onsjo-cudastrmatch-sigal09.pdf http://www.odinlake.net/papers/onsjo-cudastrmatch-sigal09.pd...