Die Levenshtein-Distanz (auch Editierdistanz) zwischen zwei Zeichenketten ist die minimale Anzahl von Einfüge-, Lösch- und Ersetzungsoperationen, die erforderlich ist, um die erste Zeichenkette in die zweite umzuwandeln. Benannt ist sie nach dem sowjetischen Mathematiker Wladimir Lewenstein (englische Transkription: Levenshtein), der die zugrunde liegende Distanz 1965 im Zusammenhang mit fehlerkorrigierenden Codes einführte.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. Englische Übersetzung in: Soviet Physics Doklady. Band 10, Nr. 8, 1966, S. 707–710. Math-Net.
Mathematisch ist die klassische Levenshtein-Distanz eine Metrik auf dem Raum der Symbolsequenzen. Sie ist ein Spezialfall der allgemeineren Editierdistanz, bei der die zugelassenen Editieroperationen oder deren Kosten auch anders gewählt werden können.Gonzalo Navarro: A guided tour to approximate string matching. In: ACM Computing Surveys. Band 33, Nr. 1, 2001, S. 31–88, doi:10.1145/375360.375365.
In der Praxis wird die Levenshtein-Distanz unter anderem bei der Rechtschreibprüfung, der unscharfen Suche, der Duplikaterkennung und beim Datenlinkage eingesetzt.
Definition
Seien und zwei Zeichenketten. Mit wird die Levenshtein-Distanz zwischen den Präfixen und bezeichnet.
Für die leere Zeichenkette gelten die Randbedingungen
Für und gilt die Rekurrenz
wobei
Die drei Fälle entsprechen einer Löschung aus der Quellzeichenkette, einer Einfügung eines Zeichens der Zielzeichenkette sowie einer Ersetzung beziehungsweise einer unveränderten Übernahme bei gleichen Zeichen.Robert A. Wagner, Michael J. Fischer: The String-to-String Correction Problem. In: Journal of the ACM. Band 21, Nr. 1, 1974, S. 168–173, doi:10.1145/321796.321811.
In der klassischen Levenshtein-Distanz haben Einfügung, Löschung und Ersetzung jeweils Kosten 1.
Beispiele
Zwischen „Bar“ und „Bier“ beträgt die Levenshtein-Distanz 2. Eine mögliche optimale Folge von Editieroperationen ist:
Wort Operation Anzahl Bar keine 0 Bir Ersetzung a → i 1 Bier Einfügung e 2
Zwischen „uninformiert“ und „uniformiert“ beträgt die Distanz 1, weil lediglich das zweite n gelöscht werden muss.
Ein weiteres häufig verwendetes Beispiel ist die Transformation von kitten in sitting:
kitten → sitten – Ersetzung von k durch s; sitten → sittin – Ersetzung von e durch i; sittin → sitting – Einfügung von g.
Damit gilt .
Eigenschaften und Schranken
Für die klassische Levenshtein-Distanz gelten die Metrikeigenschaften: Nichtnegativität, Identität der Ununterscheidbaren, Symmetrie und Dreiecksungleichung.
Für zwei Zeichenketten und der Längen und gilt
Die untere Schranke folgt daraus, dass eine einzelne Einfügung oder Löschung die Länge nur um eins verändert. Die obere Schranke kann erreicht werden, indem zunächst alle Zeichen im gemeinsamen Längenbereich ersetzt und anschließend überzählige Zeichen eingefügt oder gelöscht werden.
Sind beide Zeichenketten gleich lang, dann ist die Hamming-Distanz eine obere Schranke:
Die Hamming-Distanz ist nur für Zeichenketten gleicher Länge unmittelbar definiert und zählt ausschließlich Ersetzungen.
Wenn Ersetzungen nicht erlaubt sind und nur Einfügungen und Löschungen verwendet werden, hängt die minimale Zahl der Operationen mit der Länge einer längsten gemeinsamen Teilsequenz zusammen:
Diese Formel gilt nicht unverändert für die klassische Levenshtein-Distanz, weil dort eine Ersetzung nur Kosten 1 verursacht.
Berechnung
Dynamische Programmierung
Der klassische Algorithmus zur Berechnung der Levenshtein-Distanz verwendet dynamische Programmierung. Die Matrix enthält für jede Kombination von Präfixlängen die optimale Distanz.
funktion Levenshtein(u[1..m], v[1..n]): deklariere D[0..m, 0..n]
für i von 0 bis m: D[i,0] = i
für j von 0 bis n: D[0,j] = j
für i von 1 bis m: für j von 1 bis n: wenn u[i] = v[j]: ersetzungskosten = 0 sonst: ersetzungskosten = 1
D[i,j] = minimum( D[i-1,j] + 1, // Löschung von u[i] D[i,j-1] + 1, // Einfügung von v[j] D[i-1,j-1] + ersetzungskosten // Gleichheit oder Ersetzung )
gib D[m,n] zurück
Nach dem Ausfüllen der Matrix steht die Levenshtein-Distanz in .
Beispielmatrix
Für die Zeichenketten „Tier“ und „Tor“ ergibt sich:
ε 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
Die Distanz ist somit 2.
Backtrace
Soll zusätzlich zur Distanz eine optimale Folge von Editieroperationen bestimmt werden, kann von der Zelle aus ein Backtrace durchgeführt werden. Dabei werden rückwärts diejenigen Vorgängerzellen verfolgt, deren Übergang den Wert der aktuellen Zelle erklärt.
Es können mehrere optimale Vorgänger existieren. Daher kann die Distanz eindeutig sein, obwohl mehrere verschiedene optimale Editierfolgen existieren.
Der Hirschberg-Algorithmus ermöglicht es, eine optimale Editierfolge beziehungsweise ein entsprechendes Alignment mit linearem Speicherbedarf zu rekonstruieren.Daniel S. Hirschberg: A linear space algorithm for computing maximal common subsequences. In: Communications of the ACM. Band 18, Nr. 6, 1975, S. 341–343, doi:10.1145/360825.360861.
Komplexität
Die klassische dynamische Programmierung berechnet alle Matrixzellen. Ihre Laufzeit beträgt daher . Wenn die gesamte Matrix gespeichert wird, beträgt auch der Speicherbedarf .
Wird nur der Distanzwert benötigt, genügt es, jeweils die vorherige und die aktuelle Zeile beziehungsweise Spalte zu speichern. Der Speicherbedarf lässt sich so auf reduzieren.Esko Ukkonen: Algorithms for approximate string matching. In: Information and Control. Band 64, Nr. 1–3, 1985, S. 100–118, doi:10.1016/S0019-9958(85)80046-2.
Distanzabhängige Verfahren
Wenn die tatsächliche Editierdistanz klein gegenüber den Zeichenkettenlängen ist, muss nicht notwendigerweise die gesamte Matrix berechnet werden. Ukkonen entwickelte exakte Verfahren, deren Aufwand von abhängt. Ein Ergebnis seines Artikels von 1985 erreicht Zeit und Speicher ; für den Fall gleicher Operationskosten wird dort zudem eine Variante mit derselben Laufzeit und geringerem Speicher beschrieben.
Bit-parallele Verfahren
Für approximatives Pattern Matching entwickelte Gene Myers 1999 einen Bit-Vektor-Algorithmus, bei dem mehrere Zustände der dynamischen Programmierung gleichzeitig in den Bits eines Maschinenwortes verarbeitet werden.Gene Myers: A fast bit-vector algorithm for approximate string matching based on dynamic programming. In: Journal of the ACM. Band 46, Nr. 3, 1999, S. 395–415, doi:10.1145/316542.316550.
Davon zu unterscheiden sind der O(ND)-Differenzalgorithmus von Myers aus dem Jahr 1986 und der O(NP)-Algorithmus von Wu, Manber, Myers und Miller. Diese Verfahren behandeln einen kürzesten Editierskript aus Einfügungen und Löschungen; eine Ersetzung entspricht dort einer Löschung mit anschließender Einfügung und hat damit Kosten 2. Sie berechnen daher nicht unmittelbar die klassische Levenshtein-Distanz mit Ersetzungskosten 1.Sun Wu, Udi Manber, Gene Myers, Webb Miller: An O(NP) sequence comparison algorithm. In: Information Processing Letters. Band 35, Nr. 6, 1990, S. 317–323, doi:10.1016/0020-0190(90)90035-V.
Bedingte untere Schranke und Approximation
Für zwei Zeichenketten der Länge ist kein stark subquadratischer exakter Algorithmus bekannt. Backurs und Indyk zeigten 2015, dass ein Algorithmus mit Laufzeit für eine Konstante die Strong Exponential Time Hypothesis (SETH) widerlegen würde.Arturs Backurs, Piotr Indyk: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing. 2015, S. 51–58, doi:10.1145/2746539.2746612.
Werden Approximationen zugelassen, sind deutlich schnellere Algorithmen möglich. Andoni, Krauthgamer und Onak gaben 2010 einen Algorithmus mit Laufzeit und polylogarithmischem Approximationsfaktor an.Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak: Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. In: 51st IEEE Symposium on Foundations of Computer Science. 2010, S. 377–386, doi:10.1109/FOCS.2010.43. Andoni und Nosatzki erreichten 2020 für jedes feste eine konstante Approximation in Zeit .Alexandr Andoni, Negev Shekel Nosatzki: Edit Distance in Near-Linear Time: it's a Constant Factor. In: IEEE Symposium on Foundations of Computer Science. 2020, S. 990–1001, doi:10.1109/FOCS46700.2020.00096.
Abgrenzung zu verwandten Verfahren
Hamming-Distanz
Der Hamming-Abstand erlaubt ausschließlich Ersetzungen und setzt gleich lange Zeichenketten voraus. Die Levenshtein-Distanz erweitert dieses Modell um Einfügungen und Löschungen.
Sequenzalignment
Der DP-Algorithmus für die Levenshtein-Distanz ist eng mit Algorithmen für Sequenzalignment verwandt. Der Needleman-Wunsch-Algorithmus berechnet ein optimales globales Alignment unter einem frei wählbaren Scoring-Modell. In der heute üblichen Form mit linearen Gap-Kosten beträgt seine Laufzeit .Saul B. Needleman, Christian D. Wunsch: A general method applicable to the search for similarities in the amino acid sequence of two proteins. In: Journal of Molecular Biology. Band 48, Nr. 3, 1970, S. 443–453, doi:10.1016/0022-2836(70)90057-4.
Der Smith-Waterman-Algorithmus berechnet dagegen ein lokales Alignment. Seine Rekurrenz enthält zusätzlich den Wert 0; der Backtrace beginnt beim größten Matrixwert und endet beim ersten erreichten 0-Eintrag. Dadurch werden nur die am besten übereinstimmenden Teilsequenzen ausgerichtet.Temple F. Smith, Michael S. Waterman: Identification of Common Molecular Subsequences. In: Journal of Molecular Biology. Band 147, 1981, S. 195–197, doi:10.1016/0022-2836(81)90087-5.
Dynamic Time Warping
Dynamic Time Warping (DTW) verwendet ebenfalls dynamische Programmierung, optimiert jedoch einen Warping-Pfad zwischen Wertefolgen und erlaubt insbesondere, Werte entlang einer Zeitachse mehrfach zuzuordnen. Levenshtein-Distanz und DTW sind daher unterschiedliche Distanz- beziehungsweise Alignmentmodelle und sollten nicht ohne ein ausdrücklich definiertes Kostenmodell gleichgesetzt werden.Hiroaki Sakoe, Seibi Chiba: Dynamic programming algorithm optimization for spoken word recognition. In: IEEE Transactions on Acoustics, Speech, and Signal Processing. Band 26, Nr. 1, 1978, S. 43–49, doi:10.1109/TASSP.1978.1163055.
Varianten
Gewichtete Levenshtein-Distanz
Bei einer gewichteten Levenshtein-Distanz können Einfüge-, Lösch- und Ersetzungsoperationen unterschiedliche Kosten haben; die Kosten können zusätzlich von den beteiligten Zeichen abhängen. Ein Anwendungsbeispiel sind tastaturabhängige Fehlerkosten wie bei der Schreibmaschinendistanz.
Beliebige Gewichtungen erhalten jedoch nicht automatisch alle Metrikeigenschaften. Insbesondere können asymmetrische Kosten die Symmetrie verletzen. Ob die gewichtete Editierdistanz eine Metrik ist, hängt daher von den Bedingungen an die Kostenfunktionen ab.
Damerau-Levenshtein und Optimal String Alignment
Fred J. Damerau untersuchte bereits 1964 zusätzlich zu Einfügungen, Löschungen und Ersetzungen die Vertauschung zweier benachbarter Zeichen als elementare Fehleroperation.Fred J. Damerau: A technique for computer detection and correction of spelling errors. In: Communications of the ACM. Band 7, Nr. 3, 1964, S. 171–176, doi:10.1145/363958.363994.
Eine häufig verwendete einfache Erweiterung der Levenshtein-Rekurrenz ergänzt für benachbarte Vertauschungen den Übergang
unter der Bedingung und . Diese Rekurrenz berechnet jedoch die sogenannte Optimal-String-Alignment-Distanz (OSA), auch restricted Damerau-Levenshtein distance genannt. Bei OSA darf ein Teilstring höchstens einmal editiert werden.Mark P. J. van der Loo: The stringdist Package for Approximate String Matching. In: The R Journal. Band 6, Nr. 1, 2014, S. 111–122, doi:10.32614/RJ-2014-011.