www.wikidata.de-de.nina.az

Levenshtein Distanz Die auch Editierdistanz zwischen zwei Zeichenketten ist die minimale Anzahl einfügender löschender u

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

• Tier

  1. Toer (Ersetze i durch o)
  2. 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 und die beiden Eingabe-Zeichenketten bezeichnen:

Nachdem die Matrix berechnet ist, steht die Levenshtein-Distanz, d. h. die minimale Anzahl der Edit-Operationen, in der Matrix-Zelle . In jeder Zelle steht die Levenshtein-Distanz der Präfixe und . Bei einer weiteren Löschung bzw. Einfügung wird nun nur ein weiteres Zeichen von bzw. verbraucht. D.h. das Resultat wird in bzw. gespeichert. Also lassen sich die Kosten für eine Löschung bzw. Einfügung in Zelle rekurrent durch 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 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 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, da alle Zellen der -Matrix berechnet werden und der Rechenaufwand pro Zelle konstant ist.

Der Speicherbedarf ist in , da die Matrix Zeilen und 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 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 und lässt beliebige Kostenfunktionen für Einfüge- bzw. Löschoperationen der Länge 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 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 bewertet und im Backtrace ignoriert. D.h. der Smith-Waterman-Algorithmus berechnet das lokale „sequence alignment“. Seine Laufzeit liegt in .

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.

