5 ms·

How to Write a Spelling Corrector

124 points by dlnovell 17y ago

RiderOfGiraffes 17y ago
Previous discussions: http://news.ycombinator.com/item?id=42587 http://news.ycombinator.com/item?id=42587 http://news.ycombinator.com/item?id=327897 http://news.ycombinator.com/item?id=327897 Many great thoughts and comments already posted, so it's worth reading the thoguhts of HN contributors as well as this classic from Norvig.
- fizx 17y ago
  Google has also released a full-web 5-gram corpus that contains "counts for all 1,176,470,663 five-word sequences that appear at least 40 times" Its fun to try training on that. http://googleresearch.blogspot.com/2006/08/all-our-n-gram-are-belong-to-you.html http://googleresearch.blogspot.com/2006/08/all-our-n-gram-ar...
  - raffi 17y ago
    As the comments (on the google page) illustrate, this corpus is close to useless unless you're a university researcher. Commercial use of this data costs big $$$. And if you're an independent you still have to pay $150 or so to get LDC to mail the six DVDs to you. One of the painful things about commercial NLP work is lack of good datasets without restrictions. There are some treasures like WordNet (which is a lexical db). For tagged data I found the American National Corpus but the excerpt they release without restrictions is too little data and it contains only a few styles of writing. I had to spend a lot of time gathering, fleecing, and marking up my own data to make After the Deadline.
    - lsb 17y ago
      Start with Wikipedia? They've got a few billion words there, and it's a 5GB download.
      - raffi 17y ago
        That is what I ended up doing. Except this is raw data. Usually NLP researchers work from corpora that are already segmented into sentences and tagged with part-of-speech tags. I had to go through the hassle of segmenting and marking up the Wikipedia and Project Gutenberg.
        mattrepl 17y ago
        Would you consider making it available to others? Perhaps the UCI Machine Learning Repository would accept it. If not, I'm sure I could find a way to have it hosted at my university.
        bravura 17y ago
        archive.org will host datasets. To preprocess wikipedia, I have used the following software: http://sourceforge.net/apps/mediawiki/wikiprep/index.php?title=Main_Page http://sourceforge.net/apps/mediawiki/wikiprep/index.php?tit... To remove boilerplate from gutenberg requires painfully constructed heuristics. It would be great to have software released to do that.
      - aquarin 17y ago
        Yes, I done exactly this. it is actually 20GB uncompressed and takes 5-6h to parse. http://appraisalmind.com/articles/wikipedia-word-frequency-list/ http://appraisalmind.com/articles/wikipedia-word-frequency-l...
      - Create 17y ago
        This is why GOOG silently backed Wikipedia: to gain quality content regarding syntax and semantics. Other than give people a "good reason to surf" and hit "ads" [trackers] down the road.
    - abecedarius 17y ago
      It's worse than that: they tack on $30 shipping to mail those 6 DVDs. (When last I looked, anyway.)
- andreyf 17y ago
  I wonder how hard it would be to just merge these discussions together and re-rate them?
Create 17y ago
In case you do - not have the luxury to have such a large ecological footprint (taking into account all the externalities too) - are not always connected and - are not granted access to the full UN corpus etc. then you can still do quite good, cheaper and smarter. http://hunspell.sourceforge.net/ http://hunspell.sourceforge.net/ Hunspell is the default spell checker of OpenOffice.org and Mozilla Firefox 3 & Thunderbird. Gőg hasn't beaten that yet.
- raffi 17y ago
  If we're going to yackety yack about spell checkers, After the Deadline is really accurate because it looks at context and uses trained neural networks to sort recommendations. Hunspell does sophisticated stuff but as Norvig said (somewhere else), the simplest technique with 10x data will beat the most complicated technique every time. Oh and AtD does grammar, style checking, and misused words. Embed it in your application today :) http://www.afterthedeadline.com http://www.afterthedeadline.com
abecedarius 17y ago
Norvig expanded on this theme in a chapter in http://oreilly.com/catalog/9780596157111/ http://oreilly.com/catalog/9780596157111/ (not yet out) -- the draft I read applied the Google n-gram corpus to word segmentation, decryption, and a faster spelling corrector. Lovely and instructive code, as always.
- raffi 17y ago
  That will probably be a really good book. I read Programming Collective Intelligence by Toby Segaran and took a lot from it.
  - abecedarius 17y ago
    Could be! I've only seen the one chapter (because it used a couple suggestions I'd made for the original article linked above).
jcromartie 17y ago
Interesting: a Java implementation of this algorithm is 372 lines, while a Clojure one is 18!
- nikblack 17y ago
  35 lines in Java actually, the other one is a poor implementation. execution speed is more important than lines of code in this case

