Dopasowywanie ciągów rozmytych w języku Python

Question

Mam 2 listy ponad miliona nazw z nieco innymi konwencjami nazewnictwa. Celem jest dopasowanie podobnych rekordów, z logiką 95% pewności.

Poinformowano mnie, że istnieją biblioteki, na których mogę działać, takie jak moduł FuzzyWuzzy w Pythonie.

Jednak pod względem przetwarzania wydaje się, że zajmie zbyt dużo zasobów, mając każdy ciąg na 1 liście, aby porównać go z drugim, co w tym przypadku wydaje się wymagać miliona pomnożonego przez kolejny milion liczby iteracji.

Czy istnieją inne, bardziej skuteczne metody tego problemu?

UPDATE:

Stworzyłem więc funkcję bucketing i zastosowano prostą normalizację usuwania spacją, symboli i wartości konwersji na małe litery itp ...

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) 

za pomocą pytonów pand, dane jest ładowany do mniejszych segmentów pogrupowanych według lat, a następnie za pomocą modułu FuzzyWuzzy, process.extractOne służy do najlepszego dopasowania.

Wyniki są nadal nieco rozczarowujące. Podczas testu powyższy kod jest używany w ramce danych testowych zawierającej tylko 5 tysięcy nazw i zajmuje prawie całą godzinę.

Dane testowe są podzielone przez.

• Nazwa
• Rok Miesiąc Data urodzenia

A ja porównując je przez wiader, gdzie ich YMS są w tym samym segmencie.

Czy problem może wynikać z modułu FuzzyWuzzy, którego używam? Doceniam każdą pomoc.

Answer 1

Istnieje kilka poziom op możliwe czasy, aby zmienić ten problem z O (n^2) na mniejszy czas złożoności.

• Przetwarzanie wstępne: Sortowanie listy w pierwszym przejeździe, tworząc mapę wyjściowy dla każdej struny, klucz one na mapie można znormalizować ciąg. Normalizations mogą obejmować:

  • małą przemianę,
  • nie spacje, specjalny usunięcie znaków,
  • przekształcenia unicode do odpowiedniki ASCII, jeśli to możliwe, używać unicodedata.normalize lub unidecode Module)

  Spowodowałoby w "Andrew H Smith", "andrew h. smith", "ándréw h. smith" generowanie tego samego klucza "andrewhsmith", i zredukuje twój zestaw milionów nazw do małego r zestaw unikatowych/podobnych pogrupowanych nazw.

Można to wykorzystać utlity method znormalizować swoją ciąg (nie obejmuje części unicode chociaż):

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 

• Teraz podobne ciągi będzie już leżeć w tym samym wiadrze jeśli ich znormalizowane klucz jest taki sam.

• Aby uzyskać dalsze porównanie, należy porównać tylko klucze, a nie nazwy. np. andrewhsmith i andrewhsmeeth, ponieważ to podobieństwo nazw będzie wymagało rozmytego dopasowania ciągów znaków poza znormalizowanym porównaniem wykonanym powyżej.

• bucketing: Czy naprawdę trzeba porównać klucza 5 znaków z kluczem 9 znaków, aby sprawdzić, czy to jest 95% dopasowania? Nie, ty nie. Dzięki temu możesz tworzyć segmenty pasujące do twoich ciągów. na przykład Nazwy 5 znaków zostaną dopasowane za pomocą 4-6-znakowych nazw, 6-znakowych znaków z 5-7 znakami itd. Limit znaków n + 1, n-1 dla n-znakowego klucza jest względnie dobrym rozwiązaniem dla większości praktycznych dopasowań.

• Początek meczu: Większość odmian nazw będzie miała ten sam pierwszy znak w znormalizowanym formacie (np.g Andrew H Smith, ándréw h. smith i Andrew H. Smeeth generują odpowiednio klucze andrewhsmith, andrewhsmith i andrewhsmeeth. Zazwyczaj nie różnią się one od pierwszego znaku, więc można uruchomić dopasowanie dla kluczy zaczynając od a na inne klucze rozpoczynające się od a i mieszczące się w segmentach długości. Spowoduje to znaczne skrócenie czasu dopasowania. Nie trzeba dopasowywać klucza andrewhsmith do bndrewhsmith, ponieważ taka zmiana nazwy z pierwszą literą rzadko będzie istnieć.

Następnie można użyć coś na wzór tego method (lub moduł fuzzywuzzy), aby znaleźć podobieństwa ciąg procent, można wykluczyć jednego z jaro_winkler lub difflib zoptymalizować szybkość i jakość wyników:

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

Musisz indeksować lub normalizować ciągi, aby uniknąć uruchomienia O (n^2). Zasadniczo, musisz zmapować każdy ciąg do normalnej postaci i zbudować odwrotny słownik ze wszystkimi słowami związanymi z odpowiednimi normalnymi formularzami.

Rozważmy, że normalne formy "świata" i "słowa" są takie same. Więc najpierw zbudować odwrócony słownika Normalized -> [word1, word2, word3], np .:

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

to: 

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

tam udać - wszystkie elementy (list) w znormalizowanej dict, które mają więcej niż jedną wartość - są dobrane słowa.

Algorytm normalizacji zależy od danych, tj. Od słów.Rozważmy jeden z wielu:

• Soundex
• Metaphone
• Pokój Metaphone
• NYSIIS
• Caverphone
• Kolonia fonetyczny
• MRA Codex

Answer 3

Specyficzne dla fuzzywuzzy, zauważ, że obecnie process.extractOne domyślnie WRatio, które jest zdecydowanie najwolniejszym z ich algorytmów, a procesor domyślnie utils.full_process. Jeśli przekażesz fuzz.QRatio jako swojemu strzelcy, zrobi to znacznie szybciej, ale nie tak potężnie, w zależności od tego, co próbujesz dopasować. Może być jednak w porządku dla nazwisk. Osobiście mam szczęście z token_set_ratio, który jest co najmniej nieco szybszy od WRatio. Możesz również uruchomić utils.full_process() we wszystkich swoich wcześniejszych opcjach, a następnie uruchomić go z fuzz.ratio jako swojego strzelca i procesora = Brak, aby pominąć krok przetwarzania. (patrz poniżej) Jeśli używasz tylko podstawowej funkcji współczynnika fuzzywuzzy to prawdopodobnie przesada. Fwiw Mam port JavaScript (fuzzball.js), w którym można wstępnie obliczyć zestawy tokenów i używać ich zamiast przeliczać za każdym razem.)

Nie zmniejsza to liczby porównań, ale pomaga. (BK-drzewa na to prawdopodobnie? Sam się zaglądałam w tę samą sytuację)

Upewnij się również, że masz zainstalowany Python-Levenshtein, więc korzystasz z szybszych obliczeń.

** Zachowanie poniżej może się zmienić, otwarte kwestie omawiane itp. **

fuzz.ratio nie prowadzi pełny proces, a funkcje token_set i token_sort akceptują full_process = False param, a jeśli nie ustawiaj procesora = brak, mimo to funkcja ekstraktu i tak spróbuje uruchomić pełny proces. Może używać częściowych funkcji functools, aby przekazać fuzz.token_set_ratio z full_process = Fałsz jako swojego strzelca i uruchomić utils.full_process na swoich wyborów wcześniej.