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

Ответ 1

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

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

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

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

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

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 SequenceMatcher and and jellyfish 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

Ответ 2

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

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

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

to:

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

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

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

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

Ответ 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-дерево для этого, возможно, сам в той же ситуации)

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