Skip to main content
 首页 » 编程设计

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

2024年12月31日22xiaohuochai

我正在尝试在充满组织名称的 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 列中的每个元素生成最佳匹配?

请您参考如下方法:

鉴于您的任务是使用 fuzz.WRatio 相互比较 70k 个字符串,因此您总共有 4,900,000,000 次比较,其中每一次比较都使用 fuzzywuzzy 内的编辑距离,这是一个 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. 在计算编辑距离时,它会考虑 score_cutoff 以选择基于优化的实现。例如。当字符串之间的长度差异很大时,它可以在 O(1) 中退出。

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

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

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

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