Ähnlichkeitsanalyse von Strings
-
Hallo!
Habe mit einem neuen Projekt angefangen und habe da ein Problem, wo ich nicht so richtig weiß, wie ich das umsetzen soll.
Also, ich bin dabei ein kleines Programm zu schreiben, das automatisch ihm unbekannte Wörter lernt. Wenn der Benutzer nun dieses Wort wieder eingibt, allerdings mit 'nem Tippfehler, dann möchte ich, daß mein Programm trotzdem einen guten Vorschlag macht, sprich das richtige Wort als Korrektur vorschlägt.
Beispiel:
Das Programm kennt die Wörter "eins, einer, eines, zwei".
Wenn der Benutzer nun "ien" eingibt, möchte ich die nahelegenden Einträge "eins, einer, eines" ausgeben lassen.Bloß wie gesagt ich habe keine wirklich gute Idee wie man eine solche Analyse effizient gestaltet.
Hat da jemand ein paar gute Tips oder gibts vielleicht sogar Quellcode (C++) irgendwo für solch ein Problem?Vielen Dank,
Tsunami
-
Für den Anfang: Levenshtein-Distanz. Diese wird nicht vollständig dein Problem lösen aber es geht schon mal in diese Richtung.
-
was vlt hilfreich sein kann sind tries http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node22.html. da können dann ähnliche wörter an einem ast hängen, wobei es bei unterschiedlichen anfangsbuchstaben schwerer wird.
-
Sieh Dich mal nach "Trigrammanalyse" und "Textcorpus" um, vielleicht findest Du da was hilfreiches
-
Ähnliche Worte finden geht mit n-Grams wirklich sehr gut.
Alternativ möchte ich noch einen SoundEx Algorithmus als mögliche Problemlösung in den Raum stellen.
-
Vielen Dank für die reichlichen Tips. Ich werde mal gucken was ich so an Material finde und dann mal schauen was sich machen läßt
-
Habe mir mittels n-Grams einen Algorithmus (bigram) gebastelt der nicht nur einfach ist, sondern auch hervorragende Ergebnisse liefert. Bin selbst verdutzt wie gut das funktioniert
-
n-Gramm , Hidden Markov Modell [HMM] und Backus Naur Form [BNF]) kann ich auch empfehlen.
http://de.wikipedia.org/wiki/N-Gramm
http://en.wikipedia.org/wiki/Backus-Naur_form
http://de.wikipedia.org/wiki/Hidden_Markov_ModelMan erziehlt aber bessere Resultate, wenn man versucht die Semantik zu integrieren, zum Bleistift mit OWL & RDF(S). Das würde dein "kleines Projekt" aber ein wenig aus den Rahmen heben