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\leq |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\leq |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]\ {\textrm {oraz}}\ 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\geq 0$ \textbf{and} $x[t+1]\neq 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'[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]\neq x[j+1]$ dla $j<n$. \\Jeśli takiego k nie ma toprzyjmujemy $P'[j]=-1$. Przyjmujemy ponadto, że $P'[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 '[0..5]\ =\ [-1,\ 0,\ -1,\ 1,\ 0,\ 2\ ].$

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

$(t=P[j]\ {\textrm {oraz}}\ x[t+1]\neq x[j+1])\ \Rightarrow \ P'[j]=t$$(t=P[j],\ t\geq 0,\ {\textrm {oraz}}\ x[t+1]=x[j+1])\ \Rightarrow \ P'[j]=P'[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'[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\geq 0$ \textbf{and} $x[t+1]\neq x[j]$\textbf{do}\\ \hspace*{2.5cm} $t:=P'[t]$;\\\hspace*{1.8cm}$t:=t+1$;\\\hspace*{1.8cm}\textbf{if} $j=m$ \textbf{or} $x[t+1]\neq x[j+1]$\\\hspace*{2cm} \textbf{then} $P'[j]:=t$\\textbf{else} $P'[j]:=P'[t]$;\\\vskip0.4cm\end{minipage}}\end{center}\myskipGdyweżmiemy $x\ =\ aba^{m-2}$ to $P'[0]=-1$, $P'[1]=0$, $P'[2]=-1$,oraz $P'[j]=1$, dla $3\leq j\leq 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\leq 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\leq 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'[j]$;\ \ $j:=\max(0,P'[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'[j]$ potencjalnego początku wystąpienia wzorca gdy $x[j+1]\neq 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]\neq symbol$ \textbf{do} $j:=P'[j]$;\\\hspace*{1.8cm}$j:=j+1$; \\\hspace*{1.8cm} \textbf{if} $j=m$ \textbf{then}\\\hspace*{2.8cm} write($1$);\ j := $P'[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)$, $delay'(m)=\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'_{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'_{n}cc$ to przy wczytywaniu $|F_{n}-1|$-ego symbolu algorytm ma opóżnienie logarytmiczne, iterujemy $\Omega (\log n)$ razy operację: $j:=P'[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 := $\emptyset$;\ \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]\neq first(Kolejka)$ then \ $j:=P'[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'[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\leq n-m$ \textbf{do }\\\hspace*{1.8cm}\textbf{while} $y[i+2]\neq 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\neq b$.Oznaczmy $x'=b\alpha$ ({\em skrócony wzorzec}).\myskipPrzykład.\ $x\ =\ aaaabaaaababa$, wtedy $x'\ =\ 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 $KMP'$ będzie taką wersją algorytmu KMP w której jedynie szukamy wzorca $x'$, ale tablica $P'$ jest policzona względem wzorca $x$.Jeśli $j>0$ i $shift\leq k$ to wykonujemy przesunięcie potencjalnego początku i wzorca w y o k+1, gdzie $shift=j-P'[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\leq 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$.