PartialRatio issue

[maxbachmann]

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]

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

[maxbachmann]

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]

so it's wrong right?

[maxbachmann]

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.