Wyszukiwanie najdłuższego wspólnego podciągu


Tematy pokrewne   Podrozdziały
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie
Podstawowe operacje na tablicach
  Rozwiązanie 1
Rozwiązanie 2

 

Problem

Dla danych dwóch niepustych łańcuchów tekstowych s1 i s2 znaleźć najdłuższy wspólny podciąg znakowy.


Na pierwszy rzut oka problem wydaje się taki sam jak w poprzednim rozdziale. Jest jednak bardzo istotna różnica. Przy znajdowaniu najdłuższego wspólnego podłańcucha chodziło o znalezienie najdłuższego, spójnego fragmentu tekstu, który występuje w obu łańcuchach. W bieżącym problemie znajdowania najdłuższego wspólnego podciągu (ang. longest common subsequence) chodzi o wyznaczenie najdłuższego ciągu znaków, które występują w tej samej kolejności w obu łańcuchach. Znaki te mogą być rozdzielone w każdym z łańcuchów innymi znakami.

 

Przykład:

   Najdłuższy wspólny podłańcuch       Najdłuższy wspólny podciąg   
s1 = ALIBABA
s2 = KALIMALBA
s1 = ALIBABA
s2 = KALIMALBA
       ALI        ALIABA

 

Problem znajdowania najdłuższego wspólnego podciągu występuje we wielu dziedzinach nauki:

Rozwiązanie nr 1

W pierwszym podejściu zastosujemy nieefektywne rozwiązanie rekurencyjne. Zaobserwujmy kilka prostych faktów związanych z problemem najdłuższego wspólnego podciągu – nazwijmy go dla ułatwienia LCS (ang. longest common subsequence). Załóżmy, iż mamy dwa łańcuchy znaków takie jak w powyższym przykładzie. Zapiszmy je jeden nad drugim i połączmy strzałkami znaki należące do LCS:

 

 

Zwróć uwagę, iż strzałki nie mogą się krzyżować, gdyż wtedy nie byłaby zachowana kolejność znaków. Wynika stąd kilka bardzo istotnych wniosków:

 

Jeśli dwa łańcuchy rozpoczynają się od tego samego znaku, to znak ten na pewno należy do LCS.

Jeśli początkowe znaki w obu łańcuchach są różne, to nie mogą oba jednocześnie należeć do LCS, gdyż wymagałoby to skrzyżowania strzałek. Jeden z nich (a może oba) będzie trzeba usunąć. Gdy zdecydujemy, co z nimi zrobić, to problem zredukuje się do znalezienia najdłuższego wspólnego podciągu dla łańcuchów pomniejszonych o te pierwsze znaki. Pozwala to na rozwiązanie rekurencyjne. Na początek określimy algorytm znajdowania długości LCS, a następnie samego LCS.

 

Algorytm rekurencyjnego znajdowania długości najdłuższego wspólnego podciągu

Wejście:
s1, s2 – łańcuchy tekstowe, w których szukamy LCS. Na końcu łańcuchów dodajemy wartownika.
i – indeks w s1, od którego rozpoczynamy przeglądanie łańcucha, i N
j – indeks w s2, od którego rozpoczynamy przeglądanie łańcucha, j N
Wyjście:

Długość LCS N

Lista kroków LCS(i,j):
K01: Jeśli s1[i] = wartownik, to zakończ z wynikiem 0 ; napotkany koniec łańcucha s1
K02: Jeśli s2[j] = wartownik, to zakończ z wynikiem 0 ; napotkany koniec łańcucha s2
K03: Jeśli s1[i] = s2[j], to zakończ z wynikiem 1 + LCS(i+1,j+1) ; wywołanie rekurencyjne
K04: Zakończ z wynikiem max(LCS(i+1,j),LCS(i,j+1)) ; wywołanie rekurencyjne

 

Mając algorytm znajdowania długości LCS możemy skonstruować algorytm wyznaczania samego LCS. Opieramy się na następujących przesłankach:

 

Jeśli znaki s1[i] oraz s2[j] są równe, to należą do LCS.
Jeśli znaki s1[i] oraz s2[j] są różne, to wyliczamy LCS(i+1,j) oraz LCS(i,j+1), a następnie sprawdzamy:

  1. LCS(i+1,j) ≤ LCS(i,j+1) – odrzucamy s2[j], gdyż bez niego mamy dłuższy LCS
  2. Inaczej odrzucamy s1[i] z tego samego powodu co wyżej

Algorytm znajdowania najdłuższego wspólnego podciągu

Wejście:
s1, s2 – łańcuchy tekstowe, w których szukamy LCS. Na końcu łańcuchów dodajemy wartownika o kodzie 0 (w C++ już jest!).
i – indeks w s1, od którego rozpoczynamy przeglądanie łańcucha, i N.
j – indeks w s2, od którego rozpoczynamy przeglądanie łańcucha, j N.
Wyjście:

Zawartość sLCS

Elementy pomocnicze:
sLCS  – łańcuch zawierający LCS
Lista kroków:
K01: sLCS ← "" ; zerujemy LCS
K02: i ← 0 ; ustawiamy indeksy na pierwszych znakach s1 i s2
K03: j ← 0  
K04: Dopóki (s1[i] ≠ 0) ∧ (s2[j] ≠ 0) wykonuj K05...K11  
K05:     Jeśli s1[i] ≠ s2[j], idź do K10 ; sprawdzamy równość znaków w obu łańcuchach
K06:     sLCSsLCS + s1[i] ; dodajemy znak do LCS
K07:     ii + 1 ; przesuwamy się na następną pozycję w obu łańcuchach
K08:     jj + 1  
K09:     Następny obieg pętli K04 ; i kontynuujemy pętlę
K10:     Jeśli LCS(i+1,j) ≤ LCS(i,j+1), to idź do K08 ; odrzucamy znak s2[j]
K11:     ii + 1 ; odrzucamy znak s1[i]
K12: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje dwa wiersze znaków (niezbyt długie z uwagi na wykładniczą klasę złożoności algorytmu), znajduje dla nich najdłuższy wspólny podciąg, wypisuje go wraz z jego długością.

 

Lazarus
// Wyszukiwanie najdłuższego wspólnego podciągu
// Data: 17.07.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

program prg;

uses Math;
 
var
  s1,s2,sLCS : ansistring;

