Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

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

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

Dla danych dwóch niepustych łańcuchów tekstowych s 1 i s 2 należy wyznaczyć 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   
s 1 = ALIBABA
s 2 = KALIMALBA
s 1 = ALIBABA
s 2 = KALIMALBA
       ALI        ALIABA

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

  • Biologia molekularna – badania ciągów genów w łańcuchach DNA, które można sprowadzić do długich łańcuchów tekstowych zbudowanych z czterech znaków ACGT reprezentujących składniki DNA. Gdy zostaną znalezione nowe ciągi aminokwasów, szuka się podobieństw do nich. Do tego celu właśnie służy znajdowanie najdłuższych wspólnych podciągów.
  • Porównywanie plików – można sprawdzić w jakim stopniu dwa różne pliki są do siebie podobne wydzielając w nich najdłuższy wspólny podciąg.

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:

obrazek

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:

s 1, s 2 – łańcuchy tekstowe, w których szukamy LCS. Na końcu łańcuchów dodajemy wartownika.
i  – indeks w s 1, od którego rozpoczynamy przeglądanie łańcucha, i  ∈ N
j  – indeks w s 2, 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 s 1 [ i  ] = wartownik,
to zakończ z wynikiem 0
napotkany koniec łańcucha s 1
K02: Jeśli s 2 [ j  ] = wartownik,
to zakończ z wynikiem
0
napotkany koniec łańcucha s 2
K03: Jeśli s 1 [ i  ] = s 2 [ 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 s 1 [ i  ] oraz s 2 [ j  ] są równe, to należą do LCS.
Jeśli znaki s 1 [ i  ] oraz s 2 [ 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 s 2 [ j  ], gdyż bez niego mamy dłuższy LCS
  2. Inaczej odrzucamy s 1 [ i  ] z tego samego powodu co wyżej

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

Wejście:

s 1, s 2 – ł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 s 1, od którego rozpoczynamy przeglądanie łańcucha, i  ∈ N.
j  – indeks w s 2, od którego rozpoczynamy przeglądanie łańcucha, j  ∈ N.

Wyjście:

Zawartość s LCS

Zmienne pomocnicze:

s LCS  – łańcuch zawierający LCS

Lista kroków:

K01: s LCS  ← "" zerujemy LCS
K02: i  ← 0 ustawiamy indeksy na pierwszych znakach s 1 i s 2
K03: j  ← 0  
K04: Dopóki ( s 1 [ i  ] ≠ 0 ) ∧ ( s 2 [ j  ] ≠ 0 ):
wykonuj kroki K05...K11
 
K05:     Jeśli s 1 [ i  ] ≠ s 2 [ j  ],
    idź do kroku K10
sprawdzamy równość znaków w obu łańcuchach
K06:     s LCS  ← s LCS  + s 1 [ i  ] dodajemy znak do LCS
K07:     i  ← i  + 1 przesuwamy się na następną pozycję w obu łańcuchach
K08:     j  ← j  + 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 kroki K08
odrzucamy znak s 2 [ j ]
K11:     i  ← i  + 1 odrzucamy znak s 1 [ i ]
K12: Zakończ  

Przykładowe programy

Uwaga:

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ą.
Pascal
// Wyszukiwanie najdłuższego wspólnego podciągu
// Data: 17.07.2008
// (C)2020 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.
C++
// Wyszukiwanie najdłuższego wspólnego podciągu
// Data: 17.07.2008
// (C)2020 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;
}
Basic
' Wyszukiwanie najdłuższego wspólnego podciągu
' Data: 17.07.2008
' (C)2020 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
Na początek:  podrozdziału   strony 

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 s 1 [ 0:i  ] oraz s 2 [ 0:j  ].

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

Wejście:

s 1, s 2 – ł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.

Zmienne pomocnicze:

m  –  długość łańcucha s 1, m  ∈ N
n  – długość łańcucha s 2, 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 s 1 i s 2, i, j  ∈ N

Lista kroków:

K01: m  ← | s 1 | obliczamy długości łańcuchów s 1
K02: n  ← | s 2 | oraz s 2
K03: Dla i  = 0, 1, ..., m :
wykonuj L [ i, 0 ] ← 0
inicjujemy pierwszą kolumnę tablicy L
K04: Dla j  = 0, 1, ..., n :
wykonuj L [ 0, j  ] ← 0
oraz pierwszy wiersz
K05: Dla i  = 0, 1, ..., m - 1:
wykonuj kroki K06...K10
wyznaczamy długości kolejnych LCS
K06:     Dla j  = 0, 1, ..., n - 1:
    wykonuj kroki K07...K10
 
K07:         Jeśli s 1 [ i  ] ≠ s 2 [ j  ],
        to idź do kroku 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:

s 1, s 2 – łańcuchy tekstowe, w których szukamy LCS.

Wyjście:

Zawartość LCS

Zmienne pomocnicze:

s LCS  –  ł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 s 1 i s 2

Lista kroków:

K01: Utwórz i oblicz tablicę L wyznaczamy długości kolejnych LCS
K02: s LCS  ← "" zerujemy LCS
K03: i  ← m  - 1 ustawiamy indeksy na ostatnich znakach s 1 i s 2
K04: j  ← n  - 1  
K05: Dopóki ( i  ≥ 0 ) ∧ ( j  ≥ 0 ),
wykonuj kroki K06...K12
 
K06:     Jeśli s 1 [ i  ] ≠ s 2 [ j  ],
    idź do kroku K11
sprawdzamy równość znaków w obu łańcuchach
K07:     s LCS  ← s 1 [ i  ] + s LCS dodajemy znak na początek LCS - znaki otrzymujemy od końca!
K08:     i  ← i  - 1 przesuwamy się na poprzednią pozycję w obu łańcuchach
K09:     j  ← j  - 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 kroku K09
cofamy się w s 2
K12:     i  ← i  - 1 cofamy się w s 1
K13: Zakończ z wynikiem s LCS  

Przykładowe programy

Uwaga:

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ą.
Pascal
// Wyszukiwanie najdłuższego podciągu
// Data: 18.07.2008
// (C)2020 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.
C++
// Wyszukiwanie najdłuższego podciągu
// Data: 18.07.2008
// (C)2020 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;
}
Basic
' Wyszukiwanie najdłuższego podciągu
' Data: 18.07.2008
' (C)2020 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
Wyszukiwanie najdłuższego wspólnego podciągu
(C)2020 mgr Jerzy Wałaszek
s 1 =
s 2 =

...

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.