RapidFuzz
RapidFuzz copied to clipboard
Implement banded version of InDel distance
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.