search

rapidfuzz / RapidFuzz

Rapid fuzzy string matching in Python using various string metrics
https://rapidfuzz.github.io/RapidFuzz/
MIT License
2.61k stars 116 forks source link

use Hirschbergs algorithm for Indel.editops / LCS.editops #351

Open maxbachmann opened 10 months ago

maxbachmann commented 10 months ago

Using Hirschbergs algorithm when calculating Indel.editops / LCS.editops would significantly reduce the memory usage. This is already done for Levenshtein which reduces the memory usage from O(N*M) to a maximum of around 1mb.