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.<ref name="Levenshtein1965">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.</ref>

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.<ref name="Navarro2001">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.</ref>

In der Praxis wird die Levenshtein-Distanz unter anderem bei der Rechtschreibprüfung, der unscharfen Suche, der Duplikaterkennung und beim Datenlinkage eingesetzt.<ref name="Navarro2001" />

Definition

Seien <math>u=u_1u_2\dots u_m</math> und <math>v=v_1v_2\dots v_n</math> zwei Zeichenketten. Mit <math>D_{i,j}</math> wird die Levenshtein-Distanz zwischen den Präfixen <math>u_1\dots u_i</math> und <math>v_1\dots v_j</math> bezeichnet.

Für die leere Zeichenkette gelten die Randbedingungen

<math>D_{i,0}=i,\qquad D_{0,j}=j.</math>

Für <math>i>0</math> und <math>j>0</math> gilt die Rekurrenz

<math>

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} </math>

wobei

<math>

\delta(u_i,v_j)= \begin{cases} 0,& u_i=v_j,\\ 1,& u_i\neq v_j. \end{cases} </math>

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.<ref name="WagnerFischer1974">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.</ref>

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 <math>\operatorname{lev}(\text{kitten},\text{sitting})=3</math>.

Eigenschaften und Schranken

Für die klassische Levenshtein-Distanz gelten die Metrikeigenschaften: Nichtnegativität, Identität der Ununterscheidbaren, Symmetrie und Dreiecksungleichung.<ref name="Navarro2001" />

Für zwei Zeichenketten <math>u</math> und <math>v</math> der Längen <math>m</math> und <math>n</math> gilt

<math>|m-n|\leq \operatorname{lev}(u,v)\leq \max(m,n).</math>

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:

<math>\operatorname{lev}(u,v)\leq d_H(u,v).</math>

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

<math>m+n-2L.</math>

Diese Formel gilt nicht unverändert für die klassische Levenshtein-Distanz, weil dort eine Ersetzung nur Kosten 1 verursacht.<ref name="WagnerFischer1974" />

Berechnung

Dynamische Programmierung

Der klassische Algorithmus zur Berechnung der Levenshtein-Distanz verwendet dynamische Programmierung. Die Matrix <math>D</math> enthält für jede Kombination von Präfixlängen die optimale Distanz.<ref name="WagnerFischer1974" />

<syntaxhighlight lang="text"> 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

</syntaxhighlight>

Nach dem Ausfüllen der Matrix steht die Levenshtein-Distanz in <math>D_{m,n}</math>.

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 <math>D_{m,n}</math> 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.<ref>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.</ref>

Komplexität

Die klassische dynamische Programmierung berechnet alle <math>(m+1)(n+1)</math> Matrixzellen. Ihre Laufzeit beträgt daher <math>\Theta(mn)</math>. Wenn die gesamte Matrix gespeichert wird, beträgt auch der Speicherbedarf <math>\Theta(mn)</math>.<ref name="WagnerFischer1974" />

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 <math>O(\min(m,n))</math> reduzieren.<ref name="Ukkonen1985">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.</ref>

Distanzabhängige Verfahren

Wenn die tatsächliche Editierdistanz <math>s</math> klein gegenüber den Zeichenkettenlängen ist, muss nicht notwendigerweise die gesamte Matrix berechnet werden. Ukkonen entwickelte exakte Verfahren, deren Aufwand von <math>s</math> abhängt. Ein Ergebnis seines Artikels von 1985 erreicht Zeit und Speicher <math>O(s\min(m,n))</math>; für den Fall gleicher Operationskosten wird dort zudem eine Variante mit derselben Laufzeit und geringerem Speicher beschrieben.<ref name="Ukkonen1985" />

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.<ref name="Myers1999">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.</ref>

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.<ref>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.</ref>

Bedingte untere Schranke und Approximation

Für zwei Zeichenketten der Länge <math>n</math> ist kein stark subquadratischer exakter Algorithmus bekannt. Backurs und Indyk zeigten 2015, dass ein Algorithmus mit Laufzeit <math>O(n^{2-\delta})</math> für eine Konstante <math>\delta>0</math> die Strong Exponential Time Hypothesis (SETH) widerlegen würde.<ref name="BackursIndyk2015">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.</ref>

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

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 <math>O(mn)</math>.<ref>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.</ref>

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.<ref>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.</ref>

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.<ref>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.</ref>

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.<ref name="Navarro2001" />

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.<ref>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.</ref>

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

<math>D_{i-2,j-2}+1</math>

unter der Bedingung <math>u_i=v_{j-1}</math> und <math>u_{i-1}=v_j</math>. 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.<ref name="VanDerLoo2014">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.</ref>

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.<ref>Roy Lowrance, Robert A. Wagner: An Extension of the String-to-String Correction Problem. In: Journal of the ACM. Band 22, Nr. 2, 1975, S. 177–183, doi:10.1145/321879.321880.</ref>

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.<ref name="VanDerLoo2014" />

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.<ref name="Navarro2001" />

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:

<math>\mathrm{WER}=\frac{S+D+I}{N},</math>

wobei <math>S</math>, <math>D</math> und <math>I</math> die Zahl der Ersetzungen, Löschungen und Einfügungen und <math>N</math> die Zahl der Wörter in der Referenztranskription bezeichnen.<ref>National Institute of Standards and Technology: NIST Special Publication 1112. Beschreibung der Word Error Rate und der aus Editieroperationen abgeleiteten Fehlermessung. NIST.</ref>

Linguistik

In der quantitativen Dialektologie kann die Levenshtein-Distanz auf phonetische Transkriptionen angewendet werden, um Ausspracheunterschiede zwischen Sprachvarietäten zu messen.<ref>Wilbert J. Heeringa: Measuring Dialect Pronunciation Differences using Levenshtein Distance. Dissertation, University of Groningen, 2004. University of Groningen.</ref>

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.<ref name="Berger2021">Bonnie Berger, Michael S. Waterman, Yun William Yu: Levenshtein Distance, Sequence Comparison and Biological Database Search. In: IEEE Transactions on Information Theory. Band 67, Nr. 6, 2021, S. 3287–3294, doi:10.1109/TIT.2020.2996543.</ref>

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.<ref name="UAX29">Unicode Consortium: Unicode Standard Annex #29 – Unicode Text Segmentation. unicode.org.</ref>

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.<ref name="UAX15">Unicode Consortium: Unicode Standard Annex #15 – Unicode Normalization Forms. unicode.org.</ref>

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.<ref name="Levenshtein1965" /> 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.<ref name="WagnerFischer1974" /> Die Entwicklung effizienterer Verfahren setzte sich unter anderem mit linearem Speicher, distanzabhängigen Algorithmen, bit-parallelen Verfahren, Automaten und Approximationen fort.<ref name="Ukkonen1985" /><ref name="Myers1999" />

Neuere Arbeiten untersuchen auch die theoretischen Grenzen der exakten Berechnung und die Rolle der Levenshtein-Distanz in modernen Anwendungen, etwa der biologischen Datenbanksuche.<ref name="BackursIndyk2015" /><ref name="Berger2021" />

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.

Einzelnachweise

<references />

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)