Zurück zum Inhaltsverzeichnis - Lösungen und Tipps

Levenshtein-Distanz

- ms.tru

Die Levenshtein-Distanz ist ein Maß zur Berechnung von Unterschieden zwischen zwei Zeichenketten (=Strings; im Folgenden exemplarisch als a und b bezeichnet). Hierbei ist entscheidend, wie viele Operationen notwendig sind, um aus String a String b zu erzeugen. Für jede Operation (Einfügung, Löschung, Austausch eines Zeichens) wird die Levenshtein-Distanz um eins erhöht.
Die Grundsätze dieser Art der Stringdistanzberechnung hat der sowjetische Mathematiker Wladimir Levenshtein in einem Aufsatz 1964 (engl. 1966) dargelegt. Hierbei dienen die genannten Grundoperationen zur Korrektur von Symbolketten (s. Handout).

2015 - Schneider - Levenshtein TUSCRIPT.pdf [558 KB]

Bsp.:
Es soll die Levenshtein-Distanz der Strings „baum“ und „haus“ berechnet werden. Um aus dem String „baum“ den String „haus“ zu bilden, ist es notwendig, „b“ in „h“ und „m“ in „s“ auszutauschen. Man benötigt somit 2 Substitutionen:
LD(baum, haus) = 2

Es gelten folgende Grundsätze:

Je höher die Levenshtein-Distanz ausfällt, umso größer ist der Unterschied zwischen x und y.
Die Levenshtein-Distanz ist symmetrisch, d.h., es macht keinen Unterschied, welcher der beiden zu vergleichenden Strings als a und welcher als b definiert wird.
LD(a, b) = LD(b, a)
Die Levenshtein-Distanz ist grundsätzlich nur für das jeweilige Vergleichspaar aussagekräftig. Ergebnisse können nicht ohne Weiteres verglichen werden (s.u.)

Die Levenshtein-Distanz kann unterschiedlich berechnet werden:

im Regelfall werden alle Änderungsoperationen mit eins bewertet (s.o., = ungewichtete Levenshtein-Distanz)
je nach Forschungsgebiet, Fragestellung etc. kann es sinnvoll sein, bestimmte Änderungen höher als die anderen zu bewerten (z.B. Löschung = 4, Einfügung = 2, Austausch = 1; = gewichtete Levenshtein-Distanz)

Um die Berechnungsergebnisse unterschiedlicher Vergleichspaare zueinander in Relation setzen zu können, besteht die Möglichkeit, einen Levenshtein Similarity Index (LSI) zu errechnen. Der LSI berechnet sich wie folgt: Die Levenshtein-Distanz wird durch die Länge des längeren der beiden Vergleichsstrings dividiert und von 1 substrahiert:

Der Index variiert zwischen 0 und 1 mit 0 als Indikator für keinerlei Übereinstimmung und 1 als Indikator für Identität.

Links:
Infoseite der LMU München
Infoseite mit Demo und Erläuterung des Editierwegs

Zur Berechnung der Levenshtein-Distanz stehen in TUSCRIPT zwei Funktionen zur Verfügung.
DISTANCE() berechnet die Levenshtein-Distanz zweier Strings ohne Unterscheidung von Groß- und Kleinschreibung.
DISTANCE_EXACT() berechnet die Levenshtein-Distanz zweier Strings mit Unterscheidung von Groß- und Kleinschreibung.

Berechnung der Levenshtein-Distanz in TUSCRIPT

#MAKRO
$$ MODE TUSCRIPT, {}

- Hier ggf. andere Beispielstrings eintragen:
str_a = "Haus"
str_b = "Baum"

- Berechnung der einfachen und exakten Levenshtein-Distanz
ld = DISTANCE (str_a, str_b)
ld_ex = DISTANCE_EXACT (str_a, str_b)

- Ausgabe der Ergebnisse ins Ablaufprotokoll:
PRINT "LD({str_a}, {str_b}) = {ld}"
PRINT "LD_EXACT({str_a}, {str_b}) = {ld_ex}"

*EOF

Berechnung eines Levenshtein Similarity Index mit Ausgabe der Ergebnisse ins Ablaufprotokoll

$$! string1 = "", string2 = ""
$$ MODE TUSCRIPT, {}

-------------------------------------------------------------------------
- Levenshtein Similarity Index (LSI) für Stringpaare berechnen
-------------------------------------------------------------------------

- einfache Levenshtein-Distanz
lev = DISTANCE (string1, string2)

- Definition:
- 1 minus Levenshtein-Distanz dividiert durch den längeren der beiden
- Vergleichsstrings

- längerer Vergleichstring (Ob die Länge der Version mit Zeilenumbrüchen
- oder diejenige Version nach dem JOIN gemessen wird, macht keinen Unterschied):
zeichen_1 = LENGTH (string1)
zeichen_2 = LENGTH (string2)

zeichen_max = MAX (zeichen_1, zeichen_2)

