RapidFuzz icon indicating copy to clipboard operation
RapidFuzz copied to clipboard

Implement banded version of InDel distance

Open maxbachmann opened this issue 3 years ago • 0 comments

A banded version of the Levenshtein distance algorithm should be implemented as described in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.59.6975&rep=rep1&type=pdf. This would reduce the runtime of scorers like fuzz.ratio from O(N/64 * M) to O(score_cutoff/64 * M which could significantly improve the performance on long sequences.

maxbachmann avatar Jan 06 '22 14:01 maxbachmann