Fuzzy String Search

[rotalever]

Ich habe eine Datenbank mit vielen Namen, so in der Größenordnung von 100.000 Stück. Jetzt gibt der Benutzer einen Namen ein und die Anwendung soll entsprechend reagieren: Wenn der Name vom Benutzer falsch geschrieben wurde, soll der Name aus der Datenbank zurückgegeben werden, der am besten passt.

Das lässt sich natürlich leider nicht mit einem einfachen Index in einer SQL-Datenbank lösen.. Ich suche deshalb nach irgendwelchen schnellen Verfahren, die gute Ergebnisse liefern.

Bisher habe ich mir folgendes überlegt: Für alle 100.000 Namen in der Datenbank lege ich einen Soundex(Name)-Eintrag an, der auch in der Datenbank enthalten ist und mit einem Index verbunden ist. Dies muss ich ein einziges Mal machen, da sich die Datenbank nur selten verändert. Das ist also nicht Zeit-Kritisch.

Gibt der Benutzer nun einen Namen ein, berechne ich den Soundex und nehme alle Namen aus der Datenbank, die auch diesen Soundex haben. Dadurch hätte ich die Suchmenge schon mal stark reduziert. Anschließend würde ich die levenshtein-Distanz von diesen erhaltenen Namen zum Suchwort berechnen und den Namen mit der geringsten Distanz ausgeben.

Ich schätze mal, das würde recht performant sein und lässt sich auch mit einfachen Mitteln in kurzer Zeit implementieren. Aber es gibt sicher bessere Lösungen?

[Monger]

Das Problem an deinem Verfahren ist, dass Tippfehler sowie Prä- und Suffixe o.ä. bereits bei der Soundex Suche rausfallen. Der Soundex ist eigentlich eine sehr starke Einschränkung.

Ich glaube, man müsste an der Stelle erstmal niederschreiben, was für Formen von Fehleingaben man eigentlich erwartet. Du bist ja kein Hellseher, du musst irgendeinen Anhaltspunkt haben was der Anwender konkret erwartet.

Mein spontaner Gedanke wäre, den Suchbegriff stückweise zu erweitern, bis man genügend Ergebnisse bekommt. Also z.B. :
Ich suche nach "Monger"

Erster Suchbegriff: Monger, keine Ergebnisse
Zweiter Suchbegriff: Mong, Ergebnisse: "Monga, Mongger, Mongher"

Vorteil wäre, dass die Suche nach Teilstrings in jeder aktuellen Datenbank normalerweise schweineschnell implementiert ist, und du auf die Weise sehr schnell und einfach an ein paar Vorschläge kommst. Nachteil ist, dass man den Suchbegriff erstmal geeignet aufsplitten muss, und du mit phonetischen Ähnlichkeiten halt überhaupt nicht umgehen kannst. Wie wäre es mit einer Splittung anhand der Silben? Silben aufsplitten kann man annähernd anhand der Vokale.
Monger: Vokale bei 2 und 5, Mitte bei (2+5)/2 = 3,5, Mon-ger.
Einmal nach "Mon", und einmal nach "ger" querien, beide Ergebnisse zusammenschmeißen und meinetwegen die ersten drei Ergebnisse jeweils als Vorschläge ausspucken.

[rotalever]

Das Problem an deinem Verfahren ist, dass Tippfehler sowie Prä- und Suffixe o.ä. bereits bei der Soundex Suche rausfallen. Der Soundex ist eigentlich eine sehr starke Einschränkung.

Das stimmt wohl. Tippfehler sind in der Tat ein Problem...

Ich glaube, man müsste an der Stelle erstmal niederschreiben, was für Formen von Fehleingaben man eigentlich erwartet. Du bist ja kein Hellseher, du musst irgendeinen Anhaltspunkt haben was der Anwender konkret erwartet.

Naja, erstens eben Tippfehler und zweitens falsch geschriebene Namen, weil man zwar weiß, wie der Name klingt aber man die Schreibweise nicht kennt. Letzteres vermutlich häufiger.

Mein spontaner Gedanke wäre, den Suchbegriff stückweise zu erweitern, bis man genügend Ergebnisse bekommt. Also z.B. :
Ich suche nach "Monger"

Erster Suchbegriff: Monger, keine Ergebnisse
Zweiter Suchbegriff: Mong, Ergebnisse: "Monga, Mongger, Mongher"

Vorteil wäre, dass die Suche nach Teilstrings in jeder aktuellen Datenbank normalerweise schweineschnell implementiert ist, und du auf die Weise sehr schnell und einfach an ein paar Vorschläge kommst. Nachteil ist, dass man den Suchbegriff erstmal geeignet aufsplitten muss, und du mit phonetischen Ähnlichkeiten halt überhaupt nicht umgehen kannst. Wie wäre es mit einer Splittung anhand der Silben? Silben aufsplitten kann man annähernd anhand der Vokale.
Monger: Vokale bei 2 und 5, Mitte bei (2+5)/2 = 3,5, Mon-ger.
Einmal nach "Mon", und einmal nach "ger" querien, beide Ergebnisse zusammenschmeißen und meinetwegen die ersten drei Ergebnisse jeweils als Vorschläge ausspucken.
Das schaut nach einer interessanten Idee aus. Das müssten ich dann allerdings noch, wie du sagsts, phonetisch kombinieren, weil das sonst möglicherweise nicht gut funktioniert.
Sucht der User zum Beispiel nach "Tom" meint aber eigentlich "Thom", so würde die Datenbank erst für die Abfrage nach "T*" passende Wörter liefern. Das wären dann zu viele.
edit: Man könnte natürlich auch nach "*om" suchen, aber das wäre dann nicht mit einer einfachen Trennung nach Silben getan.

