Zaawansowane algorytmy i struktury danych/Wykład 1

Zaawansowane algorytmy tekstowe I

Tekst jest ciągiem symboli, przyjmujemy żejest 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.

Postawowym 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 jegopełna analiza (złożoność, preprocessing) jest zawansowana.

Algorytm Boyera-Moore'a

Algorytm przykłada x do tesktu 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 algorytmuKMP, 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 łatwejanalizy algorytmu KMP w tym przypadku analiza jest skomplikowana. Mamy tu przykład algorytmu, któregopoprawność jest dosyć oczywista, a analiza kosztu jest nietrywialna.

\begin{figure}%[htb]\begin{center}\includegraphics[width=12.3cm]{teksty_fig11.eps}\caption{ Historia algorytmu {BM} na przykładowych tekstach x, y.}

\end{center}\end{figure}Jeśli zastąpimy tablicę $BMShift$ przez $BMShif{t}^{\prime }$ wówczas czas algorytmu BM staje się kwadratowy. Przykłademtekstó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.\begin{figure}%[htb]\begin{center}\includegraphics[width=13.3cm]{teksty_fig12.eps}\caption{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ącytablicę BM (rysunek prawej strony).} \end{center}\end{figure}

TXT

Różnica między $BMShift$ i $BMShif{t}^{\prime }$ wydaje się być podobna do tej między silnymiprefisko-sufiksami i prefikso-sufiksami w algorytmie KMP. W obu przypadkach różnica sprowadza się dowykorzystania jednego bitu informacji, niezgodności dwóch symboli. Podczas gdy nie robi to istotnej różnicy wpesymistycznej złożoności algorytmu KMP, w tym przypadku jest to znacząca różnica między czasemkwadratowym i liniowym. Porównajmy działanie algorytmu z przesunięciem $BMShif{t}^{\prime }$ i of $BMShift$ na tekstach(patrz rysunek)\\\centerline{ $x=cababababa$ oraz $y=aaaaaaaaaababababa$.}Okresem tekstu $x$ jest każda liczba naturalna niezerowa $p$ taka, że $x[i]=x[i+p]$, dla każdego i dlaktórego obie strony są zdefiniowane. Przez period(x) oznaczmy minimalny okres x. Okres jest {\em pełny} gdyjest dzielnikiem $|x|$. Jeśli $period(x)$ jest własciwym (mniejszym od $|x|$) dzielnikeim $x$ to x nazywamy rozkładalnym, wprzeciwnym przypadku x nazywamy słowem {\em pierwotnym} (albo nierozkładalnym). Na przykład $ababab$ jest rozkładalne, natomiast $abababa$ jest pierwotne.\myskip %Lemat\(Kombinatoryczna własność słów pierwotnych) Jeśli $x$ jest pierwotne to x nie ma wystąpienia wewnątrz xx. \myskip\begin{figure}[bh]\begin{center}\includegraphics[width=6cm]{teksty_fig13.eps}\caption{Jeśli tekst x jest pierwotny to taka sytuacja jest niemozliwa (x nie może wystepowac wewnatrz tekstuxx.) } \end{center}\end{figure}\myskip Własność ta {\em mówi}, że nie może zajść sytuacja przedstawiona na Rysunku #pierwotne.Dowód własności korzysta z tzw. {\em 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. \myskip Popatrzmy na rysunek, gdyby x wystepowal w xx to xxmiałby dwa okresy p,q, takie, że $p+q\le |xx|$, z lematu o okresowości wynika wtedy, że xx ma okres mniejszyof $|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. Dokładne oszacowanie na liczbę porównań w algorytmie BM wynosi około 3n. Dowód tego faktu jest jednakzbyt skomplikowany. Pokażemy tutaj oszacowanie górne 4n oraz dolne 3n. Zaczniemy od prostszego oszacowaniadolnego. Zastosujmy algorytm BM do tekstów: $y=(b{a}^{k}b{a}^k{)}^k$, gdzie usuwamy ostatni symbol,oraz $x=b{a}^{k-1}b{a}^{k-1}$. \noindentPozostawimay jako ćwiczenie sprawdzenie tego, że dla tych danych liczba porównań symboli wynosi wprzybliżeniu $3n$, gdzie $n=(2k+2)*k-1$ jest długością $y$.\myskipPrzejdziemy teraz do górnego oszacowania $4n$. \myskipJeśli się głębiej zastanowić to liniowy czasalgorytmu BM jest zdumiewający, algorytm zapomina jaka część tekstu y pasowała do wzorca x, i sprawdzawielokrotnie te same fragmenty które już poprzednio były sprawdzone z wynikem pozytywnym. Zjawisko takie niema miejsca w algorytmie KMP, gdzie raz sprawdzony pozytywnie symbol w tekście y nie jest już nigdy więcejsprawdzany. \begin{figure}%[htb]\begin{center}\includegraphics[width=15cm]{teksty_fig14.eps}\caption{Segment $y[i+j-1..i+m]$ tekstu y jest aktualnym dopasowaniem, $v$ oznacza najkrótszy pełny okressufiksu 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). } \end{center}\end{figure} Załóżmy, że w danej nieterminalnej iteracji algorytm BM sprawdza segment $y[i+j-1..i+m]$ tekstu y, anstępnie wykonuje przesunięcie$s=BMShift[j]$, gdzie $j>0$ oraz$s>(m-j)/3$. Przez \textit{aktualne dopasowanie} rozumiemy aktualnie sprawdzany segment tekstu y bez pozycji, na którejwystępuje niezgodność symboli, (patrz Rysunek #figure3-4). Niech $k$ będzie najmniejszym pełnym okresem tekstu $x[m-s+1..m]$, a $v$ niech będzie słowemodpowiadającym temu okresowi. Inaczej mówiąc zakładamy, że mamy taką sytuację jak naRysunku #figure3-4). Zauważmy, że rozważamy tu okresowość w dwóch aspektach: jako liczbę(długość) oraz jako słowo. \noindent Zdefiniujmy własność pierwszego odwiedzenia: \begin{quotation}\noindent$(*)$: \ pozycje w segmencie $y[i+j+k..i+m-2.k]$ nie były sprawdzane w poprzednich iteracjach.\end{quotation}\myskipUdowodnimy następujący silny i całkowicie nietrywialny fakt. \noindent Lemat}.\ Własność {\em pierwszego odwiedzenia zachodzi w każdej nieterminalnejiteracji algorytmu BM. \noindent 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$ jestsufiksem wzorca.\myskipWprowadzimy kluczowe pojęcie {\em 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|$.\myskipMówimy, że poprzednie dopasowane kończyło się na pozycji $q$ w tekście $y$, jeśli wpewnej poprzedniej iteracji koniec wzorca był przyłożony do pozycji $q$ w $y$.\paragraph{Własność 1} żadne poprzednie dopasowanie nie kończy się na pozycji krytycznej w aktualnym dopasowaniu. \noindent Dowód własności 1}.\ Dowód ma charakter {\em filozoficzny: gdyby własność 1 dla pewnejiteracji nie zachodziła to by tej iteracji nie było. Gdyby poprzednia iteracja kończyła się na pozycjikrytycznej to następnym końcem dopasowania byłaby pozycja $i+m+s$. W ten sposób byśmy przeskoczyliaktualną iterację. Zatem własność 1 zawsze zachodzi.\paragraph{Własność 2} Wielkość wspólnej częśc aktualnego dopasowania idanego poprzedniego dopasowania jest mniejsza od $k$. \myskip 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ławiększa niż $k$ to słowo pierwotne $v$ występowałoby wewnątrz słowa $vv$, co zaprzecza własności słówpierwotnych. Zatem musi zachodzić własność 2.\noindent \paragraph{Własność 3.}\ Jeśli poprzednie dopasowanie kończy się na pozycji $q$ wewnątrzaktualnego dopasowania i zawiera się całkowicie w aktualnym dopasowaniu. Wtedy nie ma krytycznej pozycji naprawo od $q$.\myskipDowó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 najmniejszeprzesunię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 pozycjipoprzednich dopasowań z których każda jest mniejsza od $r$. Wszystkie te liczby są różnymi liczbaminaturalnymi, w pewnym momencie jedna z nich musi być równa $r$. W tym momencie mamy poprzednie dopasowaniekończące się na pozycji krytycznej $r$. Przeczy to własności 2. Zatem własnośc 3 musi zachodzić.\paragraphDowód własności pierwszego odwiedzenia.\Trzy własności przed chwilą udowdnione wystarczją do tego, żeby uzasadnienie własności pierwszego odwiedzeniabyło proste. Dowód jest przez zaprzeczenie. Przypuśćmy, że w pewnej poprzedniejiteracji odwiedziliśmy {\em zabroniony} obszar aktualnego dopasowania (zacienioną częśćtekstu y na Rysunku #figure3-4). Niech$q$ będzie końcem tego poprzedniego dopasowania. Zatem $q$ nie jest pozycją krytyczną, na prawo od niej jestpewna pozycja krytyczna. Jest to sprzeczne z własnością 3.Kończy to dowód własności pierwszego odwiedzenia.\myskipMożemy teraz przystąpić do ostatecznej analizy algorytmu BM. \begin{theorem} \\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 rozmiarualfabetu.\end{theorem} \noindentZ własności {\em pierwszego odwiedzenia} wynika bezpośrednio: jeśli $s$ jest przesunięciem w nieterminalnej iteracji, to co najwyżej $3.s$ pozycji tekstu y sprawdzanych wtej iteracji było sprawdzane w poprzednich iteracjach. \myskip Koszt każdej nieterminalnej iteracji możnarozdzielić 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 terminalejiteracji. Zatem w sumie liczba porównań jest ograniczona przez:$n+3(n-m)+m\le 4.n.$

