Berechnen der Levenshtein-Entfernung schnell

Suchen Sie aus einer riesigen Datenbank mit zulässigen Wörtern (alphabetisch sortiert) und einem Wort das Wort aus der Datenbank, das dem angegebenen Wort in Bezug auf die Levenshtein-Entfernung am nächsten liegt.

Der naive Ansatz besteht natürlich darin, einfach den Abstand zwischen dem angegebenen Wort und allen Wörtern im Wörterbuch zu berechnen (wir können eine binäre Suche in der Datenbank durchführen, bevor wir die Abstände tatsächlich berechnen).

Ich frage mich, ob es eine effizientere Lösung für dieses Problem gibt. Vielleicht eine Heuristik, mit der wir die Anzahl der zu durchsuchenden Wörter reduzieren können, oder Optimierungen des Abstandsalgorithmus.

Links zu Beiträgen zum Thema sind willkommen.

Was Sie fragen, ist das Problem der Suche in der Nähe des Nachbarn unter der Bearbeitungsentfernung. Sie haben nicht erwähnt, ob Sie an theoretischen Ergebnissen oder an Heuristiken interessiert sind, deshalb beantworte ich erstere.

Die Bearbeitungsentfernung ist für die Erstellung von Suchstrukturen in der Nähe von Nachbarn etwas unangenehm. Das Hauptproblem ist, dass sich eine Metrik wie andere bekannte schlechte Metriken wie um die Dimensionalität zu reduzieren und zu approximieren. Zu diesem Thema gibt es ziemlich viel zu lesen, und Ihre beste Quelle ist die Reihe von Artikeln von Alex Andoni : Wenn Sie den Rückwärtszeigern folgen (zum Beispiel aus seinem FOCS 2010-Artikel), erhalten Sie eine gute Reihe von Quellen.$\ell_1$

Levenshtein-Automaten: http://en.wikipedia.org/wiki/Levenshtein_automaton

BK-Bäume: http://en.wikipedia.org/wiki/BK-tree

Wenn Sie eine kleine Anzahl von Fehlbearbeitungen tolerieren, können Sie versuchen, einen gepunkteten Suffixbaum zu verwenden . Haftungsausschluss: Ich habe dieses Papier geschrieben, aber es löst, was Sie wollen: Es hat hohe Speicherplatzkosten, aber die Abfragen sind sehr schnell.

Im Allgemeinen ist es besser, es anders herum zu betrachten: Sie haben einen Index aller Wörter im Wörterbuch. Stoppen Sie nun für ein eingegebenes Wort w, falls es sich im Wörterbuch befindet. Andernfalls generieren Sie alle Variationen im Abstand 1 und suchen Sie nach diesen. Wenn sie nicht da sind, suchen Sie nach Variationen in Abstand 2 und so weiter ...

An dieser Grundidee gibt es mehrere Verbesserungen.

$O(m^{k+1} \cdot \sigma^{k})$$m$$\sigma$$k$

Ich habe eine Antwort auf eine sehr ähnliche Frage unter cs.stackexchange.com ( /cs//a/2096/1490 ) geschrieben und dann diese Frage gefunden. Dort lautet die Antwort für eine ungefähre Suche nach einem nahen Nachbarn in der Bearbeitungsentfernung (dh der Algorithmus gibt eine Zeichenfolge aus, die ungefähr so ​​nah an der Abfragezeichenfolge liegt wie der nächste Nachbar der Abfragezeichenfolge). Ich poste hier, da ich in den hier gegebenen Antworten keine der Referenzen finde, die ich dort angegeben habe.

Ich denke, was Sie wollen, ist der Wagner-Fischer-Algorithmus: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm Die wichtigste Erkenntnis ist, dass das Wörterbuch, das Sie durchlaufen, zwei aufeinanderfolgende Wörter enthält haben sehr wahrscheinlich ein langes Präfix, sodass Sie nicht die gesamte Matrix für jede Entfernungsberechnung aktualisieren müssen.

Sie können verwenden, Meinten Sie?

Suchen Sie dann den Levenshtein-Abstand zwischen der Antwort, die von "Meinten Sie" zurückgegeben wurde, und der Eingabezeichenfolge mithilfe der dynamischen Programmierung.

Eine Möglichkeit besteht darin, ein maschinelles Lernmodell zu trainieren, um die Wörter auf Vektoren abzubilden und die Levenshtein-Distanz auf die euklidische Distanz abzubilden. Dann können Sie einen KDTree aus den Vektoren für das Wörterbuch erstellen, das Sie verwenden möchten. Ich habe hier ein Jupyter-Notizbuch erstellt: https://gist.github.com/MichaelSnowden/9b8b1e662c98c514d571f4d5c20c3a03

Wie laut DW's Kommentare:

1. Trainingsablauf = stochastischer Gefälleabstieg mit adaptiven Gefällen
2. Verlustfunktion = mittlerer quadratischer Fehler zwischen wahrer Editierentfernung und euklidischer Entfernung
3. Trainingsdaten = zufällige Zeichenfolgen mit einer Länge zwischen 1 und 32 Zeichen (könnte durch Daten verbessert werden, die einer tatsächlichen Verteilung der gängigen Tippfehler entsprechen)
4. Quantitative Ergebnisse: Nach dem Training für ungefähr 150 Epochen mit einer Stapelgröße von 2048 (Wandzeit = ungefähr eine Minute) unter Verwendung von Worteinbettungen von 512 Dimensionen mit einer verborgenen Schicht der durchschnittliche absolute Fehler zwischen der tatsächlichen Bearbeitungsentfernung und der vorhergesagten Bearbeitungsentfernung liegt bei etwa 0,75, was bedeutet, dass die vorhergesagte Bearbeitungsentfernung ungefähr ein Zeichen abweicht

Zusammenfassung der Modellstruktur:

1. Erstellen Sie eine gelernte Einbettung für jedes Zeichen, einschließlich des Nullzeichens (wird später verwendet, um Text unter der Zeichenbeschränkung nach rechts zu füllen).
2. Fülle die rechte Seite des Textes mit dem Null-Zeichen auf, bis das Zeichenlimit erreicht ist (32)
3. Verketten Sie diese Einbettungen
4. Führen Sie die Einbettungen durch ein Feed-Forward-neuronales Netz, um eine niederdimensionale Worteinbettung (512-dimensional) zu erzeugen.
5. Tun Sie dies für beide Wörter
6. Finden Sie den euklidischen Abstand zwischen den Vektoren
7. Stellen Sie den Verlust als mittleren quadratischen Fehler zwischen der tatsächlichen Levenshtein-Distanz und der euklidischen Distanz ein

Meine Trainingsdaten sind nur zufällige Zeichenfolgen, aber ich denke, die Ergebnisse könnten sich wirklich verbessern, wenn die Trainingsdaten (Tippfehler / korrektes Wort) Paare wären. Am Ende habe ich nur verwendet, /usr/share/dict/wordsweil es allgemein verfügbar ist.