Algorytmy i struktury danych/Algorytmy tekstowe I

\noindent {\Large \bf ASD-Moduł.\ Algorytmy tekstowe I} \vskip 0.5cm Tekst jest ciągiem symboli, przyjmujemy że jest on zadany tablicą x[1..n] elementami którejsą symbole ze zbioru A (zwanego alfabetem). Liczba $n=|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. Algorytmy na tekstach wyróżniają się tym, że wykorzystują specyficzne kombinatorycznewłasności 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 per(x) oznaczmyminimalny okres x. Okresowość spełnia następującą ciekawą własność kombinatoryczną. Niech $nwd(p,q)$ oznaczanajmnieszy wspólny dzielnik p,q.\paragraphLemat o okresowości.\\Jeśli x ma okresy p, q oraz $p+q\le |x|$ to $nwd(p,q)$ jest również okresem x. \myskipLematten wynika z poprawności algorytm Euklidesa z odejmowaniem, który liczy nwd(p,q). Zauważmy, żejeśli $p>q$ są okresami to p-q też jest okresem. Dokładny dowód zostawiamy jako ćwiczenie.\myskip Lemat ten można wzmocnić osłabiając założenia. Dowód pozostawiamy jako ćwiczenie.\paragraphSilny lemat o okresowości.\\Jeśli x ma okresy p, q oraz $p+q\le |x|+nwd(p,q)$ to $nwd(p,q)$ jest również okresem x. \myskipPojęciem dualnym do okresu jestprefikso-sufiks tekstu, jest to najdłuższy własciwy (nie będący całym x) prefiks tekstu x będącyjednocześnie sufiksem x. Oczywistym jest, że $|x|-per(x)$ jest długością prefikso-sufiksu x.Jeśli $per(x)=|x|$ to prefikso-sufiksem x jest słowo puste o długości zerowej.\vskip 0.1cm

Oznaczmy przez

$P[k]$

rozmiar prefikso-sufiksu

$x[1..k]$

, zatem

$per(x)=n-P[n]$

, gdzie

$n=|x|$

.\paragraph{Przykład.\\} Dla

$x=abababababb$

mamy:

$P[1..11]=[0,0,1,2,3,4,5,6,7,8,0].$

Wartość

$P[0]$

jest warością sztuczną (przyjmiemy potem

$P[0]=-1$

).\subsection*{Liczenie tablicy Prefisko-Sufiksów}Przedstawimy jeden z możliwych algorytmów liniowych oblicznaia tablicy P, jest to iteracyjna wersja algorytmu rekurencyjnego, który moglibyśmy otrzymac korzystając z faktu:

$x[j]=x[t+1]\text{<mrow data-mjx-texclass="ORD">oraz</mrow>}t=P[j-1]\Rightarrow P[j]=t+1$

W algorytmie do liczenia

$P[j]$

korzystamy z wartości

$P[k]$

dla

$k<j$

. \vskip 0.3cm\hspace*{0.6cm}\textbf{Algorytm} \textit{Pefikso-Sufiksy};\\\hspace*{1.2cm}

$P[0]:=-1$

;

$t:=-1$

;\\\hspace*{1.2cm}\textbf{for}

$j:=1$

\textbf{to}

$m$

\textbf{do}\\\hspace*{1.8cm}\textbf{while}

$t\ge 0$

\textbf{and}

$x[t+1]\ne x[j]$

\textbf{do}

$t:=P[t]$

;\\\hspace*{1.8cm}

$t:=t+1$

;

$P[j]:=t$

;\\\myskip Złożoność liniowa wynika stąd, że w każdej iteracji zwiększamy wartość t co najwyżejo jeden, a wykonanie każdej operacji

$t:=P[t]$

zmniejsza wartość t co najmniej o jeden. Prostezastosowanie zasady magazynu (lub potencjału) implikuje, że operacji

$t:=P[t]$

wykonujemy conajwyżej n. Dowód poprawności pozostawiamy jako ćwiczenie.

\subsection*{Tablica Silnych Prefisko-Sufiksów} Wprowadzimy silną tablicę prefikso-sufisów dla wzorca $x[1..m]$:

jeśli

$j<|x|$

to

$P^{\prime }[j]=k$

, gdzie

$k$

jest maksymalnym rozmiarm słowa będącego prefiksem i sufiksem

$x[1..j]$

najdłuższego własciwegoi spełniającego dodatkowy warunek

$x[k+1]\ne x[j+1]$

dla

$j<n$

. \\Jeśli takiego k nie ma toprzyjmujemy

