¿Cuál es una buena estrategia para agrupar palabras similares?

Question

Decir que tengo una lista de nombres de películas con faltas de ortografía y pequeñas variaciones como esto -

"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" 

¿Cómo encontrar muchas grupo o grupos de palabras, de preferencia utilizando Python y/o Redis?

Answer 1

Echa un vistazo a "coincidencia difusa". Algunas herramientas geniales en el siguiente subproceso que calcula similitudes entre cadenas.

soy especialmente aficionado del módulo 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

Para agregar otro extremo a la respuesta de Fredrik, también se puede conseguir inspirado desde motores de búsqueda como el código, como éste :

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 

Fuente y más información: http://www.zackgrossbart.com/hackito/search-engine-python/

Saludos,

Max

Answer 3

creo que hay de hecho dos problemas distintos.

La primera es corrección de hechizos. Usted puede tener uno en Python aquí

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

La segunda es más funcional. Esto es lo que haría después de la corrección de hechizos. Haría una función de relación.

relacionado (oración1, oración2) si y solo si la oración1 y la oración2 tienen palabras comunes raras. Por raro, me refiero a palabras diferentes a (The, what, is, etc ...). Puede echar un vistazo al sistema TF/IDF para determinar si dos documentos están relacionados con sus palabras. Sólo googlear un poco encontré esto:

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

Answer 4

Usted puede notar que las cadenas similares tienen gran subcadena común, por ejemplo:

"bla bla bla" y "Bla bla Bra" => subcadena común es "Bla bla ba" (observe la tercera palabra)

Para encontrar una subcadena común, puede usar el algoritmo de programación dinámica. Una de las variaciones de los algoritmos es Levenshtein distancia (la distancia entre las cadenas más similares es muy pequeña, y entre las cadenas más diferentes, la distancia es mayor) - http://en.wikipedia.org/wiki/Levenshtein_distance.

También para un rendimiento rápido puede intentar adaptar Algoritmo de Soundex - http://en.wikipedia.org/wiki/Soundex.

Entonces, después de calcular la distancia entre todas sus cadenas, debe agruparlas. La forma más simple es k-means (pero necesita definir la cantidad de clusters).Si no conoce la cantidad de clústeres, debe usar la agrupación jerárquica. Tenga en cuenta que el número de clústeres en su situación es número de títulos de películas diferentes + 1 (para cadenas de texto totalmente incorrectas).

Answer 5

Un enfoque sería preprocesar todas las cadenas antes de compararlas: convierta todo a minúsculas, estandarice los espacios en blanco (por ejemplo, reemplace cualquier espacio en blanco con espacios simples). Si la puntuación no es importante para su objetivo final, también puede eliminar todos los caracteres de puntuación.

Levenshtein distance se usa comúnmente para determinar la similitud de una cadena, esto debería ayudarlo a agrupar cadenas que difieren en pequeños errores ortográficos.