Algorytmy i struktury danych/Algorytmy tekstowe I

Algorytmy tekstowe I

Tekst jest ciągiem symboli, przyjmujemy że jest on zadany tablicą x[1..n] elementami której są 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.

Lemat [Lemat o okresowości]

Jeśli x ma okresy p, q oraz $p+q\le |x|$ to $nwd(p,q)$ jest również okresem x.

Lemat ten 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.

Lemat ten można wzmocnić osłabiając założenia. Dowód pozostawiamy jako ćwiczenie.

Lemat [Silny 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.

Poję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.

Oznaczmy przez $P[k]$ rozmiar prefikso-sufiksu $x[1..k]$, zatem $per(x)=n-P[n]$, gdzie $n=|x|$.

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

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

Algorytm Prefikso-Sufiksy;

---

$P[0]:=-1$; $t:=-1$;
for $j:=1$ to $m$ do
   while $t\ge 0$ and $x[t+1]\ne x[j]$ do $t:=P[t]$
   $t:=t+1$; $P[j]:=t$;

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.

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

Wartości tablicy P' mogą być znacznie mniejsze niż wartości tablicy P.

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.

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