Quelltext der Seite Levenshtein-Distanz

Die '''Levenshtein-Distanz''' (auch '''Editierdistanz''') zwischen zwei [[Zeichenkette]]n ist die minimale Anzahl einfügender, löschender und ersetzender Operationen, um die erste Zeichenkette in die zweite umzuwandeln. Benannt ist die Distanz nach dem russischen Wissenschaftler [[Wladimir Iossifowitsch Lewenstein|Wladimir Lewenstein]] ([[Englische Sprache|engl.]] ''Levenshtein''), der sie 1965 einführte. Mathematisch ist die Levenshtein-Distanz eine [[Metrischer Raum|Metrik]] auf dem Raum der [[Symbolsequenz]]en.

Beispielsweise entspricht die Levenshtein-Distanz zwischen „Bar“ und „Bier“ zwei. Eine mögliche Folge von zwei Operationen ist:

{| class="wikitable"
! Wort !! Operation !! Anzahl
|-
| Bar || keine (Ausgangswort) || 0
|-
| Bir || Ersetzung (a → i) || 1
|-
| Bier || Einfügung (e) || '''2'''
|}

Ein anderes Beispiel ist die Distanz von eins zwischen „uninformiert“ und „uniformiert“:

{| class="wikitable"
! Wort !! Operation !! Anzahl
|-
| uninformiert || keine (Ausgangswort) || 0
|-
| uniformiert || Löschung (n) || '''1'''
|}

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 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 [[Dynamische Programmierung|dynamischen Programmierung]] verwendet, als Levenshtein-Algorithmus bezeichnet.

Der Algorithmus ist durch folgende [[Matrix (Mathematik)|Matrix]]-[[Lineare Differenzengleichung|Rekurrenzen]] spezifiziert, wobei <math>u</math> und <math>v</math> die beiden Eingabe-Zeichenketten bezeichnen:

:<math>m = |u|</math>
:<math>n = |v|</math>

:<math>D_{0, 0} = 0</math>
:<math>D_{i, 0} = i, 1 \leq i \leq m</math>
:<math>D_{0, j} = j, 1 \leq j \leq n</math>

:<math>
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}</math>,
::<math>1 \leq i\leq m, 1\leq j \leq n</math>

Nachdem die Matrix <math>D</math> berechnet ist, steht die Levenshtein-Distanz, d.&nbsp;h. die minimale Anzahl der Edit-Operationen, in der Matrix-Zelle <math>D_{m,n}</math>. In jeder Zelle <math>D_{i,j}</math> steht die Levenshtein-Distanz der Präfixe <math>u_{0,i}</math> und <math>v_{0,j}</math>. Bei einer weiteren Löschung bzw. Einfügung wird nun nur ein weiteres Zeichen von <math>u</math> bzw. <math>v</math> verbraucht. D.h. das Resultat wird in <math>D_{i + 1,j}</math> bzw. <math>D_{i,j + 1}</math> gespeichert. Also lassen sich die Kosten für eine Löschung bzw. Einfügung in Zelle <math>D_{i,j}</math> rekurrent durch <math>D_{i-1,j} + 1</math> bzw. <math>D_{i,j-1} + 1</math> 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 <math>D_{i,j-1}</math> werden rekursiv die Optimierungsentscheidungen zurückverfolgt. Im [[Pseudocode]] ist der Backtrace-Algorithmus:

<syntaxhighlight lang="python">
string backtrace(i, j):
  if i>0 && D[i-1,j] + 1 == D[i,j]
    return backtrace(i-1, j) + " Löschung "
  if j>0 && D[i,j-1] + 1 == D[i,j]
    return backtrace(i, j-1) + " Einfügung "
  if i>0 && j>0 && D[i-1, j-1] + 1 == D[i,j]
    return backtrace(i-1, j-1) + " Ersetzung "
  if i>0 && j>0 && D[i-1, j-1] == D[i,j]
    return backtrace(i-1, j-1) + " Gleichheit "
  return ""
</syntaxhighlight>

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 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 <span style="color:#FF0000;">'''2'''</span>

