Złożoność przestrzeni w celu obliczenia optymalnego wyrównania łańcucha dla odległości edycji Levenshteina

Jeśli otrzymamy dwa ciągi o rozmiarze $n_1$ i , standardowe obliczanie odległości edycji Levenshteina odbywa się za pomocą algorytmu dynamicznego o złożoności czasowej i złożoności przestrzennej . (Niektóre ulepszenia można wprowadzić w zależności od odległości edycji , ale nie zakładamy, że jest szczególnie mały.) Jeśli interesuje Cię tylko wartość odległości edycji (tj. Minimalna liczba edycji), a dobrze znane ulepszenie zwykłego algorytmu (gdzie zachowuje się tylko poprzedni i bieżący wiersz tabeli wyrównania) zmniejsza złożoność przestrzeni do . O ( n 1 n 2 ) O ( n 1 n 2 ) d d O ( maks. ( n 1 , n 2 ) $n_2$$O(n_1 n_2)$$O(n_1 n_2)$$d$$d$$O(\max(n_1, n_2))$

Jeśli jednak chcesz uzyskać rzeczywistą edycję optymalnego skryptu edycji, czy możliwe jest lepsze wykorzystanie pamięci niż , być może kosztem czasu działania?$O(n_1 n_2)$

Yuval nie ma potrzeby kompromisu. Całą optymalną sekwencję edycji można obliczyć w czasie i przestrzeni , używając mieszanki programowania dynamicznego oraz funkcji dziel i zwyciężaj, opisanej po raz pierwszy przez Dana Hirschberga. ( Algorytm przestrzeni liniowej do obliczania maksymalnych wspólnych podsekwencji. Commun. ACM 18 (6): 341–343, 1975.)O ( n + m $O(nm)$$O(n+m)$

Intuicyjnie pomysł Hirschberga polega na obliczeniu pojedynczej operacji edycji w połowie optymalnej sekwencji edycji, a następnie rekurencyjnym obliczeniu dwóch połówek sekwencji. Jeśli myślimy o optymalnej sekwencji edycji jako ścieżce od jednego rogu tabeli do zapamiętywania do drugiego, potrzebujemy zmodyfikowanego cyklu, aby zapisać, gdzie ta ścieżka przecina środkowy rząd tabeli. Jednym z powtarzających się działań jest:

$$Half(i,j) = \begin{cases} \infty & \text{if $i<m/2$}\\ j & \text{if $i=m/2$}\\ Half(i-1,j) & \text{if $i>m/2$ and $Edit(i,j) = Edit(i-1,j)+1$}\\ Half(i,j-1) & \text{if $i>m/2$ and $Edit(i,j) = Edit(i,j-1)+1$}\\ Half(i-1,j-1) & \text{otherwise} \end{cases}$$

Wartości można obliczyć w tym samym czasie, co edytowanie tabeli odległości , stosując czas . Ponieważ każdy wiersz tabeli zapamiętywania zależy tylko od wiersza nad nim, obliczenie zarówno i wymaga tylko miejsca .E d i t ( i , j ) O ( m n ) E d i t ( m , n ) H a l f ( m , n ) O ( m + n $Half(i,j)$$Edit(i,j)$$O(mn)$$Edit(m,n)$$Half(m,n)$$O(m+n)$

Wreszcie optymalna sekwencja edycji przekształcająca ciągi wejściowe na składa się z optymalnych sekwencji przekształcających na a następnie optymalna sekwencja transformująca w . Jeśli rekurencyjnie obliczymy te dwa podsekwencje, całkowity czas działania będzie zgodny z następującą powtarzalnością: Nietrudno udowodnić, żeB [ 1 .. n ] A [ 1 . . m / 2 ] B [ 1 . . H a l f ( m , n ) ] A [ m / 2 + 1 . . m ] B [ H a l f ( m , n ) + 1 . . $A[1..m]$$B[1..n]$$A[1 .. m/2]$$B[1 .. Half(m, n)]$$A[m/2 + 1 .. m]$T ( m , n ) = { O ( n ) jeśli  m ≤ 1 O ( m ) jeśli  n ≤ 1 O ( m n ) + max h ( T ( m / 2 , h ) + T ( m / 2 , n - h ) ) w innym przypadku T ( m , $B[Half(m, n) + 1 .. n]$

$$T(m,n) = \begin{cases} O(n) & \text{if $m\le 1$}\\ O(m) & \text{if $n\le 1$}\\ O(mn) + \max_h \left( T(m/2,h) + T (m/2, n−h)\right) & \text{otherwise} \end{cases}$$ $T(m,n) = O(mn)$. Podobnie, ponieważ potrzebujemy miejsca tylko na jedno przejście programowania dynamicznego naraz, łączna przestrzeń ograniczona jest nadal . (Miejsce na stos rekurencyjny jest znikome.)$O(m+n)$

Opisany algorytm działający w przestrzeni faktycznie przywraca ostateczną edycję i stan tuż przed ostateczną edycją. Jeśli więc uruchomisz ten algorytm razy, możesz odzyskać całą sekwencję edycji kosztem zwiększenia czasu działania. Ogólnie rzecz biorąc, istnieje kompromis czasoprzestrzenny, który jest kontrolowany przez liczbę wierszy, które zachowałeś w tym czasie. Dwa skrajne punkty tego kompromisu to przestrzeń i przestrzeń , a między nimi iloczyn czasu i przestrzeni jest stały (do dużego O).$O(n_1 + n_2)$$O(n_1 + n_2)$$O(n_1n_2)$$O(n_1+n_2)$