Ich arbeite an einer Rechtschreibprüfung in C ++ und ich bin bei einem bestimmten Schritt in der Implementierung stecken.
Nehmen wir an, wir haben eine Textdatei mit korrekt geschriebenen Wörtern und einer eingegebenen Zeichenfolge, die wir auf Rechtschreibfehler überprüfen möchten. Wenn dieser String ein falsch geschriebenes Wort ist, kann ich leicht seine korrekte Form finden, indem ich alle Wörter in der Textdatei überprüfe und den Text wähle, der sich von ihm mit einem Minimum an Buchstaben unterscheidet. Für diese Art der Eingabe habe ich eine Funktion implementiert, die den Levenshtein-Bearbeitungsabstand zwischen zwei Strings berechnet. So weit so gut.
Nun, der schwierige Teil: Was ist, wenn die eingegebene Zeichenfolge eine Kombination von falsch geschriebenen Wörtern ist? Zum Beispiel "iloevcokies". Berücksichtigt man, dass "i", "love" und "cookies" Wörter sind, die sich in der Textdatei befinden, wie kann ich anhand der bereits implementierten Levenshtein-Funktion feststellen, welche Wörter aus der Datei für eine Korrektur geeignet sind? Wie würde ich auch Leerzeichen in die richtigen Positionen einfügen?
Irgendeine Idee ist willkommen:)
Rechtschreibkorrektur für Phrasen kann auf verschiedene Arten erfolgen. Ein Weg erfordert einen Index von Wort-Bi-Grammen und -Tri-Grammen. Diese könnten natürlich immens sein. Eine andere Option wäre, Permutationen des Wortes mit eingefügten Leerzeichen zu versuchen und dann nach jedem Wort in der resultierenden Phrase zu suchen. Sehen Sie sich eine einfache Implementierung einer Rechtschreibprüfung von Peter Norvig von Google an. In beiden Fällen sollten Sie einen N-Gram-Index für eine bessere Leistung verwenden. In C ++ stehen Bibliotheken als Referenz zur Verfügung.
Google und andere Suchmaschinen können Rechtschreibkorrekturen für Phrasen durchführen, da sie über einen großen Index von Abfragen und zugehörigen Ergebnismengen verfügen, mit dem sie eine statistisch gute Schätzung berechnen können. Insgesamt kann das Rechtschreibkorrekturproblem mit Methoden wie kontextsensitiver Korrektur und phonetischer Korrektur sehr komplex werden. Da die Verwendung von Permutationen von möglichen Unterbegriffen teuer werden kann, können Sie bestimmte Arten von Heuristiken verwenden, dies kann jedoch schnell außer Reichweite geraten.
Sie können auch die Verwendung einer vorhandenen Rechtschreibbibliothek in Betracht ziehen, z. B. aspell .
Ein Ausgangspunkt für eine Idee: Einer der besten Treffer Ihrer L-Distanz für "iloevcokies" sollte "Cookies" sein. Wenn Sie Ihre L-Abstand-Funktion ändern können, um auch einen Min-Index und einen Max-Index zu verfolgen und zurückzugeben (dh, diese Übereinstimmung beginnt am besten mit Zeichen 5 und geht zu Zeichen 10), dann könnten Sie diesen Teilstring entfernen und L erneut prüfen -Abstand für die Zeichenfolge davor und danach, dann verketten Sie die für einen Vorschlag ....
Nur ein Gedanke, viel Glück ....
Ich nehme an, dass Sie einen vorhandenen Index haben, auf dem Sie Ihren Levenshtein-Abstand (zum Beispiel ein Trie, aber jeder sortierte Index funktioniert im Allgemeinen gut).
Sie können das Hinzufügen von Leerstellen als regulären Bearbeitungsvorgang betrachten, es gibt nur eine Wendung: Sie müssen (dann) zurück zum Stamm Ihres Indexes für das nächste Wort.
Auf diese Weise erhalten Sie den gleichen Index, fast die gleiche Route, ungefähr die gleiche Durchquerung, und das sollte nicht einmal Ihre Laufzeiten beeinflussen.
Tags und Links algorithm c++ spell-checking levenshtein-distance