Zaawansowane algorytmy i struktury danych/Wykład 1

From Studia Informatyczne

Zaawansowane algorytmy tekstowe I


Spis treści


Algorytmy tekstowe są istotne w wielu dziedzinach informatyki, jak na przykład w edytorach tekstowych lub wyszukiwarkach. Tekst jest naturalnym typem informacji.

Formalnie tekst jest ciągiem symboli. Przyjmujemy, że jest on zadany tablicą x[1..k], elementami której są symbole. Liczba k=|x| jest długością (rozmiarem) tekstu. W większości naszych algorytmów jedyne operacje dopuszczalne na symbolach wejściowych to porównania dwóch symboli.

Podstawowym problemem tekstowem jest problem string matchingu, polegający na szukaniu wzorca x=x[1..m] w tekście y=y[1..n]. Elementami tablic są symbole. Na kursie z ASD przerabialiśmy algorytm Knutha-Morrisa-Pratt(w skrócie KMP) i jego wariacje. Zaprezentujemy bardziej zaawansowany algorytm dla tego problemu: algorytm Boyera-Moore'a (w skrócie BM). Pomimo tego, że jest jasne jak ten algorytm działa, to jednak jego pełna analiza (złożoność, preprocessing) jest zawansowana.

Algorytm Boyera-Moore'a

Algorytm przykłada x do tekstu y startując od pozycji i-tej w y. Sprawdzamy, czy x[1..m]\ =\y[i+1..i+m]. Pozycja i wędruje ze strony lewej do prawej. Jednakże, w przeciwieństwie do algorytmu KMP, równość x[1..m]\ =\ y[i+1..i+m] sprawdzamy od strony prawej do lewej. Zaczniemy od algorytmu naiwnego.

Algorytm Naiwny-BM


i:=0;
'while i<n-m do
   j:=m,br>    while j>0 and x[j]=y[i+j] doj:=j-1
   if j=0 then return true;
   {zachodzi niezmiennik(i,j)} i:=i+1
return false;

Jeśli zachodzi równość, to stwierdzamy, że znaleźliśmy wystąpienie x i kończymy. W przeciwnym razie mamy niezmiennik:

niezmiennik(i,j): \ x[j+1.. m]=y[i+j+1.. i+m] oraz x[j]\neq y[i+j].

Korzystając z niezmiennika liczymy przesunięcie większe niż 1. Przesunięcie s jest bezpieczne, gdy jesteśmy pewni, że w każdej sytuacji pomiędzy i oraz i+s nie zaczyna się żadne wystąpienie wzorca x w tekście y. Przypuśćmy, że x zaczyna od pozycji i+s (zobacz Rysunek 1, gdzie jest przedstawiony przypadek s<j.)

Zachodzi wtedy następujący warunek:

warunek1(j,s): dla każdego k j<k\leq m\ \Rightarrow\ s>k lub x[k-s]=x[k],

warunek2(j,s): s<j\ \Rightarrow\ x[j-s]\neq x[j] { własność niezgodności }.


Grafika:Zasd_1.jpg
Rysunek 1: Przesunięcie w algorytmie BM. Przypadek gdy s=BMShift[j]<j.


Definiujemy dwa rodzaje przesunięć. Każde z nich dotyczy sufiksu wzorca zaczynającego się od pozycjij<m.

BMShift'[j]=\min \{ s>0:\ warunek1(j,s)  \},

BMShift[j] =\min \{ s>0:warunek1(j,s) \textrm{ oraz } warunek2(j,s)  \}.

Definiujemy również

BMShift'[m]=BMShift[m]=m-P[m]=period(x).

Algorytm {BM} jest wersją algorytmu Naiwny-BM, w którym przeunięcie i o jeden zamieniamy na przesunięcie o BMShift[j], zobacz Rysunek 2.


Algorytm BM


i:=0
while i<n-m do
   j:=m;    while j>0 and x[j]=y[i+j] doj:=j-1;
   if j=0 then return true;
   { niezmiennik(i,j) \} i:=i+BMShift[j];
