Fuzzy String Matching in Python

I see you've got issue #113 closed, however a simple reading of the GPL linked in the StringMatcher file doesn't just imply, but in fact definitively states, that your project must be licensed as GPL.

1. You may copy and distribute verbatim copies of the Program's source code as you receive it, in any medium, provided that you conspicuously and appropriately publish on each copy an appropriate copyright notice and disclaimer of warranty; keep intact all the notices that refer to this License and to the absence of any warranty; and give any other recipients of the Program a copy of this License along with the Program.

You have not copied the entire source verbatim, you've copied a select portion and incorporated it into a further derived work.

2. You may modify your copy or copies of the Program or any portion of it, thus forming a work based on the Program, and copy and distribute such modifications or work under the terms of Section 1 above, provided that you also meet all of these conditions:

a) You must cause the modified files to carry prominent notices stating that you changed the files and the date of any change.

b) You must cause any work that you distribute or publish, that in whole or in part contains or is derived from the Program or any part thereof, to be licensed as a whole at no charge to all third parties under the terms of this License.

Emphasis added. When you decided to copy in a portion of the code from python-levenshtein you incidentally selected the GPL license for your project, and it's been apparently licensed as MIT / X11, but effectively and legally licensed as GPL, ever since.

I say this as someone who has a company project that's now been copy-lefted by your code, albeit accidentally and inadvertently.

Now that #33 has been merged in, fuzzywuzzy looks good to go for python 3 compatibility. Might as well advertise this in the setup.py / on pypi. Version bumped so a new version can be pushed to pypi.

Cheers!

Added test case to check that using a processor of the form lambda x: x['key'] doesn't fail.

Set default_processor to None and do not run processor on query.

Remove test case that checked if string reduced to 0 by processor, as string will no longer be processed.

Adjusted test cases in test_fuzzywuzzy_hypothesis to not use a processor, but not fail if scorer reduces query to empty string. If the user supplies a processor that modifies the choice so that it is no longer an exact match for the query, not finding an exact match would be the expected behavior.

Saw some relevant discussion around issues #77 and #141 etc. If processor doesn't run on the query, which I feel it CAN NOT, then processor must also default to None to avoid unexpected behaviors.

(also have a separate branch that only adds the new test case fwiw)

C:\Python27\lib\site-packages\fuzzywuzzy\fuzz.py:33: UserWarning: Using slow pure-python SequenceMatcher
  warnings.warn('Using slow pure-python SequenceMatcher')

The line of code I have for importing is from fuzzywuzzy import fuzz.

I'm running Python 2.7.8 on Windows 8, pip 1.5.6, and fuzzywuzzy 0.4.0.

Could we kindly upload the latest version to pypi (directions)?

I'd like to use this library on a python 3 project where using pip install would be greatly appreciated :smile: Cheers!

Below is more information.

$> sudo pip install fuzzywuzzy   #works, no error

$> vi mytest.py
from fuzzywuzzy import fuzz
from fuzzywuzzy import process

$>python mytest.py
...
ImportError: cannot import name fuzz

Hi...

I'm new to Conda, and just re-installed fuzzywuzzy using conda version of pip. python-Levenshtein is also install according to conda.

I'm using Python 3.3.

I'm not sure what to do about this...

Cheers !

According to the intro page: "python-Levenshtein (optional, provides a 4-10x speedup in String Matching)"

I am fuzzy matching paragraphs with their best match from a significant list of paragraphs. When I use fuzzywuzzy without python-Levenshtein on Ubuntu, I receive the error that I should install it for a speed-up, and it took about 45 mins on a test set of paragraphs:

real 46m56.813s user 125m45.952s sys 0m0.432s

When I then installed python-Levenshtein, the error went away as expected, but running the same example set of paragraphs took over 200 minutes:

real 204m51.384s user 522m49.436s sys 0m21.376s

The results are identical except for one paragraph, which does match better with the slower, python-Levenshtein version. While I haven't timed an example, doing the same on the mac also seems significantly slower with python-Levenshtein installed.

The error message when python-Levenshtein is not installed says that the reason to install the package is for speed, so to me something isn't right: either it shouldn't be slower, or the error message should change to say that it should be installed for increased accuracy (if that is the case).

I get the following error:

