Levenshtein-Distanz

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Levenshtein-Distanz (auch Editierdistanz) 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 zwei 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[Bearbeiten]

In dem Levenshtein-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 die 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[Bearbeiten]

Das Verfahren lässt sich nun leicht in einer Tabelle durchführen. Hier ein Beispiel mit den beiden Zeichenketten „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 Zeichenketten ist 2. ε steht hierbei für die leere Zeichenkette "".

Komplexität[Bearbeiten]

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 eines „Backtrace“ in quadratischer Zeit und mit linearem Speicherverbrauch.

Schranken[Bearbeiten]

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

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

Abgrenzung[Bearbeiten]

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 Distanzberechnung beispielsweise mit dem Kölner Phonetik- oder dem Soundex-Algorithmus in eine Lautsymbol-Zeichenkette ü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^3) 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^2) 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 „sequence alignment“. Seine Laufzeit liegt in O(n^2).

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

Varianten[Bearbeiten]

Gewichtete Levenshtein-Distanz[Bearbeiten]

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[Bearbeiten]

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 zwei 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}
(i=1, 1\leq j\leq n)\vee (1\leq i\leq m, j=1)

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}
2 \leq i \leq m, 2\leq j \leq n

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

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

  •  Fred J. Damerau: A technique for computer detection and correction of spelling errors. In: Communications of the ACM. 7, Nr. 3, März 1964, S. 171–176.
  •  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[Bearbeiten]