Fast and easy Levenshtein distance using a trie (2011)
Here's an alternative that is more efficient at large scales (eg. if you have one order of magnitude more entries than just an English dictionary): performing Approximate Nearest Neighbor search [1] over a pre-computed  Levenshtein space.<p>- hash all your dictionary entries through a Levenshtein-locality-sensitive hash function [2] with a well-chosen hash size. Any two words within a Levenshtein distance D of each other will have the same hash (you pick D).<p>- store the hashes into an efficient DB for quick lookup. Each hash will map to one or several (levenshtein-similar) dictionary entries.<p>- when presented with a new input, compute its hash, retrieve the entry for the hash in your DB (if it exists).<p>- finish by sorting the retrieved dictionary entries by Levenshtein distance to your input... you just recovered all dictionary entries closer than distance D to your input (approximately).<p>Pretty much unbeatable, and works over spaces that have hundreds of millions of dictionary entries.<p>[1] <a href="https://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximate_nearest_neighbor" rel="nofollow">https://en.wikipedia.org/wiki/Nearest_neighbor_search#Approx...</a><p>[2] Can't find one? Build your own by computing the pairwise distance matrix of your entries, then reducing this matrix through PCA to an appropriate number of components (the length of your hash). The coordinates of each entry in this new space is the entry's hash.