Live data from Hacker News

How to write a spelling corrector (2016)

norvig.com

61–70 of 87 posts

Re: How to write a spelling corrector (2016)

#61
The article doesn't mention it explicitly, but this is a nice example of how using Bayes theorem helps you ignore the hard-to-compute normalization term of the input space. In the article, this is the P(w) term of

P(c|w) = P(c)P(w|c)/P(w),

where c is a correction, and w is the original word.

The author does implicitly talk about this when he explains that P(c|w) conflates the two factors, but it's also not that hard to see that getting a handle on P(w) -- the probability space of misspellings -- is harder than getting a hold of P(c) -- the probability space of actual words, and Bayes lets us get rid of the former during optimization.

Re: How to write a spelling corrector (2016)

#62
post #53

The unit tests worry me: assert len(WORDS) == 32192 assert sum(WORDS.values()) == 1115504 assert WORDS.most_common(10) == [ ('the', 79808), ('of', 40024), ('and', 38311), ('to', 28765), ('in', 22020), ('a', 21124), ('that', 12512), ('he', 12401), ('was', 11410), ('it', 10681)] assert WORDS['the'] == 79808 Those aren't testing the file open, or Counter, or read, but instead are tightly-coupling the tests to the exact…

His tests are appropriate because they are task-oriented. He is not writing a general spellchecker, but a spellchecker designed to work with a specific corpus. His tests ensure that the corpus remains unchanged during development (say, doesn't accidentally remove some words). What's implicit here is that if the corpus changes, he may need to change his approach.

> What's implicit here is that if the corpus changes, he may need to change his approach.

Will that be obvious to a junior engineer? (I think that's the target audience for this article)

If I was writing such an article, I would (maybe) call that out as explicit, or (extremely likely) remove those tests so as not to accidentally implicitly recommend overfitted tests as a useful technique.

Re: How to write a spelling corrector (2016)

#63
post #58
post #32

I know a spelling corrector is not the same thing as a spelling checker, but this is too good an opportunity to pass to promote Martha Snow's hilarious poem 'Spell Chequer': Eye halve a spelling chequer It came with my pea sea It plainly marques four my revue Miss steaks eye kin knot sea. Eye strike a quay and type a word And weight four it two say Weather eye am wrong oar write It shows me strait a weigh. As soon as…

A fun story in the same vein, Ladle Rat Rotten Hut, by H.L. Chace, can be found here: http://www.exploratorium.edu/files/exhibits/ladle/

Check out the book "Tahoe Leap Eyeball" at Amazon. It's the entire KJV bible in that style. (Tahoe Leap Eyeball = The Holy Bible).

Clearly the process was automated. Ingenious program. More complex than mere homophone substritution... it works syllable by phonetic syllable to string together words that, when spoken, sound pretty dang close to the original.

Re: How to write a spelling corrector (2016)

#65
post #32

I know a spelling corrector is not the same thing as a spelling checker, but this is too good an opportunity to pass to promote Martha Snow's hilarious poem 'Spell Chequer': Eye halve a spelling chequer It came with my pea sea It plainly marques four my revue Miss steaks eye kin knot sea. Eye strike a quay and type a word And weight four it two say Weather eye am wrong oar write It shows me strait a weigh. As soon as…

Obligatory party-pooping: this doesn't really seem to be a poem about a spelling checker or corrector.

Naive spelling [auto]correctors correct by text distance, because people almost always make mistakes in text input by typing the right words but making the wrong motions to do so.

Slightly-less-naive autocorrect takes this approach further, and understands that e.g. "yjr" should become "the" because it's the same letters all shifted over by one.

And, as in the submitted article, the best autocorrectors just look at the whole sentence context and try to predict what word the input "should" have been given what it looks like—this is essentially a kind of compressed sensing (like fMRIs use!), though in practice it tends to be baked down to something like markov chains of levenstein automata with back-propagation on w>n.

...whereas this poem is more like the result of a very naive speech to text algorithm, one which parses each word independently without the context of the sentence-so-far.

(Side-note: I'm surprised that speech-to-text algorithms still work mostly in "real time" with only a limited buffer, unable to go back and change anything more than a few words in the past. It's why they fail to recognize names, for example. If speech-to-text algorithms would buffer the entire audio stream for a dictated document, showing an estimate of the output text so far, but continuing to re-estimate the entire document after every word/sentence/paragraph, they'd perform much better. The difference would be on the level of a standard web-renderer's line-at-a-time reflow algorithm, vs. TeX's whole-document reflow.)

Re: How to write a spelling corrector (2016)

#66
post #54
post #51

Earlier quoted context omitted.

I think this is how all poems should be read, and I didn't realize until just now that I automatically did that.

There is apparently a big divide between people who subvocalize when they read and those who don't. Those who don't tend to read much faster than those who do which is why speedreading techniques tend to focus on eliminated subvocalization. The problem is that people who subvocalize tend to need to do so in order to understand the text. https://en.wikipedia.org/wiki/Subvocalization

I wonder whether the people who do subvocalize when they read tend to be better at writing poetry (or songwriting, or just writing beautiful prose.) I would expect that they'd have been subconsciously training themselves to the "feel" of good meter.

Re: How to write a spelling corrector (2016)

#67

While doing a bunch of research on exactly this problem space recently for a project, I stumbled onto this improvement on the Norvig corrector idea http://blog.faroo.com/2012/06/07/improved-edit-distance-base... that's one of those things that's so deceptively simple you kick yourself for not thinking of it: it turns out you can model the same "generate all the variations" effect but generating only the deletes, rath…

Here is the link to the SymSpell Github repository: https://github.com/wolfgarbe/SymSpell An here a benchmark between Norvig's spelling corrector, BK-tree and SymSpell: https://towardsdatascience.com/symspell-vs-bk-tree-100x-fast...

Ah should have shared the repo, and thanks for publishing it! We're experimenting now with adapting this idea but using a directed acyclic FSA to store the index-time variations instead of a hashtable like in your version, with the idea that we might be able to search for all of the query-time variations in a single pass rather than one at a time (as for obvious reasons they'll be textually similar to one another so there should be some shared work between the lookups).

Re: How to write a spelling corrector (2016)

#68

The unit tests worry me: assert len(WORDS) == 32192 assert sum(WORDS.values()) == 1115504 assert WORDS.most_common(10) == [ ('the', 79808), ('of', 40024), ('and', 38311), ('to', 28765), ('in', 22020), ('a', 21124), ('that', 12512), ('he', 12401), ('was', 11410), ('it', 10681)] assert WORDS['the'] == 79808 Those aren't testing the file open, or Counter, or read, but instead are tightly-coupling the tests to the exact…

Some tests are similar to the "texas sharpshooter fallacy".

Re: How to write a spelling corrector (2016)

#69
post #58
post #32

I know a spelling corrector is not the same thing as a spelling checker, but this is too good an opportunity to pass to promote Martha Snow's hilarious poem 'Spell Chequer': Eye halve a spelling chequer It came with my pea sea It plainly marques four my revue Miss steaks eye kin knot sea. Eye strike a quay and type a word And weight four it two say Weather eye am wrong oar write It shows me strait a weigh. As soon as…

A fun story in the same vein, Ladle Rat Rotten Hut, by H.L. Chace, can be found here: http://www.exploratorium.edu/files/exhibits/ladle/

https://www.hyperborea.org/humor/tweeze.phtml was done mostly by computer. It's a fun challenge to write your program to make these. To tie it back to the OP, you could "spell-correct" the source text into a sequence of words that come closest to reproducing the original sound (but with the source sequence blacklisted).

Re: How to write a spelling corrector (2016)

#70
post #65
post #32

I know a spelling corrector is not the same thing as a spelling checker, but this is too good an opportunity to pass to promote Martha Snow's hilarious poem 'Spell Chequer': Eye halve a spelling chequer It came with my pea sea It plainly marques four my revue Miss steaks eye kin knot sea. Eye strike a quay and type a word And weight four it two say Weather eye am wrong oar write It shows me strait a weigh. As soon as…

Obligatory party-pooping: this doesn't really seem to be a poem about a spelling checker or corrector. Naive spelling [auto]correctors correct by text distance, because people almost always make mistakes in text input by typing the right words but making the wrong motions to do so. Slightly-less-naive autocorrect takes this approach further, and understands that e.g. "yjr" should become "the" because it's the same le…

I typed the poem in to MS Word, and the only word flagged was 'chequer'. I guess Word's is a 'naive' spelling checker.
Post reply on HN