[go: up one dir, main page]

Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

PartialRatio issue #88

Open
maxbachmann opened this issue Nov 15, 2020 · 4 comments
Open

PartialRatio issue #88

maxbachmann opened this issue Nov 15, 2020 · 4 comments

Comments

@maxbachmann
Copy link

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
Copy link

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

@maxbachmann
Copy link
Author

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
Copy link

so it's wrong right?

@maxbachmann
Copy link
Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants