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

How to Write a Spelling Corrector

norvig.com

Post reply on HN
Print view View original

11–20 of 133 posts

Re: How to Write a Spelling Corrector

#11

Post by bradbeattie »

lb1lf wrote: post #3

Spell chequer Martha Snow 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 mist ache is maid It nose bee fore two long And eye can put the error rite It's rare lea ever wrong. Eye have run this poem threw it I am shore y…

Is this where you start considering ngrams probabilities? Curious as to the best approach to this, as it's clear we can all read the above.

Re: How to Write a Spelling Corrector

#12

Post by bsenftner »

Although not a spell checker specifically, I wrote an offensive language filter for a chat system used by the National Hockey League for a period when they hosted communal chat rooms during televised games.

The architecture I used is completely different from what is described here, but the goals are very similar. I had to handle any curse word in any language, including curses from one language translated into another language, as well as offensive phrases, and their translated equals, as well as offensive slang, and mispelt offensive slang translated from other languages.

I ended up with an offense dictionary of about 700K words and phrases. This was back in '99, so my memory may not be 100% here, but I remember using Perfect Hash to generate a compiled hash table for the dictionary, and then a trie to organize the dictionary lookups. The entire system was about 150K of a downloaded exe to access the NHL simulcast chat, as all the offensive language filtering occurred on the client side. Chatting anything that could be offensive turned into a series of words with their interiors all asterisk '*', and it ran in something like 500 ms. Fun times. That company and project died with the dot com bust.

Re: How to Write a Spelling Corrector

#13

Post by bpchaps »

I love it. Spell checking was pretty relevant to some of my work recently and I needed to correct heavily typo'd address text from Chicago parking ticket data. It used difflib to recursively find similarly typo'd address until it finds a matching address within a list of correct addresses. Definitely a lot more to polish, but I'm kinda proud of the naive approach.

https://github.com/red-bin/tyop_fixer

  coumbia,columbia,0.933333333333
  argy,argyle,0.8
  menomee,menomonee,0.875
  newladn,newland,0.857142857143
  boulevard way,boulevard,0.818181818182
  sherwn,sherwin,0.923076923077
  lawrencec,lawrence,0.941176470588

Re: How to Write a Spelling Corrector

#16

Post by DanBC »

colobas wrote: post #8
1024core wrote: post #4

The last 9 times it was submitted: http://goo.gl/mVSi7W

I found it in a StackOverflow answer and found it worth sharing. Didn't bother checking if it had already been posted on hackernews.

Normally when people tell you something has been submitted before they're saying "you might find some of these earlier comments interesting too".

Re: How to Write a Spelling Corrector

#18

Post by agd »

lb1lf wrote: post #3

Spell chequer Martha Snow 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 mist ache is maid It nose bee fore two long And eye can put the error rite It's rare lea ever wrong. Eye have run this poem threw it I am shore y…

In a way, I'm surprised I can read this so easily. Do our brains read by converting text to sounds, and then parsing the sounds?

Re: How to Write a Spelling Corrector

#19

Post by Tloewald »

lb1lf wrote: post #3

Spell chequer Martha Snow 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 mist ache is maid It nose bee fore two long And eye can put the error rite It's rare lea ever wrong. Eye have run this poem threw it I am shore y…

You should read Feersum Endjinn

Re: How to Write a Spelling Corrector

#20

Post by Tloewald »

bsenftner wrote: post #12

Although not a spell checker specifically, I wrote an offensive language filter for a chat system used by the National Hockey League for a period when they hosted communal chat rooms during televised games. The architecture I used is completely different from what is described here, but the goals are very similar. I had to handle any curse word in any language, including curses from one language translated into anoth…

Interesting. I had to write a badwords filter for a random name generator (for a procedural galaxy generator...) and it's quite a task just for English.
Post reply on HN