Najdłuższy wspólny podciąg

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Najdłuższy wspólny podciąg (NWP, ang. longest common subsequence[1]) – najdłuższy podciąg znaków, które występują w tej samej kolejności w dwóch porównywanych łańcuchach. Elementy podciągów nie muszą przy tym leżeć obok siebie (tym różni się ten problem od problemu najdłuższego wspólnego podłańcucha, ang. longest common substring[2]). Rozwiązanie tego problemu jest bardzo przydatne przy pisaniu programów mających na celu wykrycie zmian w dokumentach lub plikach, lub przy pisaniu programów służących do identyfikacji plagiatów.

Przykłady:

  • Dla ciągów abaabbaaa i babab ich NWP to baba i abab.
  • Dla ciągów POLITECHNIKA i TOALETA ich NWP to OLTA i OLEA.
  • Dla ciągów 123 oraz 543 ich NWP to 3.

Warto przy tym zaznaczyć, że implementacja rozwiązania problemu może dotyczyć zarówno ciągu rozumianego jako ciąg liter, wyrazów czy nawet akapitów.

Algorytm znajdujący tablicę długości NWP dwóch ciągów[edytuj | edytuj kod]

Idea[edytuj | edytuj kod]

Problem NWP dwóch ciągów A i B o długościach odpowiednio n i m może być rozwiązany za pomocą metody programowania dynamicznego.

Algorytm ten ma złożoność obliczeniową rzędu O(n * m), gdzie n oraz m to długości ciągów A i B. Algorytm ten tworzy tablicę dwuwymiarową C (n na m) taką, że wartość C[i][j] jest długością NWP podciągów A[1..i] i B[1..j]. A więc po zakończeniu wypełniania tablicy C komórka C[n][m] będzie zawierała wartość będąca długością NWP oryginalnych ciągów wejściowych A i B.

Optymalne rozwiązanie podproblemów[edytuj | edytuj kod]

Załóżmy, że w danym kroku algorytmu chcemy obliczyć wartość komórki C[i][j], tj. długość NWP dla podciągów A[0..i] i B[0..j]. Jeżeli A i B są identyczne na pozycjach odpowiednio i i j (A[i]=B[j]) to należy włączyć ten wspólny znak do znalezionego wcześniej wspólnego podciągu. Wtedy

\! C[i][j]\ =\ C[i-1][j-1]\ +\ 1

ponieważ długością NWP ciągów A[1..i] i B[1..j] będzie długość NWP podciągów A[1..i-1] i B[1..j-1] plus jeden wspólny element z pozycji A[i] i B[j].

Jeżeli znaki A[i] i B[j] są różne, to obliczenie C[i][j] sprowadza się do sprawdzenia, który z wspólnych podciągów słów A[1..i-1] i B[1..j] oraz A[1..i] i B[1..j-1] jest dłuższy, i włączenie go do tablicy wynikowej.

C[i][j]\ =\max\ \{C[i][j-1],\ C[i-1][j]\}

A więc algorytm wypełniania tablicy C można zapisać jako:

C[i][j] = 
\begin{cases} 
\ C[i-1][j-1] + 1, & \ A[i]=B[j]\\
\max\ \{C[i-1][j],\ C[i][j-1]\}, & \ A[i]\neq B[j]\\
\end{cases}

Stany początkowe[edytuj | edytuj kod]

Do obliczenia tablicy C potrzeba jeszcze tylko tzw. stanów początkowych, tj. wartości początkowych rekurencjnych wzorów na C[i][j]. Z obserwacji, iż C[i][0] będzie zawsze równe 0 (ponieważ długość NWP ciągu i znaków i ciągu pustego jest zawsze równa zero, ponieważ NWP jest wtedy ciągiem pustym) wynika, że \forall_{i \in <0\cdots n>} C[i][0]\ =\ 0. analogiczne rozumowanie można przeprowadzić dla C[0][j] (\forall_{j \in <0\cdots m>} C[0][j]\ =\ 0).

Algorytm w pseudokodzie[edytuj | edytuj kod]

    for i := 0 to n do   // wypełnienie stanów początkowych
        C[i][0] := 0;
    for j := 1 to m do
        C[0][j] := 0;
 
    for i := 1 to n do
        for j := 1 to m do
            if A[i] = B[j] then
                C[i][j] := C[i-1][j-1] + 1  // znaleziono kolejny element NWP
            else
                C[i][j] := max(C[i-1][j], C[i][j-1]);

Po zakończeniu działania powyższej procedury komórka C[n][m] będzie zawierać długość NWP ciągów A i B

Algorytm odtwarzający NWP[edytuj | edytuj kod]

Mając gotową tablicę C długości wspólnych podciągów podciągów A i B można łatwo odtworzyć NWP.

Przykład odtwarzania najdłuższego wspólnego podciągu zilustrujmy przykładem. Weźmy wspomniane wcześniej wyrazy 'abaabbaaa' oraz 'babab'. tworzymy tablice o wymiarach o jeden większych niż odpowiednie długości wyrazów. W tym przypadku będzie to tablica 10x6. Wypełniamy ją zgodnie z algorytmem, a więc pierwszy rząd i pierwsza kolumna zgodnie z warunkami początkowymi będzie się równała 0

Ø a b a a b b a a a
Ø 0 0 0 0 0 0 0 0 0 0
b 0
a 0
b 0
a 0
b 0
Ø a b a a b b a a a
Ø 0 0 0 0 0 0 0 0 0 0
b 0 0 1
a 0
b 0
a 0
b 0

W tym miejscu dochodzimy do miejsca (komórka [3][2]), gdzie występuje taka sama litera w kolumnie i wierszu, stąd też komórka przyjmuje wartość zainkrementowanej komórki znajdującej się po skosie u góry z lewej [2][1], w komórce [4][2] spotyka się literka 'a' oraz 'b' więc przepisuje się wartość wyższą z komórki [3][2] lub [4][1], dochodząc analogicznie do komórki [6][2] gdzie znów 'b' spotyka się z 'b' inkrementowana jest wartość komórki [5][1], i wyniesie ona 1. Po wykonaniu analogicznie całego algorytmu otrzymujemy tabele:

Ø a b a a b b a a a
Ø 0 0 0 0 0 0 0 0 0 0
b 0 0 1 1 1 1 1 1 1 1
a 0 1 1 2 2 2 2 2 2 2
b 0 1 2 2 2 3 3 3 3 3
a 0 1 2 3 3 3 3 4 4 4
b 0 1 2 3 3 4 4 4 4 4

Jak widać komórka [10][6] pokazuje nam rzeczywistą długość najdłuższego wspólnego podciągu, która w tym przypadku wynosi 4. Aby dowiedzieć się jaki to podciąg należy 'przejść' z komórki [10][6] do komórki [0][0] według następującego algorytmu:


  1. jeśli któraś komórka sąsiednia do tej w której jesteśmy (z lewej strony lub u góry) ma wartość identyczną, to przechodzimy do niej
  2. jeśli jesteśmy w komórce [0][0] to zakończ.
  3. jeśli nie ma takiej, do ciągu odpowiedzi dopisujemy na początek literę odpowiadającą tej komórce a następnie idziemy do komórki o wartości mniejszej o 1 (po skosie do góry i w lewo)
  4. jeśli nie jesteśmy w komórce [0][0] to przeskocz do punktu 1. w przeciwnym wypadku Zakończ.

W związku z tym, że w każdym kolejnym kroku można iść zarówno w lewo jak i do góry, można uzyskać dwa, lub więcej podciągów (choć w większości przypadków wystarcza nam poznanie jednego)

Sposoby przejść zilustrują następujące tabelki:

Ø a b a a b b a a a
Ø 0 0 0 0 0 0 0 0 0 0
b 0 0 1 1 1 1 1 1 1 1
a 0 1 1 2 2 2 2 2 2 2
b 0 1 2 2 2 3 3 3 3 3
a 0 1 2 3 3 3 3 4 4 4
b 0 1 2 3 3 4 4 4 4 4

Jak widać wynikiem takiego podążania po tabeli jest podciąg 'abab'

Ø a b a a b b a a a
Ø 0 0 0 0 0 0 0 0 0 0
b 0 0 1 1 1 1 1 1 1 1
a 0 1 1 2 2 2 2 2 2 2
b 0 1 2 2 2 3 3 3 3 3
a 0 1 2 3 3 3 3 4 4 4
b 0 1 2 3 3 4 4 4 4 4

Wynikiem takich przejść jest podciąg 'baba'

Optymalizacje algorytmu[edytuj | edytuj kod]

Konstrukcja tego algorytmu sprawia, że czas potrzebny na rozwiązanie tego problemu wzrasta kwadratowo wraz ze zwiększaniem się porównywanych ciągów. Dlatego też warto stosować różnego rodzaju optymalizacje.

  • W przypadku ograniczonego dostępu pamięci i potrzebie wyznaczenia jedynie długości najdłuższego wspólnego podciągu, warto zamiast tworzenia macierzy prostokątnej o wymiarach m na n stworzyć jedynie dwa wektory o długości m w których przechowywany będzie jedynie poprzedni i aktualny wiersz.
  • W przypadku gdy porównywane są 2 teksty, których mamy pewność, że na przykład początek i koniec są takie same, możemy je pominąć w analizie.
  • Zwykle najwięcej czasu w tym algorytmie zabiera porównywanie. Dlatego działania w kierunku zmniejszenia ilości porównań mogą być pożądane. Poszukiwanie najdłuższego wspólnego podciągu pod względem całych wyrazów, linii lub akapitów może być szybsze w stosunku do przeszukiwania poszczególnych liter. Jednak trzeba tu uważać, bo porównywanie ciągów znakowych pod względem identyczności też nie jest zbyt szybkie. W celu przyspieszenia tych porównań można sprowadzić je do porównań sum kontrolnych tych ciągów, co powinno skrócić długość porównywanych ciągów. Niestety trzeba się tu liczyć z tym, że mogą wystąpić kolizje sum kontrolnych i różne ciągi znakowe mogą być reprezentowane przez tą samą sumę kontrolną. Oprócz tego, przygotowanie sum kontrolnych może też być czasochłonne.
  • Zastosowanie innego algorytmu, skuteczniejszego dla tekstów mniej podobnych do siebie. Polega on na tym, że dla ciągów A oraz B tworzy się macierz L, o liczbie kolumn równej długości krótszego ciągu, taką że:
    • L(i,k), gdzie i to numer kolumny, a k to numer wiersza, jeśli istnieje to ma wartość: L(i,k)=min( L(i-1,k),j) gdzie j jest to najmniejsza liczba jaka spełnia warunki A[i]=B[j] oraz j>L(i-1,k-1).
    • Istnieją dodatkowe warunki optymalizujące:
      • L(i,k)=null dla i<k, czyli nie istnieje.
      • Jeżeli L(i-1,k) nie istnieje oraz j nie istnieje to L(i,k) nie istnieje.
      • Jeżeli L(i-1,k-1) nie istnieje to L(i,k) nie istnieje.
      • Jeżeli L(i,k)==k to L(i+1,k)=k, L(i+2,k)=k (...) L(m,k)=k
      • Jeżeli cały wiersz L(i,k)=null to koniec algorytmu
    • Przykład działania: dane są ciągi POLITECHNIKA i TOALETA. Tworzymy macierz L o liczbie kolumn równej 7
T O A L E T A
k=1 5 2 2 2 2 2 2
k=2 - - 12 3 3 3 3
3 - - - - 6 5 5
4 - - - - - - 12
5 - - - - - - -
      • - oznacza komórki macierzy L które są null
      • długość rozwiązania jest reprezentowana przez liczbę wierszy macierzy które nie są w całości null
      • na niebiesko zaznaczone są numery znaków ciągu POLITECHNIKA które są najdłuższym wspólnym podciągiem, w tym przypadku OLTA

Przypisy

  1. tłumaczenie nazwy według Bartek Nowowiejski: LCS - najdłuższy wspólny podciąg. [dostęp 12 lipca 2009].
  2. tłumaczenie nazwy według Jerzy Wałaszek: Wyszukiwanie najdłuższego wspólnego podłańcucha. [dostęp 12 lipca 2009].