Fuzzywuzzy比较两个长度不等的字符串列表，并保存多个相似度指标

Question

我试图比较两个字符串列表并在两个列表之间产生相似性度量。两个列表的长度不等，一个大约是50000个，另一个大约是3000个。

但这里有两个MWE数据帧与我的数据相似:

forbes = pd.DataFrame(
{
"company_name": [
"Deloitte",
"PriceWaterhouseCoopers",
"KPMG",
"Ernst & Young",
"intentionall typo company XYZ",
],
"revenue": [100, 200, 300, 250, 400],
}
)
sf = pd.DataFrame(
{"salesforce_name": ["Deloite", "PriceWaterhouseCooper"], "CEO": ["John", "Jane"]}
)

下面是我如何生成相似性度量。我使用了两个for循环来计算每个可能的字符串组合之间的相似性，我的实际数据是:50,000 * 3,000 = 1.5亿。这是很多，我觉得有一个更聪明的方法，但不知道那是什么。

这是我的实现:

from fuzzywuzzy import fuzz
scores = pd.DataFrame()
for friend in forbes["company_name"]:
for address in sf["salesforce_name"]:
r = fuzz.ratio(friend, address)  # Levenshtein distance
pr = fuzz.partial_ratio(friend, address)  # partial ratio
tsr = fuzz.token_sort_ratio(friend, address)  #
tser = fuzz.token_set_ratio(friend, address)  # ignores duplicated words
if r > 80 or pr > 80 or tsr > 80 or tser > 80:
scores = pd.concat(
[
scores,
pd.DataFrame.from_records(
[
{
"forbes_company": friend,
"salesforce_company": address,
"r": r,
"pr": pr,
"tsr": tsr,
"tser": tser,
}
]
),
]
)

Answer 1

使用以下玩具数据帧(每个数据帧随机包含1000行单词):

from random import choice
import pandas as pd
import requests

response = requests.get("https://www.mit.edu/~ecprice/wordlist.10000")
WORDS = [word.decode("utf-8") for word in response.content.splitlines()]
fbs = pd.DataFrame(
{
"forbes_name": [choice(WORDS) for _ in range(5_000)],
}
)
sf = pd.DataFrame({"salesforce_name": [choice(WORDS) for _ in range(5_000)]})

您的代码在157秒内输出以下数据帧(平均运行10次):

print
forbes_name salesforce_name  ratio  token_set_ratio  token_sort_ratio  
0       salad           salad    100              100               100   
1   scientist       scientist    100              100               100   
2   scientist       scientist    100              100               100   
3      person        personal     86               86                86   
4     analyst         analyst    100              100               100 
...  
partial_ratio  
0            100  
1            100  
2            100  
3            100  
4            100
...

加速的一种方法是不要一次评估所有比率，而是在每次运行后，以递归的方式在减少的数据集上依次评估，以便模糊化。比率(最快的一个)计算所有可能的组合，然后模糊。Token_set_ratio仅适用于组合<80带绒毛。比率等。

一旦确定了相似的行，您只需填写它们上缺失的度量(而不是所有可能的组合)。

要做到这一点，您可以定义以下帮助函数:

from fuzzywuzzy import fuzz

def get_similar_values(s, other_s, t):
funcs = [
fuzz.partial_ratio,
fuzz.token_sort_ratio,
fuzz.token_set_ratio,
fuzz.ratio,
]  # ordered from slowest (partial_ratio) to fastest (ratio, which will run first)
def evaluate(funcs, series, other_series, threshold, scores=None):
if not funcs:
return scores
scores = scores or []
idx = []
other_idx = []
func = funcs.pop()
for i, val in enumerate(series):
for j, other_val in enumerate(other_series):
if (score := func(val, other_val)) > threshold:
scores.append(
{
series.name: val,
other_series.name: other_val,
func.__name__: score,
}
)
idx.append(i)
other_idx.append(j)
series = series.drop(idx).reset_index(drop=True)
other_series = other_series.drop(other_idx).reset_index(drop=True)
return evaluate(funcs, series, other_series, threshold, scores)
return evaluate(funcs, s, other_s, t)

def add_missing_metrics(similar_values):
for func in [
fuzz.token_set_ratio,
fuzz.token_sort_ratio,
fuzz.partial_ratio,
fuzz.ratio,
]:
for one_pair in similar_values:
if func.__name__ not in one_pair.keys():
one_pair[func.__name__] = func(
one_pair["forbes_name"], one_pair["salesforce_name"]
)
return similar_values

:

similar_values = get_similar_values(fbs["forbes_name"], sf["salesforce_name"], 80)
similar_values = add_missing_metrics(similar_values)
df = pd.DataFrame.from_records(similar_values)

这将产生与之前相同的数据帧，但是在58秒内(平均运行10次)，~快2.5倍.

Answer 2

除了@Laurent提出的改进之外，您可以将fuzzywuzzy的使用替换为rapidfuzz。这很简单，只需将导入替换为:

from rapidfuzz import fuzz

在我的机器上实现了以下运行时:

实现	时间
原始实现	6m 16s
laurent实施	55 s
原始实现+ rapidfuzz	2m 48s
laurens实现+ rapidfuzz	8s