优化两个列表之间的元素明智的模糊匹配

Question

我有两个不同格式的公司列表（较长列表中有 > 2k 个条目）需要统一。我知道这两种格式大约 80% 的时间共享一个存根，所以我使用模糊匹配来比较两个列表：

def get_fuzz_score(str1, str2):

    from fuzzywuzzy import fuzz
    partial_ratio = fuzz.partial_ratio(str1, str2)
    return partial_ratio


a = ['Express Scripts', 'Catamaran Corp', 'Banmedica SA (96.7892%)', 'WebMD', 'ODC', 'Caremerge LLC (Stake%)']
b = ['Doctor on Demand', 'Catamaran', 'Express Scripts Holding Corp', 'ODC, Inc.', 'WebMD Health Services', 'Banmedica']

for i in b:
    for j in a:
        if get_fuzz_score(i, j) > 80:
            # process

对于如何优化此任务以提高性能（例如，不必使用 2 个 for 循环）的想法，我将不胜感激。

Answer 1

我假设您同时安装了 fuzzywuzzy 和 python-Levenshtein。第二个包的安装失败，因此我收到一条消息：

warnings.warn('Using slow pure-python SequenceMatcher. Install python-Levenshtein to remove this warning')

您可以使用 itertools.product 创建笛卡尔积：

from itertools import product
from fuzzywuzzy import fuzz

def get_fuzz_score(str1, str2):
    partial_ratio = fuzz.partial_ratio(str1, str2)
    return partial_ratio


a = ['Express Scripts', 'Catamaran Corp', 'Banmedica SA (96.7892%)', 'WebMD', 'ODC', 'Caremerge LLC (Stake%)']
b = ['Doctor on Demand', 'Catamaran', 'Express Scripts Holding Corp', 'ODC, Inc.', 'WebMD Health Services', 'Banmedica']

for first, second in product(a, b):
    if get_fuzz_score(first, second) > 80:
        # process

如果您的功能 get_fuzz_score 没有增长，您可以将其废弃：

from itertools import product
from fuzzywuzzy import fuzz  # 

a = ['Express Scripts', 'Catamaran Corp', 'Banmedica SA (96.7892%)', 'WebMD', 'ODC', 'Caremerge LLC (Stake%)']
b = ['Doctor on Demand', 'Catamaran', 'Express Scripts Holding Corp', 'ODC, Inc.', 'WebMD Health Services', 'Banmedica']

for first, second in product(a, b):
    if fuzz.partial_ratio(first, second) > 80:
        pass  # process

Answer 2

首先，我会将导入 from fuzzywuzzy import fuzz 从函数移动到文件的开头。

接下来，您似乎想要检查每个元素，所以您无论如何都要比较 all2all，但我没有看到简单的解决方法。

如果数据是 'nice'，那么您可以进行一些简单的启发式操作，例如在第一个字母上（来自您发布的示例 - 但这取决于数据）。

此致

P.s。如果我的分数足够高，我会发表评论。

Answer 3

fuzzywuzzy 提供了一个 process.extract* 系列函数来帮助解决这个问题，例如：

from fuzzywuzzy import process

a = ['Express Scripts', 'Catamaran Corp', 'Banmedica SA (96.7892%)', 'WebMD', 'ODC', 'Caremerge LLC (Stake%)']
b = ['Doctor on Demand', 'Catamaran', 'Express Scripts Holding Corp', 'ODC, Inc.', 'WebMD Health Services', 'Banmedica']

for name in a:
    print(name, process.extract(name, b, limit=3))

将打印出 a 中的每个名称以及 b 中的三个最佳匹配项。

这仍然是 O(n**2)，但是因为这个库是开源代码，你可以看到 extract 是如何定义的，也许只做一次 preprocessing 而不是每次希望加快速度

优化两个列表之间的元素明智的模糊匹配

Optimize element wise fuzzy match between two lists

python

fuzzy-search

fuzzywuzzy