优化两个列表的元素模糊匹配

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

我假设你同时安装了fuzzyfuzzy和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\u fuzz\u 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

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，而不是每次都做，这可能会加快速度