Edytuj odległość za pomocą operacji przesuwania

Motywacja: Współautor redaguje manuskrypt i chciałbym zobaczyć jasne podsumowanie edycji. Wszystkie narzędzia podobne do „diff” są zwykle bezużyteczne, jeśli zarówno przenosisz tekst (np. Reorganizując strukturę), jak i edytujesz lokalnie. Czy to naprawdę takie trudne?

Definicje: Chciałbym znaleźć minimalną odległość edycji, gdzie dozwolone operacje to:

„tanie” operacje: dodaj / zmień / usuń pojedynczy znak (zwykłe operacje Levenshtein),
„drogie”: operacje: przenieś podciąg do nowej lokalizacji ( $abcd \mapsto acbd$ dla dowolnych ciągów $a$ , $b$ , $c$ , $d$ ).

Biorąc pod uwagę dwa ciągi $x$ i $y$ i całkowite $k$ i $K$ , chciałbym rozwiązać następujący problem:

czy możesz przekształcić $x$ w $y$ przy użyciu co najwyżej $k$ tanich operacji i co najwyżej $K$ kosztownych operacji?

Pytania:

Czy ten problem ma nazwę? (Brzmi jak bardzo standardowe pytanie w kontekście wyrównania sekwencji).
Czy to trudne?
Jeśli jest trudny, czy jest możliwy do ustalenia parametr stały z jako parametrem? $K$
Czy istnieją wydajne algorytmy aproksymacyjne? (Np znaleźć rozwiązanie z co najwyżej tani i kosztownych operacji, jeżeli rozwiązanie z tanie i kosztownych operacji istnieją). $2k$ $2K$ $k$ $K$

Próbowałem spojrzeć na metryki ciągów wymienione w Wikipedii , ale żadna z nich nie wyglądała dobrze.

— Jukka Suomela
źródło

Dla

problemem jest Sortowanie według transpozycji. Patrz np. Web.cs.dal.ca/~whidden/HThesis07.pdf Nie napotkałem twojego problemu, ale wydaje się, że jest bardzo dobrze zmotywowany.

k = 0

$k=0$

— Serge Gaspers,

Twardość NP problemu sortowania według transpozycji została udowodniona w 2010 roku, patrz Sortowanie według transpozycji jest trudne .

— Marzio De Biasi,

Transpozycje są trudne, ale wstawienia i usunięcia nie. Jeśli zezwolisz, aby kosztowną operacją było albo usunięcie dowolnego podłańcucha, albo wstawienie dowolnego podłańcucha drugiego łańcucha, problem powinien stać się dość łatwy. Wynikowa odległość nie byłaby jednak symetryczna.

— Jouni Sirén,

Bardziej interesuje mnie ciągliwość parametrów o ustalonych parametrach. Czy jest jakieś nowe odkrycie?

— Yixin Cao

$k$ $ak+b$ $a,b \ge 0$

$x$ $a+b$ $a$ $A$ $A[i,j]$ $x[1 \dots i]$ $y[1 \dots j]$ $A_{d}$ $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]$ $O(1)$

$x$ $A_{s}$

$O(1)$ $x$ $O(|x|)$ $A_{s}[i,j-1]$ $y[j]$ $A[i,j]$ $A_{s}[i,j]$

$zy[j]$ $z$ $A_{s}[i,j-1]$ $x$ $z'$ $z$ $z'y[j]$ $x$ $O(|z|-|z'|)$ $A_{s}[i,j]$ $A[i, j-|z'|-1]$ $A[i,j-1]$ $z'$ $O(1)$ $A_{s}[i,j]$ $O(|z'|)$

$O(\min(|x| \cdot |y|^{2}, |x|^{2} \cdot |y|))$

— Jouni Sirén
źródło