If you're fuzzily looking up members in a fixed corpus, you can also employ the trick from https://github.com/wolfgarbe/SymSpell, which is essentially just to, for each string in your corpus, enumerate all of the variants of that string with one letter removed, and put both the original string and each variant in a hashtable as a key, with the original string as the value. To do a lookup, you do the same enumeration (original query plus each variant with one letter dropped), and look all of them up in your hashtable. The values you get out of that are a list of all of the strings in your corpus at edit distances 0 or 1, and potentially some at edit distance 2; you can do a subsequent Levenshtein calculation on each to weed out the distance-2 strings, but you only have to do it on this massively reduced set rather than on your whole corpus.

So like, to index a string "hello", you'd add all of {"hello":"hello","ello":"hello","hllo":"hello","helo":"hello","hell":"hello"} into your table, and for the query "gello", you'd look up all of ["gello", "ello", "gllo", "gelo", "gell"], and get a match on "ello"->"hello", then do a Levenshtein calculation dist("gello","hello") to confirm it's within ED=1 (it is), and be done. (Bonus: the same method works with Damerau-Levenshtein distance as well.)

I've heard this called a deletion neighborhood

Does this work if you want to look up multiple words and grade them?

For example if the input query is "ello" and there is a dict.txt with millions of entries, it should output the words that are closest to the query: "hell", "hello", "fellowship", "mellow" and their respective matching scores (e.g 0.8, 0.9, 0.3, 0.7 respectively). The scores are just random numbers in this case.

(edited for clarity)

In which case do you wind up with distance=2? I figured it'd jump out at me in an obvious way, but it hasn't.

Can't think on a real word example, but abc would match bcd in the above algo, as both permute to bc, but they are distance 2. So, any case where one letter is deleted and another is added at a different position.

Boat and Oats is a real world example with Levenshtein distance 2 that would pass through the algo

Yeah, that's the crux -- two different real words storing the same variant but having omitted different letters.

Haha, I knew the answer was going to be obvious, and it was so obviously obvious. Thanks for answering. :)

Ha ha, I imagined this algorithm for spell checking almost 20 years ago when I was wondering how Google did it.

There's a specialized algorithm specifically for running levenshtein distance over tens of thousands of strings called bitap[1]. I wrote an impl in rust a while back[2].

But your advice still applies! Run time scales with max distance.

[1] https://en.wikipedia.org/wiki/Bitap_algorithm [2] https://github.com/heyimalex/bitap

Interesting. I used a similar trick to compute a lower bound on the levenshtein distance. I was able to skip the real levenshtein distance calculation, if the lower bound already exceeded a threshold ( I used it for clustering ).

Memoization[1]?

[1] https://en.wikipedia.org/wiki/Memoization