6 ms·

How to Write a Spelling Corrector (2007)

76 points by fybs 5y ago

killingtime74 5y ago
Those interested in toy implementations in this area might also enjoy this blog https://blog.burntsushi.net/transducers/ https://blog.burntsushi.net/transducers/ on FSMs. Also the NLP Book on the data side https://web.stanford.edu/~jurafsky/slp3/ https://web.stanford.edu/~jurafsky/slp3/
Joker_vD 5y ago
And after you've read that, here's a related blogpost: "A Spellchecker Used to Be a Major Feat of Software Engineering" [0], because Python being "fast enough" and having enough memory for large dictionaries hasn't always been the case. [0] https://prog21.dadgum.com/29.html https://prog21.dadgum.com/29.html
- tgv 5y ago
  I'll repeat my feat in this area: a spelling corrector that had 32kB memory (because it was tied to a keyboard trap, or something like that) and could do four 8kB reads from CD-ROM before telling the user. It contained not only orthographic similarity (the actual letters), but also phonetic similarity. You rarely see that in older English spell checkers, because it's such an irregular language, but for other languages it's quite informative, although in extremely regular languages, such as Spanish, you could also put it in the weighting/probability model (e.g. v<->b is a pretty common confusion). The CD-ROM spelling corrector was not really great, BTW, but at least it replied in 1s on a typical end-user PC. Edit: this was late 1980s.
pandatigox 5y ago
I've had a thought and am curious how people would solve it. Sometimes, if you copy words off a PDF lecture slide, all the words are mashed together (eg. Hello Foo bar → HelloFoobar). Is this an AI domain or can it solved by simple programming?
- eutectic 5y ago
  I would try an n-gram model with dynamic programming. e.g. logp(_, "") = 0 logp(word0, text) = max(logp_bigram(word0, word1) + logp(word1, rest) for word1, rest in prefix_words(text))
- gattilorenz 5y ago
  "AI" and "simple programming" are not mutually exclusive :) look at the Speech and Language processing book, particularly chapter 3 about language models https://web.stanford.edu/~jurafsky/slp3/ https://web.stanford.edu/~jurafsky/slp3/ You can implement a language model based on character n-grams to calculate whether a sequence is more likely with or without a space. Of course you would need a way of estimating the proability of each sequence, which means you need a corpus to train your language model on.
- wodenokoto 5y ago
  This is a common problem in Japanese NLP, and while state of the art is using deep learning, almost everyone use dynamic programming or conditional random fields together with a dictionary to solve it. There also exists research on solving this problem unsupervised which basically invents new word boundaries for a language (remember that spoken languages doesn’t have word boundaries - it was invented for writing and strictly speaking, current spelling isn’t the only way to solve word boundaries for a given language)
- tester34 5y ago
  Have you tried using an ~~XML~~ PDF parser instead? /s and tried to find which sentence without spaces matches your sentence
- ghusbands 5y ago
  It's worth noting that different PDF-to-text tools (and different PDF-display tools that have text-copying) get different results and it can be worth trying a few. For the most part, the vector parts of a PDF and the association with the text is sufficient to discover spacing information.
- deleted 5y ago
  [deleted]
graycat 5y ago
My favorite, long standard spell checker is Aspell long part of a TeX distribution.
the-smug-one 5y ago
Could use a Hidden Markov Model, how to implement: https://www.cs.sjsu.edu/~stamp/RUA/HMM.pdf https://www.cs.sjsu.edu/~stamp/RUA/HMM.pdf Here's an impl of some kind: https://github.com/crisbal/hmm-spellcheck https://github.com/crisbal/hmm-spellcheck
da39a3ee 5y ago
From a pedagogical point of view presenting that as a Bayesian model and then using the error model he does, is a bit questionable. But as always his python style is inspiring.
eigenhombre 5y ago
One of the more interesting parts of the post, for me, is the list of implementations in other languages, including: one for Clojure written by that language's author, Rich Hickey; an interesting one in R that clocks in at 2 lines (with a longer, more readable version further down in the linked post); and one written in functional Java. The first one in Awk is also interesting.
mtreis86 5y ago
One of my most common spelling mistakes is physical mistypes on the keyboard, yet no spell checker seems to account for keyboard layout and locality of keys, or for something like my hand being one position off on the board but typing all the keys relatively correct only positionally shifted.
- brian_cloutier 5y ago
  spell checkers which account for keyboard layout absolutely exist. [1] is one example, but in general it's hard to believe that any trained model would fail to notice that certain mistakes are more likely than others, and it's hard to believe that any spell checker google releases these days would not be based on a trained model. [1] https://ai.googleblog.com/2017/05/the-machine-intelligence-behind-gboard.html https://ai.googleblog.com/2017/05/the-machine-intelligence-b...
