News for hackers. Stuff that matters.

A comment on Levenshtein Distance. Parent comment

Re:Levenshtein Distance by HeyImAlex on Thursday August 22, 2019 @10:00PM (#20774003)
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

[ Parent | on HN ]
Re:Levenshtein Distance by dorgo on Friday August 23, 2019 @03:48AM (#20775344)
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 ).
[ Parent | on HN ]