Zaawansowane algorytmy i struktury danych/Wykład 3: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
m (Zastępowanie tekstu - "{\em" na "\mathit{")
 
(Nie pokazano 35 wersji utworzonych przez 4 użytkowników)
Linia 5: Linia 5:
  
  
W module tym zajmiemy się wykrywaniem regularności w tekstach: szukaniem symetrii i powtórzeń. Słowo jest powtórzeniem, gdy jest postaci <math>zz</math>, gdzie <math>z</math> 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.
+
W module tym zajmiemy się wykrywaniem regularności w tekstach: szukaniem symetrii.
  
Słowo jest symetryczne gdy <math>x\ =\ x^R</math>, gdzie <math>^R</math> jest operacją odwracania słowa. Algorytmicznie symetrie w
+
Słowo jest symetryczne, gdy <math>x= x^R</math>, gdzie <math>^R</math> jest operacją odwracania słowa. Algorytmicznie symetrie w
 
słowach są bardzo interesujące.  
 
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 <math>x[i..j]</math>, który pojawił się wcześniej jako <math>x[p..q]</math>, gdzie <math>q<i</math> to
 
możemy reprezentować <math>x[i..j]</math> przez parę liczb <math>[p,q]</math>. 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 <math>x</math> jest rozkład <math>x\ =\ v_{1}v_{2}\dots v_{m}</math>, gdzie <math>v_1=x[1]</math>, oraz
 
jeśli
 
<math>|v_1v_2..v_{k-1}|=i-1</math>, to <math>v_k</math> jest najdłuższym tekstem, który występuje w <math>v_1v_2..v_{k-1}</math>, a jeśli
 
takiego nie ma, to <math>v_k=x[i]</math>.
 
\myskip
 
Oznaczmy przez <math>LZ(x)</math> faktoryzację <math>x</math>.
 
<!--%
 
-->
 
  
%************************************************************
 
\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 <math>i</math>-tej (jako najdłuższego
 
słowa, które występuje we wcześniejszym tekście).
 
Poprzedni czynnik kończy się na pozycji <math>i-1</math>. <math>Pos(i)</math> jest początkiem wcześniejszego segmentu
 
który jest referencją aktualnego czynnika.
 
}  <span id="figure8-4" \>
 
\end{center}
 
\end{figure}
 
%**********************************************************
 
<!--%
 
-->\noindent
 
'''Przykład.'''\ Faktoryzacja  przykładowego słowa Fibonacciego jest następująca: <center><math> LZ(abaababaabaab)\ =\
 
v_1\ v_2\ v_3\ v_4\ v_5\ v_6\ = \  a\ b\ a\ aba\ baaba\ ab</math></center>  Korzystając z drzew sufiksowych można udowdnić
 
następujący fact: \vskip 0.2cm dla danego tekstu <math>x</math> długości <math>n</math> możemy policzyć  <math>LZ(x)</math> w
 
czasie liniowym. Zakładamy tutaj, że alfabet da się posortować w czasie liniowym (jest to naturalne
 
założenie).
 
<!--%
 
--><!--%============================================================================================================
 
-->Przypuśćmy, że <math>x=uv</math>.  Powtórzenie jest <math>(u,v)</math>-zakotwiczone gdy zaczyna się w <math>u</math>
 
i kończą w <math>v</math>.
 
Wprowadzimy dwie funkcje logiczne <math>RighTest(u,v), \ LeftTEst(u,v)</math> dla słów <math>u,\ v</math>. <math>RightTest(u,v)</math>
 
zachodzi, gdy istnieje <math>(u,v)</math>-zakotwiczone powtórzenie 
 
którego środek znajduje się na początku, lub wewnątrz <math>v</math>. Podobnie definiuemy <math>LeftTest</math>.
 
Roważymy, tylko przypadek obliczania <math>RightTest</math>.
 
<!--%************************************************************
 
-->\begin{figure}[bht]
 
\begin{center}
 
\includegraphics[width=11.cm]{teksty_fig23.eps}
 
\caption{
 
<math>PREF[k]+S[k]\geq k</math>.}
 
<span id="figure8-2" \>
 
\end{center}
 
\end{figure}
 
<!--%**********************************************************
 
-->\myskip
 
Dla każdej pozycji <math>k</math> w <math>v</math> liczymy
 
1. <math>PREF[k]</math>: długość maksymalnego podsłowa zaczynającego się w <math>k</math> i będącego prefiksem <math>v</math>;
 
2. <math>S[k]</math>: długość maksymalnego podsłowa kończącego  się na pozycji  <math>k-1</math> i będącego sufiksem <math>u</math>.
 
\myskip
 
'''Własność funkcji <math>Righttest</math>:'''
 
<math>Rightest(u,v)</math> zachodzi wtedy i tylko wtedy gdy dla pewnego <math>k</math> mamy nierówność
 
<math>PREF[k]+S[k] \geq k</math>, patrz rysunek. \myskip Wiemy już jak obliczyć tablicę <math>PREF</math>  w czasie liniowym,
 