124 points by dlnovell 17y ago

Previous discussions: http://news.ycombinator.com/item?id=42587 http://news.ycombinator.com/item?id=42587 http://news.ycombinator.com/item?id=327897 http://news.ycombinator.com/item?id=327897 Many great thoughts and comments already posted, so it's worth reading the thoguhts of HN contributors as well as this classic from Norvig.

fizx 17y ago
Google has also released a full-web 5-gram corpus that contains "counts for all 1,176,470,663 five-word sequences that appear at least 40 times" Its fun to try training on that. http://googleresearch.blogspot.com/2006/08/all-our-n-gram-are-belong-to-you.html http://googleresearch.blogspot.com/2006/08/all-our-n-gram-ar...
- raffi 17y ago
  As the comments (on the google page) illustrate, this corpus is close to useless unless you're a university researcher. Commercial use of this data costs big $$$. And if you're an independent you still have to pay $150 or so to get LDC to mail the six DVDs to you. One of the painful things about commercial NLP work is lack of good datasets without restrictions. There are some treasures like WordNet (which is a lexical db). For tagged data I found the American National Corpus but the excerpt they release without restrictions is too little data and it contains only a few styles of writing. I had to spend a lot of time gathering, fleecing, and marking up my own data to make After the Deadline.
  - lsb 17y ago
    Start with Wikipedia? They've got a few billion words there, and it's a 5GB download.
    - raffi 17y ago
      That is what I ended up doing. Except this is raw data. Usually NLP researchers work from corpora that are already segmented into sentences and tagged with part-of-speech tags. I had to go through the hassle of segmenting and marking up the Wikipedia and Project Gutenberg.
      - mattrepl 17y ago
        Would you consider making it available to others? Perhaps the UCI Machine Learning Repository would accept it. If not, I'm sure I could find a way to have it hosted at my university.
        bravura 17y ago
        archive.org will host datasets. To preprocess wikipedia, I have used the following software: http://sourceforge.net/apps/mediawiki/wikiprep/index.php?title=Main_Page http://sourceforge.net/apps/mediawiki/wikiprep/index.php?tit... To remove boilerplate from gutenberg requires painfully constructed heuristics. It would be great to have software released to do that.
    - aquarin 17y ago
      Yes, I done exactly this. it is actually 20GB uncompressed and takes 5-6h to parse. http://appraisalmind.com/articles/wikipedia-word-frequency-list/ http://appraisalmind.com/articles/wikipedia-word-frequency-l...
    - Create 17y ago
      This is why GOOG silently backed Wikipedia: to gain quality content regarding syntax and semantics. Other than give people a "good reason to surf" and hit "ads" [trackers] down the road.
  - abecedarius 17y ago
    It's worse than that: they tack on $30 shipping to mail those 6 DVDs. (When last I looked, anyway.)
andreyf 17y ago
I wonder how hard it would be to just merge these discussions together and re-rate them?

Create 17y ago

In case you do - not have the luxury to have such a large ecological footprint (taking into account all the externalities too) - are not always connected and - are not granted access to the full UN corpus etc. then you can still do quite good, cheaper and smarter. http://hunspell.sourceforge.net/ http://hunspell.sourceforge.net/ Hunspell is the default spell checker of OpenOffice.org and Mozilla Firefox 3 & Thunderbird. Gőg hasn't beaten that yet.

raffi 17y ago
If we're going to yackety yack about spell checkers, After the Deadline is really accurate because it looks at context and uses trained neural networks to sort recommendations. Hunspell does sophisticated stuff but as Norvig said (somewhere else), the simplest technique with 10x data will beat the most complicated technique every time. Oh and AtD does grammar, style checking, and misused words. Embed it in your application today :) http://www.afterthedeadline.com http://www.afterthedeadline.com

abecedarius 17y ago

Norvig expanded on this theme in a chapter in http://oreilly.com/catalog/9780596157111/ http://oreilly.com/catalog/9780596157111/ (not yet out) -- the draft I read applied the Google n-gram corpus to word segmentation, decryption, and a faster spelling corrector. Lovely and instructive code, as always.

raffi 17y ago
That will probably be a really good book. I read Programming Collective Intelligence by Toby Segaran and took a lot from it.
- abecedarius 17y ago
  Could be! I've only seen the one chapter (because it used a couple suggestions I'd made for the original article linked above).

jcromartie 17y ago

Interesting: a Java implementation of this algorithm is 372 lines, while a Clojure one is 18!

nikblack 17y ago
35 lines in Java actually, the other one is a poor implementation. execution speed is more important than lines of code in this case