Levenshtein-Distanz

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Levenstein-Distanz)

Die Levenshtein-Distanz (auch Editierdistanz) zwischen zwei Zeichenketten 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 Lewenstein (engl. Levenshtein), 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

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} die beiden Eingabe-Zeichenketten bezeichnen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m = |u|}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n = |v|}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{0, 0} = 0}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{i, 0} = i, 1 \leq i \leq m}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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}} ,
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq i\leq m, 1\leq j \leq n}

Nachdem die Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D} berechnet ist, steht die Levenshtein-Distanz, d. h. die minimale Anzahl der Edit-Operationen, in der Matrix-Zelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{m,n}} . In jeder Zelle steht die Levenshtein-Distanz der Präfixe und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_{0,j}} . Bei einer weiteren Löschung bzw. Einfügung wird nun nur ein weiteres Zeichen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} verbraucht. D.h. das Resultat wird in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{i + 1,j}} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{i,j + 1}} gespeichert. Also lassen sich die Kosten für eine Löschung bzw. Einfügung in Zelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{i,j}} rekurrent durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{i-1,j} + 1} bzw. 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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) + " 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 ""

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 2

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

Komplexität

Die Laufzeit des Algorithmus ist in OFehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (mn)} , da alle Zellen der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (m+1)\times (n+1)} -Matrix berechnet werden und der Rechenaufwand pro Zelle konstant ist.

Der Speicherbedarf ist in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(nm)} , da die Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m+1} Zeilen und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 .

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 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

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(n^3)} und lässt beliebige Kostenfunktionen für Einfüge- bzw. Löschoperationen der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} bewertet und im Backtrace ignoriert. D.h. der Smith-Waterman-Algorithmus berechnet das lokale „sequence alignment“. Seine Laufzeit liegt in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(n^2)} .

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 zwei Operationen notwendig. Damerau-Levenshtein benötigt nur eine einzige.

Folgende Matrix-Rekurrenzen spezifizieren die Algorithmus-Variante.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m = |u|}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{0, 0} = 0}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{i, 0} = i} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq i \leq m}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{0, j} = j} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq j \leq n}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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}}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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}}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 \leq i \leq m, 2\leq j \leq n}

Wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} die Kosten für eine Vertauschung von zwei Zeichen bezeichnet.

Siehe auch

Literatur

  • Fred J. Damerau: A technique for computer detection and correction of spelling errors. In: Communications of the ACM. Band 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. Band 163, Nr. 4, 1965, S. 845–848 (russisch, Englische Übersetzung in: Soviet Physics Doklady, 10(8) S. 707–710, 1966).

Weblinks

Abgerufen von „https://de.wikiup.org/index.php?title=Levenshtein-Distanz&oldid=225473275“