Forum: PC-Programmierung S: Algorithmus: ähnliche Strings vergleichen


von berner (Gast)


Lesenswert?

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

von Rolf Magnus (Gast)


Lesenswert?

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

von Klaus (Gast)


Lesenswert?

Hi,
google mal unter >string ähnlich phonetisch< .

bye
Klaus

von Klaus W. (mfgkw)


Lesenswert?

Es gab vor etlichen Jahren auch mal einen ganz informativen
Artikel mit Beispiel in der c't dazu.

von Michael G. (linuxgeek) Benutzerseite


Lesenswert?

Kann man mit der Editierdistanz machen, auch Levenshtein-Distanz 
genannt:
http://de.wikipedia.org/wiki/Levenshtein-Distanz

von Karl H. (kbuchegg)


Lesenswert?

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

von ... .. (docean) Benutzerseite


Lesenswert?

Mit dieser Distanz könnte aber das Problem mit der Abkürzung nicht 
wirklich erschlagen oder nicht?

von Karl H. (kbuchegg)


Lesenswert?

... ... 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 :-)

von Klaus W. (mfgkw)


Lesenswert?

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.

von berner (Gast)


Lesenswert?

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%

von Karl H. (kbuchegg)


Lesenswert?

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

von Klaus W. (mfgkw)


Lesenswert?

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...

von berner (Gast)


Lesenswert?

MEIER EIEIE sind 80%

von berner (Gast)


Lesenswert?

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.

von Klaus W. (mfgkw)


Lesenswert?

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...

von berner (Gast)


Angehängte Dateien:

Lesenswert?

IHRE LHRE : 75%

(man beachte den Screenshot)

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
Noch kein Account? Hier anmelden.