Zaawansowane algorytmy i struktury danych/Wykład 1

Zaawansowane algorytmy tekstowe I

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]$ wteś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 teraz 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 Parser nie mógł rozpoznać (nieznana funkcja „\y”): {\displaystyle 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]$ do$j:=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]\ne y[i+j]$.

Korzystając z niezmiennika liczymy większe przesunięcie 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 wtekś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\le m\Rightarrow s>k$ lub $x[k-s]=x[k]$,

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

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 pozycji$j<m$.

$BMShif{t}^{\prime }[j]=\min \{s>0:warunek1(j,s)\},$

$BMShift[j]=\min \{s>0:warunek1(j,s)\text{<mrow data-mjx-texclass="ORD">oraz</mrow>}warunek2(j,s)\}$.

Definiujemy również

$BMShif{t}^{\prime }[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]$ do$j:=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 łatwe janalizy algorytmu KMP w tym przypadku analiza jest skomplikowana. Mamy tu przykład algorytmu, którego poprawność jest dosyć oczywista, a analiza kosztu jest nietrywialna.

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

Rysunek 3: Działanie dwóch wersji algorytmu BM na przykładowych tekstach. Algorytm BM stosujący przesunięcie $BMShif{t}^{\prime }$ 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 $BMShif{t}^{\prime }$ wówczas czas algorytmu BM staje się kwadratowy. Przykładem tekstów dla których osiągana jest wtedy złożoność kwadratowa są teksty:

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

Pozostawiamy jako ćwiczenie podanie wzoru na liczbę porównań z tablicą $BMShif{t}^{\prime }$ dla tych tekstów.

Różnica między $BMShift$ i $BMShif{t}^{\prime }$ wydaje się być podobna do tej między silnymi prefisko-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 $BMShif{t}^{\prime }$ i of $BMShift$ na tekstach(patrz rysunek)

$x=cababababa$ oraz $y=aaaaaaaaaababababa$.

Pewna własność kombinatoryczna tekstów

Okresem tekstu $x$ jest każda liczba naturalna niezerowa $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|$) dzielnikeim $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.

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 kresowoś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 y pasowała do wzorca x, i sprawdza wielokrotnie te same fragmenty które już poprzednio były sprawdzone z wynikiem pozytywnym. Zjawisko takie niema miejsca w algorytmie KMP, gdzie raz sprawdzony pozytywnie symbol w tekście y nie jest już nigdy więcej sprawdzany.

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 nstępnie wykonuje przesunięcie$s=BMShift[j]$, gdzie $j>0$ oraz$s>(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 by tej iteracji nie było. Gdyby poprzednia iteracja kończyła się na pozycji krytycznej to następnym końcem dopasowania byłaby pozycja $i+m+s$. W ten sposób byśmy przeskoczyli 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 1wynika, ż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. Wtedy nie ma krytycznej pozycji naprawo 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 warunek1 i warunek2 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 wystarczją 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 Rysunku5). Niech$q$ 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 znalezieniapierwszego 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żej$3.(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\le 4.n.$

Tablica Prefikso-Prefiksów

W fazie preprocessingu algorytmu BM (obliczanie tablicy $BMShift$) potrzebny będzie algorym liczenia tablicy prefikso-prefiksów. Modyfikacją tablicy prefikso-sufiksów jest tablica prefikso-prefiksów: $PREF[i]$jest długośćią 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$ \}.
Rysunek 6: Typowa sytuacja w algorytmie Prefikso-Prefiksy. 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$, co już potrafimy.

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$), wtedy zachodzi 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 $\text{<mrow data-mjx-texclass="ORD">Naive<mo stretchy="false">−</mo>Scan</mrow>}(p,q)$:

$\text{<mrow data-mjx-texclass="ORD">Naive<mo stretchy="false">−</mo>Scan</mrow>}(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 $\text{<mrow data-mjx-texclass="ORD">Naive<mo stretchy="false">−</mo>Scan</mrow>}(p,q)=0$. Wartość PREF[1] nie jest dla nas interesująca.

Algorytm Prefikso-Prefiksy

---

$PREF[1]:=0$; $s:=1$;
for $j:=2$ to $m$do
   $k:=j-s+1$; $r:=s+PREF[s]-1$;
   if $r<j$ then
      $PREF[j]:=\text{<mrow data-mjx-texclass="ORD">Naive<mo stretchy="false">−</mo>Scan</mrow>}(j,1)$;
      if $PREF[j]>0$ then $s:=j$;
   else if $PREF[k]+k<PREF[s]$ then
      $PREF[j]:=PREF[k]$
   else
      $x:=\text{<mrow data-mjx-texclass="ORD">Naive<mo stretchy="false">−</mo>Scan</mrow>}(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śniejpoliczonych 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 pozycji$j$. 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]$;

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

Korzystając 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 wtedy, że $j>1$, niech $k$ będzie długością maksymalnego prefiksu wzorca, który jest sufiksem całego wzorca, oraz $k<m-j$, wtedy przyjmujemy $BMShift[j]=m-k.$