3 ms·

How to Write a Spelling Corrector (2007)

89 points by graderjs 5y ago

isaacimagine 5y ago
What's cool is that it's now possible to use large language models to predict the probability of a given word, which doesn't only take into account the probability of a word appearing in a corpus, but also the probability in the context of the exact sentence you're writing. This makes the spell checker more robust, and even able to correct small grammatical errors. There's a lot of interesting research on how people tend to misspell words, and even more research on how to correct based on these patterns. Interesting read, this subjet is—on the whole—very fun to dive into.
- Gigachad 5y ago
  This would be a massive improvement. It’s frustrating when an extremely obscure word is the same as a common misspelling but spell check is no use since technically it is a word.
- mromanuk 5y ago
  I would love to do that for an iOS keyboard, without a backend. I've built my own spell corrector going though the rabbit hole of tries and many other structures. iOS keyboards are constrained to 40Mb of RAM, I presume it's still too big to use a language model without a backend. Would be really cool to finally achieve a smarter prediction in-device, though.
samwillis 5y ago
I have been on HN a long time, I remember reading this back in 2008 and learning from it. It’s been posted a lot but that’s an indication of an important educational resource: https://hn.algolia.com/?query=How%20to%20Write%20a%20Spelling%20Corrector&type=story&dateRange=all&sort=byDate&storyText=false&prefix&page=0 https://hn.algolia.com/?query=How%20to%20Write%20a%20Spellin... Amusingly half the comments from the first time it was posted (2007) are about how the post is a dupe… https://news.ycombinator.com/item?id=42587 https://news.ycombinator.com/item?id=42587 Another brilliant one is PGs “a plan for Spam”: http://www.paulgraham.com/spam.html http://www.paulgraham.com/spam.html
deleted 5y ago
[deleted]
melony 5y ago
This is the same generative model used for optimal Wordle prediction.
razhab 5y ago
I'd be really curious to know how long it actually took Norvig to write the spell checker. It seems like such a simple idea and piece of code after you've read it but he suggests it took him a transcontinental flight worth of time. That, to me, is surprising in a potentially interesting way. Knowing that an expert like Norvig might still take hours to write such a seemingly simple program suggests the problem is harder than it appears in retrospect.
- ghusbands 5y ago
  In general, with any project you can find online, you can find people claiming they would have done it faster. It's more tiresome than it is interesting. The program is simple once you know its shape, but there may have been quite some time spent in consideration of how it should work or the details of the edit distance. Also, most programmers overestimate how fast they can write something, and there are plenty of claims that studies show that programmers average only ten lines a day of code. It doesn't mean the problem is necessarily hard or that it needed to be for it to take time. And flights can be tiring and distracting.
