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

Faster Spelling Correction algorithm (2012)

blog.faroo.com

Post reply on HN
Print view View original

11–20 of 22 posts

Re: Faster Spelling Correction algorithm (2012)

#12

Post by TheLoneWolfling »

Hmm...

They don't mention the approach I'd take for a naive spellcheck:

Generate a (giant) trie from the dictionary. Then perform a DFS on the trie allowing only edits from the input word, keeping track of the edits done so far - try no changes at each node first, then a deletion, then a change, then an insertion. This works better with a smaller alphabet size.

An optimization: a DAWG is potentially even better space-wise than a hashmap (effectively it ends up compressing the input data), but takes a while to precompute.

Re: Faster Spelling Correction algorithm (2012)

#15

Post by JoeAltmaier »

grogenaut wrote: post #14

1000x is still O(1000N) == N. So technically not significantly faster.

Except that 'spelling' is a bounded problem. There aren't going to be more words in the dictionary, at least not orders more, any time soon. 'Scaling as the word list grows' is meaningless. So the only definition of 'faster' that matters is the one they used.

Re: Faster Spelling Correction algorithm (2012)

#16

Post by ghkbrew »

grogenaut wrote: post #14

1000x is still O(1000N) == N. So technically not significantly faster.

That all depends on what you consider a significant speed up. For small values of N constant factors will usually dominate. In this case, they mention that lookup time is independent of dictionary size, so the "N" in question is actually a combination of the word size and the edit distance, both relatively small quantities.

Re: Faster Spelling Correction algorithm (2012)

#17

Post by toolslive »

JoeAltmaier wrote: post #15
grogenaut wrote: post #14

1000x is still O(1000N) == N. So technically not significantly faster.

Except that 'spelling' is a bounded problem. There aren't going to be more words in the dictionary, at least not orders more, any time soon. 'Scaling as the word list grows' is meaningless. So the only definition of 'faster' that matters is the one they used.

That's a rather "English only" view on the topic. Spelling is not a bounded problem in every language.

Some power languages (Dutch, German) have an infinite number of words, as you can take 2 nouns (fe a and b) and concatenate them to form a new one (ab means something else than ba). Some languages also have inflection....

Re: Faster Spelling Correction algorithm (2012)

#18

Post by dvirsky »

It's a nice approach, I've implemented it in Golang a while back. It's really fast, but the cost in memory is huge, especially if you store bigrams and not just single words. But it's really elegant in its simplicity.

BTW - if anyone's interested in the Go implementation let me know, I'll try to find it and post it somewhere.

Re: Faster Spelling Correction algorithm (2012)

#19

Post by gorhill »

simias wrote: post #11
jheriko wrote: post #5

hmmm... 1000x? how does it scale though?

It's easy to say "1000x" when they don't mention the reference :) Actually even reading the article I'm not completely certain where that 1000x comes from, I suppose it's when compared to the naive approach.

I think it's compared to Peter Norvig's approach:

> This is three orders of magnitude less expensive (36 terms for n=9 and d=2)

Three orders of magnitude is 1000. Peter Norvig's approach was described above with:

> still expensive at search time (114,324 terms for n=9, a=36, d=2)

So 114,324 / 36 = 3,175, so "three orders of magnitude", and I suppose he went conservative by saying "1000x" rather than "3000x".

Post reply on HN