- m463 5y ago
  I think the problem is that there are multiple layers of correction - both the physical and the spelling/semantic. On ios I just had to turn off autocorrect, because I had reminders I jotted down quickly which missed the physical correction and were irretrievably corrected semantically into garbage. now I find a note with "spekk" and I can figure out I meant "spell" (need a better example)
- tyingq 5y ago
  I would guess that the iPhone autocorrect does this implicitly since it's ML trained.
- z3t4 5y ago
  The problem is that if you take an english word and change one letter it will likely become another valid word.
- wootest 5y ago
  Many designs does this implicitly. At least one, the original iPhone keyboard autocomplete/suggestion algorithm, did it explicitly. Ken Kocienda's book Creative Selection has a very good chapter on the algorithm being built piece by piece, but finding out words being created by surrounding keys was part of collecting all the candidates. They even used this in marketing. One of the pre-original-iPhone-launch videos was focused just on the on-screen keyboard (probably because almost everyone thought it was a really kooky idea at the time), and used the example of explicitly pressing "O-U-Z-Z-A" but still getting "pizza" as the autocomplete because it was the closest recommendation. One of the iOS versions a few years ago became incredibly fond of including the space bar and considering alternatives with slightly off key presses near the space bar split into two or more words. When you're using a language with a lot of compound words like Swedish, this yielded some almost postmodern corrections with one or more words often completely different (but close on the keyboard, of course). I don't know if this was a tweak to the manual algorithm going off the rails or an AI version that wasn't quite tuned well yet.
blondin 5y ago
just wait for old hn to show up and tell new hn that the famous Norvig's spelling corrector is not efficient and is not teaching people how to do it right.

76 points by fybs 5y ago

Those interested in toy implementations in this area might also enjoy this blog https://blog.burntsushi.net/transducers/ https://blog.burntsushi.net/transducers/ on FSMs. Also the NLP Book on the data side https://web.stanford.edu/~jurafsky/slp3/ https://web.stanford.edu/~jurafsky/slp3/

Joker_vD 5y ago

And after you've read that, here's a related blogpost: "A Spellchecker Used to Be a Major Feat of Software Engineering" [0], because Python being "fast enough" and having enough memory for large dictionaries hasn't always been the case. [0] https://prog21.dadgum.com/29.html https://prog21.dadgum.com/29.html

tgv 5y ago
I'll repeat my feat in this area: a spelling corrector that had 32kB memory (because it was tied to a keyboard trap, or something like that) and could do four 8kB reads from CD-ROM before telling the user. It contained not only orthographic similarity (the actual letters), but also phonetic similarity. You rarely see that in older English spell checkers, because it's such an irregular language, but for other languages it's quite informative, although in extremely regular languages, such as Spanish, you could also put it in the weighting/probability model (e.g. v<->b is a pretty common confusion). The CD-ROM spelling corrector was not really great, BTW, but at least it replied in 1s on a typical end-user PC. Edit: this was late 1980s.

pandatigox 5y ago

I've had a thought and am curious how people would solve it. Sometimes, if you copy words off a PDF lecture slide, all the words are mashed together (eg. Hello Foo bar → HelloFoobar). Is this an AI domain or can it solved by simple programming?

