webentwicklung-frage-antwort-db.com.de

Python: Finden Sie die nächstgelegene Zeichenfolge (aus einer Liste) zu einer anderen Zeichenfolge

Nehmen wir an, ich habe eine string"Hello" und eine Liste

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

Wie kann ich den n words finden, der "Hello" am nächsten ist und in der Liste words vorhanden ist?

In diesem Fall hätten wir ['hello', 'hallo', 'Hallo', 'hi', 'format'...]

Die Strategie besteht also darin, die Wörter der Liste vom nächstgelegenen Wort zu sortieren.

Ich dachte über so etwas nach

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

aber in großen Listen ist es sehr langsam.

UPDATEdifflib funktioniert, ist aber auch sehr langsam. (words list enthält mehr als 630000 Wörter (sortiert und einer pro Zeile)). Das Überprüfen der Liste dauert also 5 bis 7 Sekunden für jede Suche nach dem nächsten Wort!

pythonstringalgorithmlist
41
Laura

Verwenden Sie difflib.get_close_matches .

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

Bitte beachten Sie die Dokumentation, da die Funktion standardmäßig 3 oder weniger Übereinstimmungen liefert.

68
Oleh Prypin

Es gibt einen großartigen Artikel mit einem vollständigen Quellcode (21 Zeilen) von Peter Norvig zur Rechtschreibkorrektur. 

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

Die Idee ist, alle möglichen Bearbeitungen Ihres Wortes zu erstellen,

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)

Schauen Sie sich nun jede dieser Änderungen in Ihrer Liste an. 

Peters Artikel ist eine großartige Lektüre und lesenswert.

21
Amjith

Erstellen Sie eine sortierte Liste Ihrer Wörter und verwenden Sie das bisect-Modul , um den Punkt in der sortierten Liste zu identifizieren, an dem Ihr Word entsprechend der Sortierreihenfolge passen würde. Basierend auf dieser Position können Sie die k nächstgelegenen Nachbarn oben und unten angeben, um die 2k nächsten Wörter zu finden. 

1
user1308520

vielleicht heap kann dir helfen. 

sie haben einen Haufen mit dem Namen Heap, den Sie mit der Funktion n in die Variable Heap einfügen, bis sie kleiner als close ist.

diese Methode kann Ihnen helfen, wenn n klein ist :)

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)
0
Divuneh