Levenshtein-Abstand

Levenshtein-Abstand

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:

  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.

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. Erweiterungen der Levenshtein-Distanz oder parallele Entwicklungen, wie zum Beispiel 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.

Die Editierdistanz ist eine Sonderform der Dynamic-Time-Warping-Distanz (DTW).

Inhaltsverzeichnis

Algorithmus

Ein allgemein benutzter, einfacher Algorithmus zur Berechnung benötigt eine Matrix der Form (n + 1) × (m+1), wobei n und m die Längen der zu vergleichenden Strings sind. Folgende Rekursionsgleichung liegt der Berechnung der Matrix zugrunde:

D0,0 = 0
Di,0 = i
D0,j = j

\forall (i,j) i \in [1..n], j \in [1..m]:
D_{i, j} = min \begin{cases}
D_{i - 1, j - 1}&+ 0 \ {\rm(gleicher Buchstabe)} \\
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}

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 „“.

So sieht der Algorithmus 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]

Der hier vorgestellte einfache Algorithmus hat einen Speicherverbrauch von m*n. Der wesentlich komplexere Hirschberg-Algorithmus berechnet die Levenshtein-Distanz 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
  • sie ist nicht größer als die Hamming-Distanz plus dem Längenunterschied der Strings

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.

Im folgenden die Funktion in C#:

       private int DamerauLevenshteinDistance(string src, string dest){
           int[,] d = new int[src.Length + 1, dest.Length + 1];
           int i, j, cost;
           char[] str1 = src.ToCharArray();
           char[] str2 = dest.ToCharArray();    
           
           for (i = 0; i <= str1.Length; i++){
               d[i, 0] = i;
           }
           for (j = 0; j <= str2.Length; j++){
               d[0, j] = j;
           }
           for (i = 1; i <= str1.Length; i++){
               for (j = 1; j <= str2.Length; j++){
 
                   if (str1[i - 1] == str2[j - 1])
                       cost = 0;
                   else
                       cost = 1;
 
                   d[i, j] =
                       Math.Min(d[i - 1, j] + 1,     // Deletion
                       Math.Min(d[i, j - 1] + 1,     // Insertion
                       d[i - 1, j - 1] + cost));     // Substitution
 
                   if ((i > 1) && (j > 1) && (str1[i - 1] == str2[j - 2]) && (str1[i - 2] == str2[j - 1])){
                       d[i, j] = Math.Min(d[i, j], d[i - 2, j - 2] + cost);
                   }
               }
           }
           return d[str1.Length, str2.Length];
       }

adaptiert auf PHP:

       function DamerauLevenshteinDistance($srcString, $destString){ // returns int
           $d = array();
           $i = 0;
           $j = 0;
           $cost = 0;
           $str1 = str_split($srcString);
           $str2 = str_split($destString);    
       
           for ($i=0; $i<=sizeof($str1); $i++){
               $d[$i][0] = $i;
           }
           for ($j=0; $j<=sizeof($str2); $j++){
               $d[0][$j] = $j;
           }
           for ($i=1; $i<=sizeof($str1); $i++){
               for ($j=1; $j<=sizeof($str2); $j++){
                   if ($str1[($i-1)] == $str2[($j-1)]) $cost = 0;
                   else $cost = 1;
     
                   $d[$i][$j] =
                       min($d[($i-1)][$j] + 1,       // Deletion
                       min($d[$i][($j-1)] + 1,       // Insertion
                       $d[($i-1)][($j-1)] + $cost)   // Substitution
                       );
          
                   if (($i>1) && ($j>1) && ($str1[($i-1)] == $str2[($j-2)]) && ($str1[($i-2)] == $str2[($j-1)])) {
                       $d[$i][$j] = min($d[$i][$j], $d[($i-2)][($j-2)] + $cost);
                   }
               }
           }
           return $d[sizeof($str1)][sizeof($str2)];
       }

Verwandte Verfahren

Die Kosten der einzelnen Operationen können auch unterschiedlich oder abhängig von den jeweiligen Zeichen gewichtet werden.

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.

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   Deutsch Wikipedia

  • Hamming Abstand — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Hamming-Abstand — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Der Hamming Abstand zweier Blöcke mit… …   Deutsch Wikipedia

  • Edit-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… …   Deutsch Wikipedia

  • Editierdistanz — 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… …   Deutsch Wikipedia

  • Levenstein-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… …   Deutsch Wikipedia

  • Lewenstein-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… …   Deutsch Wikipedia

  • Hamming-Distanz — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Hamming-Gewicht — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Hammingabstand — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”