How to Write a Spelling Corrector (2007)

http://norvig.com/spell-correct.html

by hashx • 12 years ago

78 19 12 years ago

norvig.com

init0• 12 years ago

awk needed just 15 lines, where as java needed 372!

jonas212• 12 years ago

Well... to be fair, there's also a 35-line Java version there.

dllthomas• 12 years ago

awk is for messing with text, of course it's going to be terser.

pwf2• 12 years ago

Is there a bug in the train function? Using 'lambda: 1' for the default dict along with '+=' means that the first time a feature is encountered, the value is set to 2.

  In [1]: from collections import defaultdict

  In [2]: d = defaultdict(lambda: 1)

  In [3]: d['foo'] += 1

  In [4]: d['foo']
  Out[4]: 2

jonas212• 12 years ago

I think the code is correct. To implement smoothing, you want to add 1 to the count of every word, regardless of whether it appears in the training data or not.

That is to say, a word that appears once should get a count of 2, and word that doesn't appear at all should get a count of 1.

pwf2• 12 years ago

That makes sense, thanks!

I should learn to read...

gabemart• 12 years ago

Google cached version: http://webcache.googleusercontent.com/search?q=cache%3Ahttp%...

coldcode• 12 years ago

Argh, another blog where there are no posting dates. Is it that hard to tell people when your post was written? The post starts off with "In the past week..." but we have no idea if this was written 10 years ago or recently. It may be interesting content but without a context it's confusing to know if this is new or old.

mrcactu5• 12 years ago

I remember the spell-checker being harder than it looks. You have to train a Naive Bayes classifier to "recognize" misspelled words.

I can't access the link right now... OK: http://web.archive.org/web/20140217174744/http://norvig.com/...

StefanKarpinski2• 12 years ago

When I found myself writing a spell corrector for Etsy's search a couple years ago, I thought "yawn, solved problem". As it turns out, it's not as solved as this blog post makes it seem. The basics are correct: you need a language model and an error model. The problem is that both approaches to that presented are pretty naïve. Indeed, the resulting accuracy of 67% is completely unacceptable for an real spell corrector – an earlier version of this blog post had an evaluation bug that made it seem that the accuracy was much higher – over 90% if I recall correctly.

What's wrong with the language model? Counting occurrences in corpuses of text is not really good enough. There are very rare words that are nevertheless real words, and there are misspellings of common words (even in books) that are far more common than many actual words. You can easily find yourself in a situation where a correctly spelled rare word is corrected to a common misspelling of some other, much more common word.

What's wrong with the error model? Edit distance just isn't a very good error model. There are many common misspellings that aren't very close via additions or deletions. There are also one letter edits that completely change the meaning of something. These should be treated as a much bigger errors than modifications that have no effect on meaning.

For special contexts like Etsy where words like "jewelry" (also correctly spelled as "jewellery" in the UK), Swarovski, and "ACEO" are extremely common, you really need a custom language model. I just wanted to put this out there lest people be under the misapprehension that spell correction is quite as easy as this blog post makes it out to be.

abecedarius• 12 years ago

http://norvig.com/ngrams/ has a fancier spell-corrector and some more discussion.

abhgh• 12 years ago

If you are doing a production grade spellchecker (or for that matter, anything ML) I would suggest that you spend some time getting familiar with the literature survey (Google Scholar is your friend). I have done various implementations over time (and also, as it happens, specifically a spellchecker, but that was not meant to be production grade), and I find this to be the most rewarding way in the long run.

StefanKarpinski2• 12 years ago

Yes, reading the literature is often helpful.

ColinWright• 12 years ago

Readers might be interesting in seeing comments from other HN readers from previous discussions:

https://news.ycombinator.com/item?id=10967

https://news.ycombinator.com/item?id=42587

https://news.ycombinator.com/item?id=665544

https://news.ycombinator.com/item?id=2034981

There are more ...

========

Other submissions without comment:

https://news.ycombinator.com/item?id=1225574

https://news.ycombinator.com/item?id=2036600

https://news.ycombinator.com/item?id=4609321

msoad• 12 years ago

The easiest way to suggest correction is to have a list of correct words and compare it with Levenshtein distance[1].

To do it really good, you have to look for context (previous words) and add learning behavior. This is done nicely in Swiftkey keyboard for android.

The next step is looking at characters close to mistyped character in keyboard layout. This is also done in Swiftkey.

[1]http://en.wikipedia.org/wiki/Levenshtein_distance

How to Write a Spelling Corrector (2007)

Related Stories