S: Algorithmus: ähnliche Strings vergleichen

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.

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

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