eutectic 5y ago
I would try an n-gram model with dynamic programming. e.g. logp(_, "") = 0 logp(word0, text) = max(logp_bigram(word0, word1) + logp(word1, rest) for word1, rest in prefix_words(text))
gattilorenz 5y ago
"AI" and "simple programming" are not mutually exclusive :) look at the Speech and Language processing book, particularly chapter 3 about language models https://web.stanford.edu/~jurafsky/slp3/ https://web.stanford.edu/~jurafsky/slp3/ You can implement a language model based on character n-grams to calculate whether a sequence is more likely with or without a space. Of course you would need a way of estimating the proability of each sequence, which means you need a corpus to train your language model on.
wodenokoto 5y ago
This is a common problem in Japanese NLP, and while state of the art is using deep learning, almost everyone use dynamic programming or conditional random fields together with a dictionary to solve it. There also exists research on solving this problem unsupervised which basically invents new word boundaries for a language (remember that spoken languages doesn’t have word boundaries - it was invented for writing and strictly speaking, current spelling isn’t the only way to solve word boundaries for a given language)
tester34 5y ago
Have you tried using an ~~XML~~ PDF parser instead? /s and tried to find which sentence without spaces matches your sentence
ghusbands 5y ago
It's worth noting that different PDF-to-text tools (and different PDF-display tools that have text-copying) get different results and it can be worth trying a few. For the most part, the vector parts of a PDF and the association with the text is sufficient to discover spacing information.
deleted 5y ago
[deleted]

graycat 5y ago

My favorite, long standard spell checker is Aspell long part of a TeX distribution.

the-smug-one 5y ago

Could use a Hidden Markov Model, how to implement: https://www.cs.sjsu.edu/~stamp/RUA/HMM.pdf https://www.cs.sjsu.edu/~stamp/RUA/HMM.pdf Here's an impl of some kind: https://github.com/crisbal/hmm-spellcheck https://github.com/crisbal/hmm-spellcheck

da39a3ee 5y ago

From a pedagogical point of view presenting that as a Bayesian model and then using the error model he does, is a bit questionable. But as always his python style is inspiring.

eigenhombre 5y ago

One of the more interesting parts of the post, for me, is the list of implementations in other languages, including: one for Clojure written by that language's author, Rich Hickey; an interesting one in R that clocks in at 2 lines (with a longer, more readable version further down in the linked post); and one written in functional Java. The first one in Awk is also interesting.

mtreis86 5y ago

One of my most common spelling mistakes is physical mistypes on the keyboard, yet no spell checker seems to account for keyboard layout and locality of keys, or for something like my hand being one position off on the board but typing all the keys relatively correct only positionally shifted.

brian_cloutier 5y ago
spell checkers which account for keyboard layout absolutely exist. [1] is one example, but in general it's hard to believe that any trained model would fail to notice that certain mistakes are more likely than others, and it's hard to believe that any spell checker google releases these days would not be based on a trained model. [1] https://ai.googleblog.com/2017/05/the-machine-intelligence-behind-gboard.html https://ai.googleblog.com/2017/05/the-machine-intelligence-b...
m463 5y ago
I think the problem is that there are multiple layers of correction - both the physical and the spelling/semantic. On ios I just had to turn off autocorrect, because I had reminders I jotted down quickly which missed the physical correction and were irretrievably corrected semantically into garbage. now I find a note with "spekk" and I can figure out I meant "spell" (need a better example)
tyingq 5y ago
I would guess that the iPhone autocorrect does this implicitly since it's ML trained.
z3t4 5y ago
The problem is that if you take an english word and change one letter it will likely become another valid word.
wootest 5y ago
Many designs does this implicitly. At least one, the original iPhone keyboard autocomplete/suggestion algorithm, did it explicitly. Ken Kocienda's book Creative Selection has a very good chapter on the algorithm being built piece by piece, but finding out words being created by surrounding keys was part of collecting all the candidates. They even used this in marketing. One of the pre-original-iPhone-launch videos was focused just on the on-screen keyboard (probably because almost everyone thought it was a really kooky idea at the time), and used the example of explicitly pressing "O-U-Z-Z-A" but still getting "pizza" as the autocomplete because it was the closest recommendation. One of the iOS versions a few years ago became incredibly fond of including the space bar and considering alternatives with slightly off key presses near the space bar split into two or more words. When you're using a language with a lot of compound words like Swedish, this yielded some almost postmodern corrections with one or more words often completely different (but close on the keyboard, of course). I don't know if this was a tweak to the manual algorithm going off the rails or an AI version that wasn't quite tuned well yet.

blondin 5y ago

just wait for old hn to show up and tell new hn that the famous Norvig's spelling corrector is not efficient and is not teaching people how to do it right.