Szukaj…


Najdłuższe wspólne wyjaśnienie sekwencji

Jedną z najważniejszych implementacji programowania dynamicznego jest znalezienie najdłuższej wspólnej podsekwencji . Najpierw zdefiniujmy niektóre podstawowe terminologie.

Kolejność:

Podsekwencja to sekwencja, którą można uzyskać z innej sekwencji poprzez usunięcie niektórych elementów bez zmiany kolejności pozostałych elementów. Powiedzmy, że mamy ciąg ABC . Jeśli usuniemy zero lub jeden lub więcej niż jeden znak z tego ciągu, otrzymamy podsekwencję tego ciągu. Tak więc podsekwencje ciągu ABC będą to { „A” , „B” , „C” , „AB” , „AC” , „BC” , „ABC” , „” }. Nawet jeśli usuniemy wszystkie znaki, pusty ciąg będzie również podsekwencją. Aby znaleźć podsekwencję, dla każdego znaku w ciągu mamy dwie opcje - albo przyjmujemy znak, albo nie. Jeśli więc długość ciągu wynosi n , istnieją 2 n podciągów tego ciągu.

Najdłuższa wspólna kolejność:

Jak sama nazwa wskazuje, spośród wszystkich wspólnych podsekwencji między dwoma łańcuchami najdłuższa wspólna podsekwencja (LCS) to ta o maksymalnej długości. Na przykład: Wspólne podsekwencje między „HELLOM” i „HMLD” to „H” , „HL” , „HM” itd. Tutaj „HLL” jest najdłuższym wspólnym podsekwencją o długości 3.

Metoda Brute-Force:

Możemy wygenerować wszystkie podsekwencje dwóch łańcuchów za pomocą śledzenia wstecznego . Następnie możemy je porównać, aby znaleźć typowe podsekwencje. Po tym będziemy musieli znaleźć ten o maksymalnej długości. Widzieliśmy już, że istnieją 2 n podsekwencje ciągu o długości n . Rozwiązanie problemu zajęłoby lata, gdyby nasze n przekroczyło 20-25 .

Metoda programowania dynamicznego:

Podejdźmy do naszej metody z przykładem. Załóżmy, że mamy dwa ciągi abcdaf i acbcf . Oznaczmy je za pomocą s1 i s2 . Zatem najdłuższym wspólnym podsekwencją tych dwóch ciągów będzie „abcf” , który ma długość 4. Ponownie przypominam, podsekwencje nie muszą być ciągłe w ciągu. Aby skonstruować „abcf” , zignorowaliśmy „da” w s1 i „c” w s2 . Jak możemy się tego dowiedzieć za pomocą programowania dynamicznego?

Zaczniemy od tabeli (tablicy 2D) zawierającej wszystkie znaki s1 w rzędzie i wszystkie znaki s2 w kolumnie. Tutaj tabela jest indeksowana do 0, a my umieszczamy znaki od 1 do kolejnych. Przejdziemy przez tabelę od lewej do prawej dla każdego wiersza. Nasz stół będzie wyglądał następująco:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Tutaj każdy wiersz i kolumna reprezentują długość najdłuższego wspólnego podsekwencji między dwoma łańcuchami, jeśli weźmiemy znaki tego wiersza i kolumny i dodamy do przedrostka przed nim. Na przykład: Tabela [2] [3] reprezentuje długość najdłuższej wspólnej podsekwencji między „ac” i „abc” .

0-ta kolumna reprezentuje pustą podsekwencję s1 . Podobnie 0-ty rząd reprezentuje pustą podsekwencję s2 . Jeśli weźmiemy pusty podciąg łańcucha i spróbujemy dopasować go do innego łańcucha, bez względu na długość drugiego podłańcucha, wspólny podciąg będzie miał długość 0. Możemy więc wypełnić 0-te rzędy i 0-te kolumny zerami. Otrzymujemy:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Zaczynajmy. Kiedy wypełniamy tabelę [1] [1] , zadajemy sobie pytanie, czy jeśli mielibyśmy ciąg a i kolejny ciąg a i nic więcej, jaka będzie najdłuższa wspólna podsekwencja? Długość LCS tutaj będzie wynosić 1. Spójrzmy teraz na Tabelę [1] [2] . Mamy ciąg ab i ciąg a . Długość LCS będzie wynosić 1. Jak widać, reszta wartości będzie również równa 1 dla pierwszego wiersza, ponieważ uwzględnia tylko łańcuch a z abcd , abcda , abcdaf . Nasz stół będzie wyglądał następująco:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Dla wiersza 2, który będzie teraz obejmował c . Dla tabeli [2] [1] mamy ac z jednej strony i a z drugiej strony. Zatem długość LCS wynosi 1. Skąd wzięliśmy ten 1? Od góry, co oznacza LCS a między dwoma podciągami. Mówimy więc, że jeśli s1 [2] i s2 [1] nie są takie same, to długość LCS będzie maksymalną długością LCS u góry lub po lewej stronie . Biorąc pod uwagę długość LCS u góry, oznacza to, że nie bierzemy obecnej postaci z s2 . Podobnie, biorąc pod uwagę długość LCS po lewej stronie, oznacza to, że nie bierzemy obecnego znaku z s1, aby utworzyć LCS. Otrzymujemy:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Tak więc naszą pierwszą formułą będzie:

if s2[i] is not equal to s1[j]
    Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif

Przechodząc dalej, do tabeli [2] [2] mamy ciąg ab i ac . Ponieważ C i B nie są takie same, możemy umieścić maksymalnie górę lub w lewo tutaj. W tym przypadku jest to znowu 1. Następnie, dla tabeli [2] [3] mamy ciąg abc i ac . Tym razem aktualne wartości zarówno wiersza, jak i kolumny są takie same. Teraz długość LCS będzie równa maksymalnej dotychczasowej długości LCS + 1. Jak uzyskać maksymalną długość LCS do tej pory? Sprawdzamy wartość przekątną, która reprezentuje najlepsze dopasowanie między ab a a . Z tego stanu dla bieżących wartości dodaliśmy jeszcze jeden znak do s1 i s2, które okazały się być takie same. Długość LCS oczywiście wzrośnie. W tabeli [2] [3] umieścimy 1 + 1 = 2 . Dostajemy

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |  1  |  2  |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Zatem naszą drugą formułą będzie:

if s2[i] equals to s1[j]
    Table[i][j] = Table[i-1][j-1] + 1
endif

Zdefiniowaliśmy oba przypadki. Korzystając z tych dwóch formuł, możemy wypełnić całą tabelę. Po wypełnieniu tabeli będzie wyglądać następująco:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |  1  |  2  |  2  |  2  |  2  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |  1  |  2  |  2  |  2  |  2  |  2  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |  1  |  2  |  3  |  3  |  3  |  3  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |  1  |  2  |  3  |  3  |  3  |  4  |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Długość LCS między s1 i s2 będzie wynosić Tabela [5] [6] = 4 . Tutaj 5 i 6 są odpowiednio długością s2 i s1 . Nasz pseudo-kod będzie:

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

Złożoność czasowa dla tego algorytmu wynosi: O (mn) gdzie m i n oznacza długość każdego łańcucha.

Jak znaleźć najdłuższą wspólną podsekwencję? Zaczniemy od prawego dolnego rogu. Sprawdzimy, skąd pochodzi wartość. Jeśli wartość pochodzi z przekątnej, to znaczy, jeśli tabela [i-1] [j-1] jest równa tabeli [i] [j] - 1 , naciskamy albo s2 [i], albo s1 [j] (oba są takie same) i poruszają się po przekątnej. Jeśli wartość pochodzi z góry, oznacza to, że jeśli Tabela [i-1] [j] jest równa Tabeli [i] [j] , przechodzimy na górę. Jeśli wartość pochodzi z lewej strony, oznacza to, że jeśli Tabela [i] [j-1] jest równa Tabeli [i] [j] , przechodzimy w lewo. Gdy dojdziemy do lewej lub najwyższej kolumny, nasze wyszukiwanie się kończy. Następnie usuwamy wartości ze stosu i drukujemy je. Pseudo-kod:

Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
     if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
        S.push(s1[j])   //or S.push(s2[i])
        i := i - 1
        j := j - 1
    else if Table[i-1][j] == Table[i][j]
        i := i-1
    else
        j := j-1
    endif
endwhile
while S is not empty
    print(S.pop)
endwhile

Należy zauważyć: jeśli zarówno Tabela [i-1] [j], jak i Tabela [i] [j-1] jest równa Tabeli [i] [j] i Tabela [i-1] [j-1] nie jest równe tabeli [i] [j] - 1 , dla tego momentu mogą istnieć dwa LCS. Ten pseudo-kod nie uwzględnia tej sytuacji. Musisz rozwiązać to rekurencyjnie, aby znaleźć wiele LCS.

Złożoność czasowa dla tego algorytmu wynosi: O (maks. (M, n)) .



Modified text is an extract of the original Stack Overflow Documentation
Licencjonowany na podstawie CC BY-SA 3.0
Nie związany z Stack Overflow