Definition - Levenshtein-Distanz

• Generalisierungen:
  • Metrik
  • Dynamische Programmierung
• Involvierte Definitionen:
  • Zeichenkette
  • siehe auch Dynamic Time Warping
  • siehe auch Länge der längsten gemeinsamen Teilfolge
• Veranstaltung: DM
• Referenz:
  • @valdes2024 (p. 39 ff.)
  • Back To Back SWE - Edit Distance Between 2 Strings - The Levenshtein Distance

⠀

Definition: Levenshtein-Distanz

Als Levenshtein-Distanz (auch Edit-Distanz) bezeichnen wir die minimale Anzahl von Löschungen, Einfügungen und Ersetzungen, die erforderlich sind, um eine Zeichenkette in eine andere zu überführen. Damit bietet sie ein Maß für Ähnlichkeit zweier Strings.

In der Regel wählt man die Kosten für Löschungen , die Kosten für Einfügungen und die Kosten für Ersetzungen gleich mit

Die Levenshtein-Distanz zwischen den Präfixen und der Strings erhalten wir rekursiv durch

𝟙

Dabei stellt 𝟙 sicher, dass die Kosten für Ersetzungen nur dann anfallen, wenn und ungleich sind - denn wenn sie gleich sind, muss ja auch nichts ersetzt werden.

Für die Basisfälle setzen wir

Berechnung mittels Teilstring-Matrix

Auch wenn der Algorithmus ziemlich einfach aussieht, hat die Berechnung es in sich.

Wir betrachten den Algorithmus am Beispiel der beiden Wörter BIENE und BEIN.

Wir starten mit der Interpretation der Matrix.

	#	B	E	I	N
#
B	(a)
I		(b)	(c)
E				(d)
N					(e)
E					(f)

• Position (a) fragt nach der Distanz zwischen: B und dem leeren String .
• Position (b) fragt nach der Distanz zwischen: BI und B.
• Position (c) fragt nach der Distanz zwischen BI und BE.
• Position (d) fragt nach der Distanz zwischen: BIE und BEI.
• Position (e) fragt nach der Distanz zwischen: BIEN und BEIN.
• Position (f) fragt nach der Distanz zwischen: BIENE und BEIN.

Die Distanzen zu dem leeren String sind jeweils trivial, weshalb wir die Matrix in der Regel schon mal vorausfüllen:

	#	B	E	I	N
#	0	1	2	3	4
B	1	(a)=0	(b)=1	(c)=2	(d)=3
I	2
E	3
N	4
E	5

Für die erste und zweite Reihe gehen wir einmal alles im Detail durch.

Zur Erinnerung, für die Berechnung gilt jeweils:

• Löschen:
• Einfügen:
• Ersetzen/Gleichheit: 𝟙

In der Matrix-Darstellung können wir uns diese drei Operationen wir eine kleine Schablone vorstellen:

(Ersetzen/Gleichheit)	(Einfügen)
(Löschen)	(Aktuelle Zelle)

• (a): vs. , daher
• (b): vs. , daher Einfügen:
• (c): vs. , daher Einfügen:
• (c): vs. , daher Einfügen:

	#	B	E	I	N
#	0	1	2	3	4
B	1	0	1	2	3
I	2	(a)=1	(b)=1	(c)=1	(d)=3
E	3
N	4
E	5

In der zweiten Reihe haben wir jetzt:

• (a): vs. , daher Löschen:
• (b): vs. , daher Ersetzen:
• (c): vs. , daher Gleich:
• (d): vs. , daher Einfügen:

Der Clou

Die vorgestellte Berechnung durchzuführen und in jedem Schritt zu überlegen: ersetze ich?, lösche ich?, füge ich ein? ist ziemlich anstrengend.

Macht man das aber oft genug, erkennt man irgendwann das Muster, dass wir auch schon oben in der Definition gesehen habe. Wir haben zwei Handlungsmuster:

1. Sind die beiden aktuell betrachteten Buchstaben identisch? Dann wähle stets .
2. Sonst: wähle den kleinsten umliegenden Abstands-Wert und addiere . Für komplexere Kosten, addiere zunächst entsprechend. Kompakt wie aus der obigen Definition:

Nach diesem Muster wollen wir das Beispiel jetzt noch vervollständigen.

	#	B	E	I	N
#	0	1	2	3	4
B	1	0	1	2	3
I	2				3
E	3	(a)=2	(b)=	(c)=2	(d)=2
N	4
E	5

• (a): , der kleinste umliegende Wert ist , also
• (b): , also
• (c): , der kleinste umliegende Wert ist , also
• (d): , der kleinste umliegende Wert ist , also

Nach dem Schema vervollständigen wir noch kurz die Matrix:

	#	B	E	I	N
#		1	2	3	4
B	1			2	3
I	2	1	1		3
E	3	2	1		2
N	4	3	2	2
E	5	4	3	3

Die Distanz zwischen BIENE und BEIN können wir schließlich aus der letzten Zelle ablesen, sie beträgt .

Die durchgeführten Operationen lassen sich aus dem kürzesten Weg ablesen. Hier kann es auch mehrere Optionen geben, bspw:

B E I N B I E N E

Also:

• B gleich
• E löschen
• I gleich
• E einfügen
• Ngleich
• E einfügen