Wobei 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. 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 Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Levenshtein Distanz auch Editierdistanz zwischen zwei Zeichenketten ist die minimale Anzahl einfugender loschender 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 einfuhrte Mathematisch ist die Levenshtein Distanz eine Metrik auf dem Raum der Symbolsequenzen Beispielsweise ist die Levenshtein Distanz zwischen Tier zu Tor 2 Eine mogliche Folge von zwei Operationen ist Tier Toer Ersetze i durch o Tor Losche e In der Praxis wird die Levenshtein Distanz zur Bestimmung der Ahnlichkeit von Zeichenketten beispielsweise zur Rechtschreibprufung oder bei der Duplikaterkennung angewandt Inhaltsverzeichnis 1 Algorithmus 2 Beispiel 3 Komplexitat 4 Schranken 5 Abgrenzung 6 Varianten 6 1 Gewichtete Levenshtein Distanz 6 2 Damerau Levenshtein Distanz 7 Siehe auch 8 Literatur 9 WeblinksAlgorithmus BearbeitenIn 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 displaystyle u nbsp und v displaystyle v nbsp die beiden Eingabe Zeichenketten bezeichnen m u displaystyle m u nbsp n v displaystyle n v nbsp D 0 0 0 displaystyle D 0 0 0 nbsp D i 0 i 1 i m displaystyle D i 0 i 1 leq i leq m nbsp D 0 j j 1 j n displaystyle D 0 j j 1 leq j leq n nbsp D i j min D i 1 j 1 0 f a l l s u i v j D i 1 j 1 1 E r s e t z u n g D i j 1 1 E i n f u g u n g D i 1 j 1 L o s c h u n g displaystyle D i j min begin cases D i 1 j 1 amp 0 rm falls u i v j D i 1 j 1 amp 1 rm Ersetzung D i j 1 amp 1 rm Einf ddot u gung D i 1 j amp 1 rm L ddot o schung end cases nbsp 1 i m 1 j n displaystyle 1 leq i leq m 1 leq j leq n nbsp dd Nachdem die Matrix D displaystyle D nbsp berechnet ist steht die Levenshtein Distanz d h die minimale Anzahl der Edit Operationen in der Matrix Zelle D m n displaystyle D m n nbsp In jeder Zelle D i j displaystyle D i j nbsp steht die Levenshtein Distanz der Prafixe u 0 i displaystyle u 0 i nbsp und v 0 j displaystyle v 0 j nbsp Bei einer weiteren Loschung bzw Einfugung wird nun nur ein weiteres Zeichen von u displaystyle u nbsp bzw v displaystyle v nbsp verbraucht D h das Resultat wird in D i 1 j displaystyle D i 1 j nbsp bzw D i j 1 displaystyle D i j 1 nbsp gespeichert Also lassen sich die Kosten fur eine Loschung bzw Einfugung in Zelle D i j displaystyle D i j nbsp rekurrent durch D i 1 j 1 displaystyle D i 1 j 1 nbsp bzw D i j 1 1 displaystyle D i j 1 1 nbsp berechnen Analog ist der Fall der Ersetzung zu erklaren Wenn nicht nur die Levenshtein Distanz berechnet werden soll sondern auch die Folge der Operationen die zu dem Ergebnis gefuhrt hat muss ein Backtrace auf der berechneten Matrix durchgefuhrt werden D h beginnend von D i j 1 displaystyle D i j 1 nbsp werden rekursiv die Optimierungsentscheidungen zuruckverfolgt Im Pseudocode ist der Backtrace Algorithmus string backtrace i j if i gt 0 amp amp D i 1 j 1 D i j return backtrace i 1 j Loschung if j gt 0 amp amp D i j 1 1 D i j return backtrace i j 1 Einfugung if i gt 0 amp amp j gt 0 amp amp D i 1 j 1 1 D i j return backtrace i 1 j 1 Ersetzung if i gt 0 amp amp j gt 0 amp amp 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 moglicher Backtrace berechnet Beispiel BearbeitenDas Verfahren lasst sich nun leicht in einer Tabelle durchfuhren Hier ein Beispiel mit den beiden Zeichenketten Tier und Tor e T o r e 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 e steht hierbei fur die leere Zeichenkette Komplexitat BearbeitenDie Laufzeit des Algorithmus ist in O m n displaystyle mn nbsp da alle Zellen der m 1 n 1 displaystyle m 1 times n 1 nbsp Matrix berechnet werden und der Rechenaufwand pro Zelle konstant ist Der Speicherbedarf ist in O n m displaystyle O nm nbsp da die Matrix m 1 displaystyle m 1 nbsp Zeilen und n 1 displaystyle n 1 nbsp Spalten hat Wenn allerdings kein Backtracing durchgefuhrt wird dann wird zur zeilen bzw spaltenweisen Berechnung der Matrix nur die jeweils letzte Zeile bzw Spalte zur Berechnung der nachsten Zeile bzw Spalte benotigt Der Speicherbedarf liegt in dem Fall also in O min m n displaystyle O min m n nbsp Der Hirschberg Algorithmus ermoglicht die Berechnung der Levenshtein Distanz und eines Backtrace in quadratischer Zeit und mit linearem Speicherverbrauch Schranken BearbeitenFur die Levenshtein Distanz gelten einige obere und untere Schranken sie betragt mindestens den Unterschied der Langen beider Zeichenketten sie betragt hochstens die Lange der langeren Zeichenkette sie ist dann und nur dann 0 wenn beide Zeichenketten identisch sind Definition Metrik sie ist nicht grosser als die Hamming Distanz plus dem Langenunterschied der ZeichenkettenAbgrenzung BearbeitenDie Levenshtein Distanz kann als Erweiterung des Hamming Abstands angesehen werden welcher sich auf Ersetzungen beschrankt und daher nur Zeichenketten gleicher Lange bemessen kann Eine Phonetische Suche kann die Levenshtein Distanz verwenden um Fehler zu erlauben Zu vergleichende Worter konnen vor einer Distanzberechnung beispielsweise mit dem Kolner Phonetik oder dem Soundex Algorithmus in eine Lautsymbol Zeichenkette uberfuhrt 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 displaystyle O n 3 nbsp und lasst beliebige Kostenfunktionen fur Einfuge bzw Loschoperationen der Lange 1 displaystyle geq 1 nbsp zu Bei dem Levenshtein Algorithmus besteht eine Einfuge bzw Loschoperation aus maximal einem Zeichen Varianten des Needleman Wunsch Algorithmus beschranken die Wahl der Kostenfunktion so dass deren Laufzeit in O n 2 displaystyle O n 2 nbsp 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 Einfuge bzw Losch Operationen am Anfang bzw Ende einer Sequenz mit 0 displaystyle 0 nbsp bewertet und im Backtrace ignoriert D h der Smith Waterman Algorithmus berechnet das lokale sequence alignment Seine Laufzeit liegt in O n 2 displaystyle O n 2 nbsp Die Levenshtein Distanz kann als Sonderform der Dynamic Time Warping Distanz DTW betrachtet werden Varianten BearbeitenGewichtete Levenshtein Distanz Bearbeiten Die Kosten der einzelnen Einfuge Losch und Ersetzungsoperationen konnen auch unterschiedlich oder sogar abhangig 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 fur gewichtete Kosten fur Distanzoperationen die mit dem WLD Algorithmus minimiert werden konnen sind die Kosten der Schreibmaschinendistanz Damerau Levenshtein Distanz Bearbeiten Damerau Levenshtein erweitert die Funktionalitat von Levenshtein um die Fahigkeit zwei vertauschte Zeichen zu identifizieren beispielsweise Raisch Rasich Um die eine Zeichenfolge in die andere zu uberfuhren waren mit Levenshtein zwei Operationen notwendig Damerau Levenshtein benotigt nur eine einzige Folgende Matrix Rekurrenzen spezifizieren die Algorithmus Variante m u displaystyle m u nbsp n v displaystyle n v nbsp D 0 0 0 displaystyle D 0 0 0 nbsp D i 0 i displaystyle D i 0 i nbsp 1 i m displaystyle 1 leq i leq m nbsp D 0 j j displaystyle D 0 j j nbsp 1 j n displaystyle 1 leq j leq n nbsp D i j min D i 1 j 1 0 f a l l s u i v j D i 1 j 1 1 E r s e t z u n g D i j 1 1 E i n f u g u n g D i 1 j 1 L o s c h u n g displaystyle D i j min begin cases D i 1 j 1 amp 0 rm falls u i v j D i 1 j 1 amp 1 rm Ersetzung D i j 1 amp 1 rm Einf ddot u gung D i 1 j amp 1 rm L ddot o schung end cases nbsp i 1 1 j n 1 i m j 1 displaystyle i 1 1 leq j leq n vee 1 leq i leq m j 1 nbsp dd D i j min D i 1 j 1 0 f a l l s u i v j D i 1 j 1 1 E r s e t z u n g D i j 1 1 E i n f u g u n g D i 1 j 1 L o s c h u n g D i 2 j 2 c V e r t a u s c h u n g f a l l s u i v j 1 u i 1 v j displaystyle D i j min begin cases D i 1 j 1 amp 0 rm falls u i v j D i 1 j 1 amp 1 rm Ersetzung D i j 1 amp 1 rm Einf ddot u gung D i 1 j amp 1 rm L ddot o schung D i 2 j 2 amp c rm Vertauschung falls u i v j 1 wedge u i 1 v j end cases nbsp 2 i m 2 j n displaystyle 2 leq i leq m 2 leq j leq n nbsp dd Wobei c displaystyle c nbsp die Kosten fur eine Vertauschung von zwei Zeichen bezeichnet Siehe auch BearbeitenPattern MatchingLiteratur BearbeitenFred J Damerau A technique for computer detection and correction of spelling errors In Communications of the ACM Band 7 Nr 3 Marz 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 Ubersetzung in Soviet Physics Doklady 10 8 S 707 710 1966 Weblinks BearbeitenErklarung und Online Visualisierung mit Flash englisch Erklarung und Online Visualisierung mit JavaScript englisch Java Applet zum Berechnen der Levenshtein Distanz und Hamming Abstand englisch Algorithm Levenshtein distance Wikibooks englisch Abgerufen von https de wikipedia org w index php title Levenshtein Distanz amp oldid 231370057