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

SPIS TREŚCI
Tematy pomocnicze

Problem

Dla danego zbioru łańcuchów znakowych S = {s 1, s 2, ..., s k} 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 s 1, s 2, ..., 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ł.

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 = {s 1, s 2, ..., 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.

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, 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,
to zakończ z wynikiem S [ 0 ]
zwracamy SCS
K04: Dla i  = 0, 1, ..., k  - 1:
wykonuj kroki K05...K11
wyznaczamy najdłuższy prefiks i sufiks
K05:     Dla j  = 0, 1, ..., k  - 1:
    wykonuj kroki K06...K11
 
K06:         Jeśli i  = j,
        to następny obieg pętli K05
łańcuchy muszą być różne
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
złączeniem s-p S [ s s  ] i S [ s p  ]
wyznaczone łańcuchy łączymy sufiksem 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 1, s 2 – niepuste łańcuchy znakowe. W łańcuchu s 1 szukamy sufiksu pasującego do prefiksu łańcucha s 2.

Wyjście:

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

Zmienne pomocnicze:

ii  –  indeks w s 1, ii  ∈ N
ps  – długość prtefiksu-sufiksu, ps  ∈ N

Lista kroków:

K01: ii  ← | s 1 | - | s 2 | ustawiamy indeks pierwszego znaku sufiksu
K02: Jeśli ii  < 0,
to ii  ← 0
 
K03: ps  ← 0 indeks pierwszego znaku prefiksu
K04: s 1s 1 + wartownik 1 na końcu łańcuchów dodajemy wartowników
K05: s 2s 2 + wartownik 2 chroniących przed wyjściem poza łańcuch
K06: Dopóki s 1 [ ii  ] ≠ wartownik 1,
wykonuj kroki K07...K10
szukamy sufiksu s 1 zgodnego z prefiksem s 2
K07:     Dopóki s 1 [ ii + ps  ] = s 2 [ ps  ],
    wykonuj ps  ← ps  + 1
porównujemy znaki aż do napotkania niezgodności
K08:     Jeśli s 1 [ ii  + ps  ] = wartownik 1,
    to idź do kroku K11
sprawdzamy, czy mamy 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 1 i s 2 przywracamy normalną postać łańcuchów s 1 i s 2
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 p  ]. 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 element S [ s p  ] 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 położenia w nim 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 <time.h>

using namespace std;

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

// generujemy zbiór S

  srand ( ( unsigned )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
Wynik:
S [ 0 ] = ABA
S [ 1 ] = BBBBB
S [ 2 ] = BBAA
S [ 3 ] = ABBABBAAB
S [ 4 ] = BAABBA
S [ 5 ] = ABABBBB
S [ 6 ] = BBBAAABAA
S [ 7 ] = ABBAABB

S [ 0 ] = ABA
S [ 1 ] =    BBBBB
S [ 2 ] =       BBAA
S [ 3 ] =              ABBABBAAB
S [ 4 ] =            BAABBA
S [ 5 ] = ABABBBB
S [ 6 ] =      BBBAAABAA
S [ 7 ] =                 ABBAABB
          ABABBBBBAAABAABBABBAABB
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
©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.