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

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

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

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

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

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

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

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

• Начальное совпадение. Большинство вариантов имен будут иметь одинаковый первый символ в нормализованном формате (например, 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

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

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

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

to:

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

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

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

• Саундекс
• Метафон
• Двойной метафон
• НИСИИС
• Каверфон
• Кельн Фонетический
• Кодекс MRA

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

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

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

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

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