Levenshtein-Distanz

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.

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.

In der Praxis wird die Levenshtein-Distanz unter anderem bei der Rechtschreibprüfung, der unscharfen Suche, der Duplikaterkennung und beim Datenlinkage eingesetzt.

Definition

Seien $u=u_{1}u_{2}\dots u_{m}$ und $v=v_{1}v_{2}\dots v_{n}$ zwei Zeichenketten. Mit $D_{i,j}$ wird die Levenshtein-Distanz zwischen den Präfixen $u_{1}\dots u_{i}$ und $v_{1}\dots v_{j}$ bezeichnet.

Für die leere Zeichenkette gelten die Randbedingungen

$D_{i,0}=i,\qquad D_{0,j}=j.$

Für $i>0$ und $j>0$ gilt die Rekurrenz

$D_{i,j}=\min {\begin{cases}D_{i-1,j}+1,\\D_{i,j-1}+1,\\D_{i-1,j-1}+\delta (u_{i},v_{j}),\end{cases}}$

wobei

$\delta (u_{i},v_{j})={\begin{cases}0,&u_{i}=v_{j},\\1,&u_{i}\neq v_{j}.\end{cases}}$

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.

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:

1. kitten → sitten – Ersetzung von k durch s;
2. sitten → sittin – Ersetzung von e durch i;
3. sittin → sitting – Einfügung von g.

Damit gilt $\operatorname {lev} ({\text{kitten}},{\text{sitting}})=3$.

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 $u$ und $v$ der Längen $m$ und $n$ gilt

$|m-n|\leq \operatorname {lev} (u,v)\leq \max(m,n).$

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:

$\operatorname {lev} (u,v)\leq d_{H}(u,v).$

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 $L$ einer längsten gemeinsamen Teilsequenz zusammen:

$m+n-2L.$

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 $D$ 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 $D_{m,n}$.

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 $D_{m,n}$ 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.

Komplexität

Die klassische dynamische Programmierung berechnet alle $(m+1)(n+1)$ Matrixzellen. Ihre Laufzeit beträgt daher $\Theta (mn)$. Wenn die gesamte Matrix gespeichert wird, beträgt auch der Speicherbedarf $\Theta (mn)$.

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 $O(\min(m,n))$ reduzieren.

Distanzabhängige Verfahren

Wenn die tatsächliche Editierdistanz $s$ klein gegenüber den Zeichenkettenlängen ist, muss nicht notwendigerweise die gesamte Matrix berechnet werden. Ukkonen entwickelte exakte Verfahren, deren Aufwand von $s$ abhängt. Ein Ergebnis seines Artikels von 1985 erreicht Zeit und Speicher $O(s\min(m,n))$; 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.

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.

Bedingte untere Schranke und Approximation

Für zwei Zeichenketten der Länge $n$ ist kein stark subquadratischer exakter Algorithmus bekannt. Backurs und Indyk zeigten 2015, dass ein Algorithmus mit Laufzeit $O(n^{2-\delta })$ für eine Konstante $\delta >0$ die Strong Exponential Time Hypothesis (SETH) widerlegen würde.

Werden Approximationen zugelassen, sind deutlich schnellere Algorithmen möglich. Andoni, Krauthgamer und Onak gaben 2010 einen Algorithmus mit Laufzeit $n^{1+\varepsilon }$ und polylogarithmischem Approximationsfaktor an. Andoni und Nosatzki erreichten 2020 für jedes feste $\varepsilon >0$ eine konstante Approximation in Zeit $n^{1+\varepsilon }$.

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 $O(mn)$.

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.

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.

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.

Eine häufig verwendete einfache Erweiterung der Levenshtein-Rekurrenz ergänzt für benachbarte Vertauschungen den Übergang

$D_{i-2,j-2}+1$

unter der Bedingung $u_{i}=v_{j-1}$ und $u_{i-1}=v_{j}$. 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.

Die vollständige Damerau-Levenshtein-Distanz erlaubt dagegen mehrere, auch überlappende Editieroperationen auf demselben Teilstring. Lowrance und Wagner beschrieben 1975 eine entsprechende Erweiterung des String-to-String-Correction-Problems.

Der Unterschied zeigt sich beispielsweise bei den Zeichenketten CA und ABC: Die vollständige Damerau-Levenshtein-Distanz beträgt 2, weil CA → AC → ABC möglich ist. Die OSA-Distanz beträgt dagegen 3, da der bereits vertauschte Teilstring in diesem Modell nicht erneut editiert werden darf.

Anwendungen

Unscharfe Suche und Rechtschreibprüfung

