3 ms·
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
by HeyImAlex 7y ago
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 https://en.wikipedia.org/wiki/Bitap_algorithm
[2] https://github.com/heyimalex/bitap https://github.com/heyimalex/bitap
- dorgo 7y agoInteresting. 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 ).