How to Write a Spelling Corrector (2007)
norvig.com
How to Write a Spelling Corrector (2007)
1–10 of 25 posts
Re: How to Write a Spelling Corrector (2007)
#2Those interested in toy implementations in this area might also enjoy this blog https://blog.burntsushi.net/transducers/ on FSMs.
Also the NLP Book on the data side https://web.stanford.edu/~jurafsky/slp3/
Re: How to Write a Spelling Corrector (2007)
#3And 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.
Re: How to Write a Spelling Corrector (2007)
#4I'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?
Re: How to Write a Spelling Corrector (2007)
#5My favorite, long standard spell checker is Aspell long part of a TeX distribution.
Re: How to Write a Spelling Corrector (2007)
#6I'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?
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))
Re: How to Write a Spelling Corrector (2007)
#7Could use a Hidden Markov Model, how to implement: https://www.cs.sjsu.edu/~stamp/RUA/HMM.pdf
Here's an impl of some kind: https://github.com/crisbal/hmm-spellcheck
Re: How to Write a Spelling Corrector (2007)
#8I'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?
"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/
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.
Re: How to Write a Spelling Corrector (2007)
#9I'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?
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)
Re: How to Write a Spelling Corrector (2007)
#10I'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?
Have you tried using an ~~XML~~ PDF parser instead? /s
and tried to find which sentence without spaces matches your sentence