- Zehnerfaktor ist notwendig, um mit TUSCRIPT Gleitkommazahlvearbeitung
- simulieren zu können
lsi = (100000 - ( lev * 100000 / zeichen_max ) )
lsi = ENCODE (lsi, DECIMAL5)

-------------------------------------------------------------------------
- Ausgabe der Ergebnisse ins Ablaufprotokoll
-------------------------------------------------------------------------

PRINT "Ergebnisse Ähnlichkeitsberechnung {string1}~{string2}"
PRINT ""
PRINT "Zeichenanzahl {string1} = {zeichen_1}"
PRINT "Zeichenanzahl {string2} = {zeichen_2}"
PRINT "LSI({string1}, {string2}) = {lsi}"
PRINT "einfache Levenshtein-Distanz:"
PRINT "LD({string1}, {string2}) = {lev}"

Abruf des Beispielskripts:

Anlegen einer Datei (z.B. lsi_test.m).
Kopieren des Skriptes in die Datei.
Aufruf mit Stringpaar als Parameter:

$?$lsi_test.m,baum,haus
oder
$?$lsi_test.m,teststring,testding

Berechnung eines Levenshtein Similarity Index mit Ausgabe der Ergebnisse in ein RTF-Dokument

$$! string1 = "", string2 = "", prot = ""
$$ MODE TUSCRIPT, {}

----
- Levenshtein Similarity Index (LSI) für Stringpaare berechnen
----

- einfache Levenshtein-Distanz
lev = DISTANCE (string1, string2)

- Definition:
- 1 minus Levenshtein-Distanz dividiert durch den längeren der beiden
- Vergleichsstrings

- längerer Vergleichstring (Ob die Länge der Version mit Zeilenumbrüchen
- oder diejenige Version nach dem JOIN gemessen wird, macht keinen Unterschied):
zeichen_1 = LENGTH (string1)
zeichen_2 = LENGTH (string2)

zeichen_max = MAX (zeichen_1, zeichen_2)

- Zehnerfaktor ist notwendig, um mit TUSCRIPT Gleitkommazahlvearbeitung
- simulieren zu können
lsi = (100000 - ( lev * 100000 / zeichen_max ) )
lsi = ENCODE (lsi, DECIMAL5)

----
- Ausgabe der Ergebnisse als RTF-File
----
rtf_proto = "rtf_proto"
ERROR/STOP CREATE (rtf_proto, SEQ-O, -STD-)

- Sternvariable mit der Ausgabemeldung anlegen
ausg_meld = *
DATA
DATA <b>Ergebnisse Ähnlichkeitsberechnung {string1}~{string2}:</b>
DATA <p align="left">
DATA <br/>Zeichenanzahl {string1} = {zeichen_1}
DATA <br/>Zeichenanzahl {string2} = {zeichen_2}
DATA <br/>
DATA <br/>einfache Levenshtein-Distanz:
DATA <br/>LD({string1}, {string2}) = {lev}
DATA <br/>
DATA <br/>Levenshtein Similarity Index:<fn> Formel:
DATA <mf>LSI=1 - <mf-frac> <mf-num>LD</mf-num> <mf-den>MAX(LEN({string1}), LEN({string2}))</mf-den></mf-frac> </mf>
DATA <br/>
DATA <br/>Der Index variiert zwischen 0 und 1 mit 0 als Indikator für keinerlei Übereinstimmung und 1
DATA als Zeichen für Identität.</fn>
DATA <br/>LSI({string1}, {string2}) = {lsi}
DATA </p>

- Inhalt der Ausgabemeldung in temporäre Datei schreiben
FILE/ERASE/PRINT $rtf_proto = ausg_meld

- RTF-Protokolldatei anlegen
ERROR/STOP CREATE (prot, FDF-O, -STD-)

- Ausgabemeldung von temporärer Datei in RTF-Datei exportieren
EXECUTE #*EXPORT,{rtf_proto},{prot},LO=+

Abruf des Beispielskripts:

Anlegen einer Datei (z.B. lsi_test2.m).
Kopieren des Skriptes in die Datei.
Aufruf mit Stringpaar und RTF-Dokument als Parameter:

$?$lsi_test2.m,baum,haus,lsi_prot.rtf
oder
$?$lsi_test2.m,teststring,testding,lsi_prot.rtf

Achtung:
Öffnet man das erzeugte Dokument mit Libre oder Open Office, kann dies zu unerwünschten Darstellungsfehlern führen. So wurden bei Tests die Formeldarstellungen nicht dargestellt.
Steht auf einem Rechner kein MS-Word zur Verfügung, bietet sich alternativ die Ausgabe ins Ablaufprotokoll wie oben gezeigt oder die Ausgabe in eine TUSTEP- oder Textdatei bzw. die Ausgabe mit #*SATZ an. Mit #*SATZ könnte die Formeldarstellung äquivalent erfolgen.

Zurück zum Inhaltsverzeichnis - Lösungen und Tipps