Python softmatcher using difflib impracticably slow

I have a softmatch function (below) that takes a donor list and a new entry and looks to see if the given donor already exists.

The data is not exact, so I have to use a softmatch to determine whether a given record exists (ex: Jon Doe at 123 Sesame St. is the same as John P. Doe at 123 Sesame Street). I have this implemented with difflib, and it works; it's just slow as Christmas.

The program currently takes about two days to process 10mb of data. The profiler indicates it's the difflib operations in the softmatch function that is causing the slowness.

Is there a way to optimize my matching function to work better?

def softMatch(self, new, donors):
    #Takes new, a contribution record from a DG report, and attempts to soft match it with a record in donors
    #Returns the position of the matched record or -1 if no match 
    #Methodology
        #Name 
        #Address
        #Affiliation,Occupation,Employer not analyzed   
    #Dependences cleanAddr(str), re(from cleanAddr), difflib

    match = -1

    name = new[0]
    address = self.cleanAddr(new[1] + " " + new[2] + " " + new[3] + " " + new[4] + " " + new[5][:5])

    while address.find("  ") != -1:
        address = address.replace("  "," ")

    diff = 0.6

    for x in range(0, len(donors)):
        ratio = difflib.SequenceMatcher(None, name, donors[x].getBestName()[0]).ratio() * difflib.SequenceMatcher(None, address, donors[x].getBestAddr()).ratio()**2
        if ratio > diff:
            diff = ratio
            match = x

    return match

And the profiler output:

```
Ordered by: internal time

ncalls tottime percall cumtime percall filename:lineno(function)
3091394 53.737 0.000 66.798 0.000 difflib.py:353(find_longest_match)
368770 10.030 0.000 80.702 0.000 difflib.py:463(get_matching_blocks)
59454412 7.683 0.000 7.683 0.000 {method 'get' of 'dict' objects}
368770 6.906 0.000 10.521 0.000 difflib.py:300(__chain_b)
52104

I recommend you try different approaches:

• Use quick_ratio instead of ratio

• Apply .lower().split(' ') to the data before sending it to the SequenceMatcher

• Add a line somewhere that checks if the two strings are equal. In those cases don't call SequenceMatcher

The first approach will most likely reduce the overall run time, but decrease precision. The second approach should work pretty well, since SequenceMatcher knows how to handle lists and will match only two items: ['john', 'doe'] and ['john', 'doe'] instead of all the letters in the name.

StackExchange Code Review Q#55051, answer score: 2