Нечеткое совпадение строк в Python

Question

У меня есть 2 списка из более чем миллиона имен с немного другими соглашениями об именах. Цель здесь - сопоставить те записи, которые похожи, с логикой 95% достоверности.

Мне стало известно, что есть библиотеки, которые я могу использовать, такие как модуль FuzzyWuzzy в Python.

Однако, с точки зрения обработки, кажется, что потребуется слишком много ресурсов, чтобы каждая строка в 1 списке сравнивалась с другой, что в этом случае, по-видимому, требует 1 миллион, умноженный на еще один миллион итераций.

Есть ли другие более эффективные методы для этой проблемы?

ОБНОВИТЬ:

Поэтому я создал функцию группирования и применил простую нормализацию для удаления пробелов, символов и преобразования значений в строчные буквы и т. Д.

for n in list(dftest['YM'].unique()):
    n = str(n)
    frame = dftest['Name'][dftest['YM'] == n]
    print len(frame)
    print n
    for names in tqdm(frame):
            closest = process.extractOne(names,frame)

Используя питонов панда, данные загружаются в более мелкие группы, сгруппированные по годам, а затем с помощью модуля FuzzyWuzzy, process.extractOne используется, чтобы получить лучший матч.

Результаты все еще несколько разочаровывают. Во время теста приведенный выше код используется для тестового фрейма данных, содержащего только 5 тысяч имен, и занимает почти целый час.

Тестовые данные разделены на.

• название
• Год месяц рождения

И я сравниваю их по ведрам, где их YM находятся в одном ведре.

Может ли проблема быть из-за модуля FuzzyWuzzy, который я использую? Ценю любую помощь.

Answer 1

Здесь возможны несколько уровней оптимизации, чтобы превратить эту проблему из O(n^2) в меньшую временную сложность.

• Предварительная обработка: сортировка списка в первом проходе, создание выходной карты для каждой строки, ключ для карты может быть нормализованной строкой. Нормализации могут включать в себя:

  • преобразование в нижний регистр,
  • без пробелов, удаление специальных символов,
  • если возможно, преобразуйте юникод в эквиваленты ascii, используйте модуль unicodedata.normalize или unidecode)

  Это приведет к "Andrew H Smith", "andrew h. smith", "ándréw h. smith" генерировать тот же ключ "andrewhsmith"и уменьшит ваш набор миллионов имен до меньшего набора уникальных / похожих сгруппированных имен.

Вы можете использовать этот метод utlity для нормализации вашей строки (не включая часть юникода):

def process_str_for_similarity_cmp(input_str, normalized=False, ignore_list=[]):
    """ Processes string for similarity comparisons , cleans special characters and extra whitespaces
        if normalized is True and removes the substrings which are in ignore_list)
    Args:
        input_str (str) : input string to be processed
        normalized (bool) : if True , method removes special characters and extra whitespace from string,
                            and converts to lowercase
        ignore_list (list) : the substrings which need to be removed from the input string
    Returns:
       str : returns processed string
    """
    for ignore_str in ignore_list:
        input_str = re.sub(r'{0}'.format(ignore_str), "", input_str, flags=re.IGNORECASE)

    if normalized is True:
        input_str = input_str.strip().lower()
        #clean special chars and extra whitespace
        input_str = re.sub("\W", "", input_str).strip()

    return input_str

• Теперь подобные строки уже будут лежать в том же сегменте, если их нормализованный ключ такой же.

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

• Bucketing: Вам действительно нужно сравнить 5-символьную клавишу с 9-символьной, чтобы увидеть, соответствует ли она 95%? Нет, ты не. Таким образом, вы можете создавать группы, соответствующие вашим строкам. например, 5 имен символов будут сопоставляться с 4-6 именами символов, 6 именами символов с 5-7 символами и т. д. Пределы n+1,n-1 символов для символьной клавиши являются достаточно хорошим сегментом для наиболее практического соответствия.

