向量化或加速 PANDAS 列上的 Fuzzywuzzy 字符串匹配

Question

我正在尝试在充满组织名称的 PANDAS 列中寻找潜在匹配项。我目前正在使用 iterrows() 但它在具有 ~70,000 行的数据帧上非常慢。在查看了 StackOverflow 之后，我尝试实现一个 lambda 行（应用）方法，但这似乎几乎没有加快速度，如果有的话。

数据框的前四行如下所示：

index  org_name
0   cliftonlarsonallen llp minneapolis MN
1   loeb and troper llp newyork NY
2   dauby o'connor and zaleski llc carmel IN
3   wegner cpas llp madison WI

以下代码块有效，但需要大约五天的时间来处理：

org_list = df['org_name']
from fuzzywuzzy import process
for index, row in df.iterrows():
    x = process.extract(row['org_name'], org_list, limit=2)[1]
    if x[1]>93:
        df.loc[index, 'fuzzy_match'] = x[0]
        df.loc[index, 'fuzzy_match_score'] = x[1]

实际上，对于每一行，我将组织名称与所有组织名称的列表进行比较，取前两个匹配项，然后选择第二个最佳匹配项（因为顶部匹配项将是相同的名称），然后设置一个条件分数必须高于 93 才能创建新列。我创建附加列的原因是我不想简单地替换值——我想先仔细检查结果。

有没有办法加快这个速度？我阅读了几篇博客文章和 StackOverflow 问题，这些问题讨论了“向量化”这段代码，但我的尝试失败了。我还考虑过简单地创建一个 70,000 x 70,000 Levenshtein 距离矩阵，然后从中提取信息。有没有更快的方法来为列表或 PANDAS 列中的每个元素生成最佳匹配？

Answer 1

给定您的任务，您使用 fuzz.WRatio 将 70k 个字符串相互比较，因此您总共有 4,900,000,000 个比较，这些比较中的每一个都使用 Fuzzywuzzy 内的 levenshtein 距离，这是一个 O(N*M) 操作。fuzz.WRatio 是具有不同权重的多个不同字符串匹配比率的组合。然后它选择其中的最佳比例。因此，它甚至必须多次计算 Levenshtein 距离。所以一个目标应该是通过使用一种更快的匹配算法排除一些可能性来减少搜索空间。另一个问题是对字符串进行预处理以删除标点符号并将字符串小写。虽然这是匹配所必需的（例如，大写单词变得等于小写单词），但我们可以提前执行此操作。所以我们只需要对 70k 个字符串进行一次预处理。我会用这里是RapidFuzz而不是 FuzzyWuzzy，因为它要快得多（我是作者）。

在我的实验中，以下版本的执行速度是您之前的解决方案的 10 倍以上，并应用了以下改进：

1. 它提前预处理字符串

2. 它将 score_cutoff 传递给extractOne，因此它可以跳过已经知道无法达到此比率的计算

import pandas as pd, numpy as np
from rapidfuzz import process, utils

org_list = df['org_name']
processed_orgs = [utils.default_process(org) for org in org_list]

for (i, processed_query) in enumerate(processed_orgs):
    # None is skipped by extractOne, so we set the current element to None an
    # revert this change after the comparision
    processed_orgs[i] = None
    match = process.extractOne(processed_query, processed_orgs, processor=None, score_cutoff=93)
    processed_orgs[i] = processed_query
    if match:
        df.loc[i, 'fuzzy_match'] = org_list[match[2]]
        df.loc[i, 'fuzzy_match_score'] = match[1]

以下是 RapidFuzz 最相关的改进列表，使其在此示例中比 FuzzyWuzzy 更快：

1. 它完全用 C++ 实现，而 FuzzyWuzzy 的很大一部分是用 Python 实现的

2. 在计算 levenshtein 距离时，它会考虑score_cutoff选择基于优化的实现。例如，当字符串之间的长度差异很大时，它可以在 O(1) 中退出。

3. FuzzyWuzzy 使用 Python-Levenshtein 计算两个字符串之间的相似度，它使用权重为 2 的加权 Levenshtein 距离进行替换。这是使用 Wagner-Fischer 实现的。在另一方面RapidFuzz使用基于此一bitparallel实现BitPal，这是更快

4. fuzz.WRatio结合多个其他字符串匹配算法的结果，如fuzz.ratio，fuzz.token_sort_ratio和fuzz.token_set_ratio并在加权后取最大结果。因此，whilefuzz.ratio的权重为 1 fuzz.token_sort_ratio，权重fuzz.token_set_ratio为 0.95。当score_cutoff大于 95fuzz.token_sort_ratio并且fuzz.token_set_ratio不再计算时，因为结果保证小于score_cutoff

5. 在 process.extractOne 中，RapidFuzz 尽可能避免通过 Python 调用并提前一次预处理查询。例如，BitPal 算法需要将比较的两个字符串之一存储到位向量中，该位向量占算法运行时间的很大一部分。在 process.extractOne 中，查询只存储到这个位向量一次，之后位向量被重用，使算法更快。

6. 由于extractOne 只搜索最佳匹配，它使用当前最佳匹配score_cutoff与下一个元素的比率。通过这种方式，在许多情况下，它可以通过使用 2) 对 levenshtein 距离计算的改进来快速丢弃更多元素。当它找到一个相似度为 100 的元素时，它会提前退出，因为之后找不到更好的匹配。

Answer 2

该解决方案利用apply()并应该展示合理的性能改进。请随意使用并scorer更改threshold以满足您的需求：

import pandas as pd, numpy as np
from fuzzywuzzy import process, fuzz

df = pd.DataFrame([['cliftonlarsonallen llp minneapolis MN'],
        ['loeb and troper llp newyork NY'],
        ["dauby o'connor and zaleski llc carmel IN"],
        ['wegner cpas llp madison WI']],
        columns=['org_name'])

org_list = df['org_name']

threshold = 40

def find_match(x):

  match = process.extract(x, org_list, limit=2, scorer=fuzz.partial_token_sort_ratio)[1]
  match = match if match[1]>threshold else np.nan
  return match

df['match found'] = df['org_name'].apply(find_match)

返回：

                                   org_name                                     match found
0     cliftonlarsonallen llp minneapolis MN             (wegner cpas llp madison WI, 50, 3)
1            loeb and troper llp newyork NY             (wegner cpas llp madison WI, 46, 3)
2  dauby o'connor and zaleski llc carmel IN                                             NaN
3                wegner cpas llp madison WI  (cliftonlarsonallen llp minneapolis MN, 50, 0)

如果你只想返回匹配的字符串本身，那么你可以修改如下：

match = match[0] if match[1]>threshold else np.nan

我在这里添加了 @user3483203 与列表理解相关的评论作为替代选项：

df['match found'] = [find_match(row) for row in df['org_name']]

请注意，它process.extract()旨在处理单个查询字符串并将传递的评分算法应用于该查询和提供的匹配选项。因此，您必须针对所有 70,000 个匹配选项（您当前的代码设置方式）评估该查询。因此，您将评估len(match_options)**2（或 4,900,000,000）字符串比较。因此，我认为最好的性能改进可以通过函数中更广泛的逻辑限制潜在的匹配选项来实现find_match()，例如强制匹配选项以与查询相同的字母开头等。