Mikrooptimierung für die Berechnung der Bearbeitungsentfernung: Ist sie gültig?

Auf Wikipedia wird eine Implementierung für das dynamische Bottom-Up-Programmierschema für die Bearbeitungsentfernung angegeben. Es folgt nicht vollständig der Definition; innere Zellen werden folgendermaßen berechnet:

if s[i] = t[j] then  
  d[i, j] := d[i-1, j-1]       // no operation required
else
  d[i, j] := minimum
             (
               d[i-1, j] + 1,  // a deletion
               d[i, j-1] + 1,  // an insertion
               d[i-1, j-1] + 1 // a substitution
             )
}

Wie Sie sehen können, wählt der Algorithmus immer den Wert aus dem oberen linken Nachbarn, wenn eine Übereinstimmung vorliegt, und speichert einige Speicherzugriffe, ALU-Operationen und Vergleiche.

Das Löschen (oder Einfügen) kann jedoch zu einem kleineren Wert führen, sodass der Algorithmus lokal falsch ist, dh mit dem Optimalitätskriterium bricht. Aber vielleicht ändert der Fehler nichts am Endergebnis - er könnte aufgehoben werden.

Ist diese Mikrooptimierung gültig und warum (nicht)?

Ich denke nicht, dass der Algorithmus fehlerhaft ist. Wenn zwei Zeichenfolgen übereinstimmen, vergleichen wir zuerst die letzten beiden Zeichen (und rekursieren dann). Wenn sie gleich sind, können wir sie anpassen, um eine optimale Ausrichtung zu erhalten. Betrachten Sie zum Beispiel die Zeichenfolgen testund testat. Wenn Sie die beiden letzten ts nicht übereinstimmen , tbleibt eines der s unübertroffen, da sonst Ihre Übereinstimmung folgendermaßen aussehen würde:

Dies ist unmöglich, da sich die Pfeile nicht "kreuzen" dürfen. Die Übereinstimmung tführt zu mehreren Einsätzen (grüne Kästchen in der Abbildung), wie links dargestellt:

Aber dann finden Sie einfach eine ebenso gute Ausrichtung, wie rechts dargestellt. In beiden Fällen stimmen Sie mit a überein tund Sie haben zwei Einsätze.

Das Argument für eine Ersetzung eines der letzten ts ist das gleiche. Wenn Sie also eines der letzten ts ersetzen , können Sie stattdessen die letzten beiden t abgleichen und eine bessere Ausrichtung erzielen (siehe Abbildung).