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

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie najkrótszego wspólnego nadłańcucha

SPIS TREŚCI
Tematy pomocnicze

Problem

Dla danego zbioru łańcuchów znakowych S = {s1, s2, …, sk} należy wyznaczyć najkrótszy łańcuch s, który zawiera wszystkie łańcuchy zbioru S.

Rozwiązanie

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 s1, s2 …, sk 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 w sumie 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 = {s1, s2, …, sk} dwóch łańcuchów sisj, 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.

obrazek

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.

Zmienne pomocnicze:

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

Lista kroków:

K01: maxps ← -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 psmaxps,
       to następny obieg pętli K05
K09:   maxpsps ; zapamiętujemy długość prefiksu i sufiksu
K10:   spj ; zapamiętujemy indeks łańcucha z prefiksem
K11: ssi ; oraz indeks łańcucha z sufiksem
K12: Element S[ss] zastąp ; wyznaczone łańcuchy łączymy sufiksem
     złączeniem s-p S[ss] i S[sp] ; i prefiksem
K13: Element S[sp] 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:

s1, s2 : niepuste łańcuchy znakowe. W łańcuchu s1 szukamy sufiksu pasującego do prefiksu łańcucha s2.

Wyjście:

Maksymalna długość sufiksu łańcucha s1 pasującego do prefiksu łańcucha s2.

Zmienne pomocnicze:

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

Lista kroków:

K01: ii ← |s1|-|s2| ; ustawiamy indeks pierwszego znaku sufiksu
K02: Jeśli ii < 0,
     to ii ← 0
K03: ps ← 0 ; indeks pierwszego znaku prefiksu
K04: s1s1+wartownik1 ; na końcu łańcuchów dodajemy wartowników
K05: s2s2+wartownik2 ; chroniących przed wyjściem poza łańcuch
K06: Dopóki s1[ii] ≠ wartownik1: ; szukamy sufiksu s1
     wykonuj kroki K07…K10 ; zgodnego z prefiksem s2
K07:   Dopóki s1[ii+ps] = s2[ps]: ; porównujemy znaki
       wykonuj psps+1 ; aż do napotkania niezgodności
K08:   Jeśli s1[ii+ps] = wartownik1, ; 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:   iiii+1
K11: Usuń wartowników z s1 i s2 ; 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[ss] ← S[ss] + S[sp][maxps:|S[sp]|]

I na koniec pozostała nam operacja usunięcia elementu S[ss]. 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[ss] 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 = []
P = []
for i in range(8):
    S.append("")
    P.append("")

# generujemy zbiór S

for i in range(8):
    k = 3 + random.randrange(8)
    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

Wyszukiwanie najkrótszego wspólnego nadłańcucha
(C)2020 mgr Jerzy Wałaszek


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
©2024 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.