www.mikrocontroller.net

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


Autor: berner (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Klaus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,
google mal unter >string ähnlich phonetisch< .

bye
Klaus

Autor: Klaus Wachtler (mfgkw)
Datum:

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

Autor: Michael G. (linuxgeek) Benutzerseite
Datum:

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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: ... ... (docean) Benutzerseite
Datum:

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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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 :-)

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: berner (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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%

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht 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...

Autor: berner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
MEIER EIEIE sind 80%

Autor: berner (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht 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...

Autor: berner (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
IHRE LHRE : 75%

(man beachte den Screenshot)

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.