Zaawansowane algorytmy i struktury danych/Wykład 3

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zaawansowane algorytmy tekstowe III



W module tym zajmiemy się wykrywaniem regularności w tekstach: szukaniem symetrii i powtórzeń. Słowo jest powtórzeniem, gdy jest postaci , gdzie jest niepustym tekstem. Powtórzenia w tekstach reprezentują strukturę wewnętrznych okresowości i regularności, których wyszukiwanie ma zastosowania np. w biologii obliczeniowej. Powtórzenia są związane z kompresją tekstów. Im więcej powtórzeń w słowie tym bardziej to słowo jest kompresowalne.

Słowo jest symetryczne gdy , gdzie jest operacją odwracania słowa. Algorytmicznie symetrie w słowach są bardzo interesujące.

Kompresja typu LZ i faktoryzacja tekstów

Powtarzające się segmenty tekstu związane są z kompresją. Jeśli mamy dwie kopie tego samego (być może długiego) podsłowa, to drugą z nich możemy zastąpić referencją do pierwszej. Jeśli czytamy tekst od lewej do prawej i napotkamy segment , który pojawił się wcześniej jako , gdzie to możemy reprezentować przez parę liczb . Filozofia ta prowadzi do rodziny algorytmów kompresji podanych przez Lempela i Ziva (kompresji typu LZ). Jest wiele różnych wariantów tego typu kompresji.

Zdefiniujmy teraz faktoryzację tekstów typu LZ. Faktoryzacją tekstu jest rozkład , gdzie , oraz jeśli , to jest najdłuższym tekstem, który występuje w , a jeśli takiego nie ma, to .


Oznaczmy przez faktoryzację .

%************************************************************ \begin{figure}[h] \begin{center} \includegraphics[width=12.5cm]{teksty_fig21.eps} \caption{ Obliczanie następnego czynnika w faktoryzacji typu LZ zaczynającego się na pozycji -tej (jako najdłuższego słowa, które występuje we wcześniejszym tekście). Poprzedni czynnik kończy się na pozycji . jest początkiem wcześniejszego segmentu który jest referencją aktualnego czynnika. } \end{center} \end{figure} %********************************************************** \noindent

Przykład.\ Faktoryzacja przykładowego słowa Fibonacciego jest następująca:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle LZ(abaababaabaab)\ =\ v_1\ v_2\ v_3\ v_4\ v_5\ v_6\ = \ a\ b\ a\ aba\ baaba\ ab}

Korzystając z drzew sufiksowych można udowdnić

następujący fact: \vskip 0.2cm dla danego tekstu długości możemy policzyć w czasie liniowym. Zakładamy tutaj, że alfabet da się posortować w czasie liniowym (jest to naturalne założenie). Przypuśćmy, że . Powtórzenie jest -zakotwiczone gdy zaczyna się w i kończą w . Wprowadzimy dwie funkcje logiczne dla słów . zachodzi, gdy istnieje -zakotwiczone powtórzenie którego środek znajduje się na początku, lub wewnątrz . Podobnie definiuemy . Roważymy, tylko przypadek obliczania . \begin{figure}[bht] \begin{center} \includegraphics[width=11.cm]{teksty_fig23.eps} \caption{ .}

 

\end{center} \end{figure} \myskip Dla każdej pozycji w liczymy 1. : długość maksymalnego podsłowa zaczynającego się w i będącego prefiksem ; 2. : długość maksymalnego podsłowa kończącego się na pozycji i będącego sufiksem . \myskip Własność funkcji : zachodzi wtedy i tylko wtedy gdy dla pewnego mamy nierówność , patrz rysunek. \myskip Wiemy już jak obliczyć tablicę w czasie liniowym, tablicę liczymy symetrycznie. W ten sposób pokazaliśmy, że obliczenie wymaga jedynie czasu liniowego. Podobnie jest dla .

Niech będzie funkcją logiczną wyrażającą fakt posisadania przez powtórzenia -zakotwiczonego. Inaczej mówiąc . Następujący algorytm ma strukturę taką jak {\em merge-sort}. Szukamy powtórzenia w lewej połowie, w prawej, oraz {\em na styku} obu połówek (funkcja Test). \begin{center} \begin{minipage}{12cm} \vskip0.3cm \hspace*{0.6cm}\textbf{Algorytm} Powtórzenia-Rekurencyjnie;\\ \hspace*{1.2cm}\textbf{if} \textbf{then return } {\em false};\\ \hspace*{1.8cm} zastosuj algorytm rekurencyjnie do tekstu ; \\ \hspace*{1.8cm} zastosuj algorytm rekurencyjnie do tekstu ; \\ \hspace*{1.8cm}\textbf{if} then return} {\em true; \vskip0.4cm \end{minipage} \end{center} \myskip Algorytm w oczywisty sposób działa w czasie , gdyż liczenie funkcji jest w czasie liniowym. \myskip Dygresja.\ Istnieje ciekawa wersja tego algorytmu działająca w czasie i (dodatkowej) pamięci stałej (nie możemy mieć dodatkowych tablic ).

Algorytm liniowy szukania powtórzenia opiera się na faktoryzacji tekstów. Niech

Wtedy zawiera powtórzenie wtedy i tylko wtedy gdy dla pewnego zachodzi lub \myskip \noindent Dowód tej własności pozostawiamy jako ćwiczenie. \begin{center} \begin{minipage}{12cm} \vskip0.3cm \hspace*{0.6cm}\textbf{Algorytm} Szukanie-Powtórzeń;\\ \hspace*{1.2cm}oblicz faktoryzację ;\\ \hspace*{1.2cm}\textbf{for} \textbf{to} \textbf{do}\\ \hspace*{1.8cm}  := ;\  := ;\\ \hspace*{1.8cm}  := ;\  := ;\\ \hspace*{1.8cm}\textbf{if} \ lub \\ \hspace*{1.9cm} \textbf{then}\ \textbf{return} true;\vskip 0.1cm \hspace*{1.2cm}\textbf{return} false; \\ \vskip0.4cm \end{minipage} \end{center} Algorytm działa w czasie liniowym, gdyż złożoność liczenia alternatywy lub

jest , oraz zachodzi

Słowo nazwiemy palindromem gdy jest symetryczne oraz . Palindromy parzyste to palindromy o parzystej długości. Oznaczmy zbiór wszystkich palindromów przez , a przez oznaczmy odpowiednio zbiory palindromów parzystych i nieparzystych. Przykładami palindromów są słowa: \myskip \centerline{kajak,\ atypotopyta,\ zagwiżdżiwgaz} \myskip Problem najd"uższego prefikso-palindromu polega na rozkładzie danego słowa , takim, że oraz jest najdłuższy o tej własności. Istnieje prosty algorytm oparty na tablicy prefikso-sufiksów . \myskip Algorytm Prefikso-Palindrom;

  1. oblicz tablicę P dla słowa-kompozycji

(słowo długości ), \item jeśli to jest to długość najdłuższego prefikso-palindromu

  1. w przeciwnym przypadku nie ma prefikso-palindromu.

\myskip Podobnie możemy zdefiniować problem najkrótszego prefisko-palindromu. Algorytm powyższy można łatwo zmodyfikować aby znajdował najkrótszy prefikso-palindrom. \noindent Chociaż powyższy algorytm działa w czasie liniowym, możliwy jest szybszy algorytm, który znajduje najkrótszy prefikso-palindrom w czasie , gdzie jest długością najkrótszego prefikso-palindromu, zakładając że tekst posiada prefikso-palindrom . \myskip \noindent Skoncentrujemy się na razie na palindromach parzystych. Definiujemy, dla każdej pozycji {\em promień} palindromu parzystego o środku w jako:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Rad[i]\ =\ \max \{j\ :\ j=0 \ \textrm{lub}\ x[i-j+1.. i]=x[i+1.. i+j]\}}

