Levenshtein-Distanz - Levenshtein distance

In der Informationstheorie , Linguistik und Informatik ist die Levenshtein-Distanz eine Stringmetrik zur Messung der Differenz zwischen zwei Sequenzen. Informell ist der Levenshtein-Abstand zwischen zwei Wörtern die minimale Anzahl von Einzelzeichen-Änderungen (Einfügungen, Streichungen oder Ersetzungen), die erforderlich sind, um ein Wort in das andere zu ändern. Sie ist nach dem sowjetischen Mathematiker Vladimir Levenshtein benannt , der 1965 diese Distanz betrachtete.

Der Levenshtein-Abstand kann auch als Bearbeitungsabstand bezeichnet werden , obwohl dieser Begriff auch eine größere Familie von Abstandsmetriken bezeichnen kann, die zusammen als Bearbeitungsabstand bekannt sind . Es ist eng mit paarweisen String-Ausrichtungen verwandt .

Definition

Der Levenshtein Abstand zwischen zwei Saiten (der Länge und jeweils) gegeben ist durch wobei ${\displaystyle a,b}$${\displaystyle |a|}$${\displaystyle |b|}$${\displaystyle \operatorname {lev} (a,b)}$

${\displaystyle \operatorname {lev} (a,b)={\begin{cases}|a|&{\text{ if }}|b|=0,\\|b|&{\text{ if }} |a|=0,\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}&{\text{ if }}a[ 0]=b[0]\\1+\min {\begin{cases}\operatorname {lev} {\big (}\operatorname {tail} (a),b{\big )}\\\operatorname {lev } {\big (}a,\operatorname {tail} (b){\big )}\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b) {\big )}\\\end{cases}}&{\text{ sonst}}\end{cases}}}$

wobei das einer Zeichenfolge eine Zeichenfolge aller Zeichen bis auf das erste Zeichen von ist und das te Zeichen der Zeichenfolge ist , wobei von 0 gezählt wird . ${\displaystyle \operatorname {tail} }$${\displaystyle x}$${\displaystyle x}$${\displaystyle x[n]}$${\displaystyle n}$${\displaystyle x}$

Beachten Sie, dass das erste Element im Minimum dem Löschen entspricht (von bis ), das zweite dem Einfügen und das dritte dem Ersetzen. ${\displaystyle a}$${\displaystyle b}$

Diese Definition entspricht direkt der naiven rekursiven Implementierung .

Beispiel

Bearbeiten Sie die Abstandsmatrix für zwei Wörter, indem Sie die Kosten für die Ersetzung als 1 und die Kosten für das Löschen oder Einfügen als 0,5 verwenden

Der Levenshtein-Abstand zwischen "Kätzchen" und "Sitzen" beträgt beispielsweise 3, da die folgenden 3 Bearbeitungen ineinander übergehen und dies mit weniger als 3 Bearbeitungen nicht möglich ist:

1. k itten → s itten (Ersetzung von "s" für "k"),
2. sitt e n → sitt i n (Ersetzung von "i" für "e"),
3. sittin → sittin g (Insertion von "g" am Ende).

Ober- und Untergrenze

Die Levenshtein-Distanz hat mehrere einfache obere und untere Grenzen. Diese beinhalten:

• Es ist zumindest der Unterschied der Größen der beiden Saiten.
• Es ist höchstens die Länge der längeren Saite.
• Es ist null genau dann, wenn die Zeichenfolgen gleich sind.
• Wenn die Strings die gleiche Größe haben, ist die Hamming-Distanz eine obere Schranke für die Levenshtein-Distanz. Die Hamming-Distanz ist die Anzahl der Positionen, an denen sich die entsprechenden Symbole in den beiden Strings unterscheiden.
• Der Levenshtein-Abstand zwischen zwei Saiten ist nicht größer als die Summe ihrer Levenshtein-Abstände zu einer dritten Saite ( Dreiecksungleichung ).

Ein Beispiel, bei dem der Levenshtein-Abstand zwischen zwei Saiten gleicher Länge strikt kleiner als der Hamming-Abstand ist, wird durch das Paar "Fehler" und "Rasen" gegeben. Hier ist der Levenshtein-Abstand gleich 2 (entferne "f" von vorne; füge "n" am Ende ein). Die Hamming-Distanz beträgt 4.

Anwendungen

Beim approximativen String-Matching besteht das Ziel darin, Übereinstimmungen für kurze Strings in vielen längeren Texten zu finden, in Situationen, in denen eine geringe Anzahl von Unterschieden zu erwarten ist. Die kurzen Strings könnten zum Beispiel aus einem Wörterbuch stammen. Dabei ist eine der Saiten typischerweise kurz, während die andere beliebig lang ist. Dies hat ein breites Anwendungsspektrum, zum Beispiel Rechtschreibprüfungen , Korrektursysteme für die optische Zeichenerkennung und Software zur Unterstützung der Übersetzung in natürlicher Sprache auf der Grundlage von Translation Memorys .

Der Levenshtein-Abstand kann auch zwischen zwei längeren Strings berechnet werden, aber die Kosten für seine Berechnung, die ungefähr proportional zum Produkt der beiden Stringlängen sind, machen dies unpraktisch. Daher sind die verglichenen Zeichenfolgen , wenn sie zur Unterstützung der Fuzzy-String-Suche in Anwendungen wie Record Linkage verwendet werden, normalerweise kurz, um die Vergleichsgeschwindigkeit zu verbessern.

In der Linguistik wird die Levenshtein-Distanz als Metrik verwendet, um die linguistische Distanz zu quantifizieren , oder wie unterschiedlich zwei Sprachen voneinander sind. Es hängt mit der gegenseitigen Verständlichkeit zusammen : Je höher die sprachliche Distanz, desto geringer die gegenseitige Verständlichkeit, und je geringer die sprachliche Distanz, desto höher die gegenseitige Verständlichkeit.

Beziehung zu anderen Entfernungsmetriken bearbeiten

Es gibt andere beliebte Maßeinheiten für den Bearbeitungsabstand , die mit einem anderen Satz zulässiger Bearbeitungsvorgänge berechnet werden. Zum Beispiel,

• der Damerau-Levenshtein-Abstand ermöglicht die Transposition zweier benachbarter Zeichen neben Einfügen, Löschen, Ersetzen;
• der längste Abstand der gemeinsamen Teilsequenz (LCS) erlaubt nur Insertion und Deletion, keine Substitution;
• die Hamming-Distanz erlaubt nur eine Substitution, gilt also nur für Strings gleicher Länge.
• die Jaro-Distanz erlaubt nur die Transposition .

Der Bearbeitungsabstand wird normalerweise als parametrisierbare Metrik definiert, die mit einem bestimmten Satz zulässiger Bearbeitungsvorgänge berechnet wird, und jedem Vorgang werden Kosten (möglicherweise unendlich) zugewiesen. Dies wird durch DNA- Sequenz-Alignment- Algorithmen wie dem Smith-Waterman-Algorithmus weiter verallgemeinert , die die Kosten einer Operation davon abhängen, wo sie angewendet wird.

Berechnung der Levenshtein-Distanz

Rekursiv

Dies ist eine einfache, aber ineffiziente, rekursive Haskell- Implementierung einer lDistanceFunktion, die zwei Strings, s und t , zusammen mit ihren Längen nimmt und den Levenshtein-Abstand zwischen ihnen zurückgibt:

lDistance :: ( Eq a ) => [a] -> [a] -> Int
lDistance [] t = length t   -- If s is empty, the distance is the number of characters in t
lDistance s [] = length s   -- If t is empty, the distance is the number of characters in s
lDistance (a:s') (b:t') =
  if
    a == b
  then
    lDistance s' t'         -- If the first characters are the same, they can be ignored
  else
    1 + minimum             -- Otherwise try all three possible actions and select the best one
      [ lDistance (a:s') t' -- Character is inserted (b inserted)
      , lDistance s' (b:t') -- Character is deleted  (a deleted)
      , lDistance s' t'     -- Character is replaced (a replaced with b)
      ]

Diese Implementierung ist sehr ineffizient, da sie den Levenshtein-Abstand derselben Teilzeichenfolgen viele Male neu berechnet.

Eine effizientere Methode würde niemals dieselbe Entfernungsberechnung wiederholen. Zum Beispiel könnte der Levenshtein-Abstand aller möglichen Präfixe in einem Array gespeichert werden , wobei der Abstand zwischen den letzten Zeichen von string und den letzten Zeichen von string ist . Die Tabelle kann einfach zeilenweise aufgebaut werden, beginnend mit Zeile 0. Wenn die gesamte Tabelle erstellt wurde, befindet sich der gewünschte Abstand in der Tabelle in der letzten Zeile und Spalte, der den Abstand zwischen allen Zeichen in und allen Zeichen im . ${\displaystyle M}$${\displaystyle M[i][j]}$${\displaystyle i}$s${\displaystyle j}$tst

Iterativ mit voller Matrix

(Hinweis: In diesem Abschnitt werden 1-basierte Zeichenfolgen anstelle von 0-basierten Zeichenfolgen verwendet.)

Die Berechnung des Levenshtein-Abstands basiert auf der Beobachtung, dass wir die Werte in der Matrix dynamisch programmieren können , wenn wir eine Matrix reservieren , um die Levenshtein-Abstände zwischen allen Präfixen des ersten Strings und allen Präfixen des zweiten Strings zu halten , und Ermitteln Sie also den Abstand zwischen den beiden vollständigen Zeichenfolgen als zuletzt berechneten Wert.

Dieser Algorithmus, ein Beispiel für dynamisches Programmieren von unten nach oben , wird mit Varianten in dem 1974 erschienenen Artikel The String-to-String Correction Problem von Robert A. Wagner und Michael J. Fischer diskutiert .

Dies ist eine einfache Pseudocode- Implementierung für eine Funktion LevenshteinDistance, die zwei Strings, s der Länge m und t der Länge n verwendet und den Levenshtein-Abstand zwischen ihnen zurückgibt:

function LevenshteinDistance(char s[1..m], char t[1..n]):
  // for all i and j, d[i,j] will hold the Levenshtein distance between
  // the first i characters of s and the first j characters of t
  declare int d[0..m, 0..n]
 
  set each element in d to zero
 
  // source prefixes can be transformed into empty string by
  // dropping all characters
  for i from 1 to m:
    d[i, 0] := i
 
  // target prefixes can be reached from empty source prefix
  // by inserting every character
  for j from 1 to n:
    d[0, j] := j
 
  for j from 1 to n:
    for i from 1 to m:
      if s[i] = t[j]:
        substitutionCost := 0
      else:
        substitutionCost := 1

      d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                         d[i, j-1] + 1,                   // insertion
                         d[i-1, j-1] + substitutionCost)  // substitution
 
  return d[m, n]

Zwei Beispiele für die resultierende Matrix (wenn Sie den Mauszeiger über eine markierte Zahl bewegen, wird die Operation angezeigt, die ausgeführt wurde, um diese Zahl zu erhalten):

Die durch den Algorithmus hindurch beibehaltene Invariante besteht darin, dass wir das Anfangssegment in ein Minimum an Operationen umwandeln können . Am Ende enthält das rechte untere Element des Arrays die Antwort. s[1..i]t[1..j]d[i, j]

Iterativ mit zwei Matrixzeilen

Es stellt sich heraus, dass nur zwei Zeilen der Tabelle – die vorherige Zeile und die aktuell berechnete Zeile – für die Konstruktion benötigt werden, wenn man die bearbeiteten Eingabestrings nicht rekonstruieren möchte.

Die Levenshtein-Distanz kann iterativ mit dem folgenden Algorithmus berechnet werden:

function LevenshteinDistance(char s[0..m-1], char t[0..n-1]):
    // create two work vectors of integer distances
    declare int v0[n + 1]
    declare int v1[n + 1]

    // initialize v0 (the previous row of distances)
    // this row is A[0][i]: edit distance for an empty s
    // the distance is just the number of characters to delete from t
    for i from 0 to n:
        v0[i] = i

    for i from 0 to m - 1:
        // calculate v1 (current row distances) from the previous row v0

        // first element of v1 is A[i + 1][0]
        //   edit distance is delete (i + 1) chars from s to match empty t
        v1[0] = i + 1

        // use formula to fill in the rest of the row
        for j from 0 to n - 1:
            // calculating costs for A[i + 1][j + 1]
            deletionCost := v0[j + 1] + 1
            insertionCost := v1[j] + 1
            if s[i] = t[j]:
                substitutionCost := v0[j]
            else:
                substitutionCost := v0[j] + 1

            v1[j + 1] := minimum(deletionCost, insertionCost, substitutionCost)

        // copy v1 (current row) to v0 (previous row) for next iteration
        // since data in v1 is always invalidated, a swap without copy could be more efficient
        swap v0 with v1
    // after the last swap, the results of v1 are now in v0
    return v0[n]

Diese Variante mit zwei Zeilen ist suboptimal: Die erforderliche Speichermenge kann für eine bessere Cache-Lokalität auf eine Zeile und ein (Index-)Wort Overhead reduziert werden.

Der Algorithmus von Hirschberg kombiniert diese Methode mit Divide and Conquer . Es kann die optimale Bearbeitungssequenz und nicht nur den Bearbeitungsabstand in den gleichen asymptotischen Zeit- und Raumgrenzen berechnen.

Adaptive Variante

Die dynamische Variante ist nicht die ideale Umsetzung. Ein adaptiver Ansatz kann die erforderliche Speichermenge reduzieren und im besten Fall die Zeitkomplexität in der Länge des kürzesten Strings auf linear reduzieren und im schlimmsten Fall auf nicht mehr als quadratisch in der Länge des kürzesten Strings . Die Idee ist, dass man effiziente Bibliotheksfunktionen ( std::mismatch) verwenden kann, um nach gemeinsamen Präfixen und Suffixen zu suchen und nur bei Nichtübereinstimmung in den DP-Teil einzutauchen.

Automaten

Levenshtein-Automaten bestimmen effizient, ob eine Zeichenfolge einen geringeren Bearbeitungsabstand als eine gegebene Konstante von einer gegebenen Zeichenfolge hat.

Annäherung

Der Levenshtein-Abstand zwischen zwei Strings der Länge n kann auf einen Faktor . angenähert werden

${\displaystyle (\log n)^{O(1/\varepsilon)},}$

wobei ε > 0 ein frei abzustimmender Parameter in der Zeit O ( n ^{1 + ε} ) ist .

Rechenkomplexität

Es wurde gezeigt, dass der Levenshtein-Abstand zweier Strings der Länge n nicht in der Zeit O ( n ^{2 − ε} ) für jedes ε größer als Null berechnet werden kann, es sei denn, die Hypothese der starken Exponentialzeit ist falsch.

Siehe auch

Verweise

Externe Links

• Schwarz, Paul E., Hrsg. (14. August 2008), "Levenshtein Distance", Dictionary of Algorithms and Data Structures [online] , US National Institute of Standards and Technology , abgerufen am 2. November 2016
• Rosseta-Code-Implementierungen der Levenshtein-Distanz