Kürzeste Anzahl von Bearbeitungsbewegungen zwischen zwei Wörtern

Ich suche nach einer Datenstruktur und einem Algorithmus, um die minimale Anzahl von Änderungen zu berechnen, die erforderlich sind, um ein Wort in ein anderes umzuwandeln, wobei die beiden Wörter als Eingaben verwendet werden, wobei die einzigen zulässigen Änderungen sind

• Fügen Sie an einem der Enden einen Buchstaben hinzu (z. B. AB -> ABC).
• das ganze Wort duplizieren und verketten (zum Beispiel ABC -> ABCABC),
• Schneiden Sie ein Wort in zwei Teile (das Dual der Duplizierungsbewegung, ABCABC -> ABC + ABC),
• Löschen Sie einen der Buchstaben (z. B. ABC -> AC) und
• Wiederholen Sie einen der Buchstaben (z. B. ABC -> ABBC).

Eine minimale Folge von Verschiebungen von ABC nach BCBC ist beispielsweise ABC -> BC (Löschen von A) -> BCBC (Duplizieren).

Ich habe keinen Hintergrund in Informatik. Vielleicht ist dies ein bekanntes Problem, aber meine Google-Suche hat mir nichts gebracht.

Kennen Sie ein verwandtes, genau definiertes Problem?

Bearbeiten : Wie in der Antwort von Anthony Labarre vorgeschlagen, habe ich einige Artikel über das Poset-Permutations- / Anordnungsproblem gelesen, das dem oben beschriebenen Problem ähnlich ist. Weiß jemand mehr über dieses Problem? Ist das relevant?

Ich weiß nicht, ob genau dieses Problem untersucht wurde, aber Chaudhuri et al. studierte das damit verbundene Problem des zufälligen Verlusts von Tandem-Duplikationen : Sie erhalten eine Permutation und möchten diese in die Identitätspermutation umwandeln, indem Sie (1) ein Segment beliebiger Länge duplizieren und die Kopie direkt nach dem Original anhängen und dann (2) löschen Elemente, so dass Sie eine neue Permutation anstelle einer Zeichenfolge erhalten. Beachten Sie, dass das Anwenden von (1) und dann (2) eine Operation ausmacht.

Je nach Gewicht für jede Operation können verschiedene Varianten definiert werden, die in ihrem Artikel von der Breite der duplizierten Segmente abhängen. Sie untersuchen auch ein ähnliches Problem mit der gesamten Genomduplikation , die genau die Art der Duplikation ist, die Sie zulassen. Ich kann mich nicht erinnern, über die Arbeit an diesem Problem im Zusammenhang mit Zeichenfolgen gelesen zu haben, aber ich hoffe, dies kann Ihnen zumindest einen Ausgangspunkt für Ihre Suche geben.

Wie bereits erwähnt, ähnelt dieses Problem dem allgemein bekannten Problem der Bearbeitungsentfernung (das der Levenshtein-Entfernung zugrunde liegt ). Es hat auch Gemeinsamkeiten mit beispielsweise der dynamischen Zeitverzerrungsentfernung (das Duplizieren oder „Stottern“ in Ihrer letzten Anforderung).

Schritte zur dynamischen Programmierung

$x=x_1\ldots x_n$$y=y_1\ldots y_m$$d(x,y)$

$$\min \begin{cases} d(x,y_1\ldots y_{m-1})+1 & &\text{▻ Add letter at end}\\ d(x,y_2\ldots y_m)+1 & & \text{▻ Add letter at beginning}\\ d(x,y_1\ldots y_{m/2})+1 & \text{if $y=y_1\ldots y_{m/2}y_1\ldots y_{m/2}$} & \text{▻ Doubling}\\ d(x_1\ldots x_{n/2},y)+1 & \text{if $x=x_1\ldots x_{n/2}x_1\ldots x_{n/2}$} & \text{▻ Halving}\\ d(x_1\ldots x_n,y) + 1 && \text{▻ Deletion}\\ d(x_1\ldots x_{n-1},y_1\ldots y_{m-1}) & \text{if $y_n = y_m$} & \text{▻ Ignoring last elt.}\\ \end{cases}$$

Hier besagt die letzte Option im Wesentlichen, dass die Konvertierung von FOOX in BARX der Konvertierung von FOO in BAR entspricht. Dies bedeutet, dass Sie die Option „Brief am Ende hinzufügen“ verwenden können, um den Stottern- (Duplizierungs-) Effekt und das Löschen an einem bestimmten Punkt zu erzielen. Das Problem ist, dass Sie automatisch auch ein beliebiges Zeichen in die Mitte der Zeichenfolge einfügen können , was Sie wahrscheinlich nicht möchten. (Dieses „Ignorieren identischer letzter Elemente“ ist die Standardmethode zum Löschen und Stottern an beliebigen Positionen. Es macht das Verbot beliebiger Einfügungen und das Hinzufügen von Hinzufügungen an beiden Enden jedoch etwas schwierig…)