• Начальное совпадение: большинство вариантов имен будут иметь одинаковый первый символ в нормализованном формате (например, Andrew H Smith, ándréw h. smith, а также Andrew H. Smeeth генерировать ключи andrewhsmith,andrewhsmith, а также andrewhsmeeth соответственно. Они обычно не будут отличаться по первому символу, поэтому вы можете запустить сопоставление для ключей, начинающихся с a на другие ключи, которые начинаются с aи попадают в ведра длины. Это сильно уменьшит ваше время соответствия. Нет необходимости подбирать ключ andrewhsmith в bndrewhsmith как таковое изменение имени с первой буквой будет существовать редко.

Затем вы можете использовать что-то в строках этого метода (или модуль FuzzyWuzzy), чтобы найти процент сходства строк, вы можете исключить один из jaro_winkler или difflib для оптимизации скорости и качества результата:

def find_string_similarity(first_str, second_str, normalized=False, ignore_list=[]):
    """ Calculates matching ratio between two strings
    Args:
        first_str (str) : First String
        second_str (str) : Second String
        normalized (bool) : if True ,method removes special characters and extra whitespace
                            from strings then calculates matching ratio
        ignore_list (list) : list has some characters which has to be substituted with "" in string
    Returns:
       Float Value : Returns a matching ratio between 1.0 ( most matching ) and 0.0 ( not matching )
                    using difflib's SequenceMatcher and and jellyfish's jaro_winkler algorithms with
                    equal weightage to each
    Examples:
        >>> find_string_similarity("hello world","Hello,World!",normalized=True)
        1.0
        >>> find_string_similarity("entrepreneurship","entreprenaurship")
        0.95625
        >>> find_string_similarity("Taj-Mahal","The Taj Mahal",normalized= True,ignore_list=["the","of"])
        1.0
    """
    first_str = process_str_for_similarity_cmp(first_str, normalized=normalized, ignore_list=ignore_list)
    second_str = process_str_for_similarity_cmp(second_str, normalized=normalized, ignore_list=ignore_list)
    match_ratio = (difflib.SequenceMatcher(None, first_str, second_str).ratio() + jellyfish.jaro_winkler(unicode(first_str), unicode(second_str)))/2.0
    return match_ratio

Answer 2

Вы должны проиндексировать или нормализовать строки, чтобы избежать запуска O(n^2). По сути, вы должны сопоставить каждую строку с нормальной формой и создать обратный словарь со всеми словами, связанными с соответствующими нормальными формами.

Давайте рассмотрим, что нормальные формы "мира" и "слова" одинаковы. Итак, сначала создайте обратный словарь Normalized -> [word1, word2, word3], например:

"world" <-> Normalized('world')
"word"  <-> Normalized('wrd')

to:

Normalized('world') -> ["world", "word"]

Вот и все - все элементы (списки) в нормализованном диалоге, имеющие более одного значения, - это совпадающие слова.

Алгоритм нормализации зависит от данных, то есть слов. Рассмотрим один из многих:

• Саундэкс
• Metaphone
• Двойной метафон
• NYSIIS
• Caverphone
• Кельн Фонетическая
• Кодекс MRA

Answer 3

Обратите внимание, что в настоящее время для process.extractOne по умолчанию используется метод fuzzywuzzy, то есть WRatio, который на данный момент является самым медленным из их алгоритмов, а процессор по умолчанию - utils.full_process. Если вы передадите, скажем, fuzz.QRatio в качестве своего бомбардира, он пойдет намного быстрее, но не так сильно, в зависимости от того, что вы пытаетесь сопоставить. Может быть, просто хорошо для имен, хотя. Лично мне повезло с token_set_ratio, который по крайней мере несколько быстрее, чем WRatio. Вы также можете заранее запустить utils.full_process() для всех своих вариантов, а затем запустить его с fuzz.ratio в качестве счетчика и процессора = Нет, чтобы пропустить этап обработки. (см. ниже) Если вы просто используете базовую функцию отношения, то, возможно, fuzzywuzzy, вероятно, излишне. Кстати, у меня есть порт JavaScript (fuzzball.js), где вы также можете предварительно рассчитать наборы токенов и использовать их вместо пересчета каждый раз.)

Это не сокращает количество сравнений, но помогает. (BK-дерево для этого возможно? Я сам изучал ту же ситуацию)

Также убедитесь, что у вас установлен python-Levenshtein, чтобы вы использовали более быстрые вычисления.

** Поведение ниже может измениться, открыть обсуждаемые вопросы и т. Д.**

fuzz.ratio не запускает полный процесс, а функции token_set и token_sort принимают параметр full_process=False, и если вы не установите Processor=None, функция extract все равно попытается запустить полный процесс. Можно использовать партиал functools, чтобы передать в fuzz.token_set_ratio значение full_process=False в качестве вашего счетчика и заранее запустить utils.full_process для вашего выбора.