Levenshtein -Entfernung

Im Informationstheorie, Linguistik, und Informatik, das Levenshtein -Entfernung ist ein String Metrik zur Messung des Unterschieds zwischen zwei Sequenzen. Informell ist der Levenshtein-Abstand zwischen zwei Wörtern die minimale Anzahl von Einzelcharakter-Änderungen (Insertionen, Löschungen oder Substitutionen), die erforderlich sind, um ein Wort in das andere zu ändern. Es ist nach dem sowjetischen Mathematiker benannt Vladimir Levenshtein, der diese Entfernung 1965 betrachtete.^[1]

Levenshtein -Entfernung kann auch als bezeichnet werden Entfernung bearbeiten, obwohl dieser Begriff auch eine größere Familie von Entfernungsmetriken bezeichnen kann Entfernung bearbeiten.^{[2]: 32} Es ist eng mit dem verwandt mit paarweise Saitenausrichtungen.

Definition

Der Levenshtein -Abstand zwischen zwei Saiten ${\ displayStyle a, b}$ (von Länge ${\ displayStyle | a |}$ und ${\ displayStyle | B |}$ ist jeweils gegeben durch ${\ displayStyle \ operatorname {lev} (a, b)}$ wo

$oder | 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 {lev {lev } oder {\ big)} \\\ end {cases}} & {\ text {ansonsten,}} \ end {cases}}}$

bei dem die ${\ displayStyle \ Operatorname {Tail}}$ von einer Saite ${\ displayStyle x}$ ist eine Saite von allen außer dem ersten Charakter von ${\ displayStyle x}$, und ${\ displayStyle x [n]}$ ist der ${\ displayStyle n}$TH Zeichen der Saite ${\ displayStyle x}$, Zählen von 0.

Beachten Sie, dass das erste Element im Minimum der Löschung entspricht (von ${\ displayStyle a}$ zu ${\ displayStyle B}$), die zweite zum Einfügen und der dritte zum Ersatz.

Diese Definition entspricht direkt zu die naive rekursive Implementierung.

Beispiel

Bearbeiten Sie die Distanzmatrix für zwei Wörter mit den Substitutionskosten als 1 und Kosten für Löschung oder Insertion als 0,5

Zum Beispiel beträgt der Levenshtein -Abstand zwischen "Kätzchen" und "Sitzen" 3, da die folgenden 3 Änderungen einen in die andere ändern, und es gibt keine Möglichkeit, dies mit weniger als 3 Änderungen zu tun:

1. kitten → sitten (Substitution von "s" durch "k"),
2. sitzeN → SITTin (Substitution von "I" für "e"),
3. sittin → sitting (Einführung von "g" am Ende).

Ober- und Untergrenze

Der Levenshtein -Abstand 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, wenn und nur wenn die Zeichenfolgen gleich sind.
• Wenn die Saiten die gleiche Größe haben, die Hamming -Entfernung ist eine Obergrenze am Levenshtein -Abstand. Der Hamming -Abstand ist die Anzahl der Positionen, an denen die entsprechenden Symbole in den beiden Zeichenfolgen unterschiedlich sind.
• Der Levenshtein -Abstand zwischen zwei Saiten ist nicht größer als die Summe ihrer Levenshtein -Entfernungen von einer dritten Schnur (Dreiecksungleichung).

Ein Beispiel, bei dem der Levenshtein -Abstand zwischen zwei Strings derselben Länge streng geringer ist als der Hamming -Abstand durch das Paar "Fehler" und "Rasen". Hier entspricht der Levenshtein -Abstand 2 (löschen Sie "f" von vorne; ein "n" am Ende einfügen). Das Hamming -Entfernung ist 4.

Anwendungen

Im ungefähre Zeichenfolge MatchingZiel ist es, Übereinstimmungen für kurze Zeichenfolgen in vielen längeren Texten zu finden, in Situationen, in denen eine kleine Anzahl von Unterschieden zu erwarten ist. Die kurzen Saiten könnten zum Beispiel aus einem Wörterbuch kommen. Hier ist einer der Saiten normalerweise kurz, während der andere willkürlich lang ist. Dies hat beispielsweise eine breite Palette von Anwendungen. Zaubersprüche, Korrektursysteme für optische Zeichenerkennung, und Software zur Unterstützung der natürlichen Übersetzung basierend auf Übersetzungsgedächtnis.

Der Levenshtein -Abstand kann auch zwischen zwei längeren Zeichenfolgen berechnet werden, aber die Kosten für die Berechnung, die ungefähr proportional zum Produkt der beiden Saitenlängen sind, macht dies unpraktisch. Somit, wenn es verwendet wird, um zu helfen Fuzzy -String -Suche in Anwendungen wie z. AufzeichnungsverknüpfungDie verglichenen Saiten sind normalerweise kurz, um die Geschwindigkeit der Vergleiche zu verbessern.

In der Linguistik wird der Levenshtein -Abstand als Metrik verwendet, um die zu quantifizieren Sprachdistanz, oder wie unterschiedlich zwei Sprachen voneinander sind.^[3] Es hängt mit gegenseitige Verständlichkeit: Je höher der sprachliche Abstand, desto niedriger die gegenseitige Verständlichkeit und desto niedriger der sprachliche Abstand, desto höher ist die gegenseitige Verständlichkeit.

Beziehung zu anderen Bearbeitungsdistanzmetriken

Es gibt andere beliebte Maßnahmen von Entfernung bearbeiten, die unter Verwendung eines anderen Satzes zulässiger Bearbeitungsvorgänge berechnet werden. Zum Beispiel,

• das Damerau -Levenshtein -Entfernung erlaubt das Transposition von zwei benachbarten Zeichen neben Insertion, Löschung, Substitution;
• das längste gemeinsame Subsequenz (LCS) Entfernung ermöglicht nur Einfügen und Löschen, nicht die Substitution;
• das Hamming -Entfernung Ermöglicht nur Substitution, daher gilt sie nur für Zeichenfolgen derselben Länge.
• das Jaro -Entfernung nur erlaubt Transposition.

Entfernung bearbeiten wird normalerweise als parameterizierbare Metrik definiert, die mit einem bestimmten Satz zulässiger Bearbeitungsvorgänge berechnet wurde, und jedem Vorgang wird Kosten (möglicherweise unendlich) zugewiesen. Dies wird durch DNA weiter verallgemeinert Sequenzausrichtung Algorithmen wie die Smith -Waterman -Algorithmus, die die Kosten eines Vorgangs davon abhängen, wo er angewendet wird.

Berechnung

Rekursiv

Dies ist eine einfache, aber ineffiziente, rekursiv Haskell Implementierung von a Ldistanz Funktion, die zwei Saiten erfordert, s und t, zusammen mit ihren Längen, und gibt den Levenshtein -Abstand zwischen ihnen zurück:

Ldistanz :: Gl a => [a] -> [a] -> Int Ldistanz [] t = Länge t - Wenn s leer ist, ist die Entfernung die Anzahl der Zeichen in t Ldistanz s [] = Länge s - Wenn t leer ist, ist die Entfernung die Anzahl der Zeichen in s Ldistanz (a : s') (b : t') =  wenn a == b  dann Ldistanz s' t' - Wenn die ersten Charaktere gleich sind, können sie ignoriert werden  anders  1  + Minimum - Versuchen Sie ansonsten alle drei möglichen Aktionen und wählen Sie die besten aus  [ Ldistanz (a : s') t', - Zeichen wird eingefügt (b eingefügt)  Ldistanz s' (b : t'), - Charakter wird gelöscht (ein gelöschter)  Ldistanz s' t' - Charakter wird ersetzt (a ersetzt durch b)  ] 

Diese Implementierung ist sehr ineffizient, da sie die Levenshtein -Entfernung derselben Substrings mehrmals neu berechnet.

Eine effizientere Methode würde niemals die gleiche Entfernungsberechnung wiederholen. Zum Beispiel kann der Levenshtein -Abstand aller möglichen Suffixe in einem Array gespeichert werden ${\ displayStyle m}$, wo ${\ displayStyle m [i] [j]}$ ist der Abstand zwischen dem letzten ${\ displayStyle i}$ Zeichen der Zeichenfolge s und der letzte ${\ displayStyle j}$ Zeichen der Zeichenfolge t. Die Tabelle ist leicht zu konstruieren, um eine Zeile zu konstruieren, beginnend mit Zeile 0. Wenn die gesamte Tabelle erstellt wurde s und alle Charaktere in t.

Iterativ mit Vollmatrix

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

Die Berechnung der Levenshtein -Entfernung basiert auf der Beobachtung, dass, wenn wir a reservieren Matrix die Levenshtein -Entfernungen zwischen allen halten Präfixe der ersten Zeichenfolge und alle Präfixe des zweiten, dann können wir die Werte in der Matrix in a berechnen Dynamische Programmierung Mode, und finden Sie so den Abstand zwischen den beiden vollen Zeichenfolgen als der letzte Wert berechnet.

Dieser Algorithmus, ein Beispiel für Bottom-up Dynamische Programmierung, wird im Artikel von 1974 mit Varianten von 1974 erörtert Das String-to-String-Korrekturproblem Von Robert A. Wagner und Michael J. Fischer.^[4]

Dies ist eine einfache Pseudocode Implementierung für eine Funktion Levenshteindistanz Das braucht zwei Saiten, s von Länge m, und t von Länge nund gibt den Levenshtein -Abstand zwischen ihnen zurück:

Funktion Levenshteindistanz(verkohlen s[1..m], verkohlen t[1..n])):  // für alles i und j, d [i, j] werden den Levenshtein -Abstand zwischen sich halten  // Die ersten I -Charaktere von S und die ersten j Charaktere von t  erklären int d[0..m, 0..n]    einstellen jeder Element in d zu Null    // Quellenpräfixe können von in leere Zeichenfolge umgewandelt werden  // alle Zeichen fallen lassen  zum i aus 1 zu m:  d[i, 0] : = i    // Zielpräfixe können aus dem leeren Quellenpräfix erreicht werden  // durch Einfügen jedes Charakters  zum j aus 1 zu n:  d[0, j] : = j    zum j aus 1 zu n:  zum i aus 1 zu m:  wenn s[i] = t[j]:  SubstitutionScost : = 0  anders:  SubstitutionScost : = 1  d[i, j] : = Minimum(d[i-1, j] + 1,  // Löschen  d[i, j-1] + 1,  // Einfügung  d[i-1, j-1] + SubstitutionScost)  // Substitution    Rückkehr d[m, n] 

Zwei Beispiele für die resultierende Matrix (schweben Sie über eine markierte Nummer, zeigt die durchgeführte Operation, um diese Zahl zu erhalten):

Das unveränderlich Im gesamten Algorithmus gehalten, können wir das ursprüngliche Segment transformieren s[1..i] hinein t[1..j] mit einem Minimum von d[i, j] Operationen. Am Ende enthält das untere rechte Element des Arrays die Antwort.

Iterativ mit zwei Matrixreihen

Es stellt sich heraus, dass nur zwei Zeilen der Tabelle - die vorherige Zeile und die aktuelle Zeile berechnet werden - für die Konstruktion benötigt werden, wenn man die bearbeiteten Eingangszeichenfolgen nicht rekonstruieren möchte.

Der Levenshtein -Abstand kann iterativ unter Verwendung des folgenden Algorithmus berechnet werden:^[5]

Funktion Levenshteindistanz(verkohlen s[0..m-1], verkohlen t[0..n-1])):  // Erstellen Sie zwei Arbeitsvektoren von ganzzahligen Entfernungen  erklären int v0[n + 1]  erklären int v1[n + 1]  // V0 initialisieren (die vorherige Zeile von Entfernungen)  // Diese Zeile ist ein [0] [i]: Entfernung von einem leeren S bis t;  // Diese Entfernung ist die Anzahl der Zeichen, die an s angehängt werden soll, um t zu machen.  zum i aus 0 zu n:  v0[i] = i  zum i aus 0 zu m - 1:  // Berechnen Sie V1 (Stromzeilenabstände) aus der vorherigen Zeile v0  // Erstes Element von V1 ist ein [i + 1] [0]  // Distanz bearbeiten wird löschen (i + 1) chars von s zu leerem T passt  v1[0] = i + 1  // Verwenden Sie die Formel, um den Rest der Zeile auszufüllen  zum j aus 0 zu n - 1:  // Kosten für a [i + 1] [j + 1] berechnen  Löschen : = v0[j + 1] + 1  InsertionCost : = v1[j] + 1  wenn s[i] = t[j]:  SubstitutionScost : = v0[j]  anders:  SubstitutionScost : = v0[j] + 1  v1[j + 1] : = Minimum(Löschen, InsertionCost, SubstitutionScost)  // v1 (aktuelle Zeile) für die nächste Iteration in V0 (vorherige Zeile) kopieren  // Da Daten in V1 immer ungültig sind, könnte ein Swap ohne Kopie effizienter sein  Tauschen v0 mit v1  // Nach dem letzten Swap sind die Ergebnisse von V1 jetzt in V0  Rückkehr v0[n] 

Hirschbergs Algorithmus kombiniert diese Methode mit teilen und erobern. Es kann die optimale Bearbeitungssequenz und nicht nur die Bearbeitungsentfernung in derselben asymptotischen Zeit- und Raumgrenzen berechnen.^[6]

Automaten

Levenshtein Automaten Bestimmen Sie effizient, ob eine Zeichenfolge einen Bearbeitungsabstand unter einer bestimmten Konstante aus einer bestimmten Zeichenfolge aufweist.^[7]

Annäherung

Der Levenshtein -Abstand zwischen zwei Längenzeichenfolgen n kann sein angenähert zu einem Faktor

${\ displayStyle (\ log n)^{o (1/\ varepsilon)},},},}$

wo ε > 0 ist ein freier Parameter, der rechtzeitig abgestimmt wird O(n^{1 + ε}).^[8]

Rechenkomplexität

Es wurde gezeigt, dass der Levenshtein -Abstand von zwei Längenstaaten n kann nicht rechtzeitig berechnet werden O(n^{2 - ε}) für jede ε größer als Null, es sei denn die starke Exponentialzeithypothese ist falsch.^[9]

Siehe auch

Verweise

Externe Links

• Black, Paul E., ed.(14. August 2008), "Levenshtein Distanz", Wörterbuch von Algorithmen und Datenstrukturen [Online], US National Institute of Standards and Technology, abgerufen 2. November 2016
• Rosseta -Code -Implementierungen von Levenshtein Distanz