Welcher Algorithmus gibt Vorschläge in einem Zaubersprüchen?

StackOverflow https://stackoverflow.com/questions/2294915

Frage

Welcher Algorithmus wird normalerweise bei der Implementierung eines Zauberprüfers verwendet, der mit Wortvorschlägen begleitet wird?

Zuerst dachte ich, es könnte sinnvoll sein, jedes neue Wort (falls nicht im Wörterbuch gefunden) zu überprüfen Levenshtein -Entfernung Aus jedem anderen Wort im Wörterbuch und die Rückgabe der Top -Ergebnisse. Dies scheint jedoch sehr ineffizient zu sein und das gesamte Wörterbuch wiederholt zu bewerten.

Wie wird das normalerweise gemacht?

War es hilfreich?

Lösung

Es gibt Guter Aufsatz von Peter Norvig So implementieren Sie einen Rechtschreibkorrektor. Es ist grundsätzlich ein brutaler Kraftansatz, den Kandidatenstrings mit einer bestimmten Bearbeitungsentfernung ausprobiert. (Hier sind einige Tipps, wie Sie die Leistung der Rechtschreibkorrektor mit a verbessern können Blütefilter und schnellerer Kandidat Hashing.)

Die Anforderungen an einen Zaubersprüche sind schwächer. Sie müssen nur herausfinden, dass sich ein Wort nicht im Wörterbuch befindet. Sie können a verwenden Blütefilter Erstellen eines Zauberspurs, der weniger Speicher verbraucht. Eine alte Version wird abnimmt in Programmierperlen programmieren von Jon Bentley mit 64 KB für ein englisches Wörterbuch.

EIN Bk-Baum ist ein alternativer Ansatz. Ein schöner Artikel ist hier.

Levenshstein -Entfernung ist nicht genau die richtige Bearbeitungsentfernung für einen Zaubersprüchen. Es kennt nur Einfügen, Löschung und Substitution. Die Transposition fehlt und erzeugt 2 für eine Transposition von 1 Charakter (es ist 1 Löschen und 1 Einfügung). Damerau -Levenshtein -Entfernung ist die richtige Bearbeitungsentfernung.

Andere Tipps

Ein Ansatz zur Erzeugung von Vorschlägen, die ich erfolgreich verwendet habe, aber noch nie gesehen habe, ist die Vorbereitung von Vorschlägen (beim Aufbau des Wörterbuchs), indem "schlechte" Hash-Funktionen verwendet werden.

Die Idee ist, die Arten von Rechtschreibfehlern zu betrachten, die Menschen machen, und Hash -Funktionen zu entwerfen, die demselben Eimer eine falsche Schreibweise wie die korrekte Rechtschreibung zuweisen würden.

Zum Beispiel besteht ein häufiger Fehler darin, den falschen Vokal zu verwenden, wie Definieren Anstatt von definitiv. Sie entwerfen also eine Hash -Funktion, die alle Vokale als denselben Buchstaben behandelt. Eine einfache Möglichkeit, dies zu tun, besteht darin, zuerst das Eingangswort zu "normalisieren" und dann das normalisierte Ergebnis durch eine reguläre Hash -Funktion zu setzen. In diesem Beispiel kann die Normalisierungsfunktion alle Vokale fallen lassen, also definite wird dfnt. Das "normalisierte" Wort wird dann mit einer typischen Hash -Funktion gehasht.

Fügen Sie alle Ihre Wörterbuchwörter mit dieser speziellen Hash -Funktion in einen Hilfsindex (Hash -Tabelle) ein. Die Eimer in dieser Tabelle werden längere Kollisionslisten enthalten, da die Hash-Funktion "schlecht" ist, aber diese Kollisionslisten sind im Wesentlichen vorbereitete Vorschläge.

Wenn Sie nun ein falsch geschriebenes Wort finden, suchen Sie die Kollisionslisten für den Eimer nach, auf den die Fehlschreiber in den Auxiliary -Indizes karten. TA DA: Sie haben eine Vorschlagsliste! Alles, was Sie tun müssen, ist die Wörter darauf zu bewerten.

In der Praxis benötigen Sie einige Hilfsinizes mit anderen Hash-Funktionen, um andere Arten von Fehlern zu verarbeiten, z. In der Praxis fand ich simple Aussprache, die einen langen Weg zurücklegen und im Wesentlichen einige derjenigen veraltet haben, die für triviale Tippfehler entwickelt wurden.

Jetzt schauen Sie also in jedem der Hilfsindizes Missspellings nach und verkettet die Kollisionslisten vor dem Ranking.

Denken Sie daran, dass die Kollisionslisten nur Wörter enthalten, die sich im Wörterbuch befinden. Mit Ansätzen, die versuchen, alternative Schreibweisen zu erzeugen (wie im Peter Norvig -Artikel), können Sie (zehn) Tausende von Kandidaten erhalten, die Sie zum ersten Mal gegen das Wörterbuch filtern müssen. Mit dem vorbereiteten Ansatz erhalten Sie vielleicht ein paar hundert Kandidaten, und Sie wissen, dass sie alle richtig geschrieben sind, sodass Sie direkt zum Ranking springen können.

Aktualisieren: Ich habe seitdem eine Algorithmusbeschreibung gefunden, die dem ähnelt, die Faroo verteilte Suche. Dies ist immer noch eine begrenzte Suche in Bearbeitungsdistanz, aber sehr schnell, da der Schritt vor dem Zusammenschluss wie meine "schlechte Hash-Funktionen" -Ade funktioniert. Faroo verwendet nur ein begrenztes Konzept einer schlechten Hash -Funktion.

Algorithmus

  1. Nehmen Sie ein falsch geschriebenes Wort als Eingabe.
  2. Speichern Sie die Liste der englischen Wörter zusammen mit ihren Frequenzen in einer Textdatei.
  3. Fügen Sie alle verfügbaren englischen Wörter (in der Textdatei gespeichert) zusammen mit ihren Frequenzen (Maß dafür ein, wie häufig ein Wort in englischer Sprache verwendet wird) in einem ternären Suchbaum.
  4. Jetzt über den ternären Suchbaum überqueren -
    • Berechnen Sie für jedes Wort, das im ternären Suchbaum aufgetreten ist, seinen Levenshein -Abstand vom fälschlicherweise geschriebenen Wort.
    • Wenn Levensthein -Entfernung <= 3, speichern Sie das Wort in einer Prioritätswarteschlange.
    • Wenn zwei Wörter die gleiche Bearbeitungsentfernung haben, ist die mit höhere Frequenz Reifen. Drucken Sie die Top 10 Elemente aus der Prioritätswarteschlange.

Optimierung

  1. Sie können die Wörter in Subtree des aktuellen Knotens Eleminieren, wenn die Bearbeitungsentfernung des Substrings des Eingabefelds aus dem aktuellen Wort vergrößert als der 3 ist.
    Sie können den detaillierteren Erläuterung und den Quellcode finden Github -Projekt.

Sie müssen die genaue Bearbeitungsentfernung für jedes Wort im Wörterbuch nicht kennen. Sie können den Algorithmus nach dem Erreichen eines Grenzwerts stoppen und das Wort ausschließen. Auf diese Weise sparen Sie viel Computerzeit.

Die Zauberprüfung ist sehr einfach wie im UNIX -Zauberprogramm zu implementieren. Der Quellcode ist öffentlich verfügbar. Die Korrektur kann beteiligt sein, eine Technik besteht darin, Änderungen vorzunehmen und erneut zu überprüfen, ob sich dieses neue Wort im Wörterbuch befindet. Solche neuen Änderungen können dem Benutzer gruppiert und gezeigt werden.

UNIX System verwendet ein Programm von MC Illroy. Eine alternative Möglichkeit ist die Verwendung eines Tries, der bei großen Dateien nützlich sein kann.

Der UNIX -Ansatz benötigt einen sehr weniger Platz für ein riesiges Wörterbuch, da es einen Streuungs -Hash -Algorithmus verwendet.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top