Spell Checking Algorithm

(Autor: Η о n ѕ, Frage gestellt am Di, 20. Mär 2007)

Ich kenne leider die genaue deutsche Formulierung nicht.
Auf alle Fälle:
Ich muss einen Algorithmus entwickeln (bzw. implementieren) welcher über ein Wörterbuch einen Text (file) checkt, und dann wort für Wort kontrolliert ob es im Wörterbuch vorkommt oder nicht.

Soweit noch recht einfach...
Nun sollte er aber Vorschläge bringen wie das Wort nun wohl richtig geschrieben wird.

Da lieg das Problem, wenn in meinem Text alles richtig ist, dann komme ich zum Wort "Hsllo" was eigentlich "Hallo" sein sollte, wie muss ich meine Datenstrucktur aufbauen, dass "hallo" zumindest in den Vorschlägen vorkommt?
(Caseinsensitive, also groß und klein wäre mir momentan nicht wichtig)

Ach ja, Programmiersprache sollte C++ sein, ist aber im Moment nebensächlich

Vielen Dank!
Hannes

Artikelbaum anzeigen

Re: Spell Checking Algorithm

(Autor: р u m р k i n, Antwort nach 12 Min)

Moien

Das kann man auf die schnelle oder die langsame Methode lösen. Die langsame Methode wäre es die Levenshtein Distanz zu allen Wörter im Buch durchzurechnen und dann den besten Wert zu nehmen. => http://en.wikipedia.org/wiki/Levensht...

Die schnelle Alternative wäre ein Suffix Baum mit allen Wörter des Buchs aufzubauen (http://en.wikipedia.org/wiki/Suffix_tree). Bei einem unbekannten Wort einfach alle möglichen Wortteile in den Baum stopfen. Von den Resultaten dann das sinnvollste (gleiche Länge, Rest past,.. ) aussuchen.

Da der Suffix Baum auch beim suchen und finden von ganzen Wörtern hilft würde ich den sowieso implementieren (falls das Wörterbuch nicht zu gross ist).

cu

Du kannst auf diesen Artikel nicht antworten.

Dieser Artikelbaum ist im Archiv des Experten-Forums von wer-weiss-was zum Thema "Programmierung allgemein" archiviert. Es handelt sich um keine aktuelle Diskussion, daher kann auf die Artikel nicht mehr geantwortet werden.