Python: encontrar la cadena más cercano (de una lista) a otra cadena

Question

Digamos que tengo un string"Hello" y una lista

words = ['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo','question', 'Hallo', 'format'] 

¿Cómo puedo encontrar el n words que son los más cercanos a "Hello" y en la lista words?

En este caso, tendríamos ['hello', 'hallo', 'Hallo', 'hi', 'format'...]

Así que la estrategia es ordenar las palabras de la lista de la palabra más cercana a la más lejana.

pensé en algo como esto

word = 'Hello' 
for i, item in enumerate(words): 
    if lower(item) > lower(word): 
     ... 

pero es muy lento en grandes listas.

ACTUALIZACIÓN difflib funciona pero también es muy lento. (words list tiene más de 630000 palabras adentro (ordenadas y una por línea)). ¡Así que consultar la lista lleva de 5 a 7 segundos para cada búsqueda de palabra más cercana!

Answer 1

Use difflib.get_close_matches.

>>> words = ['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo', 'question', 'format'] 
>>> difflib.get_close_matches('Hello', words) 
['hello', 'Hallo', 'hallo'] 

Consulte la documentación, ya que la función devuelve 3 o menos coincidencias más cercanas de forma predeterminada.

Answer 2

Cree una lista ordenada de sus palabras y use bisect module para identificar el punto en la lista ordenada donde su palabra cabría según el orden de clasificación. En función de esa posición, puede dar a los k vecinos más cercanos arriba y abajo para encontrar las 2k palabras más cercanas.

Answer 3

Hay un artículo impresionante con un código fuente completo (21 líneas) proporcionado por Peter Norvig sobre la corrección ortográfica.

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

La idea es construir todas las posibles modificaciones de su palabra,

hello - helo - deletes  
hello - helol - transpose  
hello - hallo - replaces  
hello - heallo - inserts  


def edits1(word): 
    splits  = [(word[:i], word[i:]) for i in range(len(word) + 1)] 
    deletes = [a + b[1:] for a, b in splits if b] 
    transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1] 
    replaces = [a + c + b[1:] for a, b in splits for c in alphabet if b] 
    inserts = [a + c + b  for a, b in splits for c in alphabet] 
    return set(deletes + transposes + replaces + inserts) 

Ahora, mira hacia arriba cada una de estas ediciones en su lista.

El artículo de Peter es de gran lectura y vale la pena leerlo.

Answer 4

tal vez heap puede ayudarlo.

usted tiene un montón nombrado Heap que hasta su tamaño es menor que n, insertar las palabras en el uso de la función Heapclose [muestra esta cadena está más cerca que otra cadena o no].

este método puede ayudar a usted cuando n es pequeña :)

Heap = [] 
for word in words: 
    if len(Heap)<n: 
     Heap.insert(word) 
    else 
     if close(word,Heap[0]): # it means Heap[0] is the nth farthest word until now 
      Heap.pop(): 
      Heap.insert(word)