\subsection*{Tablica Prefisko-Prefiksów}W fazie {\em preprocessing}u algorytmu BM (obliczanie tablicy $BMShift$) potrzebny będzie algorym liczeniatablicy 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:

\begin{center}$PREF[i]=\max \{j:x[i..i+j-1]$ jest prefiksem $x$ \}.\end{center}\myskip 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. przeskalowanym $j$ względem s) jest małe, patrz rysunek. Przedstawimy niezależny interesujący algorytm liczenia tablicy $PREF$. W algorytmie liczymy tablicę PREFprzeglądając tekst od lewej do prawej. Załóżmy, że przetwarzamy pozycję $j$-tą (gdzie $j>1$), wtedyzachodzi następujący niezmiennik (patrz Rysunek #pref):\begin{quotation}\noindentwartości $PREF[t]$ dla $t<j$ są już policzone\\$s<j$ jest pozycją maksymalizującą $s+PREF[s]-1$.\end{quotation}\noindent 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)$: \begin{center}$\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]\}$.\end{center}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. \begin{figure}%[hb]\begin{center}\includegraphics[width=15.5cm]{teksty_fig2.eps}\caption{Typowa sytuacja w algorytmie Prefikso-Prefiksy. Liczymy PREF dla nowej pozycji $j$, zakladając, żeznamy wartości tablicy PREF dla pozycji wczesniejszych. } \end{center}\end{figure}\myskip\begin{center}\begin{minipage}{12cm}\vskip0.3cm \hspace*{0.6cm}\textbf{Algorytm} $\text{<mrow data-mjx-texclass="ORD">Prefikso<mo stretchy="false">−</mo>Prefiksy</mrow>}$;\vskip 0.1cm \noindent\hspace*{1.2cm}$PREF[1]:=0$; $s:=1$;\vskip 0.1cm \noindent \hspace*{1.2cm}\textbf{for} $j:=2$ \textbf{to} $m$\textbf{do}\vskip 0.1cm \noindent \hspace*{1.8cm}$k:=j-s+1$;\ $r:=s+PREF[s]-1$;\vskip 0.1cm \noindent\hspace*{1.8cm}\textbf{if} $r<j$ \textbf{then }\\\hspace*{2.4cm}$PREF[j]:=\text{<mrow data-mjx-texclass="ORD">Naive<mo stretchy="false">−</mo>Scan</mrow>}(j,1)$;\\\hspace*{2.4cm} \textbf{if} $PREF[j]>0$ \textbf{then} $s$ :=$j$; \\\hspace*{1.8cm}\textbf{else if} $PREF[k]+k<PREF[s]$ \textbf{then}\\\hspace*{2.4cm}$PREF[j]:=PREF[k]$\\\hspace*{1.8cm}\textbf{else}\\\hspace*{2.4cm}$x:=\text{<mrow data-mjx-texclass="ORD">Naive<mo stretchy="false">−</mo>Scan</mrow>}(r+1,r-j+2)$;\\\hspace*{2.4cm}$PREF[j]:=r-j+1+x$;\ $s:=j$;\\\vskip0.4cm\end{minipage}\end{center}\myskipNajważ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$ jestwartością $j$ przeskalowaną względem $s$). Pokażemy że czas konstrukcji tablcy $BMShift$ jest liniowy, podstawową częścią będzieobliczanie 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$. \begin{center}\begin{minipage}{10cm}\vskip0.3cm\hspace*{0.6cm}\textbf{Algorytm} Sufikso-sufiksy;\\\hspace*{1.2cm}$x^R$:=odwrócony wzorzec $x$;\\\hspace*{1.2cm}oblicz tablicę $PREF$ dla tekstu $x^R$;\\\hspace*{1.2cm}\textbf{for each {$i$} do}\ \ $S[i]:=PREF[m-i+1]$;\\\vskip0.4cm\end{minipage}\end{center}\myskip\begin{figure}%[htb]\begin{center}\includegraphics[width=15cm]{teksty_fig9.eps}\caption{Przypadek gdy $BMShift[j]<j$. Dla $j=22$, oraz przykładowgo 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$. } \end{center}\end{figure} \myskip Obserwacja.\ Jeśli $BMShift[j]=m-k<j$, to $S[k]=m-j$. \myskip Przykład.\ Dla $j=22$ iprzykładowego wzorca x na Rysunku #BM-shifts mamy: $BMShift[j]=3$, oraz $S[25-3]=m-j=3$. \myskip Korzystając z powyższej obserwacji przesunięcia w algorytmie BMobliczane są następująco. Inicjalizujemy $BMShift[j]:=m$ dla każdego $j$. \myskip\begin{center}\begin{minipage}{8cm}\vskip0.3cm\hspace*{0.6cm}\textbf{Algorytm} Oblicz-BMShift;\\\hspace*{1.2cm}\textbf{for} $k:=1$ \textbf{to} $n-1$ \textbf{do }\\\hspace*{1.8cm}$j:=m-S[k]$; $BMShift[j]:=m-k$;\\\vskip0.4cm\end{minipage}\end{center}\myskipDla przypadku, gdy $BMShift[j]>j$ po wykonaniu powyższego algorytmu,otrzymane wartości nie muszą być poprawne. W tym przypadku heurystykaniezgodnoś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 sufiksemcałego wzorca, oraz $k<m-j$, wtedy przyjmujemy $BMShift[j]=m-k.$