Spell Checking Algorithm

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

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/Levenshtein_distance

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