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

1–10 of 22 posts

Re: Faster Spelling Correction algorithm (2012)

#2

Post by philjohn »

See also the Levenshtein Automatons used by Lucene 4.0 for fuzzy matching ... fun story, although they had to treat some Python code as a "black box" when implementing it ...

http://java.dzone.com/news/lucenes-fuzzyquery-100-times

Looks like some interesting research and dev going on in this space at the moment.

Re: Faster Spelling Correction algorithm (2012)

#3

Post by robert_tweed »

Interesting, though I'm curious about whether this type of algorithm is state of the art for accuracy. At this time spell checkers are pretty much fast enough, but aren't always terribly good at suggesting replacements. I would imagine that systems based on n-grams are more effective.

Re: Faster Spelling Correction algorithm (2012)

#4

Post by philjohn »

robert_tweed wrote: post #3

Interesting, though I'm curious about whether this type of algorithm is state of the art for accuracy. At this time spell checkers are pretty much fast enough, but aren't always terribly good at suggesting replacements. I would imagine that systems based on n-grams are more effective.

it mentioned it's for search engines, in which case you may be checking against a massive wordlist taken from a search index, so accuracy isn't (quite) as important as speed.

Re: Faster Spelling Correction algorithm (2012)

#8

Post by tgb »

jheriko wrote: post #5

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

The explanation is actually very simple, you should just read it! But basically they just generate variants of the word by deletions, not also insertions or substitutions. So increasing the "edit distance" multiplies the search space by n (the length of the word) instead of by n + an + a(n+1) (where a is the number of elements in the alphabet). Then there's cost in storing a larger dictionary of words, but lookup being logarithmic or better means that this should be fine. So yes, it scales better (at a memory cost).

Re: Faster Spelling Correction algorithm (2012)

#9

Post by smoyer »

Pre-processing a fixed data-set in order to optimize search is a pretty well known technique (the phone companies have been using "preordering" (specifically Modified Preorder List Traversal [1]) as a means of routing phone calls and diagnosing network issues for a very long time.

The downside to any preorder algorithm is that you must rerun the preorder generation code anytime the input changes (in this case a dictionary) and often you must allocate extra storage to hold the pre-processed input.

This is a really interesting algorithm but, as always, you have to know the pros and cons and apply it where if fits (i.e. Not somewhere that needs a compressed dictionary).

[1] http://www.codeproject.com/Articles/31669/Hierarchical-Tree-...

Post reply on HN