// Funkcja oblicza długość LCS dla s1 i s2
// i - indeks startu w s1
// j - indeks startu w s2
//----------------------------------------
function LCS(i,j : integer) : integer;
begin
  if (s1[i] = #0) or (s2[j] = #0) then
    LCS := 0
  else if s1[i] = s2[j] then
    LCS := 1 + LCS(i+1,j+1)
  else
    LCS := max(LCS(i+1,j),LCS(i,j+1));
end;

var
  i,j : integer;

begin
  readln(s1); readln(s2);
  s1 := s1 + #0; // wartownik
  s2 := s2 + #0; // wartownik
  sLCS := ''; i := 1; j := 1;
  while (s1[i] <> #0) and (s2[j] <> #0) do
    if s1[i] = s2[j] then
    begin
      sLCS := sLCS + s1[i];
      inc(i); inc(j);
    end
    else if LCS(i+1,j) <= LCS(i,j+1) then inc(j) else inc(i);
  writeln(sLCS,' : ',length(sLCS));
end.
Code::Blocks
// Wyszukiwanie najdłuższego wspólnego podciągu
// Data: 17.07.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>

using namespace std;

string s1,s2,sLCS; // zmienne globalne

// Funkcja oblicza długość LCS dla s1 i s2
// i - indeks startu w s1
// j - indeks startu w s2
//----------------------------------------
int LCS(int i, int j)
{
  if(!s1[i] || !s2[j]) return 0;
  else if(s1[i] == s2[j]) return 1 + LCS(i+1,j+1);
  else return max(LCS(i+1,j),LCS(i,j+1));
}

int main()
{
  int i,j;

  getline(cin,s1);
  getline(cin,s2);
  sLCS = ""; i = j = 0;
  while(s1[i] && s2[j])
    if(s1[i] == s2[j])
    {
      sLCS += s1[i]; i++; j++;
    }
    else if(LCS(i+1,j) <= LCS(i,j+1)) j++; else i++;
  cout << sLCS << " : " << sLCS.length() << endl;
  return 0;
}
Free Basic
' Wyszukiwanie najdłuższego wspólnego podciągu
' Data: 17.07.2008
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------

Dim Shared As String s1,s2

' Funkcja zwraca większy ze swoich argumentów
'--------------------------------------------
Function max(Byval x As Integer, Byval y As Integer) As Integer
  If x > y Then
    max = x
  Else
    max = y
  End If
End Function

' Funkcja oblicza długość LCS dla s1 i s2
' i - indeks startu w s1
' j - indeks startu w s2
'----------------------------------------
Function LCS(Byval i As Integer, Byval j As Integer) As Integer
  If(Mid(s1,i,1) = Chr(0)) Or (Mid(s2,j,1) = Chr(0)) Then
    LCS = 0
  Elseif Mid(s1,i,1) = Mid(s2,j,1) Then
    LCS = 1 + LCS(i+1,j+1)
  Else
    LCS = max(LCS(i+1,j),LCS(i,j+1))
  End If
End Function

Dim As String sLCS
Dim As Integer i,j

Line Input s1: Line Input s2
s1 += Chr(0) ' wartownik
s2 += Chr(0) ' wartownik
sLCS = "": i = 1: j = 1
While (Mid(s1,i,1) <> Chr(0)) And (Mid(s2,j,1) <> Chr(0))
  If Mid(s1,i,1) = Mid(s2,j,1) Then
    sLCS += Mid(s1,i,1)
    i += 1: j += 1
  ElseIf LCS(i+1,j) <= LCS(i,j+1) Then
    j += 1
  Else
    i += 1
  End If
Wend
Print sLCS;" : ";Len(sLCS)
End
Wynik
ALIBABA
KALIMALBA
ALIABA : 6
 

Rozwiązanie nr 2

Algorytm rekurencyjny wyznaczania LCS posiada wykładniczą złożoność obliczeniową. Winę za to ponoszą rekurencyjne wywołania przy wyliczaniu długości LCS, gdzie wielokrotnie wykonywane są te same obliczenia. Usprawnienie zatem polega na eliminacji wywołań rekurencyjnych i zastosowaniu programowania dynamicznego – wyliczone długości LCS są zapamiętywane w osobnej tablicy L[(m+1) × (n+1)]. Dzięki takiemu podejściu klasa złożoności obliczeniowej spada do O(mn), jednakże algorytm wymaga dodatkowej pamięci rzędu O(mn). Element L[i+1,j+1] zawiera długość LCS dla podłańcuchów s1[0:i] oraz s2[0:j].

 

Algorytm dynamicznego znajdowania długości najdłuższego wspólnego podciągu

Wejście:
s1, s2 – łańcuchy tekstowe, w których szukamy LCS. Na końcu łańcuchów dodajemy wartownika.
Wyjście:

Długość LCS. Dodatkowo efektem działania algorytmu jest wypełniona tablica L, która może posłużyć do wyznaczania znaków LCS.

Elementy pomocnicze:
m  –  długość łańcucha s1, m N
n  – długość łańcucha s2, n N
L{ ]  – tablica długości o indeksach od 0 do m oraz od 0 do n, L N
i,j  – indeksy znaków w s1 i s2, i,j N

 

Lista kroków:
K01: m ← |s1| ; obliczamy długości łańcuchów s1
K02: n ← |s2| ; oraz s2
K03: Dla i = 0,1,...,m: L[i,0] ← 0 ; inicjujemy pierwszą kolumnę tablicy L
K04: Dla j = 0,1,...,n: L[0,j] ← 0 ; oraz pierwszy wiersz
K05: Dla i = 0,1,...,m - 1: wykonuj K06...K10 ; wyznaczamy długości kolejnych LCS
K06:     Dla j = 0,1,...,n - 1: wykonuj K07...K10  
K07:         Jeśli s1[i] ≠ s2[j], to idź do K10 ; sprawdzamy, czy LCS jest rozszerzalny
K08:         L[i + 1,j + 1] ← 1 + L[i,j] ; jeśli tak, to zwiększamy poprzednią długość
K09:         Następny obieg pętli K06  
K10:         L[i + 1,j + 1] ← max(L[i + 1,j],L[i,j + 1]) ; jeśli nie, wybieramy dłuższy LCS
K11: Zakończ z wynikiem L[m.n]  

 

Algorytm znajdowania najdłuższego wspólnego podciągu

Wejście:
s1, s2 – łańcuchy tekstowe, w których szukamy LCS.
Wyjście:

Zawartość LCS

Elementy pomocnicze:
sLCS  –  łańcuch zawierający LCS
L{ ]  – tablica długości LCS o indeksach od 0 do m oraz od 0 do n
i,j  – indeksy znaków w s1 i s2
Lista kroków:
K01: Utwórz i oblicz tablicę L ; wyznaczamy długości kolejnych LCS
K02: sLCS ← "" ; zerujemy LCS
K03: im - 1 ; ustawiamy indeksy na ostatnich znakach s1 i s2
K04: jn - 1  
K05: Dopóki (i ≥ 0) ∧ (j ≥ 0) wykonuj K06...K12  
K06:     Jeśli s1[i] ≠ s2[j], idź do K11 ; sprawdzamy równość znaków w obu łańcuchach
K07:     sLCSs1[i] + sLCS ; dodajemy znak na początek LCS - znaki otrzymujemy od końca!
K08:     ii - 1 ; przesuwamy się na poprzednią pozycję w obu łańcuchach
K09:     jj - 1  
K10:     Następny obieg pętli K05 ; i kontynuujemy pętlę
K11:     Jeśli L[i + 1,j] > L[i,j + 1], to idź do K09 ; cofamy się w s2
K12:     ii - 1 ; cofamy się w s1
K13: Zakończ z wynikiem sLCS  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje dwa wiersze znaków, znajduje dla nich najdłuższy wspólny podciąg i wypisuje go wraz z jego długością.

 

Lazarus
// Wyszukiwanie najdłuższego podciągu
// Data: 18.07.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

program prg;

uses Math;

type
  Tint = array of integer;
  TTint = array of Tint;

var
  s1,s2,sLCS : ansistring;
  L : TTint;
  i,j,m,n : integer;

begin
  readln(s1); readln(s2);

  m  := length(s1);
  n  := length(s2);

// tworzymy dynamicznie tablicę L

  setlength(L,m + 1);
  for i := 0 to m do setlength(L[i],n + 1);

// obliczamy tablicę L

  for i := 0 to m do L[i][0] := 0;
  for j := 0 to n do L[0][j] := 0;
  for i := 1 to m do
    for j := 1 to n do
      if s1[i] = s2[j] then
        L[i][j] := 1 + L[i - 1][j - 1]
      else
        L[i][j] := max(L[i][j - 1],L[i - 1][j]);

// wyznaczamy LCS

  sLCS := ''; i := m; j := n;
  while (i > 0) and (j > 0) do
    if s1[i] = s2[j] then
    begin
      sLCS := s1[i] + sLCS;
      dec(i); dec(j);
    end
    else if L[i][j - 1] > L[i - 1][j] then dec(j)
    else dec(i);
  writeln(sLCS,' : ',L[m][n]);
end.
Code::Blocks
// Wyszukiwanie najdłuższego podciągu
// Data: 18.07.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s1,s2,sLCS;
  int ** L,i,j,m,n;

  getline(cin,s1);
  getline(cin,s2);
  
  m  = s1.length();
  n  = s2.length();

// tworzymy dynamicznie tablicę L

  L = new int * [m + 1];
  for(i = 0; i <= m; i++) L[i] = new int[n + 1];

// obliczamy tablicę L

  for(i = 0; i <= m; i++) L[i][0] = 0;
  for(j = 0; j <= n; j++) L[0][j] = 0;
  for(i = 0; i < m; i++)
    for(j = 0; j < n; j++)
      if(s1[i] == s2[j])
        L[i + 1][j + 1] = 1 + L[i][j];
      else
        L[i + 1][j + 1] = max(L[i + 1][j],L[i][j + 1]);

// wyznaczamy LCS

  sLCS = ""; i = m - 1; j = n - 1;
  while((i >= 0) && (j >= 0))
    if(s1[i] == s2[j])
    {
      sLCS = s1[i] + sLCS;
      i--; j--;
    }
    else if(L[i + 1][j] > L[i][j + 1]) j--;
    else i--;
  cout << sLCS << " : " << L[m][n] << endl;
  return 0;
}
Free Basic
' Wyszukiwanie najdłuższego podciągu
' Data: 18.07.2008
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------

' Funkcja zwraca większy ze swoich argumentów
'--------------------------------------------
Function max(Byval x As Integer, Byval y As Integer) As Integer
  If x > y Then
    max = x
  Else
    max = y
  End If
End Function

Dim As String s1,s2,sLCS
Dim As Integer i,j,m,n

Line Input s1: Line Input s2

m = Len(s1)
n = Len(s2)

' tworzymy dynamicznie tablicę L

Dim As Integer L(m,n)

' obliczamy tablicę L

For i = 0 To m: L(i,0) = 0: Next
For j = 0 To n: L(0,j) = 0: Next
For i = 1 To m
  For j = 1 To n
    If Mid(s1,i,1) = Mid(s2,j,1) Then
      L(i,j) = 1 + L(i - 1,j - 1)
    Else
      L(i,j) = max(L(i,j - 1),L(i - 1,j))
    End If
  Next
Next

' wyznaczamy LCS

sLCS = "": i = m: j = n
While (i > 0) And (j > 0)
  If Mid(s1,i,1) = Mid(s2,j,1) Then
    sLCS = Mid(s1,i,1) + sLCS
    i -= 1: j -= 1
  Elseif L(i,j - 1) > L(i - 1,j) Then
    j -= 1
  Else
    i -= 1
  End If
Wend
Print sLCS;" : ";L(m,n)
End
Wynik
 

 

Wyszukiwanie najdłuższego wspólnego podciągu
(C)2012 mgr Jerzy Wałaszek

s1 =
s2 =


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.