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

12

Jeśli otrzymamy dwa ciągi o rozmiarze n1 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 ) )n2O(n1n2)O(n1n2)ddO(max(n1,n2))

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(n1n2)

a3nm
źródło

Odpowiedzi:

15

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)={if i<m/2jif i=m/2Half(i1,j)if i>m/2 and Edit(i,j)=Edit(i1,j)+1Half(i,j1)Jeśli ja>m/2) i mirejat(ja,jot)=mirejat(ja,jot-1)+1H.zalfa(ja-1,jot-1)Inaczej

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 )H.zalfa(ja,jot)mirejat(ja,jot)O(mn)mirejat(m,n)H.zalfa(m,n)O(m+n)

wprowadź opis zdjęcia tutaj

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 . . nZA[1 ..m]b[1 ..n]ZA[1..m/2)]b[1..H.zalfa(m,n)]ZA[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 , nb[H.zalfa(m,n)+1..n]

T.(m,n)={O(n)Jeśli m1O(m)Jeśli n1O(mn)+maxh(T.(m/2),h)+T.(m/2),n-h))Inaczej
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)
Jeffε
źródło
5
Ponieważ mi tego brakowało, kiedy Dan zapytał mnie na egzaminie kwalifikacyjnym, dlatego.
Jeffε
pamiętam, że miałem to ćwiczenie (z przewodnikiem) i uważałem, że było całkiem fajnie
Sasho Nikolov
3

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(n1+n2))O(n1+n2))O(n1n2))O(n1+n2))

Yuval Filmus
źródło