tablicę <math>S</math> liczymy symetrycznie. W ten sposób pokazaliśmy, że obliczenie <math>RightTest(u,v)</math> wymaga  jedynie
 
czasu liniowego. Podobnie jest dla <math>LeftTest</math>.
 
  
Niech <math>Test(u,v)</math> będzie funkcją logiczną wyrażającą fakt posisadania przez <math>x</math>
+
==Wykrywanie symetrii w tekstach ==
powtórzenia <math>(u,v)</math>-zakotwiczonego. Inaczej mówiąc <math>Test(u,v) \equiv RightTest(u,v)\ \textrm{lub}\ Lefttest(u,v)</math>.
 
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} <math>n=1</math> \textbf{then return } {\em false};\\
 
\hspace*{1.8cm} zastosuj algorytm rekurencyjnie do tekstu <math>x[1.. \lfloor n/2\rfloor ]</math>;
 
\\
 
\hspace*{1.8cm} zastosuj algorytm rekurencyjnie do tekstu <math>x[\lfloor n/2\rfloor +1.. n]</math>;
 
\\
 
\hspace*{1.8cm}\textbf{if} <math>Test(x[1..\lfloor n/2\rfloor],\ x[\lfloor n/2\rfloor +1.. n])</math>
 
'''then return} {\em true''';
 
\vskip0.4cm
 
\end{minipage}
 
\end{center}
 
<!--%-----------------------------------------------------------------
 
-->\myskip
 
Algorytm w oczywisty sposób działa w czasie <math>O(n \log n)</math>, gdyż liczenie funkcji <math>Test</math> jest
 
w czasie liniowym.
 
\myskip
 
'''Dygresja.'''\ Istnieje ciekawa wersja tego algorytmu działająca w czasie <math>O(n \log n)</math> i
 
(dodatkowej) pamięci stałej (nie możemy mieć dodatkowych tablic <math>PREF,\ S</math>).
 
  
Algorytm liniowy szukania powtórzenia opiera się na faktoryzacji tekstów. Niech <center><math>LZ(x)\ =\ (v_{1},v_{2},\dots ,v_{m})</math></center>
+
Słowo <math>x</math> nazwiemy palindromem, gdy jest symetryczne oraz <math>|x|>1</math>. Palindromy parzyste to palindromy o parzystej długości. Oznaczmy zbiór wszystkich palindromów przez <math>PAL</math>, a przez <math>PAL_0,\ PAL_1</math> oznaczmy odpowiednio zbiory palindromów parzystych i nieparzystych.
Wtedy <math>x</math> zawiera powtórzenie wtedy i tylko wtedy gdy dla pewnego <math>k</math> zachodzi
+
 
