Bearbeiten Sie die Entfernung mit Verschiebevorgängen

13

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 ).abcdacbdabcd

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

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

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.)2k2KkK

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

Jukka Suomela
quelle
3
Für ist das Problem Sortieren nach Transpositionen. Siehe z. B. web.cs.dal.ca/~whidden/HThesis07.pdf Ich bin auf Ihr Problem nicht gestoßen, aber es scheint sehr gut motiviert zu sein. k=0
Serge Gaspers
4
Die NP-Härte des Problems Sortieren nach Transpositionen wurde 2010 nachgewiesen, siehe Sortieren nach Transpositionen ist schwierig .
Marzio De Biasi
3
Transpositionen sind schwierig, Insertionen und Deletionen jedoch nicht. Wenn Sie für eine teure Operation entweder das Löschen einer beliebigen Teilzeichenfolge oder das Einfügen einer beliebigen Teilzeichenfolge der anderen Zeichenfolge zulassen, sollte das Problem recht einfach werden. Der resultierende Abstand wäre jedoch nicht symmetrisch.
Jouni Sirén
Ich bin eher neugierig auf die Tractability mit festen Parametern. Gibt es eine neue Entdeckung?
Yixin Cao

Antworten:

4

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 , bkak+b. Diese Konstanten können bei langen Löschvorgängen und beim Kopieren von Teilzeichenfolgen unterschiedlich sein.a,b0

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 dxa+baAA[i,j]x[1i]y[1j]Adum 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[i1,j]A[i1,j1]A[i,j1]Ad[i1,j]A[i,j]Ad[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 .xAs

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 [ iO(1)xO(|x|)As[i,j1]y[j] und A s [ i , j ] in konstanter Zeit.A[i,j]As[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 . Berechnenzy[j]zAs[i,j1]xzzzy[j]xO(|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 (As[i,j]A[i,j|z|1]A[i,j1]zO(1)As[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||y|2,|x|2|y|))

Jouni Sirén
quelle