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


Tematy pokrewne
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie
Podstawowe operacje na tablicach
Wyszukiwanie max lub min

 

Problem

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


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ł.

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ł:

 

128 zł = 100 zł + 20 zł + 18 zł reszty
128 zł = 100 zł + 20 zł + 10 zł + 8 zł reszty
128 zł = 100 zł + 20 zł + 10 zł + 5 zł + 3 zł reszty
128 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 si i sj, ij, 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
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, to zakończ z wynikiem S[0] ; zwracamy SCS
K04: Dla i = 0,1,...,k - 1: wykonuj K05...K11 ; wyznaczamy najdłuższy prefiks i sufiks
K05:     Dla j = 0,1,...,k - 1: wykonuj 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 psmaxps, to następny obieg pętli K05  
K09:         maxpsps ; zapamiętujemy długość prefiksu i sufiksu
K10:         sp  ← j ; zapamiętujemy indeks łańcucha z prefiksem
K11:         ssi ; oraz indeks łańcucha z sufiksem
K12: Element S[ss] zastąp złączeniem s-p S[ss] i S[sp] ; wyznaczone łańcuchy łączymy sufiksem i prefiksem
K13: Element S[sp] usuń z S  
K14: Idź do 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.

Elementy pomocnicze:
ii    indeks w 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 wykonuj K07...K10    ; szukamy sufiksu s1 zgodnego z prefiksem s2
K07:     Dopóki s1[ii + ps] = s2[ps], wykonuj psps + 1 ; porównujemy znaki aż do napotkania niezgodności
K08:     Jeśli s1[ii + ps] = wartownik1, to idź do K11 ; sprawdzamy, czy mamy 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 s1 i s2
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[sp]. 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[sp] 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.

 

Program

Ważne:

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.

 

Lazarus
// Wyszukiwanie najkrótszego nadłańcucha
// Data: 22.07.2008
// (C)2012 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.
Code::Blocks
// Wyszukiwanie najkrótszego nadłańcucha
// Data: 22.07.2008
// (C)2012 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;
}
Free Basic
' Wyszukiwanie najkrótszego nadłańcucha
' Data: 22.07.2008
' (C)2012 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)2012 mgr Jerzy Wałaszek


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.