[Monger]

Wenn das tatsächlich nicht ausreicht, könntest du die einzelnen Silben stückweise um einzelne Konsonanten (und zuletzt den Vokal) erleichtern und einfach nochmal neu querien. Und du könntest die Silben der Länge nach ordnen - es hat imho wenig Sinn, nach der geringsten Übereinstimmung zuerst zu suchen.

Ich glaube, dass insbesondere bei Texteingaben die Vokale eigentlich am stabilsten bleiben. So gesehen bin ich ein bißchen überrascht dass der Soundex diese überhaupt nicht berücksichtigt.

Das Problem hier ist imho, dass man einfach zu wenig über die Datenbank und deren Benutzer weiß, um zuverlässige Aussagen darüber treffen zu können wie man denn dem Anwender da entgegen kommen kann.
100.000 Einträge hören sich jetzt erstmal nach viel an, aber wenn die Suche nach Nachnamen geht, gibt es da möglicherweise gar nicht so viel Mehrdeutigkeiten wie man denken könnte.

Der häufigste Fehler bei getippten Wörtern sind fehlende Buchstaben, der zweithäufigste Buchstabendreher. Das machen locker 80% aus. Die Frage ist nur, ob du hier wirklich Tippfehler ausbügeln willst, oder klevere Alternativvorschläge bringen willst. Du kannst nicht auf beides optimieren.

So wie sich das anhört, ist die Datenbank ja bereits in Benutzung. Wenn du kannst, würde ich dir empfehlen z.B. die Suchbegriffe mitzuloggen, und ein paar Statistiken zu erheben. So bekommst du wenigstens ein paar Fakten in die Hand was denn tatsächlich verbesserungswürdig ist.

[rotalever]

Ich glaube, dass insbesondere bei Texteingaben die Vokale eigentlich am stabilsten bleiben. So gesehen bin ich ein bißchen überrascht dass der Soundex diese überhaupt nicht berücksichtigt.
Naja, aber es gibt halt ähnlich lautende Vokale, Vokalfolgen, etc. Zum Beispiel "Alicia Keys" wird gerne als "Alica Keys" geschrieben, weil man nur den Klang im Kopf hat, nicht weiß, wie man es schreibt und es dann so schreibt, wie man denkt, obwohl es falsch ist.

100.000 Einträge hören sich jetzt erstmal nach viel an, aber wenn die Suche nach Nachnamen geht, gibt es da möglicherweise gar nicht so viel Mehrdeutigkeiten wie man denken könnte.

Es sind eindeutige Namen. Kein Name kommt doppelt vor. Oder wie meintest du das?

So wie sich das anhört, ist die Datenbank ja bereits in Benutzung. Wenn du kannst, würde ich dir empfehlen z.B. die Suchbegriffe mitzuloggen, und ein paar Statistiken zu erheben. So bekommst du wenigstens ein paar Fakten in die Hand was denn tatsächlich verbesserungswürdig ist.
Dann werde ich wohl erstmal mehr Statistiken erheben. Noch habe ich auch den Inhalt der Datenbank noch nicht vollständig und nicht sonderlich viele Anfragen. Das einfach Soundex-Verfahren kann ich dann ja bei Gelegenheit schon mal implementieren und schauen, ob es gut funktioniert. Das lässt sich ja in einer halben Stunde programmieren.
Und dann könnte ich entsprechend schauen, wie ich Dein Verfahren mit einbinden könnte.

[Monger]

Es sind eindeutige Namen. Kein Name kommt doppelt vor. Oder wie meintest du das?

Ich meinte: ähnliche Namen. Sprich: Meier, Maier, Obermeier...

Die Suche ist ja die eine Sache. Eine klevere Suchfunktion nützt aber halt überhaupt gar nix, wenn gar nicht die Daten dafür da sind. Wenn du z.B. einen unglaublich ausgeklügelten Algorithmus entwickelst der deine Ergebnisse vorsortiert, obwohl du sowieso kaum Ergebnisse rauskriegst, war die ganze Mühe für die Katz.

Da kommen dann zum Schluss so sinnvolle Ergebnisse raus wie:
"Sie haben 'Meier' geschrieben. Meinten sie vielleicht: 'Helmut'?

Irgendwo früher oder später ist auch der Punkt erreicht, wo man lieber gar nichts zurückgibt als irgendeinen Blödsinn.

[rotalever]

[...]
Irgendwo früher oder später ist auch der Punkt erreicht, wo man lieber gar nichts zurückgibt als irgendeinen Blödsinn.
Ja, dafür würde ich dann ja noch die levenshtein-Distanz berechnen und nur eine gewisse Abweichung zulassen.