Оптимизация нечеткого совпадения между двумя списками - PullRequest
Новая
       45

Оптимизация нечеткого совпадения между двумя списками

1 голос
/ 21 октября 2019

У меня есть два списка компаний (более 2 тыс. Записей в длинном списке) в разных форматах, которые мне нужно объединить. Я знаю, что оба формата имеют заглушку примерно в 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 для циклов).

Ответы [ 3 ]

3 голосов
/ 21 октября 2019

во-первых, я бы переместил импорт from fuzzywuzzy import fuzz из функции в начало файла.

Далее, похоже, что вы хотите проверить каждый элемент, так что вы все равно сравниваете all2all, и я нене вижу простого обходного пути, что.

Если данные «хороши», вы могли бы сделать некоторую простую эвристику, например, по первой букве (из примеров, которые вы опубликовали - но это зависит от данных).

С уважением

Ps Я бы прокомментировал, если бы мой счет был достаточно высоким.

2 голосов
/ 21 октября 2019

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, и, возможно, просто выполните предварительную обработку один раз, а не каждый раз, что, как мы надеемся, ускоритвещи много

1 голос
/ 21 октября 2019

Полагаю, вы установили как fuzzywuzzy, так и python-Levenshtein. Установка второго пакета не удалась, и поэтому я получил сообщение:

warnings.warn («Использование медленного чистого Python SequenceMatcher. Установите python-Levenshtein, чтобы удалить это предупреждение»)

Вы можете использовать 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
...