Najdłuższy wspólny podciąg
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
Idea edytuj
Problem NWP dwóch ciągów i o długościach odpowiednio i może być rozwiązany za pomocą metody programowania dynamicznego.
Algorytm ten ma złożoność obliczeniową rzędu gdzie oraz to długości ciągów i
Algorytm ten tworzy tablicę dwuwymiarową C (n na m) taką, że wartość C[i][j] jest długością NWP podciągów i A więc po zakończeniu wypełniania tablicy komórka będzie zawierała wartość będąca długością NWP oryginalnych ciągów wejściowych i
![{\displaystyle A[1..i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1026c84adda5dfe7935892035a9e42d8bf0b8267)
![{\displaystyle B[1..j].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/38fc7f6697a8021d52607082729dce9b582f4d2b)
![{\displaystyle C[n][m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/44922ecfa581d1ac790c947e181a3c921aad669b)
Optymalne rozwiązanie podproblemów edytuj
Załóżmy, że w danym kroku algorytmu chcemy obliczyć wartość komórki tj. długość NWP dla podciągów i Jeżeli i są identyczne na pozycjach odpowiednio i to należy włączyć ten wspólny znak do znalezionego wcześniej wspólnego podciągu. Wtedy:
![{\displaystyle C[i][j],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b1f1d67b5486bf19ecc42dbb9dc0bfd31c54475)
![{\displaystyle A[0..i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90d11b2acc26648b9a8581a0753ad015e63aa384)
![{\displaystyle B[0..j].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99fd9c8f27bc8547574fc2511af640f2c4cd907b)
![{\displaystyle (A[i]=B[j])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dafcac6a3c21ffb7c09c2d2d01ebe6a686297415)
![{\displaystyle C[i][j]=C[i-1][j-1]+1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/acab83bfb98f51571fb3603f11d80ca6261fc4ce)
ponieważ długością NWP ciągów i będzie długość NWP podciągów i plus jeden wspólny element z pozycji i
![{\displaystyle B[1..j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a19bc88539250aa6d033e38fba8ed4a9f4b3a9e)
![{\displaystyle A[1..i-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9523b6cd49b9af71de2275c34721757245980b00)
![{\displaystyle B[1..j-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c33f5cf42afcfa092675f77585dbafc270ee0027)
![{\displaystyle A[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a0d7a8a3371fad84f7032042e8d1e1caf6aa15e)
![{\displaystyle B[j].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f3571877fb02354f1c2ddbe8971bb8e3d9a31de)
Jeżeli znaki i są różne, to obliczenie sprowadza się do sprawdzenia, który ze wspólnych podciągów słów i oraz i jest dłuższy, i włączenie go do tablicy wynikowej.
![{\displaystyle B[j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eca09441dce3b5f93e01443728060c4ecc7f1adb)
![{\displaystyle C[i][j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c19a84da3b01b3dd8dcd78e5de34029169dc3a6a)
![{\displaystyle C[i][j]=\max\{C[i][j-1],\ C[i-1][j]\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f7f3c89fa7b15b9281f86a7ec03ddae5a2be04)
Zatem algorytm wypełniania tablicy można zapisać jako:
![{\displaystyle 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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8219ea5cc5d96c5cc54ef0429e44216844b05a4e)
Stany początkowe edytuj
Do obliczenia tablicy potrzeba jeszcze tylko tzw. stanów początkowych, tj. wartości początkowych rekurencjnych wzorów na Z obserwacji, iż będzie zawsze równe (ponieważ długość NWP ciągu znaków i ciągu pustego jest zawsze równa zero, ponieważ NWP jest wtedy ciągiem pustym) wynika, że Analogiczne rozumowanie można przeprowadzić dla
![{\displaystyle C[i][j].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc83a03d6b599f7fc2b10e9acaa2a22c49303aca)
![{\displaystyle C[i][0]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f07d86fb4729437e3860a8aed630b0adb367e5)
![{\displaystyle \forall _{i\in <0\ldots n>}C[i][0]=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40cb72ad06a49607afc863e32a10fd9e9c8eb2fb)
![{\displaystyle C[0][j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/680642eb8818b4f4e6dc5865dff2a8f598e8d704)
![{\displaystyle (\forall _{j\in <0\ldots m>}C[0][j]=0).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4cf38dca6063150dda4ac1624f344fdcef2e0a8)
Algorytm w pseudokodzie edytuj
for i := 0 to n do // wypełnienie stanów początkowych
C[i][0] := 0;
for j := 0 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
Mając gotową tablicę długości wspólnych podciągów podciągów i można łatwo odtworzyć NWP.
Odtwarzanie najdłuższego wspólnego podciągu zilustrujmy przykładem. Weźmy wspomniane wcześniej wyrazy ‘abaabbaaa’ oraz ‘babab’. Tworzymy tablicę o wymiarach o jeden większych niż odpowiednie długości wyrazów. W tym przypadku będzie to tablica 10×6. 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 tabelę:
| Ø | 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:
- 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,
- jeśli jesteśmy w komórce [0][0] to zakończ,
- 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),
- 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
 |
Ta sekcja od 2015-05 wymaga zweryfikowania podanych informacji. |
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 na stworzyć jedynie dwa wektory o długości w których przechowywany będzie jedynie poprzedni i aktualny wiersz.
- Można także wyznaczyć NWP w czasie O(nm) i pamięci O(\min\{n,m\}), wzorując się na algorytmie Hirschberga.
- 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 o liczbie kolumn równej długości krótszego ciągu, taką że:
- gdzie to numer kolumny, a to numer wiersza, jeśli istnieje to ma wartość: gdzie jest to najmniejsza liczba jaka spełnia warunki oraz
- Istnieją dodatkowe warunki optymalizujące:
- dla i<k, czyli nie istnieje.
- Jeżeli nie istnieje oraz j nie istnieje to nie istnieje.
- Jeżeli nie istnieje to nie istnieje.
- Jeżeli to
- Jeżeli cały wiersz to koniec algorytmu
- Przykład działania: dane są ciągi POLITECHNIKA i TOALETA. Tworzymy macierz L o liczbie kolumn równej 7.
![{\displaystyle A[i]=B[j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f02bce9a1d79549da1728abb00706ffe24f163fc)
| 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 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 edytuj
- ↑ Tłumaczenie nazwy według Bartek Nowowiejski: LCS – najdłuższy wspólny podciąg. [dostęp 2009-07-12].
- ↑ Tłumaczenie nazwy według Jerzy Wałaszek: Wyszukiwanie najdłuższego wspólnego podłańcucha. [dostęp 2009-07-12]. [zarchiwizowane z tego adresu (17 listopada 2009)].