Algorytmy i struktury danych/Algorytmy tekstowe I

Z Studia Informatyczne
< Algorytmy i struktury danych
Wersja z dnia 09:12, 8 sie 2006 autorstwa Tprybick (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

\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 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 jest każda liczba naturalna niezerowa taka, że, 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 oznaczanajmnieszy wspólny dzielnik p,q.\paragraphLemat o okresowości.\\Jeśli x ma okresy p, q oraz to jest również okresem x. \myskipLematten wynika z poprawności algorytm Euklidesa z odejmowaniem, który liczy nwd(p,q). Zauważmy, żejeśli 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 to 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 jest długością prefikso-sufiksu x.Jeśli to prefikso-sufiksem x jest słowo puste o długości zerowej.\vskip 0.1cm

Oznaczmy przez rozmiar prefikso-sufiksu , zatem , gdzie .\paragraph{Przykład.\\} Dla mamy:

Wartość jest warością sztuczną (przyjmiemy potem ).\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:

W algorytmie do liczenia korzystamy z wartości dla . \vskip 0.3cm\hspace*{0.6cm}\textbf{Algorytm} \textit{Pefikso-Sufiksy};\\\hspace*{1.2cm}; ;\\\hspace*{1.2cm}\textbf{for} \textbf{to} \textbf{do}\\\hspace*{1.8cm}\textbf{while} \textbf{and} \textbf{do};\\\hspace*{1.8cm}; ;\\\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 zmniejsza wartość t co najmniej o jeden. Prostezastosowanie zasady magazynu (lub potencjału) implikuje, że operacji 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 :

jeśli to , gdzie jest maksymalnym rozmiarm słowa będącego prefiksem i sufiksem najdłuższego własciwegoi spełniającego dodatkowy warunek dla . \\Jeśli takiego k nie ma toprzyjmujemy . Przyjmujemy ponadto, że .\myskip Wartości tablicy P' mogą być znacznie mniejsze niż wartości tablicy P. %\paragraph{Przykład} Dla mamy:

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

Nie musimy liczyćtablicy P, potrzebna jest jedynie ostatnia wartość , 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}; 1;\\\hspace*{1.2cm}\textbf{for} 1 \textbf{to} \textbf{do }// \\\hspace*{1.8cm}\textbf{while} \textbf{and} \textbf{do}\\ \hspace*{2.5cm} ;\\\hspace*{1.8cm};\\\hspace*{1.8cm}\textbf{if} \textbf{or} \\\hspace*{2cm} \textbf{then} \\textbf{else} ;\\\vskip0.4cm\end{minipage}}\end{center}\myskipGdyweżmiemy to , , ,oraz , dla .\ \noindent To jest pesymistyczny przypadek dla algorytmu Silne-Prefikso-Sufiksy, algorytm wykonuje 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 wszystkie (lub pierwsze) wystąpienia danego tekstu , zwanego wzorcem (ang. pattern).\vskip 0.1cm\noindent Oznaczmy , gdzie .\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 we wzorcu x, oraz na pozycji 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}; ;\\\hspace*{1.2cm}\textbf{while} \textbf{do }\\\hspace*{1.8cm}\textbf{while} \textbf{and} \textbf{do} \;\\\hspace*{1.8cm}\textbf{if} \textbf{then return}(true);\\\hspace*{1.8cm};\ \ ;\\\vskip0.4cm\end{minipage}}\end{center}\myskip Operacją {\em dominującą} w algorytmie jest operacja:\ . 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 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 , 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 potencjalnego początku wystąpienia wzorca gdy .} \end{center}\end{figure}\subsection*{Wersja on-line algorytmu KMP}Przedstawimy teraz wersję on-line algorytmu KMP. Wczytujemy kolejne symbole 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();\\ \hspace*{1.8cm} \textbf{while} and \textbf{do} ;\\\hspace*{1.8cm}; \\\hspace*{1.8cm} \textbf{if} \textbf{then}\\\hspace*{2.8cm} write();\ j := ;\\\hspace*{1.8cm} \textbf{else} write();\\\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 oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle y=a^{m-1'''b} , to , .\myskipZ lematu o okresowości wynika, że zachodzi następujący fakt:

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

\noindent Na przykład: \myskipNiech oznacza słowo Fibonacciego z obciętymi ostatnimi dwoma symbolami. Jeśli jako wzorzec weżmiemy słowo Fionacciego , a jako tekst słowo to przy wczytywaniu -ego symbolu algorytm ma opóżnienie logarytmiczne, iterujemy razy operację: . 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:\ ;\ Kolejka := ;\ \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 then \\\hspace*{2.7cm}  := 0; delete(Kolejka);\\\hspace*{2.1cm} \textbf{else if} then \ ;\\\hspace*{2.1cm}\textbf{ else}\\\hspace*{2.7cm} ; delete(Kolejka); ;\\\hspace*{2.7cm} \textbf{if} \\\hspace*{3.1cm}output := 1;\ j := ; \vskip 0.2cm \noindent\hspace*{1.cm} return(output);\\\vskip 0.4cm\end{minipage}}\end{center} \subsection*{Wersja algorytmu KMP z 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 . Na początku załóżmy, że .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  %\{ algorithm of Morris and Pratt \}\\\hspace*{1.2cm}; ;\\\hspace*{1.2cm}\textbf{while} \textbf{do }\\\hspace*{1.8cm}\textbf{while} {do} \;\\\hspace*{1.8cm}\textbf{if} \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, \ , gdzie .Oznaczmy ({\em skrócony wzorzec}).\myskipPrzykład.\ , wtedy , .\myskipPodamy nieformalny zarys działania oszczędniejszej wersji algorytmu KMP, w której osobno szukamy x' i osobno części . \myskip Niech będzie taką wersją algorytmu KMP w której jedynie szukamy wzorca , ale tablica jest policzona względem wzorca .Jeśli i to wykonujemy przesunięcie potencjalnego początku i wzorca w y o k+1, gdzie . 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 .\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 algorytmem KMP';\\dla każdego wystąpienia x' sprawdzamy czy na lewo jest wystąpienie ;\\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 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 .} \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 z wynikiem negatywnym, wtedy przesuwamy wzorzec co najmniej o k, (2) sprawdzanie części na lewo od {\em pozytywnego} (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 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 wynosi co najwyżej n, tak więc sumaryczna liczba dodatkowych operacjijest co najwyżej , a liczb wszstkich nie przekracza .