Levenshtein Distanz Rechner

Levenshtein-Distanz-Rechner

Dieses Beispiel berechnet die Levenshtein-Distanz aus den String-Tools, vorausgefüllt mit dem klassischen Vergleich von „kitten“ zu „sitting“. Gib zwei Zeichenfolgen ein und sieh die Mindestanzahl einzelner Zeichenänderungen, die nötig ist, um eine in die andere umzuwandeln.

So funktioniert es

Die Levenshtein-Distanz nutzt dynamische Programmierung. Es wird eine Matrix aufgebaut, in der jede Zelle die Editierdistanz zwischen Teilzeichenfolgen darstellt. Der Algorithmus füllt die Matrix, indem er an jeder Position drei Operationen betrachtet:

Der Endwert in der Zelle unten rechts der Matrix ist die Levenshtein-Distanz.

Das Beispiel „kitten“ zu „sitting“

Das klassische Beispiel erfordert 3 Änderungen:

1. kitten → sitten (ersetze k durch s)
2. sitten → sittin (ersetze e durch i)
3. sittin → sitting (füge g am Ende ein)

Distanz = 3.

Zeit- und Speicherkomplexität

Der Algorithmus läuft in O(m x n) Zeit und Speicher, wobei m und n die Längen der beiden Zeichenfolgen sind. Für die meisten praktischen Textvergleiche (unter 1000 Zeichen) läuft das im Browser sofort.

Varianten

Mehrere Algorithmen passen Levenshtein für bestimmte Anwendungsfälle an:

• Damerau-Levenshtein fügt Transposition (Vertauschen benachbarter Zeichen) als vierte Operation hinzu
• Gewichtetes Levenshtein weist Operationen unterschiedliche Kosten zu (z. B. kostet Ersetzen mehr als Einfügen)
• Eingeschränkte Editierdistanz begrenzt, welche Operationen erlaubt sind

Anleitung

1. Gib die erste Zeichenfolge in das Eingabefeld ein
2. Gib die zweite Zeichenfolge in das zweite Feld ein
3. Die Editierdistanz erscheint im Ergebnisbereich
4. Das Werkzeug zeigt auch die schrittweise Umwandlung

Häufige Fragen

Was ist die maximal mögliche Distanz?

Die maximale Distanz ist die Länge der längeren Zeichenfolge, was passiert, wenn eine Zeichenfolge komplett leer ist und du jedes Zeichen einfügen musst. Für zwei Zeichenfolgen der Längen m und n beträgt die Distanz höchstens max(m, n).

Wie wirkt sich Groß-/Kleinschreibung auf das Ergebnis aus?

Der Vergleich unterscheidet Groß- und Kleinschreibung. Hello und hello haben die Distanz 1 (der H/h-Unterschied). Wandle für einen groß-/kleinschreibungsunabhängigen Vergleich beide Zeichenfolgen zuerst in Kleinbuchstaben um.

Kann ich das für DNA-Sequenzvergleiche nutzen?

Ja. Die Levenshtein-Distanz wird in der Bioinformatik häufig verwendet, um die Ähnlichkeit zwischen DNA- oder Proteinsequenzen zu messen. Jedes Zeichen steht für ein Nukleotid oder eine Aminosäure, und die Editierdistanz spiegelt die Anzahl der Mutationen zwischen den Sequenzen wider.