Algorytmy i Struktury Danych - Najdłuższy wspólny podciąg

SPIS TREŚCI

Tematy pomocnicze

Podstawowe operacje na tablicach

Podrozdziały

Rozwiązanie 1
Rozwiązanie 2

Problem

Dla danych dwóch niepustych łańcuchów tekstowych s₁ i s₂ 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₁ = ALIBABA s₂ = KALIMALBA	s₁ = ALIBABA s₂ = 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.

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₁, s₂ : łańcuchy tekstowe, w których szukamy LCS. Na końcu łańcuchów dodajemy wartownika.
i : indeks w s₁, od którego rozpoczynamy przeglądanie łańcucha; i ∈ N.j : indeks w s₂, od którego rozpoczynamy przeglądanie łańcucha; j ∈ N.

Wyjście:

Długość LCS ∈ N.

Elementy pomocnicze:

max(x, y) : zwraca większą z wartości x i y.

Lista kroków LCS(i, j):

K01: Jeśli s₁[i] = wartownik, ; napotkany koniec łańcucha s₁
     to zakończ z wynikiem 0
K02: Jeśli s₂[j] = wartownik, ; napotkany koniec łańcucha s₂
     to zakończ z wynikiem 0
K03: Jeśli s₁[i] = s₂[j], ; wywołanie rekurencyjne
     to zakończ z wynikiem 1+LCS(i+1, j+1)
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₁[i] oraz s₂[j] są równe, to należą do LCS.
Jeśli znaki s₁[i] oraz s₂[j] są różne, to wyliczamy LCS(i+1, j) oraz LCS(i, j+1), a następnie sprawdzamy:

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

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

Wejście:

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

Wyjście:

Zawartość s_LCS.

Elementy 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₁ i s₂K03: j ← 0
K04: Dopóki (s₁[i] ≠ 0) ∧ (s₂[j] ≠ 0):
     wykonuj kroki K05…K11
K05:   Jeśli s₁[i] ≠ s₂[j], ; sprawdzamy równość znaków w obu łańcuchach
       idź do kroku K10
K06:   s_LCS ← s_LCS+s₁[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), ; odrzucamy znak s₂[j]
       to idź do kroku K08
K11:   i ← i+1 ; odrzucamy znak s₁[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

Python (dodatek)

# Wyszukiwanie najdłuższego
# wspólnego podciągu
# Data: 17.03.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------

# Funkcja oblicza długość
# LCS dla s1 i s2
# i-indeks startu w s1
# j-indeks startu w s2
# ----------------------------------------
def lcs(i, j):
    global s1, s2

    if not ord(s1[i]) or not ord(s2[j]):
        return 0
    elif s1[i] == s2[j]:
        return 1 + lcs(i + 1, j + 1)
    else:
        return max(lcs(i + 1, j), lcs(i, j + 1))


s1 = input() + chr(0)
s2 = input() + chr(0)
s_lcs, i, j = "", 0, 0
while ord(s1[i]) and ord(s2[j]):
    if s1[i] == s2[j]:
        s_lcs += s1[i]
        i += 1
        j += 1
    elif lcs(i + 1, j) <= lcs(i, j + 1):
        j += 1
    else:
        i += 1
print(s_lcs, ":", len(s_lcs))
print()

Wynik:

ALIBABA
KALIMALBA
ALIABA : 6

do podrozdziału do strony

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(m×n), jednakże algorytm wymaga dodatkowej pamięci rzędu O(m×n). Element L[i+1, j+1] zawiera długość LCS dla podłańcuchów s₁[0:i] oraz s₂[0:j].

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

Wejście:

s₁, s₂– ł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 s₁; m ∈ N.
n : długość łańcucha s₂; 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₁ i s₂; i, j ∈ N.
max(x, y) : zwraca większą z wartości x i y.

Lista kroków:

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

Wyjście:

Zawartość LCS

Elementy 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₁ i s₂

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₁ i s₂K04: j ← n-1
K05: Dopóki (i ≥ 0) ∧ ( j ≥ 0), 
     wykonuj kroki K06…K12
K06:   Jeśli s₁[i] ≠ s₂[j], ; sprawdzamy równość znaków w obu łańcuchach
       to idź do kroku K11
K07:   s_LCS ← s₁[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],  ; cofamy się w s₂
       to idź do kroku K09
K12:   i ← i-1 ; cofamy się w s₁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

Python (dodatek)

# Wyszukiwanie najdłuższego podciągu
# Data: 18.03.2024
# (C)2024 mgr Jerzy Wałaszek
#-----------------------------------

s1 = input()
s2 = input()
m = len(s1)
n = len(s2)
# tworzymy dynamicznie tablicę L
t_l = [[0 for j in range(n+1)] for i in range(m+1)]
# obliczamy tablicę L
for i in range(m):
    for j in range(n):
        if s1[i] == s2[j]:
            t_l[i+1][j+1] = 1+t_l[i][j]
        else:
            t_l[i+1][j+1] = max(t_l[i+1][j], t_l[i][j+1])
# wyznaczamy LCS
s_lcs, i, j = "", m-1, n-1
while (i >= 0) and (j >= 0):
    if s1[i] == s2[j]:
        s_lcs = s1[i]+s_lcs
        i -= 1
        j -= 1
    elif t_l[i+1][j] > t_l[i][j+1]:
        j -= 1
    else:
        i -= 1
print(s_lcs, ":", t_l[m][n])

do podrozdziału do strony

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.

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

Problem

Rozwiązanie nr 1

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków LCS(i, j):

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy