Python: trovare più vicino stringa (da una lista) ad un'altra stringa

Question

Diciamo che ho un string"Hello" e un elenco

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

Come posso trovare il n words che sono più vicino a "Hello" e presente nella lista words?

In questo caso, avremmo ['hello', 'hallo', 'Hallo', 'hi', 'format'...]

Quindi la strategia è quello di ordinare le parole della lista dalla parola più vicina alla più lontana.

ho pensato a qualcosa di simile

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

ma è molto lento in grandi liste.

UPDATE difflib funziona ma è anche molto lento. (words list contiene 630000+ parole all'interno (ordinate e una per riga)). Quindi controllare l'elenco richiede da 5 a 7 secondi per ogni ricerca della parola più vicina!

Answer 1

Utilizzare difflib.get_close_matches.

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

Consultare la documentazione, poiché la funzione restituisce 3 o meno corrispondenze più vicine per impostazione predefinita.

Answer 2

Creare un elenco ordinato delle parole e utilizzare lo bisect module per identificare il punto nell'elenco ordinato in cui la parola verrà adattata in base all'ordinamento. Basandoti su quella posizione puoi dare ai k vicini più vicini sopra e sotto per trovare le parole 2k più vicine.

Answer 3

C'è un articolo fantastico con un codice sorgente completo (21 righe) fornito da Peter Norvig sulla correzione ortografica.

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

L'idea è quella di costruire tutte le possibili modifiche della tua parola,

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) 

Ora, guardare in alto ognuna di queste modifiche nella vostra lista.

L'articolo di Peter è un'ottima lettura e vale la pena leggerlo.

Answer 4

forse heap può aiutarti.

avete un mucchio di nome Heap che fino a quando la sua dimensione è inferiore a n, si inserisce le parole nella Heap tramite la funzione close [mostra questa stringa è più vicino di un'altra stringa o meno].

Questo metodo può aiutare quando n è piccolo :)

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)