Векторизация или ускорение нечеткого сопоставления строк в столбце PANDAS

Учитывая вашу задачу, вы сравниваете 70 тыс. строк друг с другом с помощью fuzz.WRatio, поэтому у вас есть в общей сложности 4 900 000 000 сравнений, причем каждое из этих сравнений использует расстояние Левенштейна внутри fuzzywuzzy, что является операцией O (N * M). fuzz.WRatio представляет собой комбинацию нескольких различных коэффициентов соответствия строк, которые имеют разные веса. Затем он выбирает наилучшее соотношение между ними. Поэтому ему даже приходится несколько раз вычислять расстояние Левенштейна. Таким образом, одна цель должна состоять в том, чтобы уменьшить пространство поиска, исключив некоторые возможности, используя более быстрый алгоритм сопоставления. Другая проблема заключается в том, что строки предварительно обрабатываются для удаления знаков препинания и перевода строк в нижний регистр. Хотя это требуется для сопоставления (например, слово в верхнем регистре становится равным слову в нижнем регистре), мы можем сделать это заранее. Таким образом, нам нужно предварительно обработать 70 тыс. строк только один раз. Я буду использовать здесь 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. Это реализовано с помощью Вагнера-Фишера. 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) во многих случаях. Когда он находит элемент со сходством 100, он завершает работу раньше, поскольку после этого не может быть лучшего совпадения.

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

Использование iterrows() не рекомендуется для фреймов данных, вместо этого вы можете использовать apply(). Но вряд ли это сильно ускорило бы процесс. Что медленно, так это метод извлечения fuzzywuzzy, в котором ваш ввод сравнивается со всеми 70 тыс. строк (методы расстояния между строками требуют больших вычислительных ресурсов). Поэтому, если вы намерены придерживаться fuzzywuzzy, одним из решений будет ограничение поиска, например, только теми, у которых одна и та же первая буква. Или, если у вас есть другой столбец в ваших данных, который можно использовать в качестве подсказки (штат, город, ...)