Załóżmy, dla uproszczenia, że tekst zaczyna się od specjalnego symbolu (marker początku), który występuje tylko na początku. Opiszemy algorytm, który oblicza tablice promieni palindromów dla kolejnych pozycji od strony lewej do prawej, załóżmy że policzyliśmy już wartości:

Okazuje się, że korzystając z symetrii, możemy obliczyć pewne nowe elementy tablicy nie wykonując żdnych porównań symboli. Wynika to z następującego faktu. \myskip {\bf Własność promieni

palindromów}

 %

\myskip Uzasadnimy krótko tę własność rozważając dwa przypadki: \begin{description}\itemsep0mm\topsep0mm \item[Przypadek (a):] .\\ Wówczas palindrom o środeku w jest całowicie zawarty w d"uższym palindromie o śrdoeku w . Pozycja jest symetryczna do ze względu na . Zatem z symetrii o środku wynika,że najdłuższy palindrom o środku m taki sam promień jak ten o środku . Zatem w tym przypadku . \begin{figure}%[htb] \begin{center} \includegraphics[width=9.4cm]{teksty_fig22.eps} \caption{ Przypadek (b) dowodu własności promieni palindromów parzystych.}

 

\end{center} \end{figure} \item[Przypadek (b):] .\\ Sytuacja jest pokazna na rysunku, który przedsatwi maksymalne palindromy o środkach , and . Ponieważ (z definicji maksymalności palindromu o środku w ), zatem . \end{description} \noindent Poniżej przedstawiamy algorytm Promienie-Palindromów. W jednej iteracji {\em głównej pętli} while algorytm oblicza dla kolejnych dla których . Jeśli ostatnim takim jest , wtedy zaczynamy całą główną iterację od nowego równego . \myskip Pozostawiamy jako ćwiczenie modyfikację algorytmu aby liczył promienie palindromów nieparzystych. \myskip W pierwszsym momencie gdy algorytm wykryje prefikso-palindrom (promień palindromu sięga do początku tekstu) możemy algorytm zatrzymać i podać długość najkrótszego prefikso-palindromu. W sumie pokazaliśmy następujący fakt: %\vskip 0.1cm \begin{description} \item(a)\ Tablicę promieni palindromów (parzystych i nieparzystych) można policzyć w czasie liniowym. \item(b)\ Długo"ć najkrótszego prefikso-palindromu (zakładając że taki istnieje) można policzyć w czasie proporcjonalnym do jego długości. \end{description}

\begin{center} \begin{minipage}{12cm} \vskip0.3cm \hspace*{0.6cm}\textbf{Algorithm} \textit{Promienie-Palindromów};\\ \hspace*{1.2cm} ; ; \\ \hspace*{1.2cm} ;\vskip 0.2cm \noindent \hspace*{1.2cm}\textbf{while} \textbf{do }\\ \hspace*{1.8cm}\textbf{while} \textbf{do} ;\\ \hspace*{1.8cm}\textbf{if} \textbf{then} ;\\ \hspace*{1.8cm};\\ \hspace*{1.8cm}\textbf{while} \textbf{do }\\ \hspace*{2.4cm}; ;\\ \hspace*{1.8cm};\ ;\\ \vskip0.4cm \end{minipage} \end{center}

  Rozważmy teraz intersujący (chociaż mało użyteczny w praktyce) problem sprawdzania, czy