Bei der unscharfen Suche dient die Levenshtein-Distanz als Ähnlichkeitsmaß, um Zeichenketten trotz Tipp- oder Schreibfehlern zu finden. In großen Datenbeständen wird die vollständige Distanzberechnung typischerweise mit Filtern, Indizes, q-Grammen oder Automaten kombiniert, damit nicht jedes Kandidatenpaar vollständig verglichen werden muss.

Duplikaterkennung und Datenlinkage

Bei der Duplikaterkennung und beim Datenlinkage können Distanzmaße eingesetzt werden, um unterschiedliche Schreibweisen derselben Namen, Adressen oder anderer Textattribute als mögliche Übereinstimmungen zu erkennen. Die Levenshtein-Distanz ist dabei eines von mehreren möglichen Ähnlichkeitsmerkmalen.

Text- und Spracherkennung

Bei der Bewertung optischer Zeichenerkennung kann eine auf Zeichenebene berechnete Editierdistanz zur Bestimmung der Zeichenfehlerrate verwendet werden. Bei der Spracherkennung wird ein verwandtes Maß auf Wortebene als Word Error Rate (WER) verwendet:

$\mathrm {WER} ={\frac {S+D+I}{N}},$

wobei $S$, $D$ und $I$ die Zahl der Ersetzungen, Löschungen und Einfügungen und $N$ die Zahl der Wörter in der Referenztranskription bezeichnen.

Linguistik

In der quantitativen Dialektologie kann die Levenshtein-Distanz auf phonetische Transkriptionen angewendet werden, um Ausspracheunterschiede zwischen Sprachvarietäten zu messen.

Bioinformatik

In der Bioinformatik sind Editierdistanz und Sequenzalignment eng miteinander verbunden. Einfügungen, Löschungen und Ersetzungen bilden ein einfaches Modell für Unterschiede zwischen DNA- oder Proteinsequenzen. Praktische Alignmentverfahren verwenden jedoch häufig reichhaltigere Scoring-Modelle und Gap-Kosten als die klassische Levenshtein-Distanz.

Unicode und Vergleichseinheit

Die mathematische Definition arbeitet mit einer Folge von Symbolen. Eine Softwareimplementierung muss daher festlegen, welche Einheit als Symbol behandelt wird. Bei Unicode-Texten kann die Berechnung beispielsweise auf Bytes, Code Units, Unicode-Codepoints oder Graphemclustern erfolgen; diese Wahl kann zu unterschiedlichen Distanzwerten führen.

Unicode Standard Annex #29 definiert extended grapheme clusters als algorithmische Annäherung an vom Benutzer wahrgenommene Zeichen.

Außerdem können kanonisch äquivalente Unicode-Zeichenketten durch unterschiedliche Codepointfolgen dargestellt werden. Unicode Standard Annex #15 definiert dafür unter anderem die Normalisierungsformen NFC und NFD.

Für reproduzierbare Distanzwerte sollte deshalb bei Unicode-Texten angegeben werden, auf welcher Vergleichseinheit gearbeitet und ob vor dem Vergleich normalisiert wird.

Geschichte

Levenshtein definierte 1965 eine Distanz auf Zeichenfolgen im Zusammenhang mit Codes, die Löschungen, Einfügungen und Ersetzungen korrigieren können. Sein Artikel enthielt noch keinen heute üblichen Matrixalgorithmus zur Berechnung der Distanz.

Wagner und Fischer veröffentlichten 1974 eine allgemeine dynamische Programmierung für das String-to-String-Correction-Problem, die zur klassischen Darstellung der Levenshtein-Berechnung wurde. Die Entwicklung effizienterer Verfahren setzte sich unter anderem mit linearem Speicher, distanzabhängigen Algorithmen, bit-parallelen Verfahren, Automaten und Approximationen fort.

Neuere Arbeiten untersuchen auch die theoretischen Grenzen der exakten Berechnung und die Rolle der Levenshtein-Distanz in modernen Anwendungen, etwa der biologischen Datenbanksuche.

Siehe auch

• Pattern Matching
• Hamming-Abstand
• Needleman-Wunsch-Algorithmus
• Smith-Waterman-Algorithmus
• Dynamic Time Warping

Literatur

• 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.
• 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.
• 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.
• Esko Ukkonen: Algorithms for approximate string matching. In: Information and Control. Band 64, Nr. 1–3, 1985, S. 100–118.
• Gonzalo Navarro: A guided tour to approximate string matching. In: ACM Computing Surveys. Band 33, Nr. 1, 2001, S. 31–88.

Weblinks

• Levenshtein distance im Dictionary of Algorithms and Data Structures des National Institute of Standards and Technology (englisch)
• Algorithm Levenshtein distance (Wikibooks) (englisch)
• Levenshtein.net – Fachressource zur Levenshtein-Distanz, ihren Algorithmen, ihrer Geschichte und ihren Anwendungen (englisch)