Levenshtein-Distanz

Die Levenshtein-Distanz zwischen zwei Zeichenketten ist die minimale Anzahl von Einfüge-, Lösch- und Ersetz-Operationen, um die erste Zeichenkette in die zweite umzuwandeln. Benannt ist die Distanz nach dem russischen Wissenschaftler Wladimir Lewenstein, der sie 1965 einführte. Mathematisch ist die Levenshtein-Distanz eine Metrik auf dem Raum der Symbolsequenzen.

Beispielsweise ist die Levenshtein-Distanz zwischen „Tier“ zu „Tor“ 2. Eine mögliche Folge von 2 Operationen ist:

1. Tier
2. Toer (Ersetze i durch o)
3. Tor (Lösche e)

In der Praxis wird die Levenshtein-Distanz zur Bestimmung der Ähnlichkeit von Zeichenketten beispielsweise zur Rechtschreibprüfung oder bei der Duplikaterkennung angewandt.

Algorithmus

In dem Lewenstein-Artikel von 1965 wird die Levenshtein-Distanz definiert, aber es wird kein Algorithmus zur Berechnung der Distanz angegeben. In der Literatur wird ein Algorithmus zur Berechnung der Levenshtein-Distanz, der die Methode der dynamischen Programmierung verwendet, als Levenshtein-Algorithmus bezeichnet.

Der Algorithmus ist durch folgende Matrix-Rekurrenzen spezifiziert, wobei u und v die beiden Eingabe-Zeichenketten bezeichnen:

m = | u |

n = | v |

D_0,0 = 0

$D_{i, 0} = i, 1 \leq i \leq m$

$D_{0, j} = j, 1 \leq j \leq n$

$D_{i, j} = min \begin{cases} D_{i - 1, j - 1}&+ 0 \ {\rm falls}\ u_i = v_j\\ D_{i - 1, j - 1}&+ 1 \ {\rm(Ersetzung)} \\ D_{i, j - 1}&+ 1 \ {\rm(Einf\ddot ugung)} \\ D_{i - 1, j}&+ 1 \ {\rm(L\ddot oschung)} \end{cases}$,

$1 \leq i\leq m, 1\leq j \leq n$

Nachdem die Matrix D berechnet ist, steht die Levenshtein-Distanz, d.h. die minimale Anzahl der Edit-Operationen, in der Matrix-Zelle D_m,n. In jeder Zelle D_i,j steht Levenshtein-Distanz der Präfixe u_0,i und v_0,j. Bei einer weiteren Löschung bzw. Einfügung wird nun nur ein weiteres Zeichen von u bzw. v verbraucht. D.h. das Resultat wird in D_{i + 1,j} bzw. D_{i,j + 1} gespeichert. Also lassen sich die Kosten für eine Löschung bzw. Einfügung in Zelle D_i,j rekurrent durch D_{i − 1,j} + 1 bzw. D_{i,j − 1} + 1 berechnen. Analog ist der Fall der Ersetzung zu erklären.

Wenn nicht nur die Levenshtein-Distanz berechnet werden soll, sondern auch die Folge der Operationen, die zu dem Ergebnis geführt hat, muss ein Backtrace auf der berechneten Matrix durchgeführt werden. D.h. beginnend von D_{i,j − 1} werden rekursiv die Optimierungsentscheidungen zurückverfolgt. Im Pseudocode ist der Backtrace-Algorithmus:

string backtrace(i, j):
  if i>0 && D[i-1,j] + 1 == D[i,j]
    return backtrace(i-1, j) + " Del "
  if j>0 && D[i,j-1] + 1 == D[i,j]
    return backtrace(i, j-1) + " Ins "
  if i>0 && j>0 && D[i-1, j-1] + 1 == D[i,j]
    return backtrace(i-1, j-1) + " Rep "
  if i>0 && j>0 && D[i-1, j-1]  == D[i,j]
    return backtrace(i-1, j-1) + " Eq "
  return ""

Um den Pseudo-Code zu vereinfachen wird nur ein möglicher Backtrace berechnet.

Beispiel

Das Verfahren lässt sich nun leicht in einer Tabelle durchführen. Hier ein Beispiel mit den beiden Strings „Tier“ und „Tor“.

  ε T o r
ε 0 1 2 3
T 1 0 1 2
i 2 1 1 2
e 3 2 2 2
r 4 3 3 2

Der Abstand der beiden Strings ist 2. ε steht hierbei für den leeren String „“.

Komplexität

Die Laufzeit des Algorithmus ist in O(mn), da alle Zellen der $(m+1)\times (n+1)$-Matrix berechnet werden, und der Rechenaufwand pro Zelle konstant ist.

Der Speicherbedarf ist in O(nm), da die Matrix m + 1 Zeilen und n + 1 Spalten hat. Wenn allerdings kein Backtracing durchgeführt wird, dann wird zur zeilen- bzw. spaltenweisen Berechnung der Matrix nur die jeweils letzte Zeile bzw. Spalte zur Berechnung der nächsten Zeile bzw. Spalte benötigt. Der Speicherbedarf liegt in dem Fall also in O(min(m,n)).

Der Hirschberg-Algorithmus ermöglicht die Berechnung der Levenshtein-Distanz und einem Backtrace in quadratischer Zeit und mit linearem Speicherverbrauch.

Schranken

Für die Levenshtein-Distanz gelten einige obere und untere Schranken:

