Algorytmy i Struktury Danych - Najkrótszy wspólny nadłańcuch

Problem znajdowania najkrótszego wspólnego nadłańcucha (ang. shortest common superstring – SCS) pojawia się w wielu dziedzinach nauki, np. w badaniach łańcuchów DNA. Samo znalezienie łańcucha zawierającego wszystkie łańcuchy s₁, s₂…, s_k nie jest zadaniem trudnym – można po prostu połączyć je ze sobą. Trudność pojawia się w momencie, gdy żądamy, aby wynikowy łańcuch posiadał najkrótszą możliwą długość. Okazuje się, iż zadanie to jest problemem NP-zupełnym.

W informatyce termin NP-zupełny odnosi się do klas złożoności obliczeniowej problemów, w których zasoby wymagane do rozwiązania rosną bardzo szybko (np. wykładniczo) wraz ze wzrostem rozmiaru problemu (tj. liczby przetwarzanych danych). W efekcie problemy te mogą nie być rozwiązywalne nawet na najszybszych komputerach z uwagi na to, iż czas oczekiwania na wynik przekracza czas istnienia naszego wszechświata. Jedną z nierozwiązanych zagadek informatyki jest to, czy problemy NP-zupełne da się rozwiązać przy mniejszej ilości zasobów. Udowodniono nawet, że jeśli dałoby się rozwiązać chociaż jeden z nich, to pozostałe można by sprowadzić do tego rozwiązania. Jako programista powinieneś umieć rozpoznawać problemy NP-zupełne, aby na próżno nie tracić czasu na szukanie rozwiązania, którego jeszcze nikt nie znalazł (no… chyba że ty masz zamiar zostać tym szczęśliwcem).

Z powyższego powodu, zamiast rozwiązania dokładnego, często zadowalamy się rozwiązaniem przybliżonym, być może nieoptymalnym, ale dającym się wyliczyć w rozsądnym czasie. Jednym z podejść do rozwiązania jest zastosowanie metody zachłannej (ang. greedy algorithm), która polega na tym, iż lokalnie dokonujemy najlepszych wyborów na każdym etapie pracy algorytmu w nadziei, iż znajdziemy w ten sposób optymalne rozwiązanie globalne.

Przykład:

Wyznaczyć najmniejszą liczbę banknotów i monet dających razem sumę 138 zł.

Rozpoczynamy od największego możliwego banknotu, który nie przekracza danej sumy (optymalne rozwiązanie lokalne):

138 zł = 100 zł+38 zł reszty

Operację kontynuujemy dla reszty 38 zł:

138 zł = 100 zł+20 zł+18 zł reszty
138 zł = 100 zł+20 zł+10 zł+8 zł reszty
138 zł = 100 zł+20 zł+10 zł+5 zł+3 zł reszty
138 zł = 100 zł+20 zł+10 zł+5 zł+2 zł+1 zł – koniec

W tym przypadku otrzymaliśmy rozwiązanie optymalne.

Często jednak metoda zachłanna nie daje optymalnego rozwiązania. Rozważmy tzw. problem plecakowy (ang. knapsack problem). Mamy zbiór liczb {2, 2, 3, 3}, które reprezentują rozmiar przedmiotów umieszczanych w plecaku. Plecak posiada pojemność równą 7. Naszym zadaniem jest optymalne wypełnienie plecaka. Wg metody zachłannej najpierw staramy się w nim umieścić największe przedmioty, czyli 3 i 3. W plecaku pozostanie miejsca na przedmiot o rozmiarze 7-3-3 = 1. Takiego przedmiotu nie mamy, zatem plecak nie będzie wypełniony optymalnie – a zmieściłyby się w nim przedmioty o rozmiarze 2, 2, 3.

Wracając do problemu SCS będziemy szukać w zbiorze łańcuchów S = {s₁, s₂, …, s_k} dwóch łańcuchów s_i i s_j, i ≠ j, o najdłuższym pasującym sufiksie i prefiksie. Po znalezieniu takich łańcuchów zastąpimy je jednym, połączonym łańcuchem.

