PartialRatio issue
Opened this issue · 4 comments
why does this and this return as 100 percent matched?
String s1 = "cant display the icon";
String s2 = "cant display screen";
why does this and this return as 100 percent matched?
The correct result would be 74, so a result of 100 would be a bug.
so it's wrong right?
In rapidfuzz I implement this metric using a sliding window approach, which skips comparisons only if it is really sure they can not occur. When searching for long needles (> 64 characters) this is slower than the approach using get matching blocks. However it is the only way I am aware of, that is guaranteed to return the correct alignment. The current implementation has the following issues:
- the implementation backtracking the Levenshtein matrix is not guaranteed to return the longest common subsequences (which difflib does). It would be possible to find this, but it would make it a lot slower, since it would require backtracking multiple times to find it.
- even when using the implementation from difflib, it is fundamentally flawed, since there is no guarantee for the optimal alignment to start at the same place as one of the longest common subsequences
- the metric allows the matched substring to be shorter if it is placed at the end of the sequence. However to make the metric symmetric the same needs to be allowed at the start of the sequence.
Especially the second issue is a fundamental flaw in the way this algorithm currently works.