search

xdrop / fuzzywuzzy

Java fuzzy string matching implementation of the well known Python's fuzzywuzzy algorithm. Fuzzy search for Java
GNU General Public License v2.0
825 stars 117 forks source link

PartialRatio issue #88

Open maxbachmann opened 3 years ago

maxbachmann commented 3 years ago

This is essentially reopening issue #39, since the introduced fix does not solve the problem, but just makes it work for this explicit example. E.g.

FuzzySearch.partialRatio("no", "bnonco");

should return the score 100. This worked until #80, but returns the score 50 after reordering the cases

ACE07-Sev commented 3 years ago

why does this and this return as 100 percent matched? String s1 = "cant display the icon"; String s2 = "cant display screen";

maxbachmann commented 3 years ago

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.

ACE07-Sev commented 3 years ago

so it's wrong right?

maxbachmann commented 1 year ago

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:

1) 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. 2) 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 3) 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.