ghusbands 5y ago
If you use a trie with suffix-sharing in a suitably dense array, and alter your edit-distance algorithm to use it directly, you can easily get two to three orders of magnitude faster, which could let you use this on a server for many clients. (My old team used that technique, though not in Python, many years ago. In modern times, for web clients, I'd export the work to the browser - a full dictionary in the above form is something maybe 200KB, if I remember correctly.)
noneeeed 5y ago
I find spelling correction systems interesting because I frequently seem to confuse them. There is something about the way I misspell that causes them issues. I am often only two letters out, but I get no suggestions. My misspelling tend to involve flipping vowels, a for o for example. I should start taking notes to see if I can work out a pattern.
- bArray 5y ago
  Better yet, it should learn from your manual corrections and the patterns you commonly mistake. One thing I do that confuses them is putting in extra letters I think should probably be in there. Like 'pherosious' instead of 'ferocious' (Firefox recommends 'heterosporous' - because that's closer!).
- ghusbands 5y ago
  When I worked on a spelling corrector around 2007, it was trivial to get better suggestions than Word and other software. If you have examples, I'd be interested to see how well our spelling corrector does, compared to Aspell and Word and such. Maybe it would be worth finding it and releasing it. The only novel thing our algorithm contained was a trie-traversal algorithm that found all words approximately within a particular edit distance of the source word in one pass. It separately found words with similar sound and scored by a heuristic of both, but that's fairly standard. It was also clear that Google was doing something far more impressive on their servers, as it came up with spelling corrections that others didn't and would even suggest corrections that took into account the rest of the search. It's a shame that they've never (to my knowledge) released that technology for others to use. It's possible, of course, that the underlying text model is too large to easily share.
simulo 5y ago
It is a great piece of code to study as a beginner. It is easy to understand, non-trivial and has an easy-to-relate-to purpose. Norvig's implementation is in python, but he links to variants in many different languages at the bottom of the post.

89 points by graderjs 5y ago

What's cool is that it's now possible to use large language models to predict the probability of a given word, which doesn't only take into account the probability of a word appearing in a corpus, but also the probability in the context of the exact sentence you're writing. This makes the spell checker more robust, and even able to correct small grammatical errors. There's a lot of interesting research on how people tend to misspell words, and even more research on how to correct based on these patterns. Interesting read, this subjet is—on the whole—very fun to dive into.

Gigachad 5y ago
This would be a massive improvement. It’s frustrating when an extremely obscure word is the same as a common misspelling but spell check is no use since technically it is a word.
mromanuk 5y ago
I would love to do that for an iOS keyboard, without a backend. I've built my own spell corrector going though the rabbit hole of tries and many other structures. iOS keyboards are constrained to 40Mb of RAM, I presume it's still too big to use a language model without a backend. Would be really cool to finally achieve a smarter prediction in-device, though.

samwillis 5y ago

I have been on HN a long time, I remember reading this back in 2008 and learning from it. It’s been posted a lot but that’s an indication of an important educational resource: https://hn.algolia.com/?query=How%20to%20Write%20a%20Spelling%20Corrector&type=story&dateRange=all&sort=byDate&storyText=false&prefix&page=0 https://hn.algolia.com/?query=How%20to%20Write%20a%20Spellin... Amusingly half the comments from the first time it was posted (2007) are about how the post is a dupe… https://news.ycombinator.com/item?id=42587 https://news.ycombinator.com/item?id=42587 Another brilliant one is PGs “a plan for Spam”: http://www.paulgraham.com/spam.html http://www.paulgraham.com/spam.html

deleted 5y ago

[deleted]

melony 5y ago

This is the same generative model used for optimal Wordle prediction.

razhab 5y ago

I'd be really curious to know how long it actually took Norvig to write the spell checker. It seems like such a simple idea and piece of code after you've read it but he suggests it took him a transcontinental flight worth of time. That, to me, is surprising in a potentially interesting way. Knowing that an expert like Norvig might still take hours to write such a seemingly simple program suggests the problem is harder than it appears in retrospect.

ghusbands 5y ago
In general, with any project you can find online, you can find people claiming they would have done it faster. It's more tiresome than it is interesting. The program is simple once you know its shape, but there may have been quite some time spent in consideration of how it should work or the details of the edit distance. Also, most programmers overestimate how fast they can write something, and there are plenty of claims that studies show that programmers average only ten lines a day of code. It doesn't mean the problem is necessarily hard or that it needed to be for it to take time. And flights can be tiring and distracting.

ghusbands 5y ago

If you use a trie with suffix-sharing in a suitably dense array, and alter your edit-distance algorithm to use it directly, you can easily get two to three orders of magnitude faster, which could let you use this on a server for many clients. (My old team used that technique, though not in Python, many years ago. In modern times, for web clients, I'd export the work to the browser - a full dictionary in the above form is something maybe 200KB, if I remember correctly.)

noneeeed 5y ago

I find spelling correction systems interesting because I frequently seem to confuse them. There is something about the way I misspell that causes them issues. I am often only two letters out, but I get no suggestions. My misspelling tend to involve flipping vowels, a for o for example. I should start taking notes to see if I can work out a pattern.

bArray 5y ago
Better yet, it should learn from your manual corrections and the patterns you commonly mistake. One thing I do that confuses them is putting in extra letters I think should probably be in there. Like 'pherosious' instead of 'ferocious' (Firefox recommends 'heterosporous' - because that's closer!).
ghusbands 5y ago
When I worked on a spelling corrector around 2007, it was trivial to get better suggestions than Word and other software. If you have examples, I'd be interested to see how well our spelling corrector does, compared to Aspell and Word and such. Maybe it would be worth finding it and releasing it. The only novel thing our algorithm contained was a trie-traversal algorithm that found all words approximately within a particular edit distance of the source word in one pass. It separately found words with similar sound and scored by a heuristic of both, but that's fairly standard. It was also clear that Google was doing something far more impressive on their servers, as it came up with spelling corrections that others didn't and would even suggest corrections that took into account the rest of the search. It's a shame that they've never (to my knowledge) released that technology for others to use. It's possible, of course, that the underlying text model is too large to easily share.

simulo 5y ago

It is a great piece of code to study as a beginner. It is easy to understand, non-trivial and has an easy-to-relate-to purpose. Norvig's implementation is in python, but he links to variants in many different languages at the bottom of the post.