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

Norvig posted a similar algorithm using a hashtable instead of a trie: edits() in ngrams.py at http://norvig.com/ngrams/ 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 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.)