Levenshtein-Distanz

Die Levenshtein-Distanz (auch Edit-Distanz, Editierdistanz oder Editierabstand) bezeichnet in der Informationstheorie ein Maß für den Unterschied zwischen zwei Zeichenketten bezüglich der minimalen Anzahl der Operationen Einfügen, Löschen und Ersetzen, um die eine Zeichenkette in die andere zu überführen. Benannt ist die Distanz nach dem russischen Wissenschaftler Wladimir Lewenstein, der sie 1965 einführte.

Um beispielsweise von „Tier“ zu „Tor“ zu kommen ist eine Ersetzung und eine Löschung notwendig, die Levenshtein-Distanz beträgt also 2:

Tier
Toer (Ersetze i durch o)
Tor (Lösche e)

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

Die Levenshtein-Distanz kann als Erweiterung der Hamming-Distanz angesehen werden, welche sich auf Ersetzungen beschränkt und daher nur Zeichenketten gleicher Länge bemessen kann. Erweiterungen der Levenshtein-Distanz oder parallele Entwicklungen, wie z.B. von Damerau, berücksichtigen auch weitere Operationen wie beispielsweise das Vertauschen zweier Zeichen oder gewichten die Operationen unterschiedlich. Mathematisch definiert die Levenshtein-Distanz eine Metrik auf dem Raum der Symbolsequenzen.

Algorithmus

Ein allgemein benutzter, einfacher Algorithmus zur Berechnung benötigt eine Matrix der Form (n + 1) x (m+1), wobei n und m die Längen der zu vergleichenden Strings sind. So sieht er in Pseudocode aus:

int LevenshteinDistance(char s[1..n], char t[1..m])
   declare int d[0..n,0..m]
   declare int i, j, cost
   for i := 0 to n
       d[i,0] := i
   for j := 0 to m
       d[0,j] := j
   for i := 1 to n
       for j := 1 to m
           if s[i] = t[j] then cost := 0
                          else cost := 1
           d[i,j] := minimum(d[i-1,j  ] + 1,    // insertion
                             d[i,  j-1] + 1,    // deletion
                             d[i-1,j-1] + cost) // substitution
   return d[n,m]

Das Verfahren lässt sich auch leicht manuell in einer Tabelle durchführen.

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
wenn beide Strings identische Längen haben, ist die Hamming-Distanz die obere Schranke
wenn die Längen nicht identisch sind, ist die Hamming-Distanz plus dem Längenunterschied die obere Schranke

Literatur

Vladimir I. Levenshtein: Binary codes capable of correcting deletions, insertions, and reversals. In: Doklady Akademii Nauk SSSR, 163(4) S. 845-848, 1965 (Russisch). Englische Übersetzung in: Soviet Physics Doklady, 10(8) S. 707-710, 1966.

Algorithmus

Schranken

Verwandte Verfahren

Literatur