My solution with references below: Apply fuzzy matching across a dataframe column and save results in a new column
df.loc[:,'fruits_copy'] = df['fruits']
compare = pd.MultiIndex.from_product([df['fruits'],
df['fruits_copy']]).to_series()
def metrics(tup):
return pd.Series([fuzz.ratio(*tup),
fuzz.token_sort_ratio(*tup)],
['ratio', 'token'])
compare.apply(metrics)
ratio token
apple apple 100 100
apples 91 91
orange 36 36
apple tree 67 67
oranges 33 33
mango 20 20
apples apple 91 91
apples 100 100
orange 33 33
apple tree 62 62
oranges 46 46
mango 18 18
orange apple 36 36
apples 33 33
orange 100 100
apple tree 25 25
oranges 92 92
mango 55 55
apple tree apple 67 67
apples 62 62
orange 25 25
apple tree 100 100
oranges 24 24
mango 13 13
oranges apple 33 33
apples 46 46
orange 92 92
apple tree 24 24
oranges 100 100
mango 50 50
mango apple 20 20
apples 18 18
orange 55 55
apple tree 13 13
oranges 50 50
mango 100 100
Answer from ah bon on Stack Overflowpython - Pandas: Matching string using fuzzywuzzy and retrieve the value of other column - Stack Overflow
python - Match similar column elements using pandas and fuzzwuzzy - Stack Overflow
How do I compare strings in two data frames using fuzzywuzzy?
python - Using FuzzyMatching Algorithm to determine whether there are similar words in Name column - Stack Overflow
I would suggest reading your Excel file with pandas and pd.read_excel(), and then using fuzzywuzzy to perform your matching, for example:
import pandas as pd
from fuzzywuzzy import process, fuzz
df = pd.DataFrame([['9Com(panynAm9e00'],
['NikE4'],
['Mitrosof2']],
columns=['Name'])
known_list = ['Microsoft','Company Name','Nike']
def find_match(x):
match = process.extractOne(x, known_list, scorer=fuzz.partial_token_sort_ratio)[0]
return match
df['match found'] = [find_match(row) for row in df['Name']]
Yields:
Name match found
0 9Com(panynAm9e00 Company Name
1 NikE4 Nike
2 Mitrosof2 Microsoft
I imagine numbers are not very common in actual company names, so an initial filter step will help immensely going forward, but here is one implementation that should work relatively well even without this. A bag-of-letters (bag-of-words) approach, if you will:
- convert everything (col 1 and 2) to lowercase
- For each known company in column 2, store each unique letter, and how many times it appears (count) in a dictionary
- Do the same (step 2) for each entry in column 1
- For each entry in col 1, find the closest bag-of-letters (dictionary from step 2) from the list of real company names
The dictionary-distance implementation is up to you.
I have two data frames (df1 and df2). df1 contains a column with around 100 company names. I want to check to what extent they match with the company names in df2 (of which there are around 1,000). The columns in both data frames are entitled ‘Name’.
I would like the output to show df1[‘Name’] and the closest matching company name in df2 and the score.
I can use fuzzywuzzy to compare two individual company names and get a score. For example
fuzz.token_sort_ratio(‘Amazon plc’, ‘Amazon PLC’)
However, I’m struggling to work out how to compare a column of strings against another in a separate data frame.
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"])
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:
Preprocess each string using
fuzz._process_and_sortRun
fuzz.partial_ratioagainst 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.