search

Daniel-Liu-c0deb0t / triple_accel

Rust edit distance routines accelerated using SIMD. Supports fast Hamming, Levenshtein, restricted Damerau-Levenshtein, etc. distance calculations and string search.
MIT License
103 stars 13 forks source link

Feature request: bounded hamming distance #10

Closed Benjamin-Lee closed 2 years ago

Benjamin-Lee commented 2 years ago

I'm working on an application in which I'll be computing the hamming distance between two strings but only care if it's below $k$. There's a bounded Levenshtein method but no corresponding Hamming function. Is it possible to get a bounded Hamming distance?

Daniel-Liu-c0deb0t commented 2 years ago

The reason why bounded Levenshtein distance exists is because the bound makes it run a lot faster. For Hamming distance, adding a bound won't affect the speed that much. For bounded Hamming distance you should just explicitly check, like if hamming(a, b) <= k { ... }.

Benjamin-Lee commented 2 years ago

Ah got it. My original Nim code for Hamming distance (non-SIMD) was bounded and it did make a performance difference but I suppose SIMD changes things. Thanks for the quick answer!