W efekcie zbiór S będzie zawierał o jeden łańcuch mniej. Operację powyższą powtarzamy dotąd, aż w zbiorze S pozostanie tylko jeden łańcuch. Łańcuch ten potraktujemy jako przybliżenie SCS.

Algorytm wyszukiwania najkrótszego wspólnego nadłańcucha

Wejście:

S : k elementowy zbiór łańcuchów znakowych; k > 0, indeksy od 0 do k-1.

Wyjście:

Łańcuch znakowy zawierający wszystkie łańcuchy ze zbioru S, być może najkrótszy z możliwych.

Elementy pomocnicze:

i, j : indeksy łańcuchów w zbiorze S; i, j ∈ N.
max_ps : maksymalna długość prefiksu i sufiksu; max_ps ∈ C.
ps : wyliczana długość najdłuższego prefiksu i sufiksu; ps ∈ N.
s_p : indeks w S łańcucha z najdłuższym prefiksem; s_p ∈ N.
s_s : indeks w S łańcucha z najdłuższym sufiksem; s_s ∈ N.
k : liczba łańcuchów w S; k ∈ N.

Lista kroków:

K01: max_ps ← -1 ; ustawiamy maksymalny prefiks i sufiks
K02: k ← |S| ; obliczamy ilość elementów w zbiorze S
K03: Jeśli k = 1, ; zwracamy SCS
     to zakończ z wynikiem S[0]
K04: Dla i = 0, 1, …, k-1: ; wyznaczamy najdłuższy prefiks i sufiks
     wykonuj kroki K05…K11
K05:   Dla j = 0, 1, …, k-1:
       wykonuj kroki K06…K11
K06:   Jeśli i = j, ; łańcuchy muszą być różne
       to następny obieg pętli K05
K07:   Oblicz ps dla S[i] i S[j] ; wyznaczamy najdłuższy wspólny
       ; sufiks S[i] i prefiks S[j]
K08:   Jeśli ps ≤ max_ps, 
       to następny obieg pętli K05
K09:   max_ps ← ps ; zapamiętujemy długość prefiksu i sufiksu
K10:   s_p ← j ; zapamiętujemy indeks łańcucha z prefiksem
K11: s_s ← i ; oraz indeks łańcucha z sufiksem
K12: Element S[s_s] zastąp ; wyznaczone łańcuchy łączymy sufiksem
     złączeniem s-p S[s_s] i S[s_p] ; i prefiksem
K13: Element S[s_p] usuń z S
K14: Idź do kroku K01

Podany powyżej algorytm nie nadaje się jeszcze do implementacji w postaci programu. Musimy rozwiązać kilka problemów. Od tego jak to zrobimy, zależeć będzie wynikowa złożoność obliczeniowa.

Zbiór S będziemy reprezentować jednowymiarową tablicą, której elementy będą łańcuchami znaków. Operacja usuwania elementu z tablicy (K13), przy zachowaniu ciągłości numeracji łańcuchów, wykonywana jest w czasie liniowym O(n). Z kolei operacja dostępu do elementu (K12) wykonywana jest w czasie stałym O(1). Umawiamy się, iż elementy tablicy S będą tworzyły ciąg niepustych łańcuchów znakowych. Za długość k zbioru S przyjmiemy liczbę tych niepustych łańcuchów.

Dla danych dwóch łańcuchów S[i] oraz S[j] musimy wyznaczyć maksymalny sufiks S[i], który pasuje do prefiksu S[j]. Najprostszy algorytm rozwiązania tego problemu wygląda następująco:

Algorytm wyszukiwania najdłuższego sufiksu pasującego do prefiksu w drugim łańcuchu

Wejście:

s₁, s₂ : niepuste łańcuchy znakowe. W łańcuchu s₁ szukamy sufiksu pasującego do prefiksu łańcucha s₂.

Wyjście:

Maksymalna długość sufiksu łańcucha s₁ pasującego do prefiksu łańcucha s₂.

Elementy pomocnicze:

ii : indeks w s₁; ii ∈ N.
ps : długość prtefiksu-sufiksu; ps ∈ N.

Lista kroków:

K01: ii ← |s₁|-|s₂| ; ustawiamy indeks pierwszego znaku sufiksu
K02: Jeśli ii < 0, 
     to ii ← 0
K03: ps ← 0 ; indeks pierwszego znaku prefiksu
K04: s₁ ← s₁+wartownik₁ ; na końcu łańcuchów dodajemy wartowników
K05: s₂ ← s₂+wartownik₂ ; chroniących przed wyjściem poza łańcuch
K06: Dopóki s₁[ii] ≠ wartownik₁: ; szukamy sufiksu s₁
     wykonuj kroki K07…K10 ; zgodnego z prefiksem s₂K07:   Dopóki s₁[ii+ps] = s₂[ps]: ; porównujemy znaki
       wykonuj ps ← ps+1 ; aż do napotkania niezgodności
K08:   Jeśli s₁[ii+ps] = wartownik₁, ; sprawdzamy, czy mamy
       to idź do kroku K11 ; pasujący sufiks do prefiksu
K09:   ps ← 0 ; jeśli nie, prefiks zerujemy i szukamy dalej
K10:   ii ← ii+1
K11: Usuń wartowników z s₁ i s₂; przywracamy normalną
     ; postać łańcuchów
K12: Zakończ z wynikiem ps ; zwracamy długość sufiksu-prefiksu

Teraz musimy określić sposób wykonania złączenia dwóch łańcuchów, tak aby nałożyły się na siebie sufiks i prefiks. W tym przypadku, skoro znamy długość sufiksu i prefiksu, operacja jest bardzo prosta:

S[s_s] ← S[s_s]+S[s_p][max_ps:|S[s_p]|]

I na koniec pozostała nam operacja usunięcia elementu S[s_s]. Z tablicy nie można tak po prostu usunąć elementu. Jeśli umówimy się, iż zbiór S jest reprezentowany przez kolejne elementy od S[0] do S[k-1], to wystarczy elementn S[s_s] zastąpić ostatnim elementem S[k-1], a następnie zmniejszyć k o 1. W ten sposób otrzymamy o jeden efektywny element mniej w zakresie od S[0] do S[k-1].

Wynikowy łańcuch SCS można czasami zoptymalizować wyznaczając w nim położenia poszczególnych łańcuchów ze zbioru S (trzeba je wtedy zapamiętać w innej tablicy) i zapamiętując ostatnie pozycje. Jeśli maksymalna ostatnia pozycja łańcuchów S w SCS jest mniejsza od ostatniej pozycji SCS, to SCS można obciąć do tej pozycji. W ten sposób ulepszymy nieco metodę zachłanną, ale lojalnie uprzedzamy, iż istnieją lepsze algorytmy wyznaczania SCS, np. drzewa sufiksowe.

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 generuje zbiór S zbudowany z 8 łańcuchów zawierających od 3 do 10 znaków należących do alfabetu {A, B}. Następnie wyznacza dla tego zbioru nadłańcuch i prezentuje w odpowiedni sposób wyniki.

Pascal

// Wyszukiwanie najkrótszego nadłańcucha
// Data: 22.07.2008
// (C)2020 mgr Jerzy Wałaszek
//--------------------------------------

program prg;

var
  S, P : array [0..7] of string;
  i, j, maxps, ps, sp, ss, k, ii : integer;