Der Abstand der beiden Zeichenketten ist 2. ε steht hierbei für die leere Zeichenkette "".

== Komplexität ==
Die Laufzeit des Algorithmus ist in [[Landau-Symbole|O]]<math>(mn)</math>, da alle Zellen der <math>(m+1)\times (n+1)</math>-Matrix berechnet werden und der Rechenaufwand pro Zelle konstant ist.

Der Speicherbedarf ist in <math>O(nm)</math>, da die Matrix <math>m+1</math> Zeilen und <math>n+1</math> Spalten hat. Wenn allerdings kein Backtracking 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 <math>O(\min(m,n))</math>.

Der [[Hirschberg-Algorithmus]] ermöglicht die Berechnung der Levenshtein-Distanz und eines „Backtrace“ in quadratischer Zeit und mit linearem Speicherverbrauch.

== Schranken ==
Für die Levenshtein-Distanz gelten einige obere und untere [[Beschränktheit|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-Abstand|Hamming-Distanz]] plus dem Längenunterschied der Zeichenketten
<!-- * If the strings are called s and t, the number of characters found in s but not in t is a lower bound. -->

== Abgrenzung ==
Die Levenshtein-Distanz kann als Erweiterung des [[Hamming-Abstand]]s 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|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 [[Sequenzalignment]]s zweier Zeichenketten verwandt. Der Needleman-Wunsch-Algorithmus ist in <math>O(n^3)</math> und lässt beliebige Kostenfunktionen für Einfüge- bzw. Löschoperationen der Länge <math>\geq 1</math> 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 <math>O(n^2)</math> 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 <math>0</math> bewertet und im Backtrace ignoriert. D.h. der Smith-Waterman-Algorithmus berechnet das lokale „sequence alignment“. Seine Laufzeit liegt in <math>O(n^2)</math>.

Die Levenshtein-Distanz kann als Sonderform der [[Dynamic Time Warping|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 zwei Operationen notwendig. Damerau-Levenshtein benötigt nur eine einzige.

Folgende Matrix-Rekurrenzen spezifizieren die Algorithmus-Variante.

:<math>m = |u|</math>
:<math>n = |v|</math>

:<math>D_{0, 0} = 0</math>
:<math>D_{i, 0} = i</math>, <math>1 \leq i \leq m</math>
:<math>D_{0, j} = j</math>, <math>1 \leq j \leq n</math>

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

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

Wobei <math>c</math> die Kosten für eine Vertauschung von zwei Zeichen bezeichnet.

== Siehe auch ==
* [[Pattern Matching]]

== Literatur ==
* {{Literatur |Autor=Fred J. Damerau |Titel=A technique for computer detection and correction of spelling errors |Sammelwerk=Communications of the ACM |Band=7 |Nummer=3 |Datum=1964-03 |Seiten=171–176}}
* {{Literatur |Autor=Vladimir I. Levenshtein |Titel=Binary codes capable of correcting deletions, insertions, and reversals |Sammelwerk=Doklady Akademii Nauk SSSR |Band=163 |Nummer=4 |Datum=1965 |Seiten=845–848 |Sprache=ru |Kommentar= Englische Übersetzung in: Soviet Physics Doklady, 10(8) S. 707–710, 1966}}

== Weblinks ==
* [http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node2.html Erklärung und Online-Visualisierung mit Flash] (englisch)
* [http://www.let.rug.nl/kleiweg/lev/ Erklärung und Online Visualisierung mit JavaScript] (englisch)
* [http://www.cut-the-knot.org/do_you_know/Strings.shtml Java-Applet zum Berechnen der Levenshtein-Distanz und Hamming-Abstand] (englisch)
* [[b:en:Algorithm Implementation/Strings/Levenshtein distance|Algorithm Levenshtein distance (Wikibooks)]] (englisch)

[[Kategorie:Informationstheorie]]
[[Kategorie:Algorithmus]]
[[Kategorie:Dynamische Programmierung]]
[[Kategorie:Quantitative Linguistik]]