• sie beträgt mindestens den Unterschied der Längen beider Strings
• sie beträgt höchstens die Länge des längeren Strings
• sie ist dann und nur dann 0, wenn beide Strings identisch sind (Definition Metrik)
• sie ist nicht größer als die Hamming-Distanz plus dem Längenunterschied der Strings

Abgrenzung

Die Levenshtein-Distanz kann als Erweiterung des Hamming-Abstands angesehen werden, welcher sich auf Ersetzungen beschränkt und daher nur Zeichenketten gleicher Länge bemessen kann. Eine Phonetische Suche kann die Levenshtein-Distanz verwenden, um Fehler zu erlauben. Zu vergleichende Wörter können vor einer Distanz-Berechnung beispielsweise mit dem Kölner Phonetik- oder dem Soundex-Algorithmus in einen Lautsymbol-String überführt werden.

Der DP-Algorithmus zur Berechnung der Levenshtein-Distanz ist mit dem Needleman-Wunsch-Algorithmus zur Berechnung des Sequenzalignments zweier Zeichenketten verwandt. Der Needleman-Wunsch-Algorithmus ist in O(n³) und lässt beliebige Kostenfunktionen für Einfüge- bzw. Löschoperationen der Länge $\geq 1$ zu. Bei dem Levenshtein-Algorithmus besteht eine Einfüge- bzw. Löschoperation aus maximal einem Zeichen. Varianten des Needleman-Wunsch Algorithmus beschränken die Wahl der Kostenfunktion, so dass deren Laufzeit in O(n²) liegt.

Der Smith-Waterman-Algorithmus optimiert die Kosten der Edit-Operationen nach dem gleichen DP-Schema wie der Needleman-Wunsch- bzw. der Levenshtein-Algorithmus, allerdings werden Einfüge- bzw. Lösch-Operationen am Anfang- bzw. Ende einer Sequenz mit 0 bewertet und im Backtrace ignoriert. D.h. der Smith-Waterman-Algorithmus berechnet das lokale Sequenzalignment. Seine Laufzeit liegt in O(n²).

Die Levenshtein-Distanz kann als Sonderform der Dynamic-Time-Warping-Distanz (DTW) betrachtet werden.

Varianten

Gewichtete Levenshtein-Distanz

Die Kosten der einzelnen Einfüge-, Lösch- und Ersetzungsoperationen können auch unterschiedlich oder sogar abhängig von den jeweiligen beteiligten Zeichen gewichtet werden. Das so verallgemeinerte Verfahren wird als gewichtete Levenshtein-Distanz, Weighted Levenshtein Distance oder kurz WLD-Algorithmus bezeichnet.

Ein Beispiel für gewichtete Kosten für Distanzoperationen, die mit dem WLD-Algorithmus minimiert werden können, sind die Kosten der Schreibmaschinendistanz.

Damerau-Levenshtein-Distanz

Damerau-Levenshtein erweitert die Funktionalität von Levenshtein um die Fähigkeit, zwei vertauschte Zeichen zu identifizieren, beispielsweise „Raisch“ ↔ „Rasich“. Um die eine Zeichenfolge in die andere zu überführen, wären mit Levenshtein 2 Operationen notwendig. Damerau-Levenshtein benötigt nur eine einzige.

Folgende Matrix-Rekurrenzen spezifizieren die Algorithmus-Variante.

m = | u |

n = | v |

D_0,0 = 0

D_i,0 = i, $1 \leq i \leq m$

D_0,j = j, $1 \leq j \leq n$

$D_{i, j} = min \begin{cases} D_{i - 1, j - 1}&+ 0 \ {\rm falls}\ u_i = v_j\\ D_{i - 1, j - 1}&+ 1 \ {\rm(Ersetzung)} \\ D_{i, j - 1}&+ 1 \ {\rm(Einf\ddot ugung)} \\ D_{i - 1, j}&+ 1 \ {\rm(L\ddot oschung)} \end{cases}$

$(1 \leq i \leq 2, 1\leq j\leq n)\vee (1\leq i\leq m, 1\leq j \leq 2)$

$D_{i, j} = min \begin{cases} D_{i - 1, j - 1}&+ 0 \ {\rm falls}\ u_i = v_j\\ D_{i - 1, j - 1}&+ 1 \ {\rm(Ersetzung)} \\ D_{i, j - 1}&+ 1 \ {\rm(Einf\ddot ugung)} \\ D_{i - 1, j}&+ 1 \ {\rm(L\ddot oschung)} \\ D_{i-2, j-2}&+c \ {\rm Vertauschung, falls}\ u_i = v_{j-1} \wedge u_{i-1} = v_j\\ \end{cases}$

$3 \leq i \leq m, 3\leq j \leq n$

Wobei c die Kosten für eine Vertauschung von zwei Zeichen bezeichnet.

Siehe auch

• Jaro-Metrik
• Jensen-Shannon-Distanz
• Pattern Matching

Literatur

• Fred J. Damerau: A technique for computer detection and correction of spelling errors. In: Communications of the ACM. 7, Nr. 3, März 1964, ISSN 0001-0782, S. 171–176 (pdf).
• Vladimir I. Levenshtein: Binary codes capable of correcting deletions, insertions, and reversals. In: Doklady Akademii Nauk SSSR. 163, Nr. 4, 1965, S. 845–848 (Russisch, Englische Übersetzung in: Soviet Physics Doklady, 10(8) S. 707–710, 1966).

Weblinks

• Erklärung und Online-Visualisierung (englisch)
• Java Applet zum Berechnen der Levenshtein-Distanz und Hamming-Abstand (englisch)
• Algorithm Levenshtein distance (englisch)