$P^{\prime }[j]=-1$

. Przyjmujemy ponadto, że

$P^{\prime }[m]=P[m]$

.\myskip Wartości tablicy P' mogą być znacznie mniejsze niż wartości tablicy P. %\paragraph{Przykład} Dla

$x=abaab$

mamy:

$P[0..5]=[-1,0,0,1,1,2];{\P }^{\prime }[0..5]=[-1,0,-1,1,0,2].$

Algorytm bazuje na następującej relacji między P i P':

$(t=P[j]\text{<mrow data-mjx-texclass="ORD">oraz</mrow>}x[t+1]\ne x[j+1])\Rightarrow P^{\prime }[j]=t$$(t=P[j],t\ge 0,\text{<mrow data-mjx-texclass="ORD">oraz</mrow>}x[t+1]=x[j+1])\Rightarrow P^{\prime }[j]=P^{\prime }[t]$

Nie musimy liczyćtablicy P, potrzebna jest jedynie ostatnia wartość

$t=P[j]$

, którą liczymy on-line.\myskip\begin{center}\fbox{\begin{minipage}{9cm}\vskip0.3cm\hspace*{0.6cm}\textbf{Algorytm} Silne-Prefikso-Sufiksy;\\\hspace*{1.2cm}

$P^{\prime }[0]:=-1$

;

$t:=-$

1;\\\hspace*{1.2cm}\textbf{for}

$j:=$

1 \textbf{to}

$m$

\textbf{do }//

$t=P[j-1]$

\\\hspace*{1.8cm}\textbf{while}

$t\ge 0$

\textbf{and}

$x[t+1]\ne x[j]$

\textbf{do}\\ \hspace*{2.5cm}

$t:=P^{\prime }[t]$

;\\\hspace*{1.8cm}

$t:=t+1$

;\\\hspace*{1.8cm}\textbf{if}

$j=m$

\textbf{or}

$x[t+1]\ne x[j+1]$

\\\hspace*{2cm} \textbf{then}

$P^{\prime }[j]:=t$

\\textbf{else}

$P^{\prime }[j]:=P^{\prime }[t]$

;\\\vskip0.4cm\end{minipage}}\end{center}\myskipGdyweżmiemy

$x=ab{a}^{m-2}$

to

$P^{\prime }[0]=-1$

,

$P^{\prime }[1]=0$

,

$P^{\prime }[2]=-1$

,oraz

$P^{\prime }[j]=1$

, dla

$3\le j\le m$

.\ \noindent To jest pesymistyczny przypadek dla algorytmu Silne-Prefikso-Sufiksy, algorytm wykonuje

$3m-5$

porównań symboli.\subsection*{String-matching: algorytm Knutha-Morrisa-Pratta}Przedstawimy klasyczny algorytm Knutha-Morrisa-Pratta (w skrócie KMP) dla problemu {\em string-matching}u:

obliczyćw w tekście $y$ wszystkie (lub pierwsze) wystąpienia danego tekstu $x$, zwanego wzorcem (ang. pattern).\vskip 0.1cm\noindent Oznaczmy $m=|x|,n=|y|$, gdzie $m\le n$.\myskip Operacją {\em dominującą} w algorytmie jest porównanie dwóch symboli.\myskip \noindent Zaczniemy od obliczania jedynie pierwszego wystąpienia. Algorytm KMP przegląda tekst y od lewej doprawej, sprawdzając, czy jest zgodność na pozycji $j+1$ we wzorcu x, oraz na pozycji $i+j+1$ wtekście y. Jeśli jest niezgodność to przesuwamy potencjalny początek (pozycja i) wystąpienia x w y.Zakładamy, że algorytm {\em zwraca} wartość {\em false} gdy nie zwróci wcześniej {\em true}.Pozostawiamy dowód poprawności(określenie niezmienników) jako ćwiczenie.\myskip\begin{center}\fbox{\begin{minipage}{12cm}\vskip0.3cm\hspace*{0.6cm}\textbf{Algorithm} KMP;  %\{ algorithm of Morris and Pratt \}\\\hspace*{1.2cm}$i:=0$; $j:=0$;\\\hspace*{1.2cm}\textbf{while} $i\le n-m$ \textbf{do }\\\hspace*{1.8cm}\textbf{while} $j<m$ \textbf{and} $x[j+1]=y[i+j+1]$ \textbf{do} \$j=j+1$;\\\hspace*{1.8cm}\textbf{if} $j=m$ \textbf{then return}(true);\\\hspace*{1.8cm}$i:=i+j-P^{\prime }[j]$;\ \ $j:=\max (0,P^{\prime }[j])$;\\\vskip0.4cm\end{minipage}}\end{center}\myskip Operacją {\em dominującą} w algorytmie jest operacja:\ $x[j+1]=y[i+j+1]$. Udowodnimy, że algorytm KMP wykonuje co najwyżej 2n-m porównań symboli. Zauważmy, że dla danejpozycji w tekście y jest ona co najwyżej raz porównana z pewną pozycją we wzorcu w porównaniupozytywnym (gdy symbole są równe). Jednocześnie każde negatywne porównanie powoduje przesunięciepozycji $i$ co najmniej o jdeden, maksymalna wartość i wynosi n-m, zatem mamy takich porównań conajwyżej n-m, w sumie co najwyżej 2n-m porównań w algorytmi KMP.

