Zuletzt aktualisiert: 2026-07-01

Levenshtein-Distanz

Die Levenshtein-Distanz, auch Editierdistanz genannt, misst, wie verschieden zwei Zeichenketten sind, indem sie die kleinste Anzahl an Einzelzeichen-Bearbeitungen zählt, die nötig sind, um die eine in die andere zu überführen. Die erlaubten Bearbeitungen sind Einfügen, Löschen und Ersetzen, jede mit Kosten eins. Der Rechner nimmt zwei Zeichenketten entgegen und liefert diese Distanz zusammen mit einer Ähnlichkeit in Prozent – nützlich für Rechtschreibprüfung, unscharfen Abgleich und den Vergleich von Sequenzen wie DNA.

Die drei Bearbeitungsoperationen

Jede Umwandlung zwischen zwei Zeichenketten lässt sich als Folge dreier Grundzüge ausdrücken. Eine Einfügung fügt ein Zeichen hinzu, eine Löschung entfernt eines, und eine Ersetzung tauscht ein Zeichen gegen ein anderes. Die Levenshtein-Distanz fragt nach der günstigsten solchen Folge, wobei jeder Zug eins kostet. Da eine Ersetzung ein einzelner Schritt ist und nicht ein Löschen gefolgt von einem Einfügen, zählt das Ändern eines Buchstabens stets als eine Bearbeitung, nicht als zwei.

Benannt nach Wladimir Lewenstein, der sie 1965 definierte, verallgemeinert das Maß die ältere Hamming-Abstand-Rechner: Die Hamming-Distanz erlaubt nur Ersetzungen und nur bei gleich langen Zeichenketten, während die Levenshtein-Distanz auch Einfügungen und Löschungen zulässt und so Zeichenketten unterschiedlicher Länge verarbeitet.

Die Tabelle der dynamischen Programmierung

Die Distanz wird berechnet, indem eine Tabelle $D$ gefüllt wird – mit einer Zeile je Zeichen der ersten Zeichenkette (plus einer führenden leeren Zeile) und einer Spalte je Zeichen der zweiten (plus einer führenden leeren Spalte). Die Zelle $D[i][j]$ enthält die Editierdistanz zwischen den ersten $i$ Zeichen von A und den ersten $j$ Zeichen von B.

Die erste Zeile und Spalte zählen Bearbeitungen gegen die leere Zeichenkette, also $D[i][0] = i$ und $D[0][j] = j$. Jede andere Zelle ist das Minimum dreier Kandidaten:

dabei sind die Ersetzungskosten $c$ gleich 0, wenn die Zeichen übereinstimmen, und 1, wenn sie sich unterscheiden. Die Antwort steht in der Zelle unten rechts. Das Füllen der Tabelle braucht eine Zeit proportional zum Produkt der beiden Längen, $m \times n$.

Rechenbeispiel

Nehmen wir das klassische Paar „kitten“ und „sitting“. Der optimale Weg durch die Tabelle ergibt drei Bearbeitungen:

Eine kürzere Folge gibt es nicht, also beträgt die Distanz 3. Die längere Zeichenkette hat 7 Zeichen, somit ist die Ähnlichkeit $1 - 3/7 \approx 0{,}571$, also etwa 57 %.

Ähnlichkeit und ihre Grenzen

Der Rechner normiert die rohe Distanz mit

$S = 1 - \dfrac{d_L}{\max(m, n)}$

zu einem Ähnlichkeitswert. Das Teilen durch die Länge der längeren Zeichenkette hält das Ergebnis zwischen 0 % für völlig verschiedene und 100 % für identische Zeichenketten; zwei leere Zeichenketten gelten als identisch. Dies ist eine gängige Normierung – andere Werkzeuge teilen durch die Summe der Längen oder verwenden verhältnisbasierte Maße –, daher sind Ähnlichkeitszahlen aus verschiedenen Quellen nicht direkt vergleichbar.

Wo sie eingesetzt wird

Rechtschreibprüfungen ordnen Korrekturvorschläge nach der Editierdistanz zum falsch geschriebenen Wort. Such- und Datenbanksysteme nutzen sie für unscharfen Abgleich und tolerieren so Tippfehler beim Nachschlagen von Namen oder Adressen. In der Bioinformatik liegt die Editierdistanz dem Sequenzalignment für den Vergleich von DNA, RNA und Proteinen zugrunde, wo Einfügungen und Löschungen Mutationen entsprechen. Das einfache Levenshtein-Kostenmodell behandelt alle Bearbeitungen gleich; Anwendungen, die unterschiedliche Strafen für verschiedene Operationen brauchen oder sehr lange Sequenzen effizient ausrichten müssen, erweitern es um gewichtete Kosten oder spezialisierte Alignment-Algorithmen.