Levenshtein Distanz (Edit Distance)

Rechner zur Berechnung der minimalen Editieroperationen mit ausführlichen Formeln und Beispielen

Levenshtein Distanz Rechner

Was wird berechnet?

Die Levenshtein Distanz (auch Editierdistanz genannt) ist die minimale Anzahl von Operationen (Einfügen, Löschen, Ersetzen), um einen String in einen anderen umzuwandeln.

Eingabestrings

Erster String
Ursprungsstring (kann leer sein)

Zweiter String
Zielstring (kann leer sein)

Ergebnis

Levenshtein Distanz:

Minimale Anzahl von Editieroperationen

Levenshtein Info

Operationen

Erlaubte Operationen:

Einfügen eines Zeichens
Löschen eines Zeichens
Ersetzen eines Zeichens

Anwendung: Rechtschreibkorrektur, DNA-Sequenzanalyse, Plagiatserkennung und Datei-Versionskontrolle.

Spezielle Fälle

Identische Strings:
LD("ABC", "ABC") = 0

Leerer String:
LD("", "ABC") = 3 (3× Einfügen)

Völlig unterschiedlich:
LD("CAT", "DOG") = 3

Formeln der Levenshtein Distanz

Rekursive Definition

\[LD(i,j) = \begin{cases} j & \text{wenn } i = 0 \\ i & \text{wenn } j = 0 \\ LD(i-1,j-1) & \text{wenn } s_i = t_j \\ 1 + \min \begin{cases} LD(i-1,j) \\ LD(i,j-1) \\ LD(i-1,j-1) \end{cases} & \text{sonst} \end{cases}\]

Matrix-Form

\[D[i,j] = \min \begin{cases} D[i-1,j] + 1 & \text{(Löschung)} \\ D[i,j-1] + 1 & \text{(Einfügung)} \\ D[i-1,j-1] + c & \text{(Substitution)} \end{cases}\] \[c = \begin{cases} 0 & \text{wenn } s_i = t_j \\ 1 & \text{sonst} \end{cases}\]

Initialisierung

\[D[i,0] = i \text{ für alle } i\] \[D[0,j] = j \text{ für alle } j\] Basis: Leere Strings

Komplexität

\[\text{Zeit: } O(m \cdot n)\] \[\text{Platz: } O(m \cdot n)\] m, n = String-Längen

Normalisierte Form

\[LD_n(s,t) = \frac{LD(s,t)}{\max(|s|,|t|)}\] Werte zwischen 0 und 1

Ähnlichkeit

\[\text{Sim}(s,t) = 1 - LD_n(s,t)\] Ähnlichkeitsmaß (0-1)

Detailliertes Rechenbeispiel

Beispiel: Levenshtein("Das Tier im Zoo", "Das Tor am Zoo")

Gegeben:

String 1: "Das Tier im Zoo"
String 2: "Das Tor am Zoo"

Benötigte Operationen:

Ersetze i → o in "Tier"
Lösche e aus "Tier"
Ersetze i → a in "im"

Transformation:

"Das Tier im Zoo" → "Das Tor im Zoo" → "Das Tor m Zoo" → "Das Tor am Zoo"

Ergebnis: Levenshtein Distanz = 3

Dynamische Programmierung Matrix

Beispiel: Berechnung für "KITTEN" → "SITTING"

DP-Matrix:

	""	S	I	T	T	I	N	G
""	0	1	2	3	4	5	6	7
K	1	1	2	3	4	5	6	7
I	2	2	1	2	3	4	5	6
T	3	3	2	1	2	3	4	5
T	4	4	3	2	1	2	3	4
E	5	5	4	3	2	2	3	4
N	6	6	5	4	3	3	2	3

Operationen:

S für K
I für I (Match)
T für T (Match)
T für T (Match)
I für E
N für N (Match)
G einfügen

Distanz: 3

Praktische Anwendungen

Textverarbeitung

Rechtschreibkorrektur
Autokorrektur
Suchvorschläge
Plagiatserkennung

Bioinformatik

DNA-Sequenz-Alignment
Protein-Vergleiche
Genetische Distanzen
Evolutionsanalyse

Software-Entwicklung

Versionskontrolle (Git diff)
Code-Ähnlichkeit
Merge-Konflikte
Refactoring-Tools

Algorithmus & Komplexität

Dynamische Programmierung vs. Rekursion

Naive Rekursion:

Zeitkomplexität: O(3^min(m,n))
Platzkomplexität: O(min(m,n))
Problem: Exponentielles Wachstum
Verwendung: Nur für sehr kurze Strings

Dynamische Programmierung:

Zeitkomplexität: O(m×n)
Platzkomplexität: O(m×n)
Vorteil: Praktikabel für lange Strings
Optimierung: O(min(m,n)) Platz möglich

Optimierungen:

Platzoptimierung: Nur zwei Zeilen der Matrix speichern

Early Termination: Bei großen Distanzen vorzeitig abbrechen

Praxisbeispiele

Suchvorschläge

Szenario: Benutzer tippt "Pariz" statt "Paris"

Kandidaten:
• Paris: LD = 1 (z→s)
• Berlin: LD = 5
• London: LD = 6
→ Vorschlag: Paris

DNA-Mutation

Szenario: Vergleich von Gensequenzen

Original: ATCGATCG
Mutiert: ATGGATCG
LD = 1: C→G an Position 3
→ Punktmutation erkannt

Varianten und Erweiterungen

Distanz Funktionen

Bray Curtis Distanz • Canberra Distanz • Euklidischer Abstand • Korrelationskoeffizient • Kosinus Ähnlichkeit • Levenshtein Distanz • Manhattan Distanz • Minkowski Distanz • Maximumsnorm •