Die Levenshtein-Distanz bemisst die Distanz zwischen zwei Zeichenketten anhand der Operationen die notwendig sind um vom der einen Zeichenkette zu der anderen zu gelangen. Operationen sind ersetzen, einfügen und löschen.
Die Distanz zwischen "Katze" und "Tatze" ist eins, weil wir ein Zeichen austauschen müssen ("K" -> "T"). Die Distanz zwischen "Katze" und "Katzen" ist ebenfalls eins, weil wir ein Zeichen einfügen müssen (" " -> "n").
An dem zweiten Beispiel erkennen wir schon das es einige Gesetzmäßigkeiten bei den Distanzen gibt. Wenn zwei Zeichenketten unterschiedlich lang sind müssen wir mindestens so viel Zeichen einfügen wie die längere Kette länger ist. Somit beträgt die Distanz mindestens die Anzahl an Zeichen um die eine Zeichenkette länger als die andere ist.
Katze Katzen (+1 Zeichen) Katzenfutter (+7 Zeichen)
Ebenso wird erkennbar das die Distanz maximal die Länge der längeren Zeichenkette sein kann. Wenn wir so viele Zeichen ausgetauscht, entfernt oder eingefügt haben wie die zweite Zeichenkette lang ist, muss diese bereits vollständig sein.
Hund Katzenfutter (4 Zeichen ersetzt + 8 Zeichen hinzugefügt = 12)
Kurz gesagt:
Die Damerau-Levenshtein-Distanz erweitert die Levenshtein-Distanz um eine Operation: Vertauschung falls zwei benachbarte Zeichen in der anderen Zeichenkette in vertauschter Reihenfolge identisch sind. Sie ermöglicht also den Austausch von zwei benachbarten Zeichen.
Die Damerau-Levenshtein-Distanz ist damit besser geeignet Buchstaben-Dreher zu erkennen bzw. diese anders zu berücksichtigen. Bei der Levenshtein-Distanz müssten für eine Vertauschung statt dessen zwei Zeichen ersetzt werden.
Katze
Kazte (Levenshtein-Distanz = 2, da zwei Operationen "t"->"z" und "z"->"t")
Kazte (Damerau-Levenshtein-Distanz = 1, da eine Operation Austausch("t"<->"z"))
Wie wir an der Damerau-Levenshtein-Distanz bereits erkennen, können die Operationen unterschiedlich gewichtet werden. Im Gegensatz zu der Levenshtein-Distanz werden die Kosten für den Austausch durch einführen einer dafür zuständigen Operation halbiert.
In der praktischen Anwendung macht es durchaus Sinn die Gewichtung von Operationen weiter zu verfeinern. Ein Beispiel dafür ist die Tastatur-Distanz. Tippfehler und Buchstaben-Dreher sind bei bestimmten Anordnungen auf der Tastatur wahrscheinlicher. Ein "R" und ein "T" sind schneller vertippt als ein "R" und ein "O". Es macht also Sinn die Kosten für bestimmte Ersetzen-Operationen zu verringern.
Ein weiterer Faktor für die Verfeinerung der Distanz-Messung ist der Einbezug der verwendeten Sprache. Im Deutsch-sprachigen Raum sind die Unterschiede zwischen "ss" und "ß" oder "Ph" und "F" beispielsweise gesondert zu betrachten. Werden ältere Formen der deutschen Sprache in Betracht gezogen, beispielsweise alte Texte, kommen auch Kombinationen wie "C" und "K" oder "i" und "ie" mehr Bedeutung.
String-Alignment ist ein interessantes Thema, das mit Bezug zur Analyse von Text und Sprache als auch mit Bezug zur automatisierten Fehlerkorrektur daher kommt. Beides sind interessante Themen für künstliche Intelligenz. Demzufolge wird String-Alignment etwas sein mit dem man sich befasst haben sollte.
Wer das alles mal ausprobieren möchte kann das unter Tools: String-Alignment tun.
Copyright © 2024