Najkrótsza liczba edycji przechodzi między dwoma słowami

Szukam struktury danych i algorytmu do obliczenia minimalnej liczby zmian wymaganych do przekształcenia jednego słowa w drugie, biorąc pod uwagę dwa słowa jako dane wejściowe, gdzie jedynymi dozwolonymi zmianami są

• dodaj literę na jednym z krańców (na przykład AB -> ABC),
• powielać i konkatenować całe słowo (na przykład ABC -> ABCABC),
• przeciąć słowo na pół (podwójny ruch kopiowania, ABCABC -> ABC + ABC),
• usuń jedną z liter (na przykład ABC -> AC) i
• powtórz jedną z liter (na przykład ABC -> ABBC).

Na przykład minimalna sekwencja ruchów z ABC do BCBC to ABC -> BC (usuń A) -> BCBC (duplikacja).

Nie mam doświadczenia w informatyce. Być może jest to znany problem, ale moje wyszukiwanie w Google nic mi nie dało.

Czy znasz jakiś powiązany, dobrze zdefiniowany problem?

Edycja : Jak sugeruje odpowiedź Anthony Labarre, przeczytałem kilka artykułów na temat problemu permutacji / aranżacji poetów, który jest podobny do problemu opisanego powyżej. Czy ktoś wie więcej na temat tego problemu? Czy to jest istotne?

Nie wiem, czy dokładnie zbadano ten problem, ale Chaudhuri i in. badał związany z tym problem tandemowego duplikacji i przypadkowej utraty : otrzymujesz permutację i chcesz ją przekształcić w permutację tożsamości poprzez (1) powielenie odcinka o dowolnej długości i dodanie kopii zaraz po oryginale, a następnie (2) usunięcie elementy, dzięki czemu uzyskasz nową permutację zamiast łańcucha. Pamiętaj, że zastosowanie (1), a następnie (2) dotyczy jednej operacji.

Różne warianty mogą być zdefiniowane w zależności od wagi nadanej każdej operacji, która w swoim papierze zależy od szerokości zduplikowanych segmentów. Badają również podobny problem z duplikacją całego genomu , który jest dokładnie takim rodzajem duplikacji, na jaki pozwalasz. Nie pamiętam, aby czytać o pracy nad tym problemem w kontekście ciągów, ale mam nadzieję, że może to dać przynajmniej punkt wyjścia do poszukiwań.

Jak już wspomniano, problem ten jest podobny do bardziej znanego problemu edycji odległości (leżącego u podstaw odległości Levenshteina ). Ma również cechy wspólne, na przykład z odległością dynamicznego dopasowywania czasu (duplikacja lub „jąkanie się” w ostatnim wymaganiu).

Kroki w kierunku programowania dynamicznego

Moja pierwsza próba rekurencyjnego rozkładu wzdłuż linii Levenshteina i dynamicznej odległości wypaczania w czasie była podobna do następującej (dla i ), przy czym ustawiono $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}$$

Ostatnia opcja mówi tutaj, że konwersja FOOX na BARX jest równoważna konwersji FOOX na BAR. Oznacza to, że można użyć opcji „dodaj literę na końcu”, aby uzyskać efekt jąkania (powielania) i usuwanie w jednym punkcie. Problemem jest to, że automatycznie pozwala dodać dowolną postać w środku łańcucha , a także , co prawdopodobnie nie ma. (To „ignorowanie identycznych ostatnich elementów” jest standardowym sposobem na usunięcie i zacinanie się w dowolnych pozycjach. Uniemożliwia wprowadzanie dowolnych wstawek, jednocześnie pozwalając na dodawanie na obu końcach, choć trochę trudne…)

Zawarłem ten podział, nawet jeśli nie spełnia on całkowicie swojej funkcji, na wypadek, gdyby ktoś inny go „uratował” - i ponieważ używam go w moim heurystycznym rozwiązaniu, poniżej.

(Oczywiście, jeśli mógłbyś dostać taki podział, który faktycznie określał twój dystans, wystarczy dodać notatkę i mieć rozwiązanie. Jednak ponieważ nie pracujesz tylko z prefiksami, nie Pomyśl, że możesz użyć tylko indeksów do zapamiętywania; być może będziesz musiał przechowywać rzeczywiste, zmodyfikowane ciągi dla każdego połączenia, które byłyby ogromne, gdyby twoje ciągi były znacznej wielkości).

Kroki w kierunku rozwiązania heurystycznego

Innym podejściem, które może być łatwiejsze do zrozumienia i które mogłoby zająć nieco mniej miejsca, jest wyszukiwanie najkrótszej „ścieżki edycji” od pierwszego ciągu do drugiego za pomocą algorytmu (w zasadzie najlepiej - pierwszy odgałęziony). Przestrzeń wyszukiwania byłaby definiowana bezpośrednio przez twoje operacje edycji. Teraz, dla dużego łańcucha, zrobiłbyś to$A^\ast$uzyskać duże sąsiedztwo, ponieważ można usunąć dowolny znak (dając sąsiada dla każdego potencjalnego usunięcia) lub zduplikować dowolny znak (ponownie, dając liniową liczbę sąsiadów), a także dodać dowolny znak na każdym końcu, co by daje liczbę sąsiadów równą dwukrotności wielkości alfabetu. (Mam tylko nadzieję, że nie używasz pełnego Unicode ;-) Przy tak dużym fanoucie możesz osiągnąć całkiem spore przyspieszenie, używając dwukierunkowego lub jakiegoś krewnego$A^*$ .

Aby działało, potrzebujesz dolnej granicy pozostałej odległości do celu. Nie jestem pewien, czy jest oczywistym wyborem tutaj, ale co mogła zrobić, to wdrożenie rozwiązania opartego na programowaniu dynamicznym rekurencyjnego rozkładu dałem powyżej (znowu z możliwych kwestiach kosmicznych jeśli struny są bardzo długie). Mimo, że rozkład nie dokładnie obliczyć dystans, to jest zagwarantowane dolną granicę (bo to jest bardziej liberalne), co oznacza, że będzie ona działać jako heurystyki w . (Jak ciasno będzie, nie wiem, ale byłoby poprawne.) Oczywiście zapamiętywanie funkcji powiązania może być współużytkowane we wszystkich obliczeniach granicy podczas$A^*$$A^*$$A^*$biegać. (Kompromis czasowy / kosmiczny.)

Więc…

Wydajność zaproponowanego przeze mnie rozwiązania wydaje się zależeć od (1) długości twoich ciągów i (2) od wielkości twojego alfabetu. Jeśli żadne z nich nie jest ogromne, może działać. To jest:

• Zaimplementuj dolną granicę odległości za pomocą mojego rekurencyjnego rozkładu i programowania dynamicznego (na przykład za pomocą zapamiętanej funkcji rekurencyjnej).
• Zaimplementuj (lub dwukierunkowy ) z operacjami edycji jako „ruchy” w przestrzeni stanów i dolną granicę opartą na programowaniu dynamicznym.$A^*$$A^*$

Naprawdę nie mogę dać żadnych gwarancji na to, jak efektywna byłaby, ale powinna być poprawna i prawdopodobnie byłaby o wiele lepsza niż rozwiązanie brutalnej siły.

Jeśli nic więcej, mam nadzieję, że daje to kilka pomysłów na dalsze badania.

Pewnym powiązanym, dobrze zdefiniowanym problemem byłby problem wyrównania sekwencji . Jest inaczej, ponieważ nie wykorzystuje operacji duplikacji. Zdefiniowane operacje to: wstawianie znaku, usuwanie znaku, transformacja znaku. Popularnym algorytmem rozwiązywania tego problemu jest Needleman-Wunsch .

Oprócz powielania, warto spojrzeć na odległość Levensteina: http://en.wikipedia.org/wiki/Levenshtein_distance