<math>RightTest(v_1, v_2\ldots v_{k-2},\ v_{k-1}v_k</math> lub <math>Righttest(v_1, v_2\ldots  v_{k-1},\ v_k)</math>
+
Przykładami palindromów są słowa:  
\myskip
+
 
\noindent Dowód tej własności pozostawiamy jako ćwiczenie.
+
<center>kajak, atypotopyta, zagwiżdżiwgaz </center>
<!--%-----------------------------------------------------------------
+
 
-->\begin{center}
+
 
\begin{minipage}{12cm}
+
Problem '''najdłuższego prefikso-palindromu''' polega na rozkładzie danego słowa <math>x =\ uv</math> takim, że <math>u\in PAL</math> oraz <math>u</math> jest
\vskip0.3cm
+
najdłuższy  o tej własności. Istnieje prosty algorytm oparty na tablicy prefikso-sufiksów <math>P</math>.  
\hspace*{0.6cm}\textbf{Algorytm} Szukanie-Powtórzeń;\\
+
 
\hspace*{1.2cm}oblicz faktoryzację <math>LZ(x)\ =\ (z_{1},z_{2},\ldots,z_{m})</math>;\\
+
 
\hspace*{1.2cm}\textbf{for} <math>k:=1</math> \textbf{to} <math>m</math> \textbf{do}\\
+
{{algorytm |Prefikso-Palindrom|algorytm_prfikso_palindrom|
\hspace*{1.8cm} <math>u1</math> := <math>z_1, z_2\ldots z_{k-2}</math>;\ <math>v1</math> := <math>z_{k-1}z_k</math>;\\
+
#oblicz tablicę P dla słowa-kompozycji <math> x\#x^{R} </math> (słowo długości  <math>2n+1</math>),  
\hspace*{1.8cm} <math>u2</math> := <math>z_1, z_2\ldots z_{k-1}</math>;\ <math>v2</math> := <math>z_k</math>;\\
+
#jeśli  <math>P(2n+1)>0</math> to jest to długość najdłuższego  prefikso-palindromu  
\hspace*{1.8cm}\textbf{if} \
 
<math>RightTest(u1,v1)</math> lub
 
<math> RightTest(u2,v2)</math> \\
 
\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
 
<math>RightTest(u1,v1)</math> lub
 
<math> RightTest(u2,v2)</math>
 
jest <math>O(|v_{k-1}v_k|)</math>, oraz zachodzi  <center><math>\sum_{k=1}^m\ |v_{k-1}v_k| \le 2n</math></center>
 
Słowo <math>x</math> nazwiemy palindromem gdy jest symetryczne oraz <math>|x|>1</math>.
 
Palindromy parzyste to palindromy o parzystej długości. Oznaczmy zbiór wszystkich palindromów przez <math>PAL</math>, a
 
przez <math>PAL_0,PAL_1</math> 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 <math>x =\ uv</math>, takim, że <math>u\in PAL</math> oraz <math>u</math> jest
 
najdłuższy  o tej własności. Istnieje prosty algorytm oparty na tablicy prefikso-sufiksów <math>P</math>. \myskip
 
<!--%
 
-->'''Algorytm''' Prefikso-Palindrom;
 
#oblicz tablicę P dla słowa-kompozycji <math> x\#x^{R} </math>
 
(słowo długości  <math>2n+1</math>), \item
 
jeśli  <math>P(2n+1)>0</math> to jest to długość najdłuższego  prefikso-palindromu
 
 
#w przeciwnym przypadku <math>x</math> nie ma prefikso-palindromu.
 
#w przeciwnym przypadku <math>x</math> 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.
+
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 <math>O(s)</math>, gdzie <math>s</math> jest długością najkrótszego prefikso-palindromu,
+
Chociaż powyższy algorytm działa w czasie liniowym, możliwy jest szybszy algorytm, który znajduje najkrótszy prefikso-palindrom w czasie <math>O(s)</math>, gdzie <math>s</math> jest długością najkrótszego prefikso-palindromu, założywszy że tekst posiada prefikso-palindrom.
zakładając że tekst posiada prefikso-palindrom .
+
 
\myskip
 
\noindent
 
 
Skoncentrujemy się na razie na palindromach parzystych.
 
Skoncentrujemy się na razie na palindromach parzystych.
Definiujemy, dla każdej pozycji <math>i</math> {\em promień} palindromu parzystego o środku w <math>i</math> jako:
+
Definiujemy dla każdej pozycji <math>i</math> ''promień'' palindromu parzystego o środku w <math>i</math> jako:
<center><math>Rad[i]\ =\ \max \{j\ :\ j=0 \ \textrm{lub}\
+
 
x[i-j+1.. i]=x[i+1.. i+j]\}</math></center>
+
<center><math>Rad[i]= \max \{j\ :\ j=0 \ \text{lub}\ x[i-j+1.. i]=x[i+1.. i+j]\}</math></center>
<!--%
+
 
-->Załóżmy, dla uproszczenia, że tekst <math>x</math> zaczyna się od specjalnego symbolu (marker początku), który
+
Załóżmy, dla uproszczenia, że tekst <math>x</math> zaczyna się od specjalnego symbolu (marker początku), który występuje tylko na początku.
występuje tylko na początku.
+
 
Opiszemy algorytm, który oblicza tablice promieni palindromów dla kolejnych
+
Opiszemy algorytm, który oblicza tablice promieni palindromów dla kolejnych pozycji <math>i</math> od strony lewej do prawej. Załóżmy, że policzyliśmy już wartości:  
pozycji <math>i</math> od strony lewej do prawej, załóżmy że policzyliśmy już wartości:
 
 
<center><math>Rad[1],\, Rad[2],\, \dots ,\, Rad[i].</math></center>
 
<center><math>Rad[1],\, Rad[2],\, \dots ,\, Rad[i].</math></center>
Okazuje się, że korzystając z symetrii, możemy obliczyć pewne nowe elementy tablicy <math>Rad</math>
+
 
nie wykonując żdnych porównań symboli. Wynika to z następującego faktu. \myskip {\bf Własność promieni
+
Okazuje się, że korzystając z symetrii możemy obliczyć pewne nowe elementy tablicy <math>Rad</math>, nie wykonując żadnych porównań symboli. Wynika to z następującego faktu.
palindromów} <center><math>1\leq k\leq Rad[i]\ \textrm{oraz}\ Rad[i-k]\neq Rad[i]-k\ \Rightarrow\ Rad[i+k]=\min
+
 
(Rad[i-k],Rad[i]-k)</math></center> %
+
 
<!--%
+
'''Własność promieni palindromów'''
-->\myskip Uzasadnimy krótko tę własność rozważając dwa przypadki:
+
 
\begin{description}\itemsep0mm\topsep0mm
+
<center><math>1\leq k\leq Rad[i]\ \text{oraz}\ Rad[i-k]\neq Rad[i]-k\ \Rightarrow\ Rad[i+k]=\min (Rad[i-k],Rad[i]-k)</math></center>  
\item[Przypadek (a):] <math>Rad[i-k]<Rad[i]-k</math>.\\
+
 
Wówczas palindrom
+
Uzasadnimy krótko tę własność rozważając dwa przypadki:
<math>Rad[i-k]</math> o środeku w <math>i-k</math> jest całowicie zawarty w d"uższym palindromie o śrdoeku w <math>i</math>. Pozycja <math>i-k</math>
+
 
jest symetryczna do  <math>i+k</math> ze względu na <math>i</math>. Zatem z symetrii o środku <math>i</math> wynika,że najdłuższy palindrom o
+
 
środku  <math>i+k</math> m taki sam promień jak ten o środku  <math>i-k</math>.
+
'''Przypadek (a):''' <math>Rad[i-k]<Rad[i]-k</math>.
Zatem w tym przypadku  <math>Rad[i+k]=Rad[i-k]</math>.
+
 
<!--%************************************************************
+
Wówczas palindrom <math>Rad[i-k]</math> o środku w <math>i-k</math> jest całowicie zawarty w dłuższym palindromie o środku w <math>i</math>. Pozycja <math>i-k</math> jest symetryczna do  <math>i+k</math> ze względu na <math>i</math>. Zatem z symetrii o środku <math>i</math> wynika, że najdłuższy palindrom o środku  <math>i+k</math> ma taki sam promień jak ten o środku  <math>i-k</math>. Zatem w tym przypadku  <math>Rad[i+k]=Rad[i-k]</math>.
-->\begin{figure}%[htb]
+
 
\begin{center}
+
'''Przypadek (b):''' <math>Rad[i-k]>Rad[i]-k</math>.
\includegraphics[width=9.4cm]{teksty_fig22.eps}
+
 
\caption{
+
Sytuacja jest pokazna na rysunku, który przedstawia maksymalne palindromy o środkach <math>i-k</math>, <math>i</math> i <math>i+k</math>.
Przypadek  (b) dowodu własności promieni palindromów parzystych.}
 
<span id="figure8-5" \>
 
\end{center}
 
\end{figure}
 
<!--%**********************************************************
 
-->
 
\item[Przypadek (b):] <math>Rad[i-k]>Rad[i]-k</math>.\\
 
Sytuacja jest pokazna na rysunku, który przedsatwi maksymalne palindromy o środkach <math>i-k</math>, <math>i</math> and <math>i+k</math>.
 
 
Ponieważ <math>a\ne b</math> (z definicji maksymalności palindromu o środku w <math>i</math>), zatem <math>Rad[i+k]=Rad[i]-k</math>.
 
Ponieważ <math>a\ne b</math> (z definicji maksymalności palindromu o środku w <math>i</math>), zatem <math>Rad[i+k]=Rad[i]-k</math>.
\end{description}
+
 
\noindent
+
<center> [[Grafika:ZASD_3_3.jpg]]<br>Rysunek 3:
Poniżej przedstawiamy algorytm Promienie-Palindromów. W jednej iteracji {\em głównej pętli} while
+
Przypadek  (b) dowodu własności promieni palindromów parzystych.</center>
algorytm oblicza  <math>Rad[i+k]</math> dla kolejnych <math>k=1,2,\dots </math> dla których  <math>Rad[i-k]\neq Rad[i]-k</math>. Jeśli ostatnim takim <math>k</math> jest <math>k'</math>,
+
 
wtedy zaczynamy całą główną iterację od nowego <math>i</math> równego <math>i+k'</math>.
+
Poniżej przedstawiamy algorytm Promienie-Palindromów. W jednej głównej iteracji pętli while algorytm oblicza  <math>Rad[i+k]</math> dla kolejnych <math>k=1,2,\dots </math>, dla których  <math>Rad[i-k]\neq Rad[i]-k</math>. Jeśli ostatnim takim <math>k</math> jest <math>k'</math>,
\myskip
+
wtedy zaczynamy całą główną iterację od nowego <math>i</math> równego <math>i+k'</math>.
Pozostawiamy jako ćwiczenie modyfikację algorytmu aby liczył promienie palindromów nieparzystych.
+
 
\myskip
+
Pozostawiamy jako ćwiczenie modyfikację algorytmu, aby liczył promienie palindromów nieparzystych.
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 pierwszym 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:
W sumie pokazaliśmy następujący fakt:
+
 
%\vskip 0.1cm
+
'''(a) ''' Tablicę promieni palindromów (parzystych i nieparzystych) można policzyć w czasie liniowym.
\begin{description}
+
 
\item'''(a)\ '''
+
'''(b) ''' Długość <math>s</math> najkrótszego prefikso-palindromu (zakładając że taki istnieje) można policzyć w czasie
Tablicę promieni palindromów (parzystych i nieparzystych) można policzyć w czasie liniowym.
 
\item'''(b)\ '''
 
Długo"ć <math>s</math> najkrótszego prefikso-palindromu (zakładając że taki istnieje) można policzyć w czasie
 
 
proporcjonalnym do jego długości.
 
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*{0.6cm}\{ on-line computation of prefix even palindromes and of table <math>Rad</math>;\\
 
--><!--%\hspace*{0.9cm} <math>x</math> starts with a unique left end-marker \}\\
 
-->\hspace*{1.2cm} <math>Rad[1]:=0</math>; <math>j:=0</math>;
 
<!--%\{ <math>j=Rad[i]</math> \}
 
-->\\
 
\hspace*{1.2cm} <math>i:=2</math>;\vskip 0.2cm \noindent
 
\hspace*{1.2cm}\textbf{while} <math>i\leq \lfloor n/2\rfloor</math> \textbf{do }\\
 
\hspace*{1.8cm}\textbf{while} <math>x[i-j]=x[i+1+j]</math> \textbf{do} <math>j:=j+1</math>;\\
 
\hspace*{1.8cm}\textbf{if} <math>j=i</math> \textbf{then}  <math>Rad[i]:=j</math>;\\
 
\hspace*{1.8cm}<math>k:=1</math>;\\
 
\hspace*{1.8cm}\textbf{while} <math>Rad[i-k]\neq Rad[i]-k</math> \textbf{do }\\
 
\hspace*{2.4cm}<math>Rad[i+k]:=\min (Rad[i-k],Rad[i]-k)</math>; <math>k:=k+1</math>;\\
 
<!--%\hspace*{1.8cm}\textbf{end};\\
 
--><!--%\hspace*{1.8cm}\{ <math>invariant(i,j)</math>: <math>x[i-j]\neq x[i+j+1]</math> \}\\
 
-->\hspace*{1.8cm}<math>j:=max(j-k,0)</math>;\
 
<math>i:=i+k</math>;\\
 
<!--%\hspace*{1.2cm}\textbf{end}\\
 
-->\vskip0.4cm
 
\end{minipage}
 
\end{center}
 
<!--%-----------------------------------------------------------------
 
--><!--%--------+---------+---------+---------+---------+---------+---------+---------+
 
--> <span id="section8-2" \>  Rozważmy teraz intersujący (chociaż mało użyteczny w praktyce) problem sprawdzania, czy
 
słowo jest nietrywialną kompozycją słów symetrycznych. Przez <math>PAL_0^*, PAL^*</math> oznaczmy odpowiednio zbiór
 
konkatenacji dowolenj liczby słów należących do <math>PAL_0,\ PAL</math>.
 
Elementy <math>PAL^*</math> nazywamy {\em palstarami} a
 
elementy <math>PAL_0^*</math> nazywamy {\em palstarami parzystymi}. \myskip Niech <math>first(i)</math>, <math>first_0(i)</math> będzie
 
Ze względów technicznych załóżmy, że słowo puste teź jest palstarem (parzystm i nieparzystym jednocześnie).
 
odpowiednio pierwszą pozycją <math>j>i</math> w słowie <math>x</math> taką, że  <math>x[i.. j]\in PAL</math>, <math>x[i.. j]\in PAL_0</math>, wartością
 
funkcji jest zero gdy nie ma takiego <math>j</math>.
 
<!--%-----------------------------------------------------------------
 
-->\begin{center}
 
\begin{minipage}{9cm}
 
\vskip0.3cm \hspace*{0.6cm}\textbf{Algorytm} Parzyste-Palstary;
 
%\{ is <math>x</math> an even palstar ? \}\\
 
\hspace*{1.2cm}<math>s</math> := <math>0</math>;\\
 
\hspace*{1.2cm}\textbf{while} <math>s<n</math> \textbf{do }\\% \{ cut <math>x[s+1.. n]</math> \}\\
 
\hspace*{1.8cm} <math>s</math> := <math>s+1</math>;\\
 
\hspace*{1.8cm}\textbf{if} <math>first_0(s)=0</math> \textbf{then return} false;\\
 
\hspace*{1.8cm}<math>s:=first(s)</math>;\\
 
\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 <math>first_0(i)</math> zajmuje czas
 
proporcjonalny do wartości <math>s=first(i)</math>, zakładając, że <math>s \ne 0</math>.
 
Netrywialna natomiast jest poprawność algorytmu. Zdefiniujmy
 
\begin{center}
 
<math>parse_0(i)=\min \{j\ :\ x[i.. j]\in PAL_0</math> oraz <math>j=n</math> lub <math>x[j+1.. n]\in PAL_0^{*}\}</math>.
 
\end{center}
 
<!--%************************************************************
 
--><!--%\begin{figure}%[htb]
 
--><!--%\begin{center}
 
--><!--%\includegraphics[width=8.7cm]{Fig8-2.eps}
 
--><!--%\caption{
 
--><!--%The proof  (by contradiction) of Theorem&nbsp;[[#theorem8-13]].
 
--><!--%}
 
--><!--% <span id="figure8-6" \>
 
--><!--%\end{center}
 
--><!--%\end{figure}
 
--><!--%**********************************************************
 
-->
 
\noindent '''Własność parzystych palstarów:'''
 
\ <math>x[i..n] \in PAL_0^* \ \Rightarrow\ parse_0(i)=first_0(i)</math>
 
\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ę <math>parse(i)</math> 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}:
 
<math>x[i..n] \in PAL^* \ \Rightarrow\ parse(i)\in \{first(i),\ 2\cdot first(i)+1,\ 2\cdot first(i)-1\}</math>
 
\myskip
 
Pozostawimay dowód tej własności  jako ćwiczenie.
 
<!--%i wynikający z niej algorytm liniowy na palstary
 
-->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 <math>first</math>, obliczamy tablicę <math>FIRST[i]=first(i)</math>, w czasie
 
liniowym dla wszystkich <math>i</math> lącznie. \myskip Pozostawiamy jako ćwiczenie policzenie tej tablicy w czasie
 
<math>O(n)</math>. Obliczenie takie opiera się na wykorzystaniu tablicy promieni palindromów. \myskip Załóżmy teraz że
 
mamy tablicę FIRST, funkcja <math>first</math> działa teraz w czasie stałym (gotowe wartości z tablicy). Poniższy algorytm
 
dla każdej pozycji <math>i</math> sprawdza czy <math>x[i..n]\in PAL^*</math>. Odpowiedź jest zapisana w tablicy logicznej <math>PAL</math>.
 
Zakładamy, że początkowo tabica <math>PAL</math> 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;
 
<!--% \{ palstar recognition \}
 
-->\\
 
\hspace*{1.2cm}<math>PAL[n]:=</math> true; %\{ the empty word is a palstar \}
 
\\
 
\hspace*{1.2cm}\textbf{for} <math>i:=n-1</math> \textbf{down to} <math>0</math> \textbf{do }\\
 
\hspace*{1.7cm}<math>f:=FIRST[i]</math>;\\
 
\hspace*{1.7cm}\textbf{if} <math>f=0</math> \textbf{then} <math>PAL[i]:=</math> false\\
 
<!--%\hspace*{1.7cm}\textbf{else if} <math>PAL[i]</math> \textbf{then}
 
--><!--%<math>PAL[i]:=</math>true\\
 
-->\hspace*{1.7cm}\textbf{else}\
 
<math>PAL[i]:=\\
 
\hspace*{2.7cm} (PAL[i+f]</math> \textbf{or} <math>PAL[i+2f-1]</math>
 
\textbf{or} <math>PAL[i+2f+1])</math>\\
 
<!--%\hspace*{1.2cm}\textbf{end;}\\
 
--><!--%\hspace*{1.2cm}\textbf{return} <math>PAL[0]</math>;\\
 
-->\vskip0.4cm
 
\end{minipage}
 
\end{center}
 
<!--%-----------------------------------------------------------------
 
-->
 
  
\noindent
+
 
Intersującym problemem jest rozkład słowa <math>x</math> w postaci <math>PAL^k</math>, gdzie <math>k</math> jest ustalone.
+
{{algorytm|Promienie-Palindromów|algorytm_prom_palind|
Istnieją algorytmy liniowe dla <math>k=2,3,4</math> oparte na następującej własności zawężającej zbiór rozkładów
+
<math>Rad[1]:=0</math>; <math>j:=0</math>;<br>
do zweryfikowania:
+
<math>i:=2</math>;<br>
jeśli <math>x \in PAL^2</math> to <math>x=uv</math>, dla pewnych <math>u,v \in PAL</math> gdzie <math>u</math> jest najdłuższym palindromem będącym prefiksem
+
 
<math>x</math> lub <math>v</math> jest najdłuższym palindromem będącym sufiksem  <math>x</math>.
+
'''while''' <math>i\leq \lfloor n/2\rfloor</math> '''do'''<br>
 +
&nbsp;&nbsp;&nbsp;'''while''' <math>x[i-j]=x[i+1+j]</math> '''do''' <math>j:=j+1</math>;<br>
 +
&nbsp;&nbsp;&nbsp;<math>Rad[i]:=j</math>;<br>
 +
&nbsp;&nbsp;&nbsp;<math>k:=1</math>;<br>
 +
&nbsp;&nbsp;&nbsp;'''while''' <math>Rad[i-k]\neq Rad[i]-k</math> '''do''' <br>
 +
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>Rad[i+k]:=\min (Rad[i-k],Rad[i]-k)</math>; <math>k:=k+1</math>;<br>
 +
&nbsp;&nbsp;&nbsp;<math>j:=max(j-k,0)</math>;<math>i:=i+k</math>;<br>
 +
}}
 +
 
 +
== Kompozycje słów symetrycznych ==
 +
 
 +
Rozważmy teraz interesujący (chociaż tylko czysto teoretyczny ) problem sprawdzania, czy słowo jest nietrywialną kompozycją słów symetrycznych. Przez <math>PAL_0^*, PAL^*</math> oznaczmy odpowiednio zbiór konkatenacji dowolnej liczby słów należących do <math>PAL_0,\ PAL</math>.
 +
 
 +
Elementy <math>PAL^*</math> nazywamy ''palstarami'' a elementy <math>PAL_0^*</math> nazywamy ''palstarami parzystymi''.
 +
 
 +
Niech <math>first(i)</math>, <math>first_0(i)</math> będzie (ze względów technicznych załóżmy, że słowo puste też jest palstarem (parzystm i nieparzystym jednocześnie)) odpowiednio pierwszą pozycją <math>j>i</math> w słowie <math>x</math> taką, że <math>x[i.. j]\in PAL</math>, <math>x[i.. j]\in PAL_0</math>, wartością funkcji zaś jest zero, gdy nie ma takiego <math>j</math>.
 +
 
 +
 
 +
{{algorytm|Parzyste-Palstary|algorytm_parz_palstary|
 +
<math>s  := 0</math>;<br>
 +
'''while''' <math>s<n</math> ''do''
 +
&nbsp;&nbsp;&nbsp;<math>s := s+1</math>;<br>
 +
&nbsp;&nbsp;&nbsp;'''if''' <math>first_0(s)=0</math> '''then return''' false;<br>
 +
&nbsp;&nbsp;&nbsp;<math>s:=first(s)</math>;<br>
 +
'''return''' true;
 +
}}
 +
 
 +
 
 +
Mówiąc nieformalnie, algorytm Parzyste-Palstary obcina słowo o najkrótszy prefikso-palindrom, aż tekst będzie pusty (sukces) albo aż się '' zatnie'' (nie ma rozkładu na parzyste palindromy). Algorytm Parzyste-Palstary ma złożoność liniową, ponieważ policzenie <math>first_0(i)</math> zajmuje czas proporcjonalny do wartości <math>s=first(i)</math>, zakładając, że <math>s \ne 0</math>.  Nietrywialna natomiast jest poprawność algorytmu. Zdefiniujmy
 +
 
 +
<center> <math>parse_0(i)=\min \{j\ :\ x[i.. j]\in PAL_0</math> oraz <math>j=n</math> lub <math>x[j+1.. n]\in PAL_0^{*}\}</math></center>
 +
 
 +
 
 +
'''Własność parzystych palstarów:''' <math>x[i..n] \in PAL_0^* \ \Rightarrow\ parse_0(i)=first_0(i)</math>
 +
 
 +
Poprawność algorytmu wynika natychmiast z powyższej własności. Pozostawiamy dowód tej własności jako ćwiczenie.
 +
 
 +
Możemy podobnie zdefiniować funkcję <math>parse(i)</math> 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.
 +
 
 +
'''Własność dowolnych palstarów:<br>
 +
<center> <math>x[i..n] \in PAL^* \ \Rightarrow\ parse(i)\in \{first(i),\ 2\cdot first(i)+1,\ 2\cdot first(i)-1\}</math></center>
 +
 
 +
 
 +
Pozostawimay dowód tej własności jako ćwiczenie. Algorytm testowania dowolnych palstarów jest interesujący, ponieważ przebiega on zupełnie inaczej niż dla parzystych palstarów.
 +
 
 +
Pierwszym krokiem algorytmu jest stablicowanie funkcji <math>first</math>. Obliczamy tablicę <math>FIRST[i]=first(i)</math> w czasie
 +
liniowym dla wszystkich <math>i</math> łącznie.
 +
 
 +
Pozostawiamy jako ćwiczenie policzenie tej tablicy w czasie <math>O(n)</math>. Obliczenie takie opiera się na wykorzystaniu tablicy promieni palindromów.
 +
 
 +
Załóżmy teraz, że mamy tablicę FIRST. Funkcja <math>first</math> działa teraz w czasie stałym (gotowe wartości z tablicy). Poniższy algorytm
 +
dla każdej pozycji <math>i</math> sprawdza, czy <math>x[i..n]\in PAL^*</math>. Odpowiedź jest zapisana w tablicy logicznej <math>PAL</math>.
 +
Zakładamy, że początkowo tablica <math>PAL</math> ma wartości \mathit{ false}, włącznie z elementami wykraczającymi poza zakres tablicy (dla uproszczenia zapisu).
 +
 
 +
 
 +
{{algorytm|Testowanie-Palstarów|algorytm_testowanie_palstarow|
 +
<math>PAL[n]:=</math> true; <br>
 +
'''for''' <math>i:=n-1</math> '''down to''' <math>0</math> '''do'''
 +
&nbsp;&nbsp;&nbsp;<math>f:=FIRST[i]</math>;<br>
 +
&nbsp;&nbsp;&nbsp;'''if''' <math>f=0</math> '''then''' <math>PAL[i]:=</math> false<br>
 +
&nbsp;&nbsp;&nbsp;'''else''' <math>PAL[i]:= (PAL[i+f]</math> or <math>PAL[i+2f-1]</math> or <math>PAL[i+2f+1])</math>
 +
 
 +
}}
 +
 
 +
 
 +
Interesującym problemem jest rozkład słowa <math>x</math> w postaci <math>PAL^k</math>, gdzie <math>k</math> jest ustalone. Istnieją algorytmy liniowe dla <math>k=2,3,4</math> oparte na następującej własności zawężającej zbiór rozkładów do zweryfikowania:  
 +
 
 +
jeśli <math>x \in PAL^2</math> to <math>x=uv</math>, dla pewnych <math>u,v \in PAL</math> gdzie <math>u</math> jest najdłuższym palindromem będącym prefiksem <math>x</math> lub <math>v</math> jest najdłuższym palindromem będącym sufiksem  <math>x</math>.

Aktualna wersja na dzień 13:38, 9 cze 2020

Zaawansowane algorytmy tekstowe III



W module tym zajmiemy się wykrywaniem regularności w tekstach: szukaniem symetrii.

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


Wykrywanie symetrii w tekstach

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:

kajak, atypotopyta, zagwiżdżiwgaz


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 .


Algorytm Prefikso-Palindrom


  1. oblicz tablicę P dla słowa-kompozycji (słowo długości ),
  2. jeśli to jest to długość najdłuższego prefikso-palindromu
  3. w przeciwnym przypadku nie ma prefikso-palindromu.

Podobnie możemy zdefiniować problem najkrótszego prefisko-palindromu. Algorytm powyższy można łatwo zmodyfikować, aby znajdował najkrótszy prefikso-palindrom.

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, założywszy że tekst posiada prefikso-palindrom.

Skoncentrujemy się na razie na palindromach parzystych. Definiujemy dla każdej pozycji promień palindromu parzystego o środku w jako:

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 żadnych porównań symboli. Wynika to z następującego faktu.


Własność promieni palindromów

Uzasadnimy krótko tę własność rozważając dwa przypadki:


Przypadek (a): .

Wówczas palindrom o środku w jest całowicie zawarty w dłuższym palindromie o środku w . Pozycja jest symetryczna do ze względu na . Zatem z symetrii o środku wynika, że najdłuższy palindrom o środku ma taki sam promień jak ten o środku . Zatem w tym przypadku .

Przypadek (b): .

Sytuacja jest pokazna na rysunku, który przedstawia maksymalne palindromy o środkach , i . Ponieważ (z definicji maksymalności palindromu o środku w ), zatem .

ZASD 3 3.jpg
Rysunek 3: Przypadek (b) dowodu własności promieni palindromów parzystych.

Poniżej przedstawiamy algorytm Promienie-Palindromów. W jednej głównej iteracji 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 .

Pozostawiamy jako ćwiczenie modyfikację algorytmu, aby liczył promienie palindromów nieparzystych.

W pierwszym 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:

(a) Tablicę promieni palindromów (parzystych i nieparzystych) można policzyć w czasie liniowym.

(b) Długość najkrótszego prefikso-palindromu (zakładając że taki istnieje) można policzyć w czasie proporcjonalnym do jego długości.


Algorytm Promienie-Palindromów


; ;
;

while do
   while do ;
   ;
   ;
   while do
      ; ;
   ;;

Kompozycje słów symetrycznych

Rozważmy teraz interesujący (chociaż tylko czysto teoretyczny ) problem sprawdzania, czy słowo jest nietrywialną kompozycją słów symetrycznych. Przez oznaczmy odpowiednio zbiór konkatenacji dowolnej liczby słów należących do .

Elementy nazywamy palstarami a elementy nazywamy palstarami parzystymi.

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 zaś jest zero, gdy nie ma takiego .


Algorytm Parzyste-Palstary


;
while do    ;
   if then return false;
   ;
return true;


Mówiąc nieformalnie, algorytm Parzyste-Palstary obcina słowo o najkrótszy prefikso-palindrom, aż tekst będzie pusty (sukces) albo aż się 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 . Nietrywialna natomiast jest poprawność algorytmu. Zdefiniujmy

oraz lub


Własność parzystych palstarów:

Poprawność algorytmu wynika natychmiast z powyższej własności. Pozostawiamy dowód tej własności jako ćwiczenie.

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.

Własność dowolnych palstarów:


Pozostawimay dowód tej własności jako ćwiczenie. Algorytm testowania dowolnych palstarów jest interesujący, ponieważ przebiega on zupełnie inaczej niż dla parzystych palstarów.

Pierwszym krokiem algorytmu jest stablicowanie funkcji . Obliczamy tablicę w czasie liniowym dla wszystkich łącznie.

Pozostawiamy jako ćwiczenie policzenie tej tablicy w czasie . Obliczenie takie opiera się na wykorzystaniu tablicy promieni palindromów.

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 tablica ma wartości \mathit{ false}, włącznie z elementami wykraczającymi poza zakres tablicy (dla uproszczenia zapisu).


Algorytm Testowanie-Palstarów


true;
for down to do    ;
   if then false
   else or or



Interesują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 .