Ich habe diese Aufschlüsselung aufgenommen, obwohl sie den Job nicht vollständig erledigt, falls jemand anderes sie irgendwie "retten" kann - und weil ich sie in meiner heuristischen Lösung unten verwende.

(Wenn Sie eine Aufschlüsselung wie diese erhalten könnten, die tatsächlich Ihre Entfernung definiert, müssten Sie nur Memoisierung hinzufügen, und Sie hätten eine Lösung. Da Sie jedoch nicht nur mit Präfixen arbeiten, tue ich das nicht. Ich glaube nicht, dass Sie nur Indizes für Ihre Memoisierung verwenden könnten. Möglicherweise müssen Sie die tatsächlichen, geänderten Zeichenfolgen für jeden Aufruf speichern. Dies würde sehr groß werden, wenn Ihre Zeichenfolgen eine beträchtliche Größe haben.)

Schritte zu einer heuristischen Lösung

Ein anderer Ansatz, der möglicherweise einfacher zu verstehen ist und viel weniger Platz benötigt, besteht darin, mit dem Algorithmus (im Grunde genommen am besten) nach dem kürzesten „Bearbeitungspfad“ von Ihrer ersten Zeichenfolge zu Ihrer zweiten zu suchen. erste Verzweigung). Der Suchraum wird direkt durch Ihre Bearbeitungsvorgänge definiert. Nun, für eine große Saite würden Sie$A^\ast$A ∗Erhalten Sie eine große Nachbarschaft, da Sie ein beliebiges Zeichen löschen können (indem Sie für jede mögliche Löschung einen Nachbarn angeben) oder ein beliebiges Zeichen duplizieren können (wiederum eine lineare Anzahl von Nachbarn) und an beiden Enden ein beliebiges Zeichen hinzufügen können Geben Sie eine Anzahl von Nachbarn an, die der doppelten Alphabetgröße entspricht. (Hoffe nur, dass du nicht den vollen Unicode verwendest ;-) Mit einem so großen Fanout kannst du mit einem bidirektionalen oder einem Verwandten$A^*$ eine beträchtliche Beschleunigung erzielen .

Damit funktioniert, benötigen Sie eine Untergrenze für die verbleibende Entfernung zu Ihrem Ziel. Ich bin mir nicht sicher, ob es hier eine offensichtliche Wahl gibt, aber Sie könnten eine dynamische Programmierlösung implementieren, die auf der oben angegebenen rekursiven Zerlegung basiert (wiederum mit möglichen Platzproblemen, wenn Ihre Zeichenfolgen sehr lang sind). Während diese Zerlegung Ihre Entfernung nicht genau berechnet, ist sie garantiert eine Untergrenze (weil sie freizügiger ist), was bedeutet, dass sie in als Heuristik funktioniert . (Wie eng es sein wird, weiß ich nicht, aber es wäre richtig.) Natürlich könnte die Memoisierung Ihrer gebundenen Funktion über alle Berechnungen der gebundenen während IhresA ∗ A $A^*$$A^*$$A^*$Lauf. (Ein Zeit- / Raum-Kompromiss dort.)

So…

Die Effizienz meiner vorgeschlagenen Lösung scheint ziemlich stark von (1) der Länge Ihrer Zeichenfolgen und (2) der Größe Ihres Alphabets abzuhängen. Wenn beides nicht riesig ist, könnte es funktionieren. Das ist:

• Implementieren Sie die Untergrenze für Ihre Entfernung mithilfe meiner rekursiven Zerlegung und dynamischen Programmierung (z. B. mithilfe einer gespeicherten rekursiven Funktion).
• Implementieren Sie (oder bidirektionales ) mit Ihren Bearbeitungsoperationen als "Verschiebungen" im Statusraum und der auf dynamischer Programmierung basierenden Untergrenze.A $A^*$$A^*$

Ich kann nicht wirklich garantieren, wie effizient es sein würde, aber es sollte korrekt sein, und es wäre wahrscheinlich viel besser als eine Brute-Force-Lösung.

Wenn nichts anderes, hoffe ich, dass dies Ihnen einige Ideen für weitere Untersuchungen gibt.

Ein verwandtes, genau definiertes Problem wäre das Problem der Sequenzausrichtung . Es ist anders, weil es keine Duplizierungsoperation verwendet. Definierte Operationen sind: Einfügen eines Zeichens, Löschen eines Zeichens, Transformation eines Zeichens. Ein beliebter Algorithmus zur Lösung dieses Problems ist Needleman-Wunsch .

Mit Ausnahme von Duplikaten ist die Levenstein-Entfernung möglicherweise einen Blick wert: http://en.wikipedia.org/wiki/Levenshtein_distance