String Similarity using fuzzywuzzy on big data

Question

I have a file in which I was to check the string similarity within the names in a particular column. I use fuzzywuzzy token sort ratio algorithm as it is required for my use case. here is the code, is there a way to speed it up? It is taking a lot of time for 30000 records.

import csv
import itertools
import pandas as pd
from fuzzywuzzy import fuzz

data = pd.read_csv('D:\\Sim_Input.csv')

Dishes = data['Product_Name']

threshold_ratio = 85

with open('D:\\Sim_Score.csv', 'w') as f1:
    writer = csv.writer(f1, delimiter='\t', lineterminator='\n', )
    writer.writerow(['tag4'])
    for str_1, str_2 in itertools.permutations(Dishes, 2):
        list = []
        ratio = (fuzz.token_sort_ratio(str_1, str_2))
        if ratio > threshold_ratio:
            row = (str_1, str_2, ratio)
            list.append(row)
            print(list)
            writer.writerow(list)

I need the output in a csv file with the names of ItemA, ItemB and similarity score, where the similarity should be above 85.

Answer 1

To avoid processing each dish so many times, you can use this to process them only 1 time:

dishes = ["pizza with bacon", "pizza with extra cheese", "vegetarian pizza", "cheese and bacon pizza", "bacon with pizza"]

processedDishes = []

for dish in dishes:
    processedDishes.append(fuzz._process_and_sort(dish, True, True))

for dish1, dish2 in itertools.combinations(enumerate(processedDishes), 2):  
    if fuzz.ratio(dish1[1], dish2[1]) >= 85:
        print(dishes[dish1[0]], dishes[dish2[0]])

You can then combine this with @scnerd solution to add multiprocessing

If you know your data is all the same type, you can further optimize it:

dishes = ["pizza with bacon", "pizza with extra cheese", "vegetarian pizza", "cheese and bacon pizza", "bacon with pizza"]

processedDishes = []
matchers = []

for dish in dishes:
    if dish:
        processedDish = fuzz._process_and_sort(dish, True, True)
        processedDishes.append(processedDish)
        matchers.append(fuzz.SequenceMatcher(None, processedDish))


for dish1, dish2 in itertools.combinations(enumerate(processedDishes), 2):
    matcher = matchers[dish1[0]]
    matcher.set_seq2(dish2[1])
    ratio = int(round(100 * matcher.ratio()))

    if ratio >= 85:
        print(dishes[dish1[0]], dishes[dish2[0]])

Update: checked how these ratios are calculated, here is a more efficient answer that avoids a lot of checks between pairs:

dishes = ["pizza with bacon", "pizza with extra cheese", "vegetarian pizza", "cheese and bacon pizza", "bacon with pizza", "a"]


processedDishes = []
matchers = []

for dish in dishes:
    if dish:
        processedDish = fuzz._process_and_sort(dish, True, True)
        processedDishes.append({"processed": processedDish, "dish": dish})


processedDishes.sort(key= lambda x: len(x["processed"]))

for idx, dish in enumerate(processedDishes):
    length = len(dish["processed"])
    matcher = fuzz.SequenceMatcher(None, dish["processed"])
    for idx2 in range(idx + 1, len(processedDishes)):
        dish2 = processedDishes[idx2]
        if 2 * length / (length + len(dish2["processed"])) < 0.85: # upper bound
            break

        matcher.set_seq2(dish2["processed"])

        if matcher.quick_ratio() >= 0.85 and matcher.ratio() >= 0.85: # should also try without quick_ratio() check
            print(dish["dish"], dish2["dish"])

Answer 2

The first algorithmic recommendation is to use itertools.combinations instead of .permutations, since you don't care about order. This assumes fuzz.token_sort_ratio(str_1, str_2) == fuzz.token_sort_ratio(str_2, str_1). There are half as many combinations as there are permutations, so that gives you a free 2x speedup.

This code also lends itself easily to parallelization. On an i7 (8 virtual cores, 4 physical), you could probably expect this to give you ~4-8x speedup, but that depends on a lot of factors. The least intrusive way to do this is to use multiprocessing.Pool.map or .imap_unordered:

import multiprocessing as mp

def ratio(strings):
    s1, s2 = strings
    return s1, s2, fuzz.token_sort_ratio(s1, s2)

with open('D:\\Sim_Score.csv', 'w') as f1:
    writer = csv.writer(f1, delimiter='\t', lineterminator='\n', )
    writer.writerow(['tag4'])

    with mp.Pool() as pool:
        for s1, s2, r in pool.imap_unordered(ratio, itertools.combinations(Dishes, 2)):
            if r > threshold_ratio:
                writer.writerow([(s1, s2, r)])

All told, I'd expect these changes to give you 5-10x speedup, depending heavily on the number of cores you have available.

For reference, a generator comprehension version of this might look something like:

with mp.Pool() as pool:
    writer.writerows((s1, s2, r)
                     for s1, s2, r in pool.imap_unordered(ratio, itertools.combinations(Dishes, 2))
                     if r > threshold_ratio)

That version has a some, but very little, performance improvement over the non-comprehension version, and IMO is harder to read/maintain.

One other minor thing I noticed in testing my code was that fuzzywuzzy recommends installing python-Levenshtein in order to run faster; when I did so, it ran about 20x slower than when it used the built-in SequenceMatcher. When I uninstalled python-Levenshtein it got fast again. That seems very odd to me, but it's certainly something worth trying.

Finally, if performance is important, you could consider digging into what fuzz.token_sort_ratio does to see if you could remove some repeated work. For example, it's tokenizing and sorting each string again every time you pass it in, so maybe you could pre-tokenize/sort the strings and only run the ratio logic inside the main loop. A quick dig tells me that token_sort_ratio is two main steps:

1. Preprocess each string using fuzz._process_and_sort

2. Run fuzz.partial_ratio against the processed strings

I'm not able to get this to run faster at the moment, but I'll edit and update this answer if I can get that approach to work well.