4 ms·
If you're fuzzily looking up members in a fixed corpus, you can also employ the trick from https://github.com/wolfgarbe/SymSpell https://github.com/wolfgarbe/Sy
by apendleton 7y ago
If you're fuzzily looking up members in a fixed corpus, you can also employ the trick from https://github.com/wolfgarbe/SymSpell 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.)
- visarga 7y agoHa ha, I imagined this algorithm for spell checking almost 20 years ago when I was wondering how Google did it.
- fuzzyexplainer 7y agoDoes 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)
- hackcasual 7y agoI've heard this called a deletion neighborhood
- developer2 7y agoIn 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.
- bryondowd 7y agoCan'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.
- aripickar 7y agoBoat and Oats is a real world example with Levenshtein distance 2 that would pass through the algo
- apendleton 7y agoYeah, that's the crux -- two different real words storing the same variant but having omitted different letters.
- developer2 7y agoHaha, I knew the answer was going to be obvious, and it was so obviously obvious. Thanks for answering. :)