Zaawansowane algorytmy i struktury danych/Wykład 3

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 $zz$, gdzie $z$ 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 $x=x^R$, gdzie $R^{}$ 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 $x[i..j]$, który pojawił się wcześniej jako $x[p..q]$, gdzie $q<i$ to możemy reprezentować $x[i..j]$ przez parę liczb $[p,q]$. 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 $x$ jest rozkład $x=v_1{v}_2\dots v_m$, gdzie $v_1=x[1]$, oraz
jeśli $|v_1{v}_2..v_{k-1}|=i-1$, to $v_k$ jest najdłuższym tekstem, który występuje w $v_1{v}_2..v_{k-1}$, a jeśli takiego nie ma, to $v_k=x[i]$.

Oznaczmy przez $LZ(x)$ faktoryzację $x$.

Rysunek 1:

Obliczanie następnego czynnika w faktoryzacji typu LZ zaczynającego się na pozycji $i$-tej (jako najdłuższego słowa, które występuje we wcześniejszym tekście). Poprzedni czynnik kończy się na pozycji $i-1$. $Pos(i)$ jest początkiem wcześniejszego segmentu który jest referencją aktualnego czynnika.

Przykład

Faktoryzacja przykładowego słowa Fibonacciego jest następująca:

Parser nie mógł rozpoznać (nieznana funkcja „\v”): {\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 udowodnić następujący fakt:

dla danego tekstu $x$ długości $n$ możemy policzyć $LZ(x)$ w czasie liniowym. Zakładamy tutaj, że alfabet da się posortować w czasie liniowym (jest to naturalne założenie).

Powtórzenia zakotwiczone

Przypuśćmy, że $x=uv$. Powtórzenie jest $(u,v)$-zakotwiczone gdy zaczyna się w $u$ i kończą w $v$. Wprowadzimy dwie funkcje logiczne $RighTest(u,v),LeftTEst(u,v)$ dla słów $u,v$. $RightTest(u,v)$ zachodzi, gdy istnieje $(u,v)$-zakotwiczone powtórzenie którego środek znajduje się na początku, lub wewnątrz $v$. Podobnie definiuemy $LeftTest$. Roważymy, tylko przypadek obliczania $RightTest$. \begin{figure}[bht] \begin{center} \includegraphics[width=11.cm]{teksty_fig23.eps} \caption{ $PREF[k]+S[k]\ge k$.}

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

Niech $Test(u,v)$ będzie funkcją logiczną wyrażającą fakt posisadania przez $x$ powtórzenia $(u,v)$-zakotwiczonego. Inaczej mówiąc $Test(u,v)\equiv RightTest(u,v)\text{<mrow data-mjx-texclass="ORD">lub</mrow>}Lefttest(u,v)$. 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} $n=1$ \textbf{then return } {\em false};\\ \hspace*{1.8cm} zastosuj algorytm rekurencyjnie do tekstu $x[1..\lfloor n/2\rfloor ]$; \\ \hspace*{1.8cm} zastosuj algorytm rekurencyjnie do tekstu $x[\lfloor n/2\rfloor +1..n]$; \\ \hspace*{1.8cm}\textbf{if} $Test(x[1..\lfloor n/2\rfloor ],x[\lfloor n/2\rfloor +1..n])$ then return} {\em true; \vskip0.4cm \end{minipage} \end{center} \myskip Algorytm w oczywisty sposób działa w czasie $O(n\log n)$, gdyż liczenie funkcji $Test$ jest w czasie liniowym. \myskip Dygresja.\ Istnieje ciekawa wersja tego algorytmu działająca w czasie $O(n\log n)$ i (dodatkowej) pamięci stałej (nie możemy mieć dodatkowych tablic $PREF,S$).

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

$LZ(x)=(v_1,v_2,\dots ,v_m)$

Wtedy $x$ zawiera powtórzenie wtedy i tylko wtedy gdy dla pewnego $k$ zachodzi $RightTest(v_1,v_2\dots v_{k-2},v_{k-1}{v}_k$ lub $Righttest(v_1,v_2\dots v_{k-1},v_k)$ \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ę $LZ(x)=(z_1,z_2,\dots ,z_m)$;\\ \hspace*{1.2cm}\textbf{for} $k:=1$ \textbf{to} $m$ \textbf{do}\\ \hspace*{1.8cm} $u1$ := $z_1,z_2\dots z_{k-2}$;\ $v1$ := $z_{k-1}{z}_k$;\\ \hspace*{1.8cm} $u2$ := $z_1,z_2\dots z_{k-1}$;\ $v2$ := $z_k$;\\ \hspace*{1.8cm}\textbf{if} \ $RightTest(u1,v1)$ lub $RightTest(u2,v2)$ \\ \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 $RightTest(u1,v1)$ lub $RightTest(u2,v2)$

jest

$O(|v_{k-1}{v}_k|)$

, oraz zachodzi

$\sum _{k=1}^m|v_{k-1}{v}_k|\le 2n$

Słowo $x$ nazwiemy palindromem gdy jest symetryczne oraz $|x|>1$. Palindromy parzyste to palindromy o parzystej długości. Oznaczmy zbiór wszystkich palindromów przez $PAL$, a przez $PA{L}_0,PA{L}_1$ 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 $x=uv$, takim, że $u\in PAL$ oraz $u$ jest najdłuższy o tej własności. Istnieje prosty algorytm oparty na tablicy prefikso-sufiksów $P$. \myskip Algorytm Prefikso-Palindrom;

1. oblicz tablicę P dla słowa-kompozycji $x\mathrm{\#}{x}^R$

(słowo długości $2n+1$), \item jeśli $P(2n+1)>0$ to jest to długość najdłuższego prefikso-palindromu

1. w przeciwnym przypadku $x$ 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 $O(s)$, gdzie $s$ 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 $i$ {\em promień} palindromu parzystego o środku w $i$ 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 $x$ 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 $i$ od strony lewej do prawej, załóżmy że policzyliśmy już wartości:

$Rad[1],Rad[2],\dots ,Rad[i].$

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

palindromów}

$1\le k\le Rad[i]\text{<mrow data-mjx-texclass="ORD">oraz</mrow>}Rad[i-k]\ne Rad[i]-k\Rightarrow Rad[i+k]=\min (Rad[i-k],Rad[i]-k)$

 %

\myskip Uzasadnimy krótko tę własność rozważając dwa przypadki: \begin{description}\itemsep0mm\topsep0mm \item[Przypadek (a):] $Rad[i-k]<Rad[i]-k$.\\ Wówczas palindrom $Rad[i-k]$ o środeku w $i-k$ jest całowicie zawarty w d"uższym palindromie o śrdoeku w $i$. Pozycja $i-k$ jest symetryczna do $i+k$ ze względu na $i$. Zatem z symetrii o środku $i$ wynika,że najdłuższy palindrom o środku $i+k$ m taki sam promień jak ten o środku $i-k$. Zatem w tym przypadku $Rad[i+k]=Rad[i-k]$. \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):] $Rad[i-k]>Rad[i]-k$.\\ Sytuacja jest pokazna na rysunku, który przedsatwi maksymalne palindromy o środkach $i-k$, $i$ and $i+k$. Ponieważ $a\ne b$ (z definicji maksymalności palindromu o środku w $i$), zatem $Rad[i+k]=Rad[i]-k$. \end{description} \noindent Poniżej przedstawiamy algorytm Promienie-Palindromów. W jednej iteracji {\em głównej pętli} while algorytm oblicza $Rad[i+k]$ dla kolejnych $k=1,2,\dots$ dla których $Rad[i-k]\ne Rad[i]-k$. Jeśli ostatnim takim $k$ jest $k^{\prime }$, wtedy zaczynamy całą główną iterację od nowego $i$ równego $i+k^{\prime }$. \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"ć $s$ 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} $Rad[1]:=0$; $j:=0$; \\ \hspace*{1.2cm} $i:=2$;\vskip 0.2cm \noindent \hspace*{1.2cm}\textbf{while} $i\le \lfloor n/2\rfloor$ \textbf{do }\\ \hspace*{1.8cm}\textbf{while} $x[i-j]=x[i+1+j]$ \textbf{do} $j:=j+1$;\\ \hspace*{1.8cm}\textbf{if} $j=i$ \textbf{then} $Rad[i]:=j$;\\ \hspace*{1.8cm}$k:=1$;\\ \hspace*{1.8cm}\textbf{while} $Rad[i-k]\ne Rad[i]-k$ \textbf{do }\\ \hspace*{2.4cm}$Rad[i+k]:=\min (Rad[i-k],Rad[i]-k)$; $k:=k+1$;\\ \hspace*{1.8cm}$j:=max(j-k,0)$;\ $i:=i+k$;\\ \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 $PA{L}_0^{*},PA{L}^{*}$ oznaczmy odpowiednio zbiór konkatenacji dowolenj liczby słów należących do $PA{L}_0,PAL$. Elementy $PA{L}^{*}$ nazywamy {\em palstarami} a elementy $PA{L}_0^{*}$ nazywamy {\em palstarami parzystymi}. \myskip Niech $first(i)$, $firs{t}_0(i)$ będzie Ze względów technicznych załóżmy, że słowo puste teź jest palstarem (parzystm i nieparzystym jednocześnie). odpowiednio pierwszą pozycją $j>i$ w słowie $x$ taką, że $x[i..j]\in PAL$, $x[i..j]\in PA{L}_0$, wartością funkcji jest zero gdy nie ma takiego $j$. \begin{center} \begin{minipage}{9cm} \vskip0.3cm \hspace*{0.6cm}\textbf{Algorytm} Parzyste-Palstary; %\{ is $x$ an even palstar ? \}\\ \hspace*{1.2cm}$s$ := $0$;\\ \hspace*{1.2cm}\textbf{while} $s<n$ \textbf{do }\\% \{ cut $x[s+1..n]$ \}\\ \hspace*{1.8cm} $s$ := $s+1$;\\ \hspace*{1.8cm}\textbf{if} $firs{t}_0(s)=0$ \textbf{then return} false;\\ \hspace*{1.8cm}$s:=first(s)$;\\ \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 $firs{t}_0(i)$ zajmuje czas proporcjonalny do wartości $s=first(i)$, zakładając, że $s\ne 0$. Netrywialna natomiast jest poprawność algorytmu. Zdefiniujmy \begin{center} $pars{e}_0(i)=\min \{j:x[i..j]\in PA{L}_0$ oraz $j=n$ lub $x[j+1..n]\in PA{L}_0^{*}\}$. \end{center} \noindent Własność parzystych palstarów: \ $x[i..n]\in PA{L}_0^{*}\Rightarrow pars{e}_0(i)=firs{t}_0(i)$ \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ę $parse(i)$ 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}: $x[i..n]\in PA{L}^{*}\Rightarrow parse(i)\in \{first(i),2\cdot first(i)+1,2\cdot first(i)-1\}$ \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 $first$, obliczamy tablicę $FIRST[i]=first(i)$, w czasie liniowym dla wszystkich $i$ lącznie. \myskip Pozostawiamy jako ćwiczenie policzenie tej tablicy w czasie $O(n)$. Obliczenie takie opiera się na wykorzystaniu tablicy promieni palindromów. \myskip Załóżmy teraz że mamy tablicę FIRST, funkcja $first$ działa teraz w czasie stałym (gotowe wartości z tablicy). Poniższy algorytm dla każdej pozycji $i$ sprawdza czy $x[i..n]\in PA{L}^{*}$. Odpowiedź jest zapisana w tablicy logicznej $PAL$. Zakładamy, że początkowo tabica $PAL$ 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}$PAL[n]:=$ true; %\{ the empty word is a palstar \} \\ \hspace*{1.2cm}\textbf{for} $i:=n-1$ \textbf{down to} $0$ \textbf{do }\\ \hspace*{1.7cm}$f:=FIRST[i]$;\\ \hspace*{1.7cm}\textbf{if} $f=0$ \textbf{then} $PAL[i]:=$ 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} $PAL[i+2f-1]$ \textbf{or} $PAL[i+2f+1])$\\ \vskip0.4cm \end{minipage} \end{center}

\noindent Intersującym problemem jest rozkład słowa $x$ w postaci $PA{L}^k$, gdzie $k$ jest ustalone. Istnieją algorytmy liniowe dla $k=2,3,4$ oparte na następującej własności zawężającej zbiór rozkładów do zweryfikowania: jeśli $x\in PA{L}^2$ to $x=uv$, dla pewnych $u,v\in PAL$ gdzie $u$ jest najdłuższym palindromem będącym prefiksem $x$ lub $v$ jest najdłuższym palindromem będącym sufiksem $x$.