Algorytm dla $x=ab$, $y=aa..a$ wykonuje 2n-2porównania, zatem 2n-m jest dolną i jednocześnie górną granicą na liczbę porównań w algorytmie.%--------------\myskipObserwacja.\ Tablicę P' możemy w algorytmie KMP zamienić na P bez zmiany złożoności pesymistycznej.\myskipW wersji on-line algorytmu okaże się, że jest zdecydowana różnica między użyciem P' i P,to właśnie jest motywem wprowadzenia silnych prefikso-sufiksów.\myskip \begin{figure}[hbt]\begin{center}\includegraphics[width=6in]{teksty_fig3.eps}\caption{Jedna iteracja algorytmu KMP. Przesunięcie $shift=j-P^{\prime }[j]$ potencjalnego początku wystąpienia wzorca gdy $x[j+1]\ne y[i+j+1]$.} \end{center}\end{figure}\subsection*{Wersja on-line algorytmu KMP}Przedstawimy teraz wersję on-line algorytmu KMP. Wczytujemy kolejne symbole $y$ i wypisujemy on-line (nabieżąco) odpowiedż:

\myskip\begin{center}\fbox{\begin{minipage}{11cm}\vskip0.3cm\hspace*{0.6cm}\textbf{Algorithm} \textit{On-Line-KMP};\\\hspace*{1.2cm}\textbf{repeat forever}\\ % \vskip 0.2cm \noindent\hspace*{1.8cm} read(

$symbol$

);\\ \hspace*{1.8cm} \textbf{while}

$j>-1$

and

$x[j+1]\ne symbol$

\textbf{do}

$j:=P^{\prime }[j]$

;\\\hspace*{1.8cm}

$j:=j+1$

; \\\hspace*{1.8cm} \textbf{if}

$j=m$

\textbf{then}\\\hspace*{2.8cm} write(

$1$

);\ j :=

$P^{\prime }[m]$

;\\\hspace*{1.8cm} \textbf{else} write(

$0$

);\\\vskip0.4cm\end{minipage}}\end{center}\myskipOznaczmy przez delay(m) maksymalną liczbę kroków algorytmu On-Line-KMP między wczytaniem symbolui daniem odpowiedzi. Przez delay'(m) oznaczmy podobną wielkość, w sytuacji gdy zamiast tablicy P' użyjemy P.\myskipPrzykład}. Jeśli

$x=aaaa\dots a$

oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle y=a^{m-1'''b} , to

$delay(m)=O(1)$

,

$dela{y}^{\prime }(m)=\mathrm{\Theta }(m)$

.\myskipZ lematu o okresowości wynika, że zachodzi następujący fakt:

$delay(m)=O(\log m)$

Uzasadnienie pozostawiamy jako ćwiczenie.\myskipSłowa Fibonacciego definiujemy następująco:

$F_0=a,F_1=ab,F_{n+1}=F_n\cdot F_{n-1}$

\noindent Na przykład:

$F_3=abaab,F_4=abaababa,F_5=abaababaabaab.$

\myskipNiech

$F{\text{'}}_n$

oznacza słowo Fibonacciego z obciętymi ostatnimi dwoma symbolami. Jeśli jako wzorzec weżmiemy słowo Fionacciego

$F_n$

, a jako tekst słowo

$F{\text{'}}_{n}cc$

to przy wczytywaniu

$|F_n-1|$

-ego symbolu algorytm ma opóżnienie logarytmiczne, iterujemy

$\mathrm{\Omega }(\log n)$

razy operację:

$j:=P^{\prime }[j]$

. Uzasadnienie pozostawiamy jako ćwiczenie.

Przy okazji wprowadzenia słów Fibonacciego zostawiamy jako ćwiczenie podaniewzoru na tablice P i P' dla słów Fibonacciego, we wzorze możemy używać liczb Fibonacciego.W związku z tym proponujemy jako ćwiczenie napisanie wersji algorytm KMP dla wzorca będącego słowem Fibonacciego w czasie liniowym i bez dodatkowej tablicy (typu P lub P'). \subsection*{Wersja real-time algorytmu KMP}Pokażemy teraz wersje algorytmu on-line która działa real-time, tzn. czas reakcji między wczytaniem symbolui daniem odpowiedzi jest O(1). Algorytm zachowuje się podobnie jak algorytm On-Line-KMP, podstawowa różnica polega na tym, że algorytmwkłada do kolejki wczytane symbole, które jeszcze nie są przetworzone w sensie algorytmu KMP. Algorytm zachowuje siępodobnie jak algorytm on-line, ale wczytuje kolejne symbole z kolejki, a nie bezpośrednio z wejścia. Rysunekpokazuje relacje tego algorytmu do algorytmu KMP. Symbole z wejścia najpierw wędrują do kolejki.\myskip\begin{figure}[hbt]\begin{center}\includegraphics[width=6.2in]{teksty_fig4.eps}\caption{Typowa konfiguracja w algorytmie real-time-KMP.} \end{center}\end{figure} \begin{center}\fbox{\begin{minipage}{7cm}\vskip0.3cm\hspace*{0.3cm}\textbf{Algorytm} \textit{Real-Time-KMP};\\\hspace*{.8cm} inicjalizacja:\ $j:=0$;\ Kolejka := $\mathrm{\varnothing }$;\ \vskip 0.1cm \noindent\hspace*{0.5cm}\textbf{repeat forever} \vskip 0.2cm \noindent\hspace*{0.8cm} read(symbol); \\\hspace*{1.cm}insert(symbol,Kolejka); \\\hspace*{1cm} write(OUTPUT(Kolejka,\ j));\\\vskip 0.4cm\end{minipage}}\end{center}\myskipW celu skrócenia zapisów pojedyńczych algorytmów rozbijamy algorytm na dwie części. Zasadniczaczęść jest zapisana jako osobna funkcja OUTPUT(Kolejka,\ j). Funkcja taliczy 0 lub 1, w zależności od tego czy ostatnio wczytany symbol kończy wystąpieniewzorca x. Zmienne Kolejka, j są globalne. \noindent Oczywistym jest że opóżnienie (czas reakcji) tego algorytmu jest O(1).\myskipPozostawiamy jako ćwiczenie uzasadnienie tego, że algorytm Real-Time-KMP jest poprawny. \begin{center}\fbox{\begin{minipage}{12cm}\vskip0.3cm\hspace*{0.3cm}\textbf{Funkcja} \textit{OUTPUT(Kolejka,\ j)};\\\hspace*{1.cm}output := 0;\\\hspace*{1.cm} repeat 2 times\\\hspace*{1.8cm} if Kolejka niepusta then\\\hspace*{2.1cm} if $j=-1$ then \\\hspace*{2.7cm} $j$ := 0; delete(Kolejka);\\\hspace*{2.1cm} \textbf{else if} $x[j+1]\ne first(Kolejka)$ then \ $j:=P^{\prime }[j]$;\\\hspace*{2.1cm}\textbf{ else}\\\hspace*{2.7cm} $j:=j+1$; delete(Kolejka); ;\\\hspace*{2.7cm} \textbf{if} $j=m$ \\\hspace*{3.1cm}output := 1;\ j := $P^{\prime }[m]$; \vskip 0.2cm \noindent\hspace*{1.cm} return(output);\\\vskip 0.4cm\end{minipage}}\end{center} \subsection*{Wersja algorytmu KMP z $\frac{3}{2}n$ porównaniami}Algorytm KMP wykonuje co najmniej 2n-m porównań symboli. Załóżmy, że są to operacje dominujące ispróbujmy zmniejszyć stały wspó:lczynnik 2 do $\frac{3}{2}$. Na początku załóżmy, że $x=ab$.Następujący algorytm znajduje wszystkie wystąpienia wzorca ab w tekście y.\myskip\begin{center}\fbox{\begin{minipage}{12cm}\vskip0.3cm\hspace*{0.6cm}\textbf{Algorithm} Szukanie-ab; \\wzorcem jest $ab$ %\{ algorithm of Morris and Pratt \}\\\hspace*{1.2cm}$i:=0$; ;\\\hspace*{1.2cm}\textbf{while} $i\le n-m$ \textbf{do }\\\hspace*{1.8cm}\textbf{while} $y[i+2]\ne b$ {do} \$i=i+1$;\\\hspace*{1.8cm}\textbf{if} $y[i+1]=a$ \textbf{then }\\\hspace*{2.4cm} wypisz-wystąpienie; i:=i+2;\\\vskip0.4cm\end{minipage}}\end{center}\myskipAlgorytm KMP dla wzorca ab wykonywał 2n-2 porównań symboli, nowy algorytm jest lepszy. Zachodzi fakt: algorytm Szukanie-abwykonuje co najwyżej n porównań w tym przypadku. \myskip\noindent Uzasadnienie pozostawimay jako ćwiczenie.\myskipUogólnimy algorytm na dowolne wzorce. Niech x zawiera co najmniej dwa różne symbole, \ $x=a^{k}b\alpha$, gdzie $a\ne b$.Oznaczmy $x^{\prime }=b\alpha$ ({\em skrócony wzorzec}).\myskipPrzykład.\ $x=aaaabaaaababa$, wtedy $x^{\prime }=baaaababa$, $\alpha =aaaababa$.\myskipPodamy nieformalny zarys działania oszczędniejszej wersji algorytmu KMP, w której osobno szukamy x' i osobno części $a^k$. \myskip Niech $KM{P}^{\prime }$ będzie taką wersją algorytmu KMP w której jedynie szukamy wzorca $x^{\prime }$, ale tablica $P^{\prime }$ jest policzona względem wzorca $x$.Jeśli $j>0$ i $shift\le k$ to wykonujemy przesunięcie potencjalnego początku i wzorca w y o k+1, gdzie $shift=j-P^{\prime }[j]$. Inaczej mówiąc, nie szukamy wszystkich wystąpień x', ale jedynie takich, które mają sens pod względem potencjalnego znalezienia na lewo ciągu $a^k$.\myskipTak zmodyfikowany algorytm KMP zastosujemy jako część algorytmu Oszczędny-KMP. \noindent Graficzna ilustracja działania algorytmu Oszczędny-KMP jest pokazana na rysunku.\myskip Algorytm Oszczędny-KMP;\begin{description}\item\hspace*{0.7cm}Znajdujemy wystąpienia x' w tekście $y[k+1..m]$ algorytmem KMP';\\dla każdego wystąpienia x' sprawdzamy czy na lewo jest wystąpienie $a^k$;\\nie sprawdzamy tych pozycji w y, których zgodność z pewną pozycją w x jest znana; \end{description}

\begin{figure}[hbt]\begin{center}\includegraphics[width=5.9in]{teksty_fig5.eps}\caption{Typowa konfiguracja w algorytmie Oszczędny-KMP.} \end{center}\end{figure} \noindent Pozostawiamy jako ćwiczenie dokładny zapis algorytmu w pseudokodzie oraz dowód tego, że algorytm Oszczędny-KMP wykonuje co najwyżej $\frac{3}{2}n$ porównan. \myskipOgólna idea jest przedsatwiona na rysunku.

\begin{figure}[hbt] \begin{center} \includegraphics[width=5.9in]{teksty_fig6.eps} \caption{Ilustracja tego, że liczba operacji dodatkowych jest ograniczona przez $\frac{1}{2}n$.} \end{center} \end{figure}  %********************

Niech zasadniczymi operacjami będą operacje sprawdzania pierwszego b na danej pozycji tekstu y,oraz te sprawdzania symboli ktore sa z wynikiem pozytywnym. Takich operacji jest co najwyżej n. Pozostałe operacje to (1) sprawdzanie w części $\alpha$ z wynikiem negatywnym, wtedy przesuwamy wzorzec co najmniej o k, (2) sprawdzanie części $a^k$ na lewo od {\em pozytywnego} $b$ (w kwadraciku na rysunku), na pozycjach gdzie wcześniej było sprawdzanie{\em negatywnego} b. Wtedy odległość między pozytywnymi kolejnymi b jest co najmniej 2w, gdzie $w\le k$ liczba sprawdzanych na lewo symboli a.Zatem lokalnie przesunięcie jest co najmniej dwukrotnie większe niż liczba dodatkowych operacji. \noindent Suma przesunięć wzorca na tekście $y$ wynosi co najwyżej n, tak więc sumaryczna liczba dodatkowych operacjijest co najwyżej $\frac{1}{2}n$, a liczb wszstkich nie przekracza $\frac{3}{2}n$.