# Unscharfe Suche



## Hubivan (13. April 2007)

Hallo,

Ich habe folgendes Problem, in einer Kundendatenbank soll über die Kundennummer eine unscharfe Suche durchgeführt werden. Um z.B. auch Kunden zu finden die ihre Nummer nicht ganz wissen, oder sie auf der Überweisung E-Mail was auch immer...
falsch angegeben haben z.B. Zahlendreher o.ä.

Da die Kundennummern nur aus Ziffern bestehen, kommt eine unscharfe Suche mit SOUNDEX nicht in Frage, da dieser Alogrithmus ja für Wörter gedacht ist.

Ich habe schon überlegt, die Kundennummern mittels Levenshtein-Distanz zu vergleichen, aber das würde wohl zu lange dauern, da das dann ja mit jedem einzelnen Datensatz gemacht werden müsste und das wiederum würde bei fast 4 Millionen Kunden etwas lange dauern oder?

Die zu verwendente Datenbank wird vermutlich Oracle sein, MySQL steht aber auch zur Debatte. Bei der ganzen Sache handelt es sich mehr oder weniger um ein "Versuchsprojekt", das nicht zwingend zu dem Resultat führen muss, dass die Suche sinnvoll ist bzw in endlicher Zeit durchführbar ist.


----------



## tobias_petry (13. April 2007)

Zahlendreher bekommst du mit keinem Algorithmus wieder raus, es seidenn du machst nen komplexen Query der auf zig Möglichkeiten prüft, das sicherste wird sein, noch weitere Daten zu haben, wie E-Mail, Vor- und Nachname etc, dann sollte das relativ simpel zu lösen sein, um so mehr Daten du über die Person hast, umso einfacher


----------



## Hubivan (13. April 2007)

Ich will die Zahlendreher ja auch nicht aus der Kundennummer rausrechnen oder so, sondern
mit der verfälschten Nummer quasi in der Datenbank nach ähnlichen Nummern suchen und die gefundenen Kunden als Vorschlag anzeigen. 
Das blöde dabei ist, das im Moment nur eine Afrage über alle vorhandenen Datensätze und ein Vergleich mittels Levenshtein Distanz eine Möglichkeit darstellt, zu suchen.
Ich schätze auf genau das wird es dann wohl hinauslaufen.

Versuchsweise hab ich mal den bei Wikipedia beschriebenen Damerau-Levenshtein Algorithmus implementiert. 

http://de.wikipedia.org/wiki/Levenshtein-Distanz

Als Ergebnisse der Suche werden alle Kundennummer ausgegeben die eine Maximale Distanz von 3 haben, alle anderen werden als unwahrscheinlich verworfen.
Für die Prüfung wird im Moment jede einzelne Kundennummer mit der zu suchenden Nummer verglichen. Da meine "Testdatenbank" zur Zeit nur aus einem Array mit 20 Fantasienummern besteht geht das zwar recht flott, aber mit der echten DB wird das wohl ne weile dauern.
Angeblich gibt es ein paar Tricks wie man zumindest den Vergleichsalgorithmus selbst etwas "beschleunigen" kann um zumindest hier Zeit zu sparen. Kennt die Jemand?

Die Firma Exorbyte will es angeblich geschafft haben. http://www.exorbyte.de natürlich rücken die keine Infos raus wie...  

Für den Fall, dass ich Vor oder Nachnamen haben sollte, habe ich bereits Möglichkeiten gefunden die Suche auf ähnliche bzw gleiche Namen einigermaßen effizient zu gestalten.


----------



## Radhad (13. April 2007)

Ich denke es würde dir helfen, einen dump der Live-DB zu ertsellen und diese auf dein Testsystem einzuspielen, dann kannst du die Dauer der Suchanfragen besser analysieren!


----------



## Hubivan (13. April 2007)

Ja das mit dem Dump wird wohl das beste sein, fragt sich nur ob ich das genehmigt kriege...
wegen Datenschutz und so.


----------

