Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to write a spelling corrector (2016)

norvig.com

Post reply on HN
Print view View original

71–80 of 87 posts

Re: How to write a spelling corrector (2016)

#71

Post by abecedarius »

falsedan wrote: post #31

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…

This is a fair criticism, I think. Anyone want to write a blog post about the tests they would write for this task? Maybe it'd be especially interesting as going from "here's what you might do for the first version coded on a plane flight, now here's how it might evolve as it's polished for publication". I'm not volunteering as I'm not especially good at writing tests.

Re: How to write a spelling corrector (2016)

#72

Post by abecedarius »

karterk wrote: post #14

This has been an area of interest for me as part of working on Typesense[1]. If you are looking to implement spelling correction, you cannot but not stumble on this excellent post by Peter Norvig (most of it written on a bored flight journey!). While it's clever and concise, in terms of raw speed, indexing your vocabulary in a Trie, and then doing a traversal on it using a Levenshtein distance is way faster[2]. By us…

Norvig also wrote about using a fancier error model and a faster algorithm at http://norvig.com/ngrams/ -- similar to a trie, but a literal trie would not be so efficient in Python.

Re: How to write a spelling corrector (2016)

#73

Post by abecedarius »

hellofunk wrote: post #23

Here is Rich Hickey's port of this Norvig exercise to Clojure: https://en.wikibooks.org/wiki/Clojure_Programming/Examples/N...

It turns out Hickey added some functions to Clojure to be able to write that code. Nothing wrong with that -- they're useful functions! -- but I found it kind of amusing. It can be good to be a king.

Re: How to write a spelling corrector (2016)

#74

Post by abecedarius »

nl wrote: post #5

This is a great technique to know. I’ve used a variant to segment Twitter hash tags into meaningful words, which is a surprisingly hard thing to do.

He has that covered too! http://norvig.com/ngrams/

But yeah, I tackled the same problem (for Flickr tags) and did not at first use the "obvious" algorithm; I did something slower and suboptimal.

Re: How to write a spelling corrector (2016)

#75

Post by dahart »

lcuff wrote: post #58
lb1lf wrote: 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/

I'm learning a little Icelandic right now, and it's eerie how similar reading this poem feels. The words make no sense at first glance, but there are sounds and a language I understand somewhere underneath.

Re: How to write a spelling corrector (2016)

#76

Post by djtriptych »

falsedan wrote: post #31

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…

1. Read blog post.

2. Opine on how blog code is not ready for production.

3. Post to HN.

4. Propser.

Re: How to write a spelling corrector (2016)

#77

Post by Someone »

lb1lf wrote: 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…

Judging by how the iOS speech synthesizer pronounces them, that is a lot better than “Ladle Rat Rotten Hut” and “Tweeze Denied Beef Worker Isthmus” (both mentioned in comments to the post mentioning “Spell Chequer”)

Re: How to write a spelling corrector (2016)

#78

Post by chipotle_coyote »

derefr wrote: post #65
lb1lf wrote: 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…

Obligatory "Well Actually": the poem isn't trying to demonstrate the technology behind spellcheckers (or correctors). It's demonstrating a near-universal weakness of algorithmic checking/correcting that isn't shared with human proofreaders: when the mistaken word is the correct spelling of another word. The poem takes this to absurd extremes, but it's quite possible to make such mistakes through typos (e.g., "pun" instead of "pin").

Re: How to write a spelling corrector (2016)

#80

Post by earenndil »

derefr wrote: post #66
astine wrote: post #54

Earlier quoted context omitted.

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.

There might be a correlation, but it's not a hard-and-fast rule. I've been told that my prose -- and poetry -- is good, and I definitely don't subvocalize.
Post reply on HN