return false;

Udowodnimy potem, że algorytm ten ma złożoność liniową. Jednakże w przeciwieństwie do łatwej analizy algorytmu KMP, w tym przypadku analiza jest skomplikowana. Mamy tu przykład algorytmu, którego poprawność jest dosyć oczywista, a analiza kosztu jest nietrywialna.

Grafika:Zasd_2.jpg
Rysunek 2: Historia algorytmu BM na przykładowych tekstach x, y.


Grafika:Zasd_2.jpg
Rysunek 3: Działanie dwóch wersji algorytmu BM na przykładowych tekstach. Algorytm BM stosujący przesunięcie BMShift' wykonuje 30 porównań symboli więcej (rysunek z lewej strony) niż normalny algorytm BM stosujący tablicę BM (rysunek prawej strony).

Algorytm BM ze słabszą tablicą przesunięć

Jeśli zastąpimy tablicę BMShift przez BMShift', wówczas czas algorytmu BM staje się kwadratowy. Przykładem tekstów, dla których osiągana jest wtedy złożoność kwadratowa są:

x=ca(ba)^{k} \mbox{ oraz } y=a^{2.k+2}(ba)^{k}.

Pozostawiamy jako ćwiczenie podanie wzoru na liczbę porównań z tablicą BMShift' dla tych tekstów.


Różnica między BMShift i BMShift' wydaje się być podobna do tej między silnymi prefikso-sufiksami i prefikso-sufiksami w algorytmie KMP. W obu przypadkach różnica sprowadza się do wykorzystania jednego bitu informacji, niezgodności dwóch symboli. Podczas gdy nie robi to istotnej różnicy w pesymistycznej złożoności algorytmu KMP, w tym przypadku jest to znacząca różnica między czasem kwadratowym i liniowym. Porównajmy działanie algorytmu z przesunięciem BMShift' i of BMShift na tekstach(patrz rysunek)

x\ =\ cababababa oraz y\ =\ aaaaaaaaaababababa.

Pewna własność kombinatoryczna tekstów

Okresem tekstu x jest każda niezerowa liczba naturalna p taka, że x[i]=x[i+p] dla każdego i, dla którego obie strony są zdefiniowane. Przez period(x) oznaczmy minimalny okres x. Okres jest {\em pełny} gdy jest dzielnikiem |x|.

Jeśli period(x) jest własciwym (mniejszym od |x|) dzielnikiem x, to x nazywamy rozkładalnym, w przeciwnym przypadku x nazywamy słowem pierwotnym (albo nierozkładalnym).

Na przykład ababab jest rozkładalne, natomiast abababa jest pierwotne.

Lemat Kombinatoryczna własność słów pierwotnych

Jeśli x jest pierwotne to x nie ma wystąpienia wewnątrz xx.


Grafika:Zasd_4.jpg
Rysunek 4: Jeśli tekst x jest pierwotny, to taka sytuacja jest niemożliwa (x nie może występować wewnątrz tekstu xx.


Własność ta mówi, że nie może zajść sytuacja przedstawiona na Rysunku 4. Dowód własności korzysta z tzw. lematu o okresowości dla tekstów: jeśli x ma okresy p, q oraz p+q\le |x| to nwd(p,q) jest również okresem x.

Popatrzmy na rysunek. Gdyby x występował w xx, to xx miałby dwa okresy p,q takie, że p+q\le |xx|. Z lematu o okresowości wynika wtedy, że xx ma okres mniejszy od |x| i będący dzielnikiem |x|. Zatem słowo x nie byłoby pierwotne, co jest sprzeczne z założeniem. \myskip Jako ćwiczenie pozostawiamy problem sprawdzania w czasie liniowym czy słowo x jest pierwotne.

Analiza złożoności algorytmu BM

Dokładne oszacowanie na liczbę porównań w algorytmie BM wynosi około 3n. Dowód tego faktu jest jednak zbyt skomplikowany. Pokażemy tutaj oszacowanie górne 4n, dolne oszacowanie 3n pozostawiamy jako ćwiczenie.

Jeśli się głębiej zastanowić, to liniowy czas algorytmu BM jest zdumiewający. Algorytm zapomina, jaka część tekstu <mathy</math> pasowała do wzorca x i sprawdza wielokrotnie te same fragmenty, które już poprzednio były sprawdzone z wynikiem pozytywnym. Zjawisko takie nie ma miejsca w algorytmie KMP, gdzie raz sprawdzony pozytywnie symbol w tekście y nie jest już nigdy więcej sprawdzany.


Grafika:Zasd_5.jpg
Rysunek 5: Segment y[i+j-1.. i+m] tekstu y jest aktualnym dopasowaniem, v oznacza najkrótszy pełny okres sufiksu wzorca x, v jest również okresem aktualnego dopasowania. Zaciemniony obszar jest częścią tekstu, która nigdy wcześniej nie była odwiedzana (sprawdzana).


Załóżmy, że w danej nieterminalnej iteracji algorytm BM sprawdza segment y[i+j-1.. i+m] tekstu y, a następnie wykonuje przesunięcie s=BMShift[j], gdzie j>0 orazs>(m-j)/3. Przez aktualne dopasowanie rozumiemy aktualnie sprawdzany segment tekstu y bez pozycji, na której występuje niezgodność symboli (patrz Rysunek 5).

Niech k będzie najmniejszym pełnym okresem tekstu x[m-s+1.. m], a v niech będzie słowem odpowiadającym temu okresowi. Inaczej mówiąc zakładamy, że mamy taką sytuację jak na Rysunku 5. Zauważmy, że rozważamy tu okresowość w dwóch aspektach: jako liczbę (długość) oraz jako słowo.

Zdefiniujmy własność pierwszego odwiedzenia:

  • pozycje w segmencie y[i+j+k.. i+m-2.k] nie były sprawdzane w poprzednich iteracjach.

Udowodnimy następujący silny i całkowicie nietrywialny fakt.

Lemat

Własność pierwszego odwiedzenia zachodzi w każdej nieterminalnej iteracji algorytmu BM.

Dowód będzie polegał na zauważeniu kilku drobniejszych własności. Następująca własność wynika w sposób oczywisty z założeń: v jest słowem-okresem aktualnego dopasowania oraz v jest sufiksem wzorca.

Wprowadzimy kluczowe pojęcie pozycji krytycznej jako pozycji w aktualnym dopasowaniu y[i+j+1..i+m], która jest odległa od końca aktualnego dopasowania o wielokrotność |v| oraz od początku co najmniej o |v|.

Mówimy, że poprzednie dopasowane kończyło się na pozycji q w tekście y, jeśli w pewnej poprzedniej iteracji koniec wzorca był przyłożony do pozycji q w y.

Własność 1 Żadne poprzednie dopasowanie nie kończy się na pozycji krytycznej w aktualnym dopasowaniu.

Dowód własności 1 Dowód ma charakter filozoficzny: gdyby własność 1 dla pewnej iteracji nie zachodziła, to nie byłoby tej iteracji. Gdyby poprzednia iteracja kończyła się na pozycji krytycznej, następnym końcem dopasowania byłaby pozycja i+m+s. W ten sposób przeskoczylibyśmy aktualną iterację. Zatem własność 1 zawsze zachodzi.

Własność 2 Wielkość wspólnej częśc aktualnego dopasowania i danego poprzedniego dopasowania jest mniejsza od k. Dowód własności 2. Z własności 1 wynika, że koniec poprzedniego dopasowania nie kończy się na pozycji krytycznej. Gdyby wspólna część była większa niż k, to słowo pierwotne v występowałoby wewnątrz słowa vv, co zaprzecza własności słów pierwotnych. Zatem musi zachodzić własność 2.

Własność 3 Jeśli poprzednie dopasowanie kończy się na pozycji q wewnątrz aktualnego dopasowania i zawiera się całkowicie w aktualnym dopasowaniu, nie ma krytycznej pozycji na prawo od q.

Dowód własności 3. Przypuśćmy, że jest pewna pozycja krytyczna r na prawo od q. Wówczas r-q jest dobrym kandydatem na przesunięcie w Algorytmie BM. Ponieważ algorytm BM wybiera najmniejsze przesunięcie spośród kandydatów na przesunięcie, spełniających warunek 1. i warunek 2., otrzymamy nową pozycję q1<r jako koniec następnego dopasowania. Wynika stąd, że mamy sekwencję q1<q2<q3<.. końcowych pozycji poprzednich dopasowań, z których każda jest mniejsza od r. Wszystkie te liczby są różnymi liczbami naturalnymi. W pewnym momencie jedna z nich musi być równa r. W tym momencie mamy poprzednie dopasowanie, kończące się na pozycji krytycznej r. Przeczy to własności 2. Zatem własność 3 musi zachodzić.

Dowód własności pierwszego odwiedzenia. Trzy własności, przed chwilą udowodnione, wystarczają do tego, żeby uzasadnienie własności pierwszego odwiedzenia było proste. Dowód jest przez zaprzeczenie. Przypuśćmy, że w pewnej poprzedniej iteracji odwiedziliśmy "zabroniony" obszar aktualnego dopasowania (zacienioną część tekstu y na Rysunku 5). Niechq będzie końcem tego poprzedniego dopasowania. Zatem q nie jest pozycją krytyczną. Na prawo od niej jest pewna pozycja krytyczna. Jest to sprzeczne z własnością 3. Kończy to dowód własności pierwszego odwiedzenia.

Możemy teraz przystąpić do ostatecznej analizy algorytmu BM.

Theorem 3.1 [Analiza algorytmu BM]

Algorytm BM wykonuje co najwyżej 4n porównań symboli do momentu znalezienia pierwszego wystąpienia wzorca lub zakończenia szukania z wynikiem negatywnym. Algorytm działa w czasie O(n), współczynnik kosztu nie zależy od rozmiaru alfabetu.

Z własności pierwszego odwiedzenia wynika bezpośrednio: jeśli s jest przesunięciem w nieterminalnej iteracji, to co najwyżej 3.s pozycji tekstu y sprawdzanych w tej iteracji było sprawdzane w poprzednich iteracjach.

Koszt każdej nieterminalnej iteracji można rozdzielić na dwie części.

(1) Koszt odwiedzenia symboli w tekście y po raz pierwszy, (2) Potrojone przesunięcie.

Sumaryczna liczba porównań symboli typu (1) wynosi co najwyżej n, sumaryczna liczba porównań typu (2)wynosi co najwyżej3.(n-m), ponieważ suma przesunięć nie przekracza n-m. Dodatkowo może dojść m porównań w terminalej iteracji. Zatem w sumie liczba porównań jest ograniczona przez:

n+3(n-m)+m\leq 4.n.


Tablica Prefikso-Prefiksów

W fazie preprocessingu algorytmu BM (obliczanie tablicy BMShift) potrzebny będzie algorym liczenia dodatkowej tablicy PREF tzw. prefikso-prefiksów. Jest ona modyfikacją tablicy prefikso-sufiksów: PREF[i] jest długością najdłuższego prefiksu tekstu x, którego wystąpienie rozpoczyna się na pozycji i. Bardziej formalnie:

PREF[i]=\max \{ j:\ x[i.. i+j-1] jest prefiksem x \}.
Grafika:Zasd_6.jpg
Rysunek 6: Typowa sytuacja w algorytmie Prefikso-Prefiksu. Liczymy PREF dla nowej pozycji j, zakładając, że znamy wartości tablicy PREF dla pozycji wcześniejszych.

Przykład

Dla x\ =\ abababababb mamy:

PREF[1..11]\ =\ [11,\ 0,\ 8,\ 0,\ 6,\ 0,\ 4,\ 0,\ 2,\ 0,\ 0].

Jako ćwiczenie pozostawiamy redukcję problemu liczenia tablicy PREF do liczenia tablicy P (tablica ta była liczona na wykładzie z ASD).

Przedstawimy niezależny interesujący algorytm liczenia tablicy PREF. W algorytmie liczymy tablicę PREF przeglądając tekst od lewej do prawej. Załóżmy, że przetwarzamy pozycję j-tą (gdzie j>1). Zachodzi wtedy następujący niezmiennik (patrz Rysunek 6)

wartości PREF[t] dla t <j są już policzone

s<j jest pozycją maksymalizującą s + PREF[s] - 1.

Dodajemy specjalny znacznik końca tekstu na pozycji m+1 w x. Korzystamy z dodatkowej prostej funkcji \textit{Naive-Scan}(p,q):

\textit{Naive-Scan}(p,q) = \max\{k \ge 1 takie, że x[p .. p+k-1] = x[q .. q+k-1]\}.


Jeśli nie ma takiego k>0 to \textit{Naive-Scan}(p,q)=0. Wartość PREF[1] nie jest dla nas interesująca.


Algorytm Prefikso-Prefiksy


PREF[1]:=0; s:=1;
for j:=2 to mdo
   k:=j-s+1; r:=s+PREF[s]-1;
   if r<j then
      PREF[j]:=\textit{Naive-Scan}(j,1);
      if PREF[j]>0 then s :=j;
   else if PREF[k]+k<PREF[s] then
      PREF[j]:=PREF[k]
   else
      x:=\textit{Naive-Scan}(r+1,r-j+2);
      PREF[j]:=r-j+1+x;s:=j;


Najważniejszą częścią algorytmu jest przekopiowywanie, w pewnych sytuacjach, wartości PREF[k] wcześniej policzonych na PREF[j]. Dzieje się to wtedy, gdy Pref[s] jest duże i PREF[j-s+1] jest małe (j-s+1 jest wartością j przeskalowaną względem s).

Obliczanie tablicy BMShift

Pokażemy, że czas konstrukcji tablicy BMShift jest liniowy, podstawową częścią będzie obliczanie tablicy PREF. Używając algorytmu liczenia PREF, obliczamy w czasie liniowym symetryczną tablicę S sufisko-sufiksów: S[j] jest długością maksymalnego sufiksu tekstu x, który kończy się na pozycjij. Tablica S odpowiada tablicy PREF obliczonej dla odwróconego wzorca x^R.

Algorytm Sufikso-sufiksy


x^R:= odwrócony wzorzec x;

oblicz tablicę PREF dla tekstu x^R;

for each {i} do S[i]:= PREF[m-i+1];


Grafika:Zasd_7.jpg
Rysunek 7: Przypadek gdy BMShift[j] < j. Dla j=22, oraz przykładowego tekstu rozmiaru m=25, mamy BMShift[22]\ =\ \min\{m-k\ :\ j=m-S[k]=22\}. Otrzymujemy m-S[k]=22, zatem S[k]=3. Dla k=9,\ 14,\ 22,mamy S[9]=S[14]=S[22]=3, zatem BMShift[22] = m-22 = 25-22 = 3.


Obserwacja. Jeśli BMShift[j] = m-k < j, to S[k]=m-j.


Przykład

Dla j=22 i przykładowego wzorca x na Rysunku 7 mamy:

BMShift[j]=3, oraz S[25-3]=m-j=3.


Gdy korzystamy z powyższej obserwacji, przesunięcia w algorytmie BM obliczane są następująco. Inicjalizujemy BMShift[j] := m dla każdego j.


Algorytm Oblicz-BMShift


for k:=1 to n-1 do
   j := m-S[k]; BMShift[j] := m-k


Dla przypadku, gdy BMShift[j] > j po wykonaniu powyższego algorytmu, otrzymane wartości nie muszą być poprawne. W tym przypadku heurystyka niezgodności na jednej pozycji jest ignorowana i sprowadzamy obliczenie do prefikso-sufiksów całego wzorca x. Załóżmy, że j>1, niech k będzie długością maksymalnego prefiksu wzorca, który jest sufiksem całego wzorca, oraz k<m-j. Przyjmujemy wtedy BMShift[j]= m-k.