Wie funktioniert die Rechtschreibprüfung?

Question

Ich muss eine Rechtschreibprüfung in C zu implementieren. Grundsätzlich brauche ich alle Standard-Operationen ... Ich muss in der Lage sein, einen Textblock auf Rechtschreibung zu prüfen, Wortvorschläge zu machen und neue Wörter dynamisch zum Index hinzuzufügen.

Ich würde das gerne selbst schreiben, aber ich weiß nicht, wo ich anfangen soll.

Answer 1

Lesen Sie mehr über Baum-Traversal . Das Grundkonzept ist wie folgt:

1. Einlesen einer Wörterbuchdatei in den Speicher (diese Datei enthält die gesamte Liste der richtig geschriebenen Wörter, die für eine bestimmte Sprache möglich/üblich sind). Sie können kostenlose Wörterbuchdateien online herunterladen, z. B. Oracles Beispiel-Wörterbuch .
2. Parsen Sie diese Wörterbuchdatei in einen Suchbaum, um die eigentliche Textsuche so effizient wie möglich zu gestalten. Ich werde nicht alle schmutzigen Details dieser Art von Baumstruktur beschreiben, aber der Baum wird aus Knoten bestehen, die (bis zu) 26 Verknüpfungen zu untergeordneten Knoten haben (eine für jeden Buchstaben), plus eine Markierung, die anzeigt, ob der aktuelle Knoten das Ende eines gültigen Wortes ist oder nicht.
3. Führen Sie eine Schleife durch alle Wörter in Ihrem Dokument und vergleichen Sie jedes einzelne mit dem Suchbaum. Wenn Sie einen Knoten im Baum erreichen, bei dem der nächste Buchstabe des Wortes kein gültiges Kind des aktuellen Knotens ist, ist das Wort nicht im Wörterbuch enthalten. Wenn Sie das Ende Ihres Wortes erreichen und das Kennzeichen "Gültiges Wortende" an diesem Knoten nicht gesetzt ist, ist das Wort nicht im Wörterbuch enthalten.
4. Wenn ein Wort nicht im Wörterbuch gefunden wird, informieren Sie den Benutzer. In diesem Stadium können Sie auch alternative Schreibweisen vorschlagen, aber das wird ein bisschen komplizierter. Sie müssen jedes Zeichen des Wortes in einer Schleife durchgehen, alternative Zeichen ersetzen und jedes dieser Zeichen mit dem Suchbaum vergleichen. Wahrscheinlich gibt es effizientere Algorithmen, um die empfohlenen Wörter zu finden, aber ich weiß nicht, welche.

Ein wirklich kurzes Beispiel:

Wörterbuch:

apex apple ernannt

Baum: ( * zeigt gültiges Wortende an) aktualisieren: Vielen Dank an Curt Sampson für den Hinweis, dass diese Datenstruktur als Patricia Baum

A -> P -> E -> X*       \\-> P -> L -> E*            \\-> O -> I -> N -> T* -> E -> D*

Dokument:

Apfelbaumäffchen

Ergebnisse:

• "Apfel" wird im Baum gefunden und gilt daher als korrekt.
• "appint" wird als falsch gekennzeichnet. Wenn Sie den Baum durchlaufen, folgen Sie A -> P -> P aber die zweite P nicht über eine I Kindknoten, so dass die Suche fehlschlägt.
• "ape" wird ebenfalls fehlschlagen, da die E Knoten in A -> P -> E nicht das Kennzeichen "gültiges Wortende" gesetzt hat.

bearbeiten: Weitere Einzelheiten zu Vorschlägen zur Rechtschreibung finden Sie unter Levenshtein-Abstand der die kleinste Anzahl von Änderungen misst, die vorgenommen werden müssen, um eine Zeichenkette in eine andere umzuwandeln. Die besten Vorschläge wären die Wörter im Wörterbuch mit dem geringsten Levenshtein-Abstand zum falsch geschriebenen Wort.

Answer 2

Da Sie nicht wissen, wo Sie anfangen sollen, würde ich vorschlagen, eine bestehende Lösung zu verwenden. Siehe zum Beispiel, aspell (GLPL-lizenziert). Wenn Sie es wirklich selbst implementieren müssen, sagen Sie uns bitte, warum.

Answer 3

E James gibt eine gute Antwort darauf, wie man feststellen kann, ob ein Wort gültig ist. Es hängt wahrscheinlich von der Rechtschreibprüfung ab, wie sie wahrscheinliche Rechtschreibfehler ermittelt.

Eine solche Methode, die ich verwenden würde, ist die Levenshteinn String-Ähnlichkeit die untersucht, wie viele Buchstaben in einem Wort hinzugefügt, entfernt oder ausgetauscht werden müssen, um ein anderes Wort zu bilden.

Wenn Sie sagen, buchstabiert: Land als Contry. Die Ähnlichkeit der Levenshtein-Zeichenkette wäre 1, da Sie nur einen Buchstaben hinzufügen müssen, um "Contry" in "Country" umzuwandeln.

Sie könnten dann alle möglichen korrekten Schreibweisen von Wörtern durchgehen (es gibt nur 171.000 englische Wörter, von denen 3000 95 % des Textes ausmachen). Ermitteln Sie die Wörter mit dem niedrigsten Levenshtein-String-Ähnlichkeitswert, und geben Sie dann die X Wörter zurück, die dem falsch geschriebenen Wort am ähnlichsten sind.

Es gibt ein großartiges Python-Paket namens Fuzzy Wuzzy das dies effizient umsetzt und auf der Grundlage dieser Formel eine prozentuale Ähnlichkeit zwischen zwei Wörtern oder Sätzen erzeugt.

Answer 4

Man sollte auf Präfixe und Suffixe achten.

plötzlich = plötzlich + ly.

Wenn Sie die ly's entfernen, können Sie nur das Wort "Root" speichern.

Ebenso preallocate = pre + allocate.

Und liebevoll = Liebe + ing + ly wird ein wenig komplexer, da die englischen Regeln für ing aufgerufen werden.

Es besteht auch die Möglichkeit, eine Art Hashing-Funktion zu verwenden, um ein Root-Wort zuzuordnen auf ein bestimmtes Bit einer großen Bitmap abzubilden, um in konstanter Zeit festzustellen, ob das Wurzelwort richtig geschrieben ist.

Noch komplexer wird es, wenn Sie versuchen, zu einem falsch geschriebenen Wort eine Liste mit alternativen Schreibweisen zu erstellen. Sie könnten den Soundex-Algorithmus untersuchen, um einige Ideen zu erhalten.

Ich würde empfehlen, mit einer kleinen Anzahl von Wörtern einen Prototyp zu erstellen. Führen Sie viele Tests durch und erweitern Sie dann. Es ist ein wunderbares pädagogisches Problem.

Answer 5

Die Aufteilung eines Wortes in Wurzel und Suffix wird als "Porter Stemming Algorithmus" bezeichnet und ist eine gute Möglichkeit, ein englisches Wörterbuch in einen erstaunlich kleinen Speicher einzupassen.
Es ist auch nützlich für die Suche, so dass "Rechtschreibprüfung" auch "Rechtschreibprüfung" und "Rechtschreibprüfung" findet.