File "/usr/lib/python3.4/site-packages/fuzzywuzzy/fuzz.py", line 49, in ratio
    s1, s2 = utils.make_type_consistent(s1, s2)
  File "/usr/lib/python3.4/site-packages/fuzzywuzzy/utils.py", line 43, in make_type_consistent
    elif isinstance(s1, unicode) and isinstance(s2, unicode):
NameError: name 'unicode' is not defined

Hi, First of all, thanks for maintaining this. I just noticed that both token_sort_ratio and token_set_ratio don't support Arabic characters. I don't know about other non-English ones but at lease they don't support Arabic.. It's returning 0 as a result of comparing anything with Arabic string. Even if they were 2 Arabic strings..

>>> print fuzz.token_sort_ratio("مرحبا جميعا", "مرحبا جميعا وشكرا لكم")
0
>>> print fuzz.partial_ratio("مرحبا جميعا", "مرحبا جميعا وشكرا لكم")
100

So I'm just wondering if this's a bug or it simply just doesn't support non-English characters? Thanks

Fixes #233

According to PEP 479, if raise StopIteration occurs directly in a generator, simply replace it with return.

This is both backwards and forwards compatible code.

While running the Fuzzy Wuzzy process.extract() method the following error is thrown :-

    matches = fw_process.extract(
../../.local/share/virtualenvs/proj-NKfiPrkj/lib/python3.8/site-packages/fuzzywuzzy/process.py:168: in extract
    return heapq.nlargest(limit, sl, key=lambda i: i[1]) if limit is not None else \
/usr/lib/python3.8/heapq.py:563: in nlargest
    result = [(key(elem), i, elem) for i, elem in zip(range(0, -n, -1), it)]
/usr/lib/python3.8/heapq.py:563: in <listcomp>
    result = [(key(elem), i, elem) for i, elem in zip(range(0, -n, -1), it)]
../../.local/share/virtualenvs/proj-NKfiPrkj/lib/python3.8/site-packages/fuzzywuzzy/process.py:117: in extractWithoutOrder
    score = scorer(processed_query, processed)
../../.local/share/virtualenvs/proj-NKfiPrkj/lib/python3.8/site-packages/fuzzywuzzy/fuzz.py:276: in WRatio
    base = ratio(p1, p2)
../../.local/share/virtualenvs/proj-NKfiPrkj/lib/python3.8/site-packages/fuzzywuzzy/utils.py:38: in decorator
    return func(*args, **kwargs)
../../.local/share/virtualenvs/proj-NKfiPrkj/lib/python3.8/site-packages/fuzzywuzzy/utils.py:29: in decorator
    return func(*args, **kwargs)
../../.local/share/virtualenvs/proj-NKfiPrkj/lib/python3.8/site-packages/fuzzywuzzy/utils.py:47: in decorator
    return func(*args, **kwargs)
../../.local/share/virtualenvs/proj-NKfiPrkj/lib/python3.8/site-packages/fuzzywuzzy/fuzz.py:28: in ratio
    return utils.intr(100 * m.ratio())
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 

self = <fuzzywuzzy.StringMatcher.StringMatcher object at 0x7f115ab32160>

    def ratio(self):
        if not self._ratio:
>           self._ratio = ratio(self._str1, self._str2)
E           NameError: name 'ratio' is not defined

I found that pinning the python-Levenshtein version to 0.12.2 solve the issue.

I am using process.extract method, And I know it uses WRatio under the hood for calculating score. Following is the case in which I am getting very high score of 90 despite the string hardly equal. Is there any way to fix this in WRatio?

inp_name="america"

name_list=["american Futures and Options Exchange"]
        
process.extractOne(inp_name,name_list)

Output--> ('american Futures and Options Exchange', 90.0, 0)

PS: I know other alternatives likes fuzz.ratio, partial_ratio, token_sort_ratio. But WRatio works pretty well for my usecase. So any workaround for the same would be appreciated... Thanks!

When trying to get the data of such a string 'hello 𝙎𝙈𝙈 world' using token_set_ratio(), no problems arise, but there is an error when calling process.extract().

If you remove the incomprehensible characters "SMM" from the line, then there is no error

Example:

strtest = 'hello 𝙎𝙈𝙈 world'
stroka = "word"
print(str(fuzz.token_set_ratio(stroka, strtest))) # OK
for message in process.extract(stroka, [strtest, 'sss'], limit=1): # ERROR
    pass

Error:

Traceback (most recent call last):
  File "C:\Users\Alexey\AppData\Local\Programs\Python\Python39\lib\site-packages\fuzzywuzzy\process.py", line 108, in extractWithoutOrder
    for key, choice in choices.items():
AttributeError: 'list' object has no attribute 'items'

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "C:\Users\Alexey\Documents\fuzzywuzzy\index.py", line 191, in <module>
    for message in process.extract(stroka, [strtest, 'sss'], limit=1): # ERROR
  File "C:\Users\Alexey\AppData\Local\Programs\Python\Python39\lib\site-packages\fuzzywuzzy\process.py", line 168, in extract
    return heapq.nlargest(limit, sl, key=lambda i: i[1]) if limit is not None else \
  File "C:\Users\Alexey\AppData\Local\Programs\Python\Python39\lib\heapq.py", line 531, in nlargest
    result = max(it, default=sentinel, key=key)
  File "C:\Users\Alexey\AppData\Local\Programs\Python\Python39\lib\site-packages\fuzzywuzzy\process.py", line 117, in extractWithoutOrder
    score = scorer(processed_query, processed)
  File "C:\Users\Alexey\AppData\Local\Programs\Python\Python39\lib\site-packages\fuzzywuzzy\fuzz.py", line 288, in WRatio
    partial = partial_ratio(p1, p2) * partial_scale
  File "C:\Users\Alexey\AppData\Local\Programs\Python\Python39\lib\site-packages\fuzzywuzzy\utils.py", line 38, in decorator
    return func(*args, **kwargs)
  File "C:\Users\Alexey\AppData\Local\Programs\Python\Python39\lib\site-packages\fuzzywuzzy\utils.py", line 29, in decorator
    return func(*args, **kwargs)
  File "C:\Users\Alexey\AppData\Local\Programs\Python\Python39\lib\site-packages\fuzzywuzzy\utils.py", line 47, in decorator
    return func(*args, **kwargs)
  File "C:\Users\Alexey\AppData\Local\Programs\Python\Python39\lib\site-packages\fuzzywuzzy\fuzz.py", line 47, in partial_ratio
    blocks = m.get_matching_blocks()
  File "C:\Users\Alexey\AppData\Local\Programs\Python\Python39\lib\site-packages\fuzzywuzzy\StringMatcher.py", line 58, in get_matching_blocks
    self._matching_blocks = matching_blocks(self.get_opcodes(),
ValueError: apply_edit edit operations are invalid or inapplicable

The problem There was a case where the code was using a manual file handler pitfall, where a file stream was being opened and closed manually. But since Python supports automatic stream closing using the block 'with', its better to use it instead of the manual close in order to remove a bug vector.

Solution Refactored the code to remove the manual file handler

Referring to the description of token_set_ratio in the original blog post: if the SORTED_INTERSECTION is a strict subset of STRING2, the result ratio will be 100. E.g.,

fuzz.token_set_ratio("Deep Learning", "Python Machine Learning: Machine Learning and Deep Learning with Python, scikit-learn, and TensorFlow 2")

yields 100. This is patently incorrect, and does not uphold the purported intuition ("because the SORTED_INTERSECTION component is always exactly the same, the scores increase when (a) that makes up a larger percentage of the full string, and (b) the string remainders are more similar").

Looking at fuzz._token_set, we see that it returns

max(
    [
        ratio_func(sorted_sect, combined_1to2),
        ratio_func(sorted_sect, combined_2to1),
        ratio_func(combined_1to2, combined_2to1)
    ]
)

It appears the assumption is that the string remainder will never be empty. Perhaps something like this is more appropriate:

max(
    [
        0 if sorted_sect == combined_1to2 else ratio_func(sorted_sect, combined_1to2),
        0 if sorted_sect == combined_2to1 else ratio_func(sorted_sect, combined_2to1),
        ratio_func(combined_1to2, combined_2to1)
    ]
)

since this repo seems to haven been depercated I suggest to mark it as read-only in the settings. This also displays a banner on top of the page, which may be even easier to catch than the readme …