Heuristik zur Bestimmung von möglichen Eingabefehlern bei Strings

Hallo Leute,
folgende Situation:

-Datenbank mit verschiedenen Strings, zB Namen:
Michael Müller
Max Mustermann
etc.

-Manuelle Eingabe dieser Namen => Fehlerpotential (bsp. Max Msterman)

-Abgleich der manuellen Eingabe mit der Datenbankspeicherung

Ich interessiere mich jetzt für eine Heuristik die erkennt, dass "Max Mustermann" und "Max Msterman" mit einer gewissen Wahrscheinlichkeit "ähnlich" sind und dem Benutzer eine Korrektur anbieten. Also in etwas das was beispielsweise auch die Google-Suche macht.

Stehe grad auf dem Schlauch, wie heißt denn diese Gruppe von Algorithmen/Problemstellugen? Gibt es das Lib-mäßig was? (C) Optimalerweise sogar trainierbar? (müsste ja möglich sein)

Danke&Gruß Justadude

muemmel

Hi,

da wirst Du nicht allzu viele Möglihckeiten haben, weil gerade bei namen sehr viel möglihc ist. Gerade bei Mustermann kann es ganau so gut auch Mastemann, Meistermann, Musstermann... sein.
Aus meiner Sich tkann man da eigentlihc nur die jeweils hintereinander sthenden Konsonanten auswerten. Dass die Vokale dagegen kaum irgendwelchen Regeln folgen sieht man an so Worten wie Aioli.
Ich würde versuchen, so viel wie möglich Text in maschinenlesbarer Form in die finger zu kriegen (zum Beispiel Tageszeitungen...) umnd die nach zusammenhängenden gruppen von Konsonanten scannen, und einer Liste (mit Häufigkeit) aller vorkommenden Konsonantenreihungen aufstellen und dabei merken wie oft im Wortinnern, wie oft am Wortanfang und wie oft am Wortende. Und dann jeden einzelnen Begriff in Konsonantengruppen zerlegen und danach suchen. Was nicht in der Liste steht oder nur mit sehr geringer Häufigkeit (unter Beachtung der Stellung im Wort) ist bedenklich.
Denk aber daran, das die Liste nationaltypisch ist. Worte wie z.B. "naschtschinajetza" kommen im Deutschen kaum vor, also ist das Auftreten von "schtsch" im deutschen immer ein Hinweis auf einen Fehler, im Russischen gibts dagegen einen extra buchstaben dafür.

Gruß Mümmel

Ein Ansatzpunkt könnte die phonetische Suche sein.

muemmel

Hi,

fdfdg schrieb:

Ein Ansatzpunkt könnte die phonetische Suche sein.

denke ich eher nicht, denn die erkennt ja keine Falschschreibungen. Dann schon eher ne komplette Wörterliste und einen Gramatikalgorithmus.

Eine phonetische Suche würde vertmutlich kaum zwischen nämlich und nähmlich unterscheiden. Klingt ja beides gleich. Zugegeben, eine Tokenliste aus Konsonantentoken auch nicht. Aber ein richtiges Wörtrbuch ist sicher noch aufwendiger. Eventuell bei Textverarbeitungen nach Flüchtigkeitsfehlerkorrekturmakros gucken und danach suchen lassen. In jedem fall wird man aber immer nur Verdachstfälle bekommen.

Gruß Mümmel

*Q* 1

Evtl. hilft dir die Levenshtein-Distanz weiter

Hallo Leute,
danke für euren Input, ich werde mir das mal anschauen. Die Güte und Treffergenauigkeit muss nicht besonders hoch sein. Hauptsächlich interessant ist es triviale Fehler zu erkennen (2 Buchstaben vertauscht, Accent über dem e vergessen, etc.), die momentan noch komplett ungeprüft durchgehen. Daher wäre auch eine kleine Verbesserung bereits eine Verbesserung Da es um Namen aus allen Sprachräumen geht wird Datenmaterial sammeln nicht funktionieren.

Levenshtein-Distanz mal auf die Beispiele angewandt:
Mustermann <-> Mastemann (2)
Mustermann <-> Meistermann (2)
Mustermann <-> Musstermann (1)

Hm, im schlechtesten Fall also 1. Bei 0 ist alles richtig, ab 1 Alarm schlagen? Geht natürlich nicht, also kann ich diese Fehlerart schonmal nicht abfangen. Hm muss nochmal drüber nachdenken.

Auf jeden Fall vielen Dank für den Moment:) Justadude

Das sollte dir weiterhelfen:
http://norvig.com/spell-correct.html

volkard

Und einfach bei jedem Nachnamen anschlagen, den es noch nicht gibt?