Jaka jest dobra strategia grupowania podobnych słów?

Question

Powiedzmy mam listę imion filmowych z pisowni i małych wahań takiego -

"Pirates of the Caribbean: The Curse of the Black Pearl" 
"Pirates of the carribean" 
"Pirates of the Caribbean: Dead Man's Chest" 
"Pirates of the Caribbean trilogy" 
"Pirates of the Caribbean" 
"Pirates Of The Carribean" 

Jak grupa lub znaleźć takie zestawy słów, najlepiej przy użyciu Python i/lub Redis?

Answer 1

Zobacz "dopasowanie rozmyte". Kilka świetnych narzędzi w poniższym wątku, które obliczają podobieństwa między łańcuchami.

Jestem szczególnie lubiący modułu difflib

>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy']) 
['apple', 'ape'] 
>>> import keyword 
>>> get_close_matches('wheel', keyword.kwlist) 
['while'] 
>>> get_close_matches('apple', keyword.kwlist) 
[] 
>>> get_close_matches('accept', keyword.kwlist) 
['except'] 

https://stackoverflow.com/questions/682367/good-python-modules-for-fuzzy-string-comparison

Answer 2

Aby dodać kolejną końcówkę na odpowiedź Fredrik użytkownika, można także znaleźć inspirację z wyszukiwarek jak kod, taki jak ten :

def dosearch(terms, searchtype, case, adddir, files = []): 
    found = [] 
    if files != None: 
     titlesrch = re.compile('>title<.*>/title<') 
     for file in files: 
      title = "" 
      if not (file.lower().endswith("html") or file.lower().endswith("htm")): 
       continue 
      filecontents = open(BASE_DIR + adddir + file, 'r').read() 
      titletmp = titlesrch.search(filecontents) 
      if titletmp != None: 
       title = filecontents.strip()[titletmp.start() + 7:titletmp.end() - 8] 
      filecontents = remove_tags(filecontents) 
      filecontents = filecontents.lstrip() 
      filecontents = filecontents.rstrip() 
      if dofind(filecontents, case, searchtype, terms) > 0: 
       found.append(title) 
       found.append(file) 
    return found 

Źródło i więcej informacji: http://www.zackgrossbart.com/hackito/search-engine-python/

Pozdrowienia,

Max

Answer 3

Wierzę, że jest w rzeczywistości dwa różne problemy.

Pierwsza to korekta pisowni. Możesz mieć jeden w Pythonie tutaj

http://norvig.com/spell-correct.html

Drugi jest bardziej funkcjonalny. Oto, co zrobię po korekcie zaklęć. Zrobiłbym funkcję relacji.

pokrewne (zdanie 1, zdanie 2) tylko wtedy, gdy zdania 1 i zdanie 2 mają rzadkie wspólne słowa. Przez rzadkie mam na myśli różne słowa niż (Co, co, jest, itp ...). Możesz rzucić okiem na system TF/IDF, aby ustalić, czy dwa dokumenty są powiązane przy użyciu ich słów. Wystarczy googlowania nieco znalazłem to:

https://code.google.com/p/tfidf/

Answer 4

można zauważyć, że podobne ciągi mają duży wspólny podciąg, na przykład:

"bla bla bla" i "Bla bla bra" => wspólnym substringiem jest "Bla bla" (zauważ trzecie słowo)

Aby znaleźć wspólny substring, możesz użyć algorytmu programowania dynamicznego. Jedną z wariacji algorytmów jest Levenshtein odległość (odległość między najbardziej podobnymi ciągami jest bardzo mała, a pomiędzy bardziej różnymi odstępami jest większa) - http://en.wikipedia.org/wiki/Levenshtein_distance.

Również w celu uzyskania szybkiej wydajności możesz spróbować dostosować algorytm Soundex - http://en.wikipedia.org/wiki/Soundex.

Po obliczeniu odległości między wszystkimi strunami należy je zgrupować. Najprostszym sposobem jest k-znaczy (ale wymaga to zdefiniowania liczby klastrów).Jeśli faktycznie nie znasz liczby klastrów, musisz użyć hierarchicznego klastrowania. Zauważ, że liczba klastrów w twojej sytuacji to liczba różnych tytułów filmów + 1 (dla całkowicie złych napisów orkiszowych).

Answer 5

Jednym z podejść byłoby wstępne przetworzenie wszystkich łańcuchów przed ich porównaniem: przekonwertuj wszystkie na małe litery, ustandaryzuj białe spacje (np. Zamień dowolne spacje na pojedyncze spacje). Jeśli interpunkcja nie jest ważna dla celu końcowego, możesz również usunąć wszystkie znaki interpunkcyjne.

Levenshtein distance jest powszechnie używany do określania podobieństwa łańcucha znaków, powinno to pomóc ci w grupowaniu ciągów, które różnią się małymi błędami ortograficznymi.