10
\$\begingroup\$

I have a dictionary with author names as keys and values of None. I want to use fuzzywuzzy to compare these author names to see if there are similar ones that I can combine.

So far I am using two dictionaries (they have the same data in both of them, and ideally I would just use one) and then using a double for loop. I want to optimize it further, and I was thinking of using Dictionary Composition, but I couldn't figure out how to get that working with my fuzzy compare logic.

import uuid
from fuzzywuzzy import fuzz

authorToDelete = {}
dictOfAllData1 = {'Trevor Jacobs': None, 'Josh Francis': None, 'Marcie Lank': None, 'Marcie H. Lank': None}
dictOfAllData2 = {'Trevor Jacobs': None, 'Josh Francis': None, 'Marcie Lank': None, 'Marcie H. Lank': None}

for key in dictOfAllData1:
    for key2 in dictOfAllData2:
        str1 = ' '.join(key.split()) #some spaces are different so I handle those here
        str2 = ' '.join(key2.split())
        ratio = fuzz.ratio(str1, str2)
        if fuzz.ratio(str1, str2) > 85 and dictOfAllData1[key] == None:
            dictOfAllData1[key] = str(uuid.uuid1())
        elif ratio > 85:
            if str1 != str2:
                authorToDelete[key2] = None
            else:
                dictOfAllData1[key] = str(uuid.uuid1())

for deleteMe in authorToDelete:
    dictOfAllData1.pop(deleteMe)

print(dictOfAllData1)

#Output is: {'Trevor Jacobs': 'edb6e3d8-3898-11ea-9b62-784f4397bfaf', 'Josh Francis': 'edb6e892-3898-11ea-9b62-784f4397bfaf', 'Marcie Lank': 'edb6eaea-3898-11ea-9b62-784f4397bfaf'}

This is the code I have so far. It works, but it takes longer than I think it should (about 4 seconds with a dictionary of ~700 keys, and about 80 seconds with a dictionary of ~2,700 keys)

My question is how can I make this more efficient? Is there a way I can use if in dict or something like that instead of my second for loop?

I originally posted this on StackOverflow

\$\endgroup\$
7
\$\begingroup\$

Before speaking about the actual algorithm, let me hint you at the official Style Guide for Python Code (often just called PEP 8), a set of guidelines to write idiomatic-looking Python code. A core takeaway of the read should be, that in Python lower_case_with_underscores is the preferred way to name variables and functions. Fortunately you don't have to remember all those rules. There is good tool support for style and also static code checking in Python. A non-exhaustive list can be found here on this post here on Code Review Meta. I personally most often use flake8 and pylint from that list.

With that out of the way, let's have a look at the code. First, you don't need to have two copies of your dict. Also, the whitespace normalization inside the loop is run more often than needed, because it is calculated several times for every key. Fortunately, it's easy to solve both of those problems:

keys = list(dict_of_all_data.keys())
authors = {key: ' '.join(key.split()) for key in keys}

keys now holds all author names from the original dict, whereas authors holds their normalized versions. Maybe you should also consider to convert all the names to upper-/lowercase in order to make it even more robust, but you'll have to see yourself if that's worth it.

Looking at the fuzzywuzzy documentation of fuzzywuzzy.fuzz reveals that it basically seems to be a wrapper around difflib.SequenceMatcher. From a few quick experiments I got the impression that the following is true:

fuzzywuzzy.fuzz(str1, str2) == fuzzywuzzy.fuzz(str2, str1)

With that in mind, the amount of computations can be cut down even more, by avoiding duplicate comparisons. Since you gave no special reason for using UUIDs, I skipped them in the reworked code for the moment.

dict_of_all_data = {'Trevor Jacobs': None, 'Josh Francis': None, 'Marcie Lank': None, 'Marcie H. Lank': None}

keys = list(dict_of_all_data.keys())
authors = {key: ' '.join(key.split()) for key in keys}
authors_to_delete = []

for i, key1 in enumerate(keys, 1):
    author1 = authors[key1]
    for key2 in keys[i:]:   # this helps to avoid duplicate comparison
        author2 = authors[key2]
        ratio = fuzz.ratio(author1, author2)
        if ratio > 85 and dict_of_all_data[key1] is None:
            dict_of_all_data[key1] = True   # likely not even necessary
            authors_to_delete.append(key2)

for delete_me in authors_to_delete:
    dict_of_all_data.pop(delete_me)

print(dict_of_all_data)

As a bonus, one should wrap the code into a function to nicely separate it from the rest of the code. Whether or not you want to convert this code into a function, it would be a good idea to replace the magic value 85 with a parameter/constant with a meaningful name.

Grajdeanu Alex presents a similar idea in his answer, but uses itertools.combinations instead of doing the de-duplication manually as I suggested above.

\$\endgroup\$
5
\$\begingroup\$

WARNINGS

First of all, let's listen to the warning we get when we run this and get rid off it:

UserWarning: Using slow pure-python SequenceMatcher. Install python-Levenshtein to remove this warning warnings.warn('Using slow pure-python SequenceMatcher. Install python-Levenshtein to remove this warning')

You can fix that by installing the mentioned package:

pip install python-Levenshtein

I'm not sure how much it'll improve the speed, but it's usually a good idea to listen to warnings and try to fix them.


Your code returns wrong data!

Shouldn't you only return "Marcie Lank" (or the other name that's matching her) in the output since she's the only one with a ratio over 85?

Having the above in mind, I'd do the following:

  • use itertools.combinations which will pair each element with each other element in the iterable only once.
  • add only the authors with ratio > 85 to the new dictionary and assign an uuid() to it
  • follow PEP8 style-guide
import itertools
import uuid

from fuzzywuzzy import fuzz


def process_authors(max_ratio=85):
    """Compare authors against each other and return the ones with
    a ratio greater than 85... etc

    :return: (dict) A dictionary containing ... etc
    """

    all_authors = {
        'Trevor Jacobs': None,
        'Josh Francis': None,
        'Marcie Lank': None,
        'Marcie H. Lank': None
    }
    result = {}

    for author_1, author_2 in itertools.combinations(all_authors, 2):
        author_1, author_2 = " ".join(author_1.split()), " ".join(author_2.split())
        ratio = fuzz.ratio(author_1, author_2)
        if ratio > max_ratio and all_authors[author_1] not in result:
            result[author_1] = str(uuid.uuid1())

    return result


print(process_authors())

{'Marcie Lank': '0342fa08-38a7-11ea-905b-9801a797d077'}

PEP8 aspects:

  • always use docstrings;
  • variable names should be snake_cased. The same goes for function names
  • In Python, the == operator compares the values of both the operands and checks for value equality. Whereas is operator checks whether both the operands refer to the same object or not.

In my opinion, the use of a dict to store the initial authors is a bit overkill since you're not using any property of that. I'd just store all the authors in a list.


About timings

Oh yes, with the new code, it takes ~1 second to process 700 items and ~14 seconds to process a 2700 items dict so there's also that ^_^. It probably can be further improved but I'll let that to you or other reviewers.

\$\endgroup\$
  • \$\begingroup\$ Thank you so much for the through response. I wasn't totally clear in my post, but I actually want to return all of the authors in the dictionary, but if there is a match then I want to only return one of them (arbitrarily chosen). I'll probably write out all of the matches that fuzzy finds, just to spot check them. With that being said, the function and other information you provided are very helpful, and I am going to try implementing it now. \$\endgroup\$ – Trevor Allen Jan 16 at 21:47
  • 1
    \$\begingroup\$ itertools is so useful, somehow I still manage to forget about it ;-) \$\endgroup\$ – AlexV Jan 16 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.