słowo jest nietrywialną kompozycją słów symetrycznych. Przez oznaczmy odpowiednio zbiór konkatenacji dowolenj liczby słów należących do . Elementy nazywamy {\em palstarami} a elementy nazywamy {\em palstarami parzystymi}. \myskip Niech , będzie Ze względów technicznych załóżmy, że słowo puste teź jest palstarem (parzystm i nieparzystym jednocześnie). odpowiednio pierwszą pozycją w słowie taką, że , , wartością funkcji jest zero gdy nie ma takiego . \begin{center} \begin{minipage}{9cm} \vskip0.3cm \hspace*{0.6cm}\textbf{Algorytm} Parzyste-Palstary; %\{ is an even palstar ? \}\\ \hspace*{1.2cm} := ;\\ \hspace*{1.2cm}\textbf{while} \textbf{do }\\% \{ cut \}\\ \hspace*{1.8cm}  := ;\\ \hspace*{1.8cm}\textbf{if} \textbf{then return} false;\\ \hspace*{1.8cm};\\ \hspace*{1.2cm}\textbf{return} true;\\ \vskip0.4cm \end{minipage} \end{center} Mówiąc nieformalnie, algorytm Parzyste-Palstary obcina słowo o najkrótszy prefikso-palindrom, aż tekst będzie pusty (sukces) albo aż się {\em zatnie} (nie ma rozkładu na parzyste palindromy). Algorytm Parzyste-Palstary ma złożoność liniową ponieważ policzenie zajmuje czas proporcjonalny do wartości , zakładając, że . Netrywialna natomiast jest poprawność algorytmu. Zdefiniujmy \begin{center} oraz lub . \end{center} \noindent Własność parzystych palstarów: \ \myskip Poprawność algorytmu wynika natychmiast powyższej własności. Pozostawimay dowód tej włsności jako ćwiczenie. \myskip Możemy podobnie zdefiniować funkcję dla dowolnych palstarów i dowolnych palindromów. Własność parzystych palstarów nie zachodzi dla dowolnych palstarów, ale zachodzi własność bardziej skomplikowana. \noindent {\bf Własność dowolnych palstarów}: \myskip Pozostawimay dowód tej własności jako ćwiczenie. Algorytm testowania dowolnych palstarów jest intersujący ponieważ pzebiega on zupełnie inaczej niż dla parzystych palstarów. Piewszym krokiem algorytmu jest stablicowanie funkcji , obliczamy tablicę , w czasie liniowym dla wszystkich lącznie. \myskip Pozostawiamy jako ćwiczenie policzenie tej tablicy w czasie . Obliczenie takie opiera się na wykorzystaniu tablicy promieni palindromów. \myskip Załóżmy teraz że mamy tablicę FIRST, funkcja działa teraz w czasie stałym (gotowe wartości z tablicy). Poniższy algorytm dla każdej pozycji sprawdza czy . Odpowiedź jest zapisana w tablicy logicznej . Zakładamy, że początkowo tabica ma wartości {\em false} włącznie z elementami wykraczjącymi poza zakres tablicy (dla uproszczenia zapisu). \begin{center} \begin{minipage}{13.2cm} \vskip0.3cm \hspace*{0.6cm}\textbf{Algorytm} Testowanie-Palstarów; \\ \hspace*{1.2cm} true; %\{ the empty word is a palstar \} \\ \hspace*{1.2cm}\textbf{for} \textbf{down to} \textbf{do }\\ \hspace*{1.7cm};\\ \hspace*{1.7cm}\textbf{if} \textbf{then} false\\ \hspace*{1.7cm}\textbf{else}\ Parser nie mógł rozpoznać (błąd składni): {\displaystyle PAL[i]:=\\ \hspace*{2.7cm} (PAL[i+f]} \textbf{or} \textbf{or} \\ \vskip0.4cm \end{minipage} \end{center}

\noindent Intersującym problemem jest rozkład słowa w postaci , gdzie jest ustalone. Istnieją algorytmy liniowe dla oparte na następującej własności zawężającej zbiór rozkładów do zweryfikowania: jeśli to , dla pewnych gdzie jest najdłuższym palindromem będącym prefiksem lub jest najdłuższym palindromem będącym sufiksem .