Bearbeiten Sie die Entfernung mit Verschiebevorgängen

Motivation: Ein Mitautor bearbeitet ein Manuskript und ich würde gerne eine übersichtliche Zusammenfassung der Änderungen sehen. Alle "diff" -ähnlichen Werkzeuge sind in der Regel unbrauchbar, wenn Sie sowohl Text verschieben (z. B. die Struktur neu organisieren) als auch lokale Änderungen vornehmen. Ist es wirklich so schwer, es richtig zu machen?

Definitionen: Ich möchte die minimale Bearbeitungsentfernung finden, bei der die zulässigen Operationen sind:

• "billige" Operationen: Hinzufügen / Ändern / Löschen eines einzelnen Zeichens (die üblichen Levenshtein-Operationen),

• "Teuer": Operationen: Verschieben eines Teilstrings an eine neue Position ( für beliebige Zeichenfolgen a , b , c , d ).$abcd \mapsto acbd$$a$$b$$c$$d$

Mit zwei Zeichenketten und y und den ganzen Zahlen k und K möchte ich das folgende Problem lösen:$x$$y$$k$$K$

• Können Sie in y umwandeln, indem Sie höchstens k billige Operationen und höchstens K teure Operationen verwenden?$x$$y$$k$$K$

Fragen:

1. Hat dieses Problem einen Namen? (Es klingt wie eine sehr Standardfrage im Kontext der Sequenzausrichtung.)

2. Ist es schwer?

3. Wenn es schwierig ist, ist es mit als Parameter als fester Parameter verfolgbar ?$K$

4. Gibt es effiziente Approximationsalgorithmen? (Finden Sie beispielsweise eine Lösung mit höchstens billigen und 2 k teuren Operationen, wenn eine Lösung mit k billigen und k teuren Operationen vorhanden ist.)$2k$$2K$$k$$K$

Ich habe versucht, einen Blick auf die in Wikipedia aufgelisteten String-Metriken zu werfen , aber keine davon sah richtig aus.

Wie von Serge Gaspers kommentiert, für lautet das Problem 0 Sorting by Transpositionsund wurde 1995 von Bafna und Pevzner eingeführt. Seine NP-Härte wurde erst 2010 nachgewiesen; sieheLaurent Bulteau, Guillaume Fertin und Irena Rusu, "Sortieren nach Transpositionen ist schwierig".$k=0$

Das Problem wird einfacher, wenn wir lange Löschvorgänge und das Kopieren von Teilzeichenfolgen anstelle von Transpositionen berücksichtigen. Es sei angenommen , dass wir den Standard dynamischen Programmieralgorithmus für die Bearbeitungsabstandsberechnung verwenden, und dass eine teuere Operation der Länge erhöht den Abstand von einem k + b , für einige Konstanten a , $k$$ak+b$. Diese Konstanten können bei langen Löschvorgängen und beim Kopieren von Teilzeichenfolgen unterschiedlich sein.$a,b \ge 0$

Eine lange Löschung ist die Löschung eines beliebigen Teilstrings aus . Sie zu unterstützen ist einfach, wenn wir sie in zwei Arten von einfachen Operationen aufteilen: Löschen des ersten Zeichens (Kosten a + b ) und Erweitern des Löschens um ein Zeichen (Kosten a ). Zusätzlich zum Standard-Array A , wobei A [ i , j ] der Bearbeitungsabstand zwischen den Präfixen x [ 1 … i ] und y [ 1 … j ] ist , verwenden wir ein anderes Array A $x$$a+b$$a$$A$$A[i,j]$$x[1 \dots i]$$y[1 \dots j]$$A_{d}$um die Bearbeitungsentfernung zu speichern, wenn die zuletzt verwendete Operation ein langes Löschen war. Mit diesem Array müssen wir beim Rechnen nur , A [ i - 1 , j - 1 ] , A [ i , j - 1 ] und A d [ i - 1 , j ] betrachten A [ i , j ] und A , j $A[i-1,j]$$A[i-1,j-1]$$A[i,j-1]$$A_{d}[i-1,j]$$A[i,j]$$A_{d}[i,j]$, so dass wir es in O tun ( Zeit.$O(1)$

Unter Kopieren von Teilstrings versteht man das Einfügen eines beliebigen Teilstrings von in den bearbeiteten String. Wie bei langen Löschungen teilen wir die Operation in zwei einfache Operationen auf: Einfügen des ersten Zeichens und Erweitern der Einfügung um ein Zeichen. Wir verwenden auch Array A s die Bearbeitungs Abstand zwischen Präfixe zu speichern, vorausgesetzt , dass die letzte Operation verwendet Kopieren wurde Strings zurück .$x$$A_{s}$

Dies effizient durchzuführen ist komplizierter als bei langen Löschvorgängen, und ich bin nicht sicher, ob wir die amortisierte -Zeit pro Zelle erreichen können. Wir erstellen einen Suffixbaum für x , der unter der Annahme eines Alphabets mit konstanter Größe O ( | x | ) benötigt . Wir speichern einen Zeiger auf die aktuellen Suffixbaum Knoten in A s [ i , j - 1 ] , so dass wir in konstanter Zeit prüfen, ob wir die Einfügung von Zeichen erstrecken y [ j ] . Wenn das wahr ist, können wir A berechnen [ $O(1)$$x$$O(|x|)$$A_{s}[i,j-1]$$y[j]$ und A s [ i , j ] in konstanter Zeit.$A[i,j]$$A_{s}[i,j]$

Andernfalls , wobei z der inserierte String ist, der verwendet wurde zum Berechnen A s [ i , j - 1 ] , ist kein String von x . Wir verwenden den Suffixbaum, um das längste Suffix z ' von z , für das z ' y [ j ] eine Teilzeichenfolge von x ist , in O ( | z | - | z ' | ) zu finden . Berechnen$zy[j]$$z$$A_{s}[i,j-1]$$x$$z'$$z$$z'y[j]$$x$$O(|z|-|z'|)$ | z müssen wir uns nun die Zellen A [ i , j - | ansehen z ' | - 1 ] bis A [ i , j - 1 ] . Das Auffinden des Suffix z ' erfordert nur die amortisierte O ( 1 ) -Zeit pro Zelle, aber die Berechnung von A s [ i , j ] mit einem Brute-Force-Ansatz benötigt O $A_{s}[i,j]$$A[i, j-|z'|-1]$$A[i,j-1]$$z'$$O(1)$$A_{s}[i,j]$ Zeit. Es gibt wahrscheinlich eine Möglichkeit, dies effizienter zu gestalten, aber ich kann sie derzeit nicht finden.$O(|z'|)$

Im schlimmsten Fall benötigt der Algorithmus die Zeit , aber eine bessere Analyse sollte möglich sein. Die resultierende Bearbeitungsentfernung bei langen Löschvorgängen und beim Kopieren von Teilzeichenfolgen ist nicht symmetrisch, aber das sollte kein Problem sein. Schließlich ist es normalerweise einfacher, die leere Zeichenfolge von einer nicht leeren Zeichenfolge aus zu erreichen, als umgekehrt.$O(\min(|x| \cdot |y|^{2}, |x|^{2} \cdot |y|))$