Levenshtein Distance: Die Editieroperationen werden von der Matrix übernommen

Die Frage ist
Wie kann man angesichts der vom Levenshtein-Algorithmus erzeugten Matrix " die optimale Lösung " finden? Wie können wir die genaue Folge von String-Operationen finden: Einfügungen, Löschungen und Ersetzungen [eines einzelnen Buchstabens], die notwendig sind, um die 's-Zeichenkette' in die 't-Zeichenkette' umzuwandeln?

Zuerst sollte angemerkt werden, dass in vielen Fällen mehrere optimale Lösungen sind.
Der Levenshtein-Algorithmus liefert die minimale Anzahl von Operationen (8 in der Demokraten (republican Beispiel) es gibt viele Sequenzen (von 8 Operationen), die diese Konvertierung erzeugen können.

Indem man die Levenshtein-Matrix "decodiert", kann man ALLE solchen optimalen Sequenzen aufzählen.
Die allgemeine Idee ist, dass die optimalen Lösungen alle einem "Pfad" folgen, von der oberen linken Ecke zur unteren rechten Ecke (oder in die andere Richtung), wobei die Matrixzellenwerte auf diesem Pfad bleiben sie entweder gleich oder erhöhen sich um eins (oder verringern sich um eins in umgekehrter Richtung), beginnend bei 0 und endend bei der optimalen Anzahl von Operationen für die betreffenden Strings (0 bis 8 Demokraten / Republikaner). Die Anzahl erhöht sich, wenn eine Operation notwendig ist, sie bleibt gleich, wenn der Buchstabe an entsprechenden Positionen in den Strings gleich ist.

Es ist einfach, einen Algorithmus zu erzeugen, der einen solchen Pfad erzeugt (etwas komplizierter, um alle möglichen Pfade zu erzeugen) und aus diesem Pfad die Abfolge von Operationen abzuleiten.

Dieser Pfadfindungsalgorithmus sollte in der unteren rechten Ecke beginnen und sich rückwärts arbeiten. Der Grund für diesen Ansatz ist, dass wir für eine Tatsache wissen, dass, um eine optimale Lösung zu sein, es in dieser Ecke enden muss, und um in dieser Ecke zu enden, muss es von einer der 3 Zellen entweder unmittelbar zu seiner Linken direkt darüber gekommen sein es oder sofort schräg. Durch Auswählen einer Zelle unter diesen drei Zellen, von denen eine unsere Anforderung "gleicher Wert oder abnehmend um eins" erfüllt, wählen wir effektiv eine Zelle auf einem der optimalen Pfade aus. Indem wir die Operation wiederholen, bis wir in die obere linke Ecke kommen (oder tatsächlich, bis wir eine Zelle mit einem Wert von 0 erreichen), kehren wir unseren Weg auf einem optimalen Pfad zurück.

Illustration mit dem demokrat-republikanischen Beispiel

Es sollte auch angemerkt werden, dass man die Matrix auf eine von zwei Arten aufbauen kann: mit "Demokraten" horizontal oder vertikal. Dies ändert weder die Berechnung der Levenshtein-Distanz noch ändert es die Liste der benötigten Operationen; es ändert nur die Art, wie wir die Matrix interpretieren, zum Beispiel horizontal auf dem "Pfad" zu bewegen bedeutet entweder ein Zeichen [aus der t-Zeichenfolge] einzufügen oder ein Zeichen [aus der s-Zeichenfolge] zu löschen, abhängig davon, ob 'string s' "horizontal" ist oder "vertikal" in der Matrix.

Ich werde die folgende Matrix verwenden. Die Konventionen sind daher (nur in der Richtung von links nach rechts und / oder von oben nach unten)

• Eine horizontale Verschiebung ist eine INSERTION eines Buchstabens aus der 't string'
• Eine vertikale Bewegung ist eine DELETION eines Buchstabens aus der 's-Zeichenfolge'
• eine diagonale Bewegung ist entweder:
  • eine Nicht-Operation (beide Buchstaben an den entsprechenden Positionen sind gleich); die Nummer ändert sich nicht
    
  • eine ERSETZUNG (Buchstaben an den jeweiligen Positionen sind verschieden); die Zahl wird um eins erhöht.

Levenshtein-Matrix für s="Demokrat", t="Republikaner"

Die Methode arbitrary , die ich für die Auswahl eines Pfades unter mehreren möglichen optimalen Pfaden verwende, wird im Folgenden kurz beschrieben:

Nach diesem informellen Pseudocode erhalten wir folgendes:

Beginne mit der Zelle "n", "t" unten rechts.
Wählen Sie die [diagonale] "a", "a" Zelle als nächstes Ziel, da es weniger als die anderen beiden ist (und erfüllt die gleiche oder -1 Bedingung).
Beachten Sie, dass die neue Zelle weniger als die aktuelle Zelle ist Daher ist der Schritt 8 Ersatz "t" mit "n": demokra N

Weiter mit "a", "a" Zelle,
    Wählen Sie die [diagonale] "c", "r" Zelle als nächstes Ziel ...
    Beachten Sie, dass die neue Zelle denselben Wert wie aktuelle Zelle == & gt; keine Operation erforderlich .

Weiter mit "c", "r" Zelle,
   Wählen Sie die [diagonale] "i", "c" Zelle als nächstes Ziel ...
   Beachten Sie, dass die neue Zelle weniger als die aktuelle Zelle ist      Daher ist Schritt 7 ein Ersatz "r" mit "c": democ C ein

Weiter mit "i", "c" Zelle,
   Wählen Sie die [diagonale] "l", "o" Zelle als nächstes Ziel ...
   Beachten Sie, dass die neue Zelle weniger als die aktuelle Zelle ist      daher ist Schritt 6 Ersatz "c" mit "i": demo I kann

Weiter mit "l", "o" Zelle,
   Wählen Sie die [diagonale] "b", "m" -Zelle als nächstes Ziel ...
   Beachten Sie, dass die neue Zelle weniger als die aktuelle Zelle ist      daher ist Schritt 5 Ersatz "o" mit "l": dem L ican

Weiter mit "b", "m" Zelle,
   Wählen Sie die [diagonale] "u", "e" Zelle als nächstes Ziel ...
   Beachten Sie, dass die neue Zelle weniger als die aktuelle Zelle ist      Daher ist der Schritt 4 Ersatz "m" mit "b": de B lican

Weiter mit "u", "e" Zelle,
   Beachten Sie, dass die Zelle "diagonal" nicht geeignet ist, da die Zelle "left" kleiner ist als diese Zelle.    Wählen Sie die [links] "p", "e" -Zelle als nächstes Ziel ...
        daher ist der Schritt 3 nach "e": "u" / blican

Weiter mit "p", "e" Zelle,
   wieder qualifiziert sich die "diagonale" Zelle nicht    Wählen Sie die [left] "e", "e" -Zelle als nächstes Ziel ...
        daher ist der Schritt 2 nach "e" "p" eingefügt: de P ublican

Weiter mit "e", "e" Zelle,
   Wählen Sie die [diagonale] "r", "d" Zelle als nächstes Ziel ...
   Beachten Sie, dass die neue Zelle denselben Wert wie aktuelle Zelle == & gt; keine Operation erforderlich .

Weiter mit "r", "d" Zelle,
   Wählen Sie die [diagonale] "Start" -Zelle als nächstes Ziel ...
   Beachten Sie, dass die neue Zelle weniger als die aktuelle Zelle ist      daher ist Schritt 1 Ersatz "d" mit "r": R epublican

Sie sind bei einer Zelle angekommen, deren Wert 0 ist: Ihre Arbeit ist erledigt !

Es ist einige Male her, dass ich damit gespielt habe, aber es scheint mir, dass die Matrix ungefähr so ​​aussehen sollte:

Aber nimm es nicht für selbstverständlich.

Hier ist ein VBA-Algorithmus, der auf der Antwort von mjv basiert. (sehr gut erklärt, aber einige Fälle fehlten).

Ich habe vor kurzem mit der Levenshtein-Distanzalgorithmus-Matrix gearbeitet. Ich musste die Operationen erzeugen, die eine Liste in eine andere verwandeln würden. (Dies wird auch für Strings funktionieren.)

Zeigen die folgenden Tests die gewünschte Funktionalität?