How I Trie to Make Spelling Suggestions

http://blog.afterthedeadline.com/2010/01/29/how-i-trie-to-make-spelling-suggestions/

by raffi • 16 years ago

46 17 16 years ago

blog.afterthedeadline.com

llimllib• 16 years ago

http://en.wikipedia.org/wiki/Patricia_tree would be an improvement.

raffi4• 16 years ago

Possibly. I think it's the difference between a plain BST and an AVL or Red/Black tree. More work for some gain but ultimately the data has something to say about whether it matters. I think this scheme would certainly balloon the logic for generating edits for a word which is the whole purpose of this post.

elblanco3• 16 years ago

Clever title. In my experience, in a practical sense, tries tend to be very memory intensive with only a marginal increase in speed over other alternatives like simple hash lookups. However, this is a very interesting and more typical use-case for a trie. I've always like it better than using Hamming distance which still seems to get recommended in undergraduate texts.

Oh, and I glossed over the perl code, until I reread it and realized it was sleep code. First time hearing about this language...interesting.

http://sleep.dashnine.org/

raffi4• 16 years ago

AtD uses a lot of memory but this technique made a difference speeding up the spell checker. For things best done with a hash lookup, we use hashtables. This is what we're using for generating edits still (I wrote most of this post in August 09, finally finished it today).

[Edit: I wrote Sleep :) I don't promote it much but it's been with me for many years and I've applied it to a lot of problems including the NLP in AtD]

elblanco3• 16 years ago

Sweet. I tried doing a similar experiment targeting C++ years ago but never finished it.

Nicely done! How far along is it? Writing Perl-ish code that targets the JVM seems inspired to me.

Object oriented? Can write threaded code and all that? (there's been a number of times where Perl's shortcomings in those areas have prevented me from building better code).

mrshoe• 16 years ago

Rather than re-implement this it might be better to use an existing library. In Python, I've used pylevenshtein:

http://code.google.com/p/pylevenshtein/

However, I've found the Jaro-Winkler distance to be more useful than the Levenshtein. You can find good implementations for Jaro out there as well.

http://en.wikipedia.org/wiki/Jaro-Winkler_distance

raffi4• 16 years ago

These algorithms solve a different problem. They calculate the edit distance between a string A and B. The algorithm in the post finds all strings B within an edit distance N of string A.

tom_pinckney• 16 years ago

Careful what dictionary you use...my /usr/share/dict/words has things in it that might not be polite/acceptable to suggest.

yan• 16 years ago

Do people pronounce trie as 'try' or 'tree'? I pronounce it as 'tree,' which is why it took me a second to catch the pun.

astine• 16 years ago

Phonetically, it should be 'try,' but I don't know how it is pronounced usually.

bmm6o• 16 years ago

The etymology suggests that you should pronounce it "tree". The argument for pronouncing it "try" is to avoid creating a homophone with the other (more popular) data structure. I would pronounce it "try", but honestly it doesn't come up in conversation as much as I would like.

elblanco3• 16 years ago

I've heard both with equal frequency.

fallintothis• 16 years ago

I actually pronounce it "tree-eye", even though that's all sorts of incorrect.

indigoviolet• 16 years ago

I've used Burkhard-Keller trees to do something like this:

http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK...

I don't know off the top of my head which one is more efficient.

kristianp• 16 years ago

What is the algorithmic complexity of your trie code compared to Norvig's example corrector?

abecedarius• 16 years ago

Norvig posted a similar algorithm using a hashtable instead of a trie: edits() in ngrams.py at http://norvig.com/ngrams/

You use a table of all prefixes of all dictionary words. This might be more or less efficient than a trie, depending on implementation; but in interpreted Python the built-in hashtables are bound to win.

(It's descended from code I sent in response to http://norvig.com/spell-correct.html, rewritten to return a dict of candidates each paired with a description of how it's different from the original word. There's a bug of sorts in that the result set misses a very few candidates his first article's code finds, unless you extend the edit-distance cutoff; I only noticed the problem after I'd mailed him the code. I'm not sure if the OP's algorithm has the same shortcoming -- I haven't read it closely.)

How I Trie to Make Spelling Suggestions

Related Stories