Размито съпоставяне на низове в Python

Има няколко възможни нива на оптимизация тук, за да се превърне този проблем от O(n^2) в по-малка времева сложност.

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

  • lowercase conversion,
  • без бели интервали, премахване на специални знаци,
  • трансформирайте unicode в ascii еквиваленти, ако е възможно, използвайте unicodedata.normalize или модул за унидекод)

  Това би довело до "Andrew H Smith", "andrew h. smith", "ándréw h. smith" генериране на същия ключ "andrewhsmith" и би намалило вашия набор от милиони имена до по-малък набор от уникални/подобни групирани имена.

Можете да използвате този полезен метод, за да нормализирате своя низ (все пак не включва частта от 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, тъй като това сходство на имената ще изисква размито съвпадение на низове, освен нормализираното сравнение, направено по-горе.

• Букетинг: Наистина ли трябва да сравните ключ от 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 като такъв вариант на име с first писмо рядко ще съществува.

След това можете да използвате нещо в съответствие с този метод (или модул 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"]

Ето ви - всички елементи (списъци) в нормализирания dict, които имат повече от една стойност - са съвпадащите думи.

Алгоритъмът за нормализиране зависи от данните, т.е. думите. Помислете за един от многото:

• Soundex
• Метафон
• Двоен метафон
• NYSIIS
• Caverphone
• Кьолн фонетичен
• MRA кодекс

Специфично за 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, функцията за извличане така или иначе ще се опита да изпълни пълен процес. Може да използва partial на functools, за да каже pass in fuzz.token_set_ratio с full_process=False като резултат и стартирайте utils.full_process по ваш избор предварително.