Norvig posted a similar algorithm using a hashtable instead of a trie: edits() in ngrams.py at <a href="http://norvig.com/ngrams/" rel="nofollow">http://norvig.com/ngrams/</a><p>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.<p>(It's descended from code I sent in response to <a href="http://norvig.com/spell-correct.html" rel="nofollow">http://norvig.com/spell-correct.html</a>, 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.)