begin

  // generujemy zbiór S
  randomize;

  for i := 0 to 7 do
  begin
    k := 3+random(8);
    S[i] := '';
    for j := 1 to k do
      S[i] := S[i]+chr(65+random(2));
    writeln('S[', i, '] = ', S[i]);
    P[i] := S[i];
  end;

  // wyznaczamy SCS
  for k := 8 downto 2 do
  begin
    maxps := -1;
    for i := 0 to k-1 do
      for j := 0 to k-1 do
        if i <> j then
        begin
          ii := length(S[i])-length(S[j])+1;
          if ii < 1 then ii := 1;
          ps := 0;
          S[i] := S[i]+'@'; // wartownik1
          S[j] := S[j]+'#'; // wartownik2
          while S[i][ii] <> '@' do
          begin
            while S[i][ii+ps] = S[j][ps+1] do
              inc(ps);
            if S[i][ii+ps] = '@' then break;
            ps := 0; inc(ii);
          end;
          delete(S[i], length(S[i]), 1);
          delete(S[j], length(S[j]), 1);
          if ps > maxps then
          begin
            maxps := ps; sp := j; ss := i;
          end;
        end;
    S[ss] := S[ss]+copy(S[sp], maxps+1, length(S[sp])-maxps);
    S[sp] := S[k-1];
  end;

  writeln;

  // wypisujemy łańcuchy odpowiednio przesunięte
  // zapamiętujemy również maksymalną ostatnią pozycję
  maxps := 0;
  for i := 0 to 7 do
  begin
    write('S[', i, '] =');
    ps := pos(P[i], S[0]);
    for j := 1 to ps do write(' ');
    writeln(P[i]);
    inc(ps, length(P[i])-1);
    if ps > maxps then maxps := ps;
  end;

  // optymalizujemy SCS
  S[0] := copy(S[0], 1, maxps);
  writeln('       ', S[0]);
  writeln;
end.

C++

// Wyszukiwanie najkrótszego nadłańcucha
// Data: 22.07.2008
// (C)2020 mgr Jerzy Wałaszek
//--------------------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
  string S[8], P[8];
  int i, j, maxps, ps, sp, ss, k, ii;

  // generujemy zbiór S
  srand(time(NULL));
  for(i = 0; i < 8; i++)
  {
    k = 3+rand()%8; 
    S[i] = "";
    for(j = 0; j < k; j++)
      S[i] += char(65+rand()%2);
    cout << "S[" << i << "] = "
         << S[i] << endl;
    P[i] = S[i];
  }

// wyznaczamy SCS

  for(k = 8; k > 1; k--)
  {
    maxps = -1;
    for(i = 0; i < k; i++)
      for(j = 0; j < k; j++)
        if(i != j)
        {
          ii = S[i].length()-S[j].length();
          if(ii < 0) ii = 0;
          ps = 0;
          S[i] += '@'; // wartownik1
          S[j] += '#'; // wartownik2
          while(S[i][ii] != '@')
          {
            while(S[i][ii+ps] == S[j][ps]) ps++;
            if(S[i][ii+ps] == '@') break;
            ps = 0; ii++;
          }
          S[i].erase(S[i].length()-1, 1);
          S[j].erase(S[j].length()-1, 1);
          if(ps > maxps)
          {
            maxps = ps; sp = j; ss = i;
          }
        }
    S[ss] += S[sp].substr(maxps, S[sp].length()-maxps);
    S[sp] = S[k-1];
  }

  cout << endl;

  // wypisujemy łańcuchy odpowiednio przesunięte
  // zapamiętujemy również maksymalną ostatnią pozycję
  maxps = 0;
  for(i = 0; i < 8; i++)
  {
    cout << "S[" << i << "] =";
    ps = S[0].find(P[i]);
    for(j = 0; j <= ps; j++) cout << " ";
    cout << P[i] << endl;
    ps += P[i].length();
    if(ps > maxps) maxps = ps;
  }

  // optymalizujemy SCS
  S[0].erase(maxps, S[0].length()-maxps);
  cout << "       " << S[0] << endl << endl;
  return 0;
}

Basic

' Wyszukiwanie najkrótszego nadłańcucha
' Data: 22.07.2008
' (C)2020 mgr Jerzy Wałaszek
'--------------------------------------

Dim As String S(7), P(7)
Dim As Integer i, j, maxps, ps, sp, ss, k, ii

' generujemy zbiór S
Randomize
For i = 0 To 7
  k = 3+Cint(Rnd*7)
  S(i) = ""
  For j = 1 To k
    S(i) += Chr(65+Cint(Rnd))
  Next
  Print Using "S[#] = ";i;
  Print S(i)
  P(i) = S(i)
Next

' wyznaczamy SCS
For k = 8 To 2 Step -1
  maxps = -1
  For i = 0 To k-1
    For j = 0 To k-1
      If i <> j Then
        ii = Len(S(i))-Len(S(j))+1
        If ii < 1 Then ii = 1
        ps = 0
        S(i) += "@" ' wartownik1
        S(j) += "#" ' wartownik2
        While Mid(S(i), ii, 1) <> "@"
          While Mid(S(i), ii+ps, 1) = Mid(S(j), ps+1, 1)
            ps += 1
          Wend
          If Mid(S(i), ii+ps, 1) = "@" Then Exit While
          ps = 0: ii += 1
        Wend
        S(i) = Left(S(i), Len(S(i))-1)
        S(j) = Left(S(j), Len(S(j))-1)
        If ps > maxps Then
          maxps = ps: sp = j: ss = i
        End If
      End If
    Next
  Next 
  S(ss) += Mid(S(sp), maxps+1, Len(S(sp))-maxps)
  S(sp) = S(k-1)
Next

Print

' wypisujemy łańcuchy odpowiednio przesunięte
' zapamiętujemy również maksymalną ostatnią pozycję
maxps = 0
For i = 0 To 7
  Print Using "S[#] =";i;
  ps = Instr(S(0), P(i))
  For j = 1 To ps
    Print " ";
  Next
  Print P(i)
  ps += Len(P(i))-1
  If ps > maxps Then maxps = ps
Next

' optymalizujemy SCS
S(0) = Left(S(0), maxps)
Print "       ";S(0)
Print
End

Python (dodatek)

# Wyszukiwanie najkrótszego nadłańcucha
# Data: 19.03.2024
# (C)2024 mgr Jerzy Wałaszek
#--------------------------------------

import random

# tworzymy tablice łańcuchów
s = [""] * 8
p = [""] * 8
ss, sp = 0, 0
# generujemy zbiór S
for i in range(8):
    k = random.randrange(3,11)
    for j in range(k):
        s[i] += chr(random.randrange(65, 67))
    print("S[%d] = %s" % (i, s[i]))
    p[i] = str(s[i])
# wyznaczamy SCS
for k in reversed(range(1, 9)):
    maxps = -1
    for i in range(k):
        for j in range(k):
            if i != j:
                ii = len(s[i])-len(s[j])
                if ii < 0: ii = 0
                ps = 0
                s[i] += '@' # wartownik1
                s[j] += '#' # wartownik2
                while s[i][ii] != '@':
                    while s[i][ii+ps] == s[j][ps]:
                        ps += 1
                    if s[i][ii+ps] == '@': break
                    ps = 0
                    ii += 1
                s[i] = s[i][:-1]
                s[j] = s[j][:-1]
                if ps > maxps:
                    maxps, sp, ss = ps, j, i
    s[ss] += s[sp][maxps:]
    s[sp] = s[k-1][:]
print()
# wypisujemy łańcuchy odpowiednio przesunięte
# zapamiętujemy również maksymalną ostatnią pozycję
maxps = 0
for i in range(8):
    print("S[%d] =" % i, end="")
    ps = s[0].find(p[i])
    for j in range(ps+1):
        print(" ", end="")
    print(p[i])
    ps += len(p[i])
    if ps > maxps: maxps = ps
# optymalizujemy SCS
s[0] = s[0][:maxps]
print("      ", s[0])
print()

Wynik:

S[0] = ABAAAAA
S[1] = BAABB
S[2] = AABBABB
S[3] = ABAAA
S[4] = BBBBBBA
S[5] = ABBABAAA
S[6] = AABABABA
S[7] = BABABAB

S[0] =              ABAAAAA
S[1] =      BAABB
S[2] =       AABBABB
S[3] =              ABAAA
S[4] = BBBBBBA
S[5] =           ABBABAAA
S[6] =                   AABABABA
S[7] =                     BABABAB
       BBBBBBAABBABBABAAAAABABABAB

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 najkrótszego wspólnego nadłańcucha

Problem

Rozwiązanie

Algorytm wyszukiwania najkrótszego wspólnego nadłańcucha

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm wyszukiwania najdłuższego sufiksu pasującego do prefiksu w drugim łańcuchu

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy