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:

1. Czy ten problem ma nazwę? (Brzmi jak bardzo standardowe pytanie w kontekście wyrównania sekwencji).

2. Czy to trudne?

3. Jeśli jest trudny, czy jest możliwy do ustalenia parametr stały z jako parametrem?$K$

4. Czy istnieją wydajne algorytmy aproksymacyjne? (Np znaleźć rozwiązanie z co najwyżej tani i 2 K kosztownych operacji, jeżeli rozwiązanie z k tanie i K 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.

$k=0$

$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|))$