Hallo, In einer Kundendatenbank steht "Hauptstrasse 123". Jetzt bekomm ich ne Bestellung rein von nem Kunden mit "Hauptstr. 123" Ich möchte prüfen, ob der Kunden schon in der Datenbank existiert, wenn nicht nen neuen anlegen. Bei nur kleinen Änderungen oder Schreibfehler soll ggf. ein Dialog aufgehen, wo man gefragt wird: "meinst Du nicht etwa "Hauptstrasse 123" Wie kann ich die Ähnlichkeit von Strings vergleichen ? Als Ergebnis dann sowas wie: 100% oder eben 95% (bzw 1.0 oder 0.95) berner
Das kommt drauf an, wie gut der Algorithmus sein soll. Man kann einen einfachen Vergleich basierend darauf, wieviele Buchstaben übereinstimmen, oder man kann einen Vergleich z.B. auch über Wörter, die ähnlich klingen/ähnlich geschrieben werden oder denselben Wortstamm haben, machen. Sowas machen Suchmaschinen meist. Siehe http://de.wikipedia.org/wiki/Fuzzy-Suche und http://en.wikipedia.org/wiki/Approximate_string_matching Auch das hier könnte interessant sein: http://de.wikipedia.org/wiki/Kölner_Phonetik
Hi, google mal unter >string ähnlich phonetisch< . bye Klaus
Es gab vor etlichen Jahren auch mal einen ganz informativen Artikel mit Beispiel in der c't dazu.
Kann man mit der Editierdistanz machen, auch Levenshtein-Distanz genannt: http://de.wikipedia.org/wiki/Levenshtein-Distanz
Michael G. schrieb: > Kann man mit der Editierdistanz machen, auch Levenshtein-Distanz > genannt: > http://de.wikipedia.org/wiki/Levenshtein-Distanz genau das wars. Mit fiel der Name nicht mehr ein. Den hatte ich mal, wie Klaus noch wusste, aus der c't geklaut. Das Ding funktioniert nicht schlecht. Hab ich heute noch im Einsatz
Mit dieser Distanz könnte aber das Problem mit der Abkürzung nicht wirklich erschlagen oder nicht?
... ... schrieb: > Mit dieser Distanz könnte aber das Problem mit der Abkürzung nicht > wirklich erschlagen oder nicht? Ich sage mal so. "Hauptstrasse 123" und "Hauptstr. 123" werden eine relativ kleine Levenshtein-Distanz haben. Ich würde diesen Fund eigentlich schon unter den ersten paar Treffern erwarten. "Häuplstr. 123" wäre sicher ein besserer Match, aber welches dann richtig ist, kann letztenendes sowieso nur der Mensch entscheiden. Baut man so eine Ähnlichkeitssuche, muss es sowieso für den Benutzer IMMER eine Möglichkeit geben, daraus auszubrechen und auf eigene Faust die Datenbasis zu durchforsten. Und sei es nur, indem man ihm alles zum Durchscrollen und auswählen anbietet. Bin mir nicht sicher, aber ich glaube mich zu erinnern, dass die c't Funktion für Buchstabenvertauschungen eine eigene Gewichtung hat. Das ist der volle Hit, wenn Personen trotz typischer Tippfehler trotzdem korrekt gefunden werden :-)
Zudem kann man vor dem Berechnen der Levenshtein-Distanz die zu vergleichenden Wörter normieren, wie man will. Z.B. aus irgendwasstrasse und irgendwasstraße immer irgendwasstr machen bei den entsprechenden Feldern der Adresse.
Damit hab ich ein bisschen gespielt: http://www.functions-online.com/levenshtein.html Hauptstrasse Hauptstr. Distanz: 4 M. Meier Matthias Meier Distanz: 7 Hans Jörg Distanz: 4 Also für Adresssuchen nicht besonders geeignet. Aber ich habe mir einen Alorithmus selbst ausgedacht. Und der scheint recht gut zu funktionieren Ich such die Buchstabenfolge 2er Buchstaben im 2. String. Zähle die Treffer und teile sie duch die Anzahl der Buchstaben des kürzeren Strings. Wobei Anfang und Ende des Strings noch mit berücksichtigt werden. [start]M. MEIER[ende] [start]MATTHIAS MEIER[ende] ich finde in MATTHIAS MEIER: [start]_M _M ME EI IE ER R_[ende] also 7 Funde. Bei 8 Zeichen sind das 87% Übereinstimmung. Hauptstrasse Hauptstr. 88% M. Meier Matthias Meier 87% Hans Jörg 0%
berner schrieb: > Damit hab ich ein bisschen gespielt: > http://www.functions-online.com/levenshtein.html > > Hauptstrasse > Hauptstr. > Distanz: 4 > > M. Meier > Matthias Meier > Distanz: 7 > > Hans > Jörg > Distanz: 4 > > Also für Adresssuchen nicht besonders geeignet. ist aber Implementierungssache. der erste Vergleich könnte auch eine Distanz von 1 haben. (Generell: Dinge wie . , Satzzeichen vorher schon aussortieren, bei mehreren Wörtern die Worte einzeln betrachten) Die 1 Distanz ergibt sich dann daraus, dass am Ende nicht 4 Character sondern 1 Sequenz mehr kommt. Da ist beim Levenshtein noch viel Spielraum und Raum für Kreativität Levenshtein ist dann gut, wenn es darum geht die typischen Tippfehler (link Hand ist schneller als die rechte Hand) auszufiltern. "Hans" versus "Hnas" > Hauptstrasse > Hauptstr. > 88% > > M. Meier > Matthias Meier > 87% > > Hans > Jörg > 0% Sieht auch nicht schlecht aus
Zumindest bei diesen Texten. Vergleiche ich jedoch MEIER mit EIEIE, kommen 100% raus, weil alle EI und IE im andern String vorkommen. Vorschlag: den Test nicht nur mit je zwei Buchstaben machen, sondern auch mit Gruppen von 3, 4 etc. Zeichen langen Folgen. Wenn solche längeren Folgen auch Treffer ergeben, sind die Strings bestimmt ähnlicher. Oder: mit testen, ob die Strings auch an einer ähnlichen Stelle vorkommen. Oder Levenshtein vernünftig anpassen...
MEIER EIEIE sind 40%, wenn ich nach dem gefundenen EI weiter zum nächsten Buchstaben gehen. Die anderen 3 Beispiele liefern weiterhin den gleichen Wert.
je nachdem, ob du den ersten zerlegst und im zweiten testest, oder umgekehrt. Ich habe mal gesucht wg. c't-Artikel. Das ist nicht einer, sondern gleich vier, die vermutlich interessant sind: Jahr/Ausgabe/Seite: 07 20 214 99 25 252 97 04 386 95 05 294 Bei Bedarf kurze Mail...
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.