Levenshtein-Algorithmus Stringvergleich

[p. specht]

Unscharfe String-Vergleiche
=====================

Es ist nicht ganz einfach, Eingaben mit Tippfehlern vom Computer trotzdem erkennen zu lassen. Der Levenshtein-Algorithmus erlaubt zumindest, einfache Preller bzw. Auslassungen zu erkennen. Etwas besser ist bei Datenbanken die SOUNDEX-Funktion, die allerdings meist für Englisch optimiert ist.

Das Gelbe vom Ei ist der Original-Levenshtein jedenfalls noch nicht. Es fehlt z.B. eine Änderung der Kostenbewertung (Variable cost&) in Abhängigkeit von möglichen Hörfehlern (y,ü,i,j ; sh sch ; t d ; p b; k g; h _ ), und vieles anderes mehr. Hier mal eine Basis zum rumspielen:

'### Alpha Version Code für Paule´s PC Forum ###
'### P. Specht  Nov.2010;  XProfan 11a Interpreter ###
WindowTitle "Levenshtein-Distanz (Stringvergleich)"
Cls @rgb(200,200,100)

proc LD  ' Compute Levenshtein-Distance
parameters s$,t$
s$=lower$(s$):var m&=len(s$)
t$=lower$(t$):var n&=len(t$)
declare d&[m&,n&],i&,j&,cost&,mi&,c&
case m& = 0 : return n&
case n& = 0 : return m&
i&=0 : while i&<=m& : d&[i&,0]=i& : inc i& : endwhile
j&=0 : while j&<=n& : d&[0,j&]=j& : inc j& : endwhile
i&=1
WHILE i&<=m&
    j&=1
    While j&<=n&
      cost&=1
      case Mid$(s$,i&,1)=Mid$(t$,j&,1):cost& = 0
        mi&=d&[i&-1,j&]+1
        c&=d&[i&,j&-1]+1
        case c&<mi& : mi&=c&
        c&=d&[i&-1,j&-1]+cost&
        case c&<mi& : mi&=c&
      d&[i&,j&]=mi&
   inc j&
   EndWhile
inc i&    
ENDWHILE
return d&[m&,n&]
Endproc

' Input Loop
declare str1$,str2$
While 1
Locate 10,10 : print "String1  =                                   ";
Locate 12,10 : print "String2  =                                   ";
Locate 14,10 : print "Ergebnis =                                   ";
Locate 10,21 : input str1$ : case str1$="" : End
Locate 12,21 : input str2$
Locate 14,21 : Print LD(str1$,str2$)
WaitInput
EndWhile
END

[commänder]

Ein sehr guter Algorithmus in diesem Bereich, der vor allem mit deutschen Wörtern sehr gut funktioniert, ist die sogenannte "Kölner Phonetik".

Kölner Phonetik ? Wikipedia

[Jac de Lad]

Hm, ok, aber wie errechne ich dann die Ähnlichkeit zweier Wörter, die ich in Zahlenkolonnen umgewandelt habe?

[p. specht]

@commänder: Danke - Super Hinweis!

@Jaq: A) Beziehst du Dich jetzt auf Levenshtein (Die Zahl die da rauskommt ist eine Art Verwandtschaftsmaß zwischen zwei Worten): Du setzt einfach einen Treshold level und prüfst das Ergebnis, ob diese zulässige Fehlergrenze überschritten ist oder nicht.

@Alle: B) Wenns es um "Kölner Phonetik" geht: Meine Umsetzung ist noch immer nicht fertig, weil ich die Resultate erst an offiziellen Ergebnissen verifizieren möchte (man blamiert sich ja nicht sonderlich gerne).

Sinn des Kölner Verfahrens ist es, ein Filter darzustellen, das die Eingabeinterpretation gewissermaßen schwerhörig macht. Da sich Vokale in unterschiedlichen Dialekten oft verändern, werden sie z.B. mit "0" kodiert und, wenn sie nicht am Anfang stehen, einfach weggelassen. Zischlaute wiederum landen in Klasse "3", etc etc.

Achtung: Es sind keine Zahlen, die dabei rauskommen, weil die scheinbar aus Ziffern bestehenden Vergleichsmuster eine führende Null kennen (Wenn nämlich Vokale als erstes Zeichen stehen) - sämtliche Math-Packages würden führende Nullen klarerweise wegschneiden. Weiters haben Integer-Zahlen eine begrenzte Stellenzahl, der Kölner Algorithmus aber nicht, was allgemein als Vorteil gegenüber Soundex() ins Treffen geführt wird.

Wenn man das Ergebnis aber doch unbedingt als Zahl speichern will (meine Überlegungen gingen auch zuerst in diese Richtung), könnte man führende Nullen eventuell als negatives Vorzeichen speichern und dann alles Modulo (höchste Integerzahl/2) nehmen (Vorsicht, Rechte Dritter!).
Es bleibt eine Frage der zeitlichen Performance, ob man die Vergleichsdatenbank um eine Spalte "Klingt wie ..." erweitert und nach Aufrufhäufigkeit index-sortiert (das setzt halt zu Beginn u.U. eine Vorab-Berechnung voraus), oder ob man das ganze "fliegend" hält.

Die Übereinstimmung der erzeugten Muster ist dabei das Kriterium (in Google kommt da z.B. die Meldung "Meinten Sie ....?"). Eine Fehlerschwelle gibts dabei nicht, die ist - optimiert für die Deutsche Sprache - in den Kölner Algorithmus gewissermaßen schon eingebaut.

Ich hoffe, das klang jetzt nicht anmaßend

Gruss

[Frabbing]

Klang es nicht.
Ist wohl nur die Frage, ob man das in einer annehmbaren Geschwindigkeit realisieren kann...

[Jac de Lad]

Ich bezog mich auf die Kölner Phonetik. Da kommt am Ende eine Zahlenschlange raus, die ich unmöglich mit "=" oder so vergleichen kann.

[p. specht]

Die Ziffern sind Gruppenzugehörigkeitsbezeichner für die einzelnen Laute (Phoneme) eines Wortes. Es entsteht eine Ziffernzeichen-Schlange ("String"). Das selbe machst du für die Einträge Deiner Datenbank, somit hast du einen Suchstring und Vergleichsstrings.
Und die kann man mit "=" vergleichen, oder etwa nicht?

[Jac de Lad]

Ja schon, aber wenn ein Wort eine Ziffer mehr hat, dann kann ich den String nicht so einfach vergleichen, aber sie sind sich ziemlich ähnlich.

[p. specht]

Jaq hat recht: Mit dem Original-Levenshtein kann man nur Tippfehler ausbügeln, während das Kölner Verfahren nur Hörfehler ausbügelt. Sucht man ein Verfahren, daß beides gleichzeitig kann, ist man in Deutsch mit dem PHONEM-Algorithmus gut bedient. PHONEM funktioniert so, daß vor einem Levenshtein-Vergleich Buchstabengruppen austauscht werden: ph wird f, p wird b, t wird d etc., also (fast) gemäß den Regeln, die auch dem Kölner Algorithmus zugrunde liegen.