Najdłuższy wspólny podciąg

02.10.2010 - Marcin Oczeretko
TrudnośćTrudność

Przykład działania algorytmu

    Aby przekonać się o tym, że algorytm jest naprawdę bardzo prosty, wyznaczmy za jego pomocą LCS dla wyrazów "markotny" i "romantyk".

Krok 1

    Najpierw tworzymy tablicę 9x9 (długość pierwszego słowa + 1 na długość drugiego słowa + 1) i wypełniamy zerowy wiersz i zerową kolumnę zerami.


Rozpoczynamy z tak wypełnioną tablicą.

Krok 2

    Wypełniamy resztę pól tablicy. Wyliczamy wartości dla kolejnych wierszy, idąc od lewej do prawej. Jeśli jakiemuś polu odpowiadają różne literki w obu wyrazach, to wpisujemy weń większą z liczb z pól nad nim i po lewej. Jeśli zaś rozpatrywane pole odpowiada tym samym literkom, to wpisujemy do niego zwiększoną o jeden liczbę z pola "na skos" (w lewo i do góry).


Częściowo wypełniona tablica. Czy potrafisz powiedzieć dlaczego właśnie takie liczby wpisaliśmy w pola?

Krok 3

    Teraz będziemy odtwarzać wyznaczony podciąg. Zaczynamy od pola (9,9) i "cofamy" się aż do lewej lub górnej krawędzi. Jeśli pole odpowiada różnym literkom, to "idziemy" do pola po lewej lub w górę - decyzja zależy od tego, w którym znajduje się większa liczba. W przypadku gdy polu odpowiadają te same literki w obu słowach idziemy na skos (znów w lewo i do góry) i zapisujemy sobie gdzieś, że znaleźliśmy następną literkę wyznaczonego LCS. Gdy dotrzemy do lewej/górnej krawędzi, znamy już cały najdłuższy wspólny podciąg wyrazów "markotny" i "romantyk" - jest to wyraz "rony".


Po wypełnieniu tablicy wyznaczamy postać LCS, idąc po "strzałkach".

Zmniejszamy zużycie pamięci

    Jeśli przyjrzymy się powyższemy przykładowi, to zauważymy, że jeśli zależy nam jedynie na wyliczeniu długości LCS, to o dużej ilości wierszy wypełnianej tablicy możemy "zapominać". Do wyliczenia wartości w dowolnej komórce z i-tego wiersza potrzebujemy bowiem jedynie informacji o liczbach z komórek leżących bezpośrednio na lewo, w górę i na skos od niego. Wszystkie one znajdują się w wierszach o numerach i-1 oraz i. Zatem to, jakie wartości znajdują się w wierszach od 0 do i-2 jest już kompletnie bezużyteczną informacją! Możemy więc ograniczyć się do przechowywania jedynie poprzedniego wiersza i tego, który aktualnie wypełniamy. Dzięki temu zmniejszamy zużycie pamięci - nie potrzebujemy już $ n \cdot m $ komórek tablicy, wystarczy ich nam $ 2 \cdot m $. Gdy wypełnimy jakiś wiersz, to on staje się nowym "poprzednim wierszem", a my na jego podstawie wyliczamy wartości w kolejnym. Gdy skończymy, w pamięci znajdować się będą dwa wiersze - ostatni i przedostatni. Na końcu ostatniego wiersza odnajdziemy liczbę będącą długością LCS. Oczywiście nie ma nic za darmo, teraz nie uda się nam już odtworzyć postaci LCS poprzez wędrowanie po tablicy.

    Możliwe jest jeszcze bardziej oszczędne wyliczanie LCS - wystarczy bowiem jeden wiersz. Czy widzisz jak należałoby nadpisywać w nim wartości z poprzedniego wiesza liczbami wyliczonymi dla następnego? Przeanalizuj ponownie działanie algorytmu i zwróć uwagę na to, jak długo potrzebujemy kolejnych wartości z początkowych komórek poprzedniego wiersza.

    Na następnej stronie znajdują się dwa zadania programistyczne, które pomogą w sprawdzeniu zrozumienia powyższego algorytmu. Z całego serca polecam rozwiązanie choć jednego z nich.

5
Twoja ocena: Brak Ocena: 5 (10 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com