Welcher Algorithmus gibt Vorschläge in einer Rechtschreibprüfung?

114

Welcher Algorithmus wird normalerweise verwendet, wenn eine Rechtschreibprüfung implementiert wird, die Wortvorschläge enthält?

Zuerst dachte ich, es könnte sinnvoll sein, jedes neu eingegebene Wort (falls es nicht im Wörterbuch gefunden wird) mit seiner Levenshtein-Entfernung von jedem anderen Wort im Wörterbuch zu vergleichen und die besten Ergebnisse zurückzugeben. Dies scheint jedoch äußerst ineffizient zu sein, da das gesamte Wörterbuch wiederholt ausgewertet werden muss.

Wie wird das normalerweise gemacht?

algorithm language-agnostic spell-checking levenshtein-distance Mithrax
quelle

Antworten:

203

Es gibt einen guten Aufsatz von Peter Norvig, wie man eine Rechtschreibkorrektur implementiert. Grundsätzlich handelt es sich um einen Brute-Force-Ansatz, bei dem Kandidaten-Strings mit einem bestimmten Bearbeitungsabstand ausprobiert werden. ( Hier sind einige Tipps, wie Sie die Leistung der Rechtschreibkorrektur mithilfe eines Bloom-Filters und eines schnelleren Hashing von Kandidaten verbessern können .)

Die Anforderungen an eine Rechtschreibprüfung sind schwächer. Sie müssen nur herausfinden, dass ein Wort nicht im Wörterbuch enthalten ist. Mit einem Bloom-Filter können Sie eine Rechtschreibprüfung erstellen, die weniger Speicher benötigt. Eine alte Version wird in Programming Pearls von Jon Bentley mit 64 KB für ein englisches Wörterbuch beschrieben.

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

Die Levenshstein-Entfernung ist nicht genau die richtige Bearbeitungsentfernung für eine Rechtschreibprüfung. Es kennt nur das Einfügen, Löschen und Ersetzen. Die Transposition fehlt und erzeugt 2 für eine Transposition von 1 Zeichen (1 Löschen und 1 Einfügen). Der Abstand Damerau - Levenshtein ist der richtige Bearbeitungsabstand.

Thomas Jung
quelle
2
+1 für die relativ unbekannte BK-Tree-Referenz. So machen es Unternehmen wie Google, die mit realen Datenmengen arbeiten.
NoozNooz42
2
Es gibt eine viel bessere Erklärung von BK-Bäume hier .
Ian Boyd
17

Ein Ansatz zum Generieren von Vorschlägen, die ich erfolgreich verwendet habe, aber nirgendwo beschrieben habe, besteht darin, Vorschläge (beim Erstellen des Wörterbuchs) mithilfe von "schlechten" Hash-Funktionen vorab zu berechnen.

Die Idee ist, die Arten von Rechtschreibfehlern zu untersuchen und Hash-Funktionen zu entwerfen, die demselben Bucket eine falsche Rechtschreibung zuweisen wie die richtige Rechtschreibung.

Zum Beispiel ist ein häufiger Fehler , den falschen Vokal zu bedienen, wie definate statt bestimmten . Sie entwerfen also eine Hash-Funktion, die alle Vokale als denselben Buchstaben behandelt. Eine einfache Möglichkeit, dies zu tun, besteht darin, zuerst das eingegebene Wort zu "normalisieren" und dann das normalisierte Ergebnis durch eine reguläre Hash-Funktion zu führen. In diesem Beispiel werden durch die Normalisierungsfunktion möglicherweise alle Vokale definitegelöscht dfnt. Das "normalisierte" Wort wird dann mit einer typischen Hash-Funktion gehasht.

Fügen Sie mit dieser speziellen Hash-Funktion alle Wörter aus Ihrem Wörterbuch in einen Hilfsindex (Hash-Tabelle) ein. Die Buckets in dieser Tabelle haben längere Kollisionslisten, da die Hash-Funktion "schlecht" ist, aber diese Kollisionslisten sind im Wesentlichen vorberechnete Vorschläge.

Wenn Sie nun ein falsch geschriebenes Wort finden, suchen Sie in den Kollisionslisten nach dem Bucket, dem die Rechtschreibfehler in den Hilfsindizes zugeordnet sind. Ta da: Sie haben eine Vorschlagsliste! Alles was Sie tun müssen, ist die Wörter darauf zu ordnen.

In der Praxis benötigen Sie einige Hilfsindizes mit anderen Hash-Funktionen, um andere Arten von Fehlern zu behandeln, z. B. transponierte Buchstaben, Einzel- / Doppelbuchstaben und sogar einen vereinfachten Soundex-ähnlichen, um phonetische Rechtschreibfehler zu erkennen. In der Praxis fand ich, dass vereinfachte Aussprachen einen langen Weg gehen und einige derjenigen, die triviale Tippfehler finden sollen, im Wesentlichen überholt haben.

Jetzt suchen Sie in jedem der Hilfsindizes nach Rechtschreibfehlern und verketten die Kollisionslisten, bevor Sie ein Ranking erstellen.

Denken Sie daran, dass die Kollisionslisten nur Wörter enthalten, die im Wörterbuch enthalten sind. Mit Ansätzen, die versuchen, alternative Schreibweisen zu generieren (wie im Artikel von Peter Norvig), können Sie (Zehntausende) Kandidaten erhalten, die Sie zuerst anhand des Wörterbuchs filtern müssen. Mit dem vorberechneten 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.

Update : Ich habe seitdem eine ähnliche Algorithmusbeschreibung gefunden, die FAROO Distributed Search . Dies ist immer noch eine Suche mit begrenzter Bearbeitungsentfernung, aber sie ist sehr schnell, da der Vorberechnungsschritt wie meine Idee "schlechte Hash-Funktionen" funktioniert. FAROO verwendet nur ein begrenztes Konzept einer schlechten Hash-Funktion.

Adrian McCarthy
quelle
Vielen Dank, dass Sie auf den SymSpell-Algorithmus von Faroos verwiesen haben. Während beide Algorithmen mögliche Tippfehler vorberechnen und eine Hash-Tabelle für die schnelle Suche verwenden, besteht der Hauptunterschied darin, dass SymSpell garantiert, dass alle möglichen Rechtschreibfehler bis zu einem bestimmten Bearbeitungsabstand erkannt werden (in dieser Hinsicht entspricht SymSpell nur dem Algorithmus von Peter Norvig 3..6 Größenordnungen schneller), während Ihr Algorithmus einen heuristischen Ansatz verwendet, der nur eine begrenzte Teilmenge aller theoretisch möglichen Rechtschreibfehler erkennt (daher sind Ihre Vorberechnungskosten möglicherweise niedriger).
Wolf Garbe
Der SymSpell-Algorithmus berechnet mögliche Tippfehler explizit vor und speichert sie, mein "Bad Hash" -Schema jedoch nicht. Für Englisch ist es trivial, nur einen simplen phonetischen Hash hinzuzufügen, der viel Boden abdeckt (z. B. "terradacktle" -> "pterodactyl" mit einem Bearbeitungsabstand von 6). Zugegeben, wenn Sie mehrsprachige Suchvorgänge benötigen, ist dies möglicherweise viel schwieriger.
Adrian McCarthy
Indem Sie empirisches Wissen über wahrscheinliche Tippfehler nutzen (und auf diese beschränken), sparen Sie Zeit und Platz vor der Berechnung. Um jedoch alle möglichen Rechtschreibfehler abzudecken, muss SymSpell nur einen winzigen Bruchteil davon vorberechnen. Ein 5-Buchstaben-Wort weist innerhalb eines maximalen Bearbeitungsabstands von 3 etwa 3 Millionen mögliche Rechtschreibfehler auf. Mit SymSpell müssen Sie jedoch nur 25 Löschvorgänge vorberechnen und speichern. Dies ist wichtig für die Fuzzy- / Ähnlichkeitssuche über die Rechtschreibkorrektur hinaus, wenn keine empirischen Kenntnisse vorliegen.
Wolf Garbe
7

Algorithmus

  1. Nehmen Sie ein falsch geschriebenes Wort als Eingabe.
  2. Speichern Sie die Liste der englischen Wörter zusammen mit ihren Häufigkeiten in einer Textdatei.
  3. Fügen Sie alle verfügbaren englischen Wörter (in der Textdatei gespeichert) zusammen mit ihrer Häufigkeit (Maß dafür, wie häufig ein Wort in englischer Sprache verwendet wird) in einen ternären Suchbaum ein.
  4. Durchqueren Sie nun den ternären Suchbaum -
    • Berechnen Sie für jedes Wort im ternären Suchbaum die Levensthein-Entfernung aus dem falsch geschriebenen Wort.
    • Wenn Levensthein Distance <= 3 ist, speichern Sie das Wort in einer Prioritätswarteschlange.
    • Wenn zwei Wörter den gleichen Bearbeitungsabstand haben, ist das mit der höheren Frequenz größer. Drucken Sie die 10 wichtigsten Elemente aus der Prioritätswarteschlange.

Optimierung

  1. Sie können die Wörter im Teilbaum des aktuellen Knotens entfernen, wenn der Bearbeitungsabstand der Teilzeichenfolge des Eingabeworts vom aktuellen Wort größer als die 3 ist.
    Die detailliertere Erklärung und den Quellcode finden Sie im Github-Projekt .
amarjeetAnand
quelle
Hmm, der Levenshtein-Abstand von "Reibe" zu "Größer" würde in diesem Fall nicht ausreichen, da "Reibe" auch ein Wörterbuchwort ist. ;-)
Tony Brasunas
1
@ TonyBrasunas, ja du hast recht. Das Programm gibt jedoch tatsächlich eine Liste mit 10 Wörtern zurück, wenn "Reibe" als Eingabe verwendet wird, und schlägt "Reibe" mit einem Bearbeitungsabstand von 0 und "Größer" mit einem Bearbeitungsabstand von 1 vor. Dies könnte hilfreich sein. ;)
amarjeetAnand
Wenn ein Kandidat einen Abstand von 2 hat, aber extrem häufig ist und ein anderer Kandidat einen Abstand von 1 hat, aber extrem selten ist, wie ordnen Sie die beiden ein? Bei dem obigen Ansatz würde der seltene Gegenstand immer gewinnen. Ist dies das richtige Ergebnis?
Speedplane
@speedplane Ja. der Seltene wird gewinnen. Und ich denke, es ist das richtige Ergebnis. Was wir erwarten, ist das nächste Wort, basierend auf der Schreibweise des eingegebenen Wortes. Wenn Sie immer noch Zweifel haben, denken Sie so - nehmen wir an, es gibt ein seltenes Wort, das der Benutzer richtig geschrieben hat. Jetzt ist sein Abstand 0, aber die Frequenz ist sehr gering. In Vorschlägen sollten wir dieses seltene Wort (mit Abstand 0) oben (weil die geringste Bearbeitungsentfernung gewinnt) und andere Wörter mit Abstand 1-2-3 unten auflisten.
AmarjeetAnand
3

Sie müssen nicht für jedes Wort im Wörterbuch den genauen Bearbeitungsabstand kennen. Sie können den Algorithmus nach Erreichen eines Grenzwerts stoppen und das Wort ausschließen. Dies spart Ihnen viel Rechenzeit.

Petr Peller
quelle
1

Die Rechtschreibprüfung ist wie im Unix-Rechtschreibprogramm sehr einfach 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 dieses neue Wort im Wörterbuch enthalten ist. Solche neuen Änderungen können gruppiert und dem Benutzer angezeigt werden.

Das Unix-System verwendet ein von Mc IllRoy geschriebenes Programm. Eine alternative Möglichkeit ist die Verwendung eines Trie, der bei großen Dateien hilfreich sein kann.

Der Unix-Ansatz benötigt sehr wenig Platz für ein großes Wörterbuch, da er einen Scatter-Hash-Algorithmus verwendet.

Harisankar Krishna Swamy
quelle