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

Question

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

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

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

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

UPDATE:

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

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 тысяч имен, и занимает почти целый час.

Данные испытаний разделены.

• Имя
• Год Месяц Дата рождения

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

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

Answer 1

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

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

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

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

Вы можете использовать это utlity method нормализовать строку (не включает юникод часть, хотя):

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 для символьной клавиши n является достаточно хорошим ведром для наиболее практичного сопоставления.

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

Затем вы можете использовать что-то на линиях этого method (или модуль 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"] 

Там вы идете - все элементы (списки) в нормализованном Словаре, которые имеют более чем одно значение - это совпавшие слова.

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

• Soundex
• Metaphone
• Double Metaphone
• NYSIIS
• Caverphone
• Cologne фонетический
• MRA Codex

Answer 3

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

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

Также убедитесь, что установлен 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 для ваших выборов заранее.