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

Aktualna wersja na dzień 22:15, 11 wrz 2023

Zaawansowane algorytmy tekstowe III

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

Słowo jest symetryczne, gdy $x = x^{R}$ , gdzie $R$ jest operacją odwracania słowa. Algorytmicznie symetrie w słowach są bardzo interesujące.

Wykrywanie symetrii w tekstach

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 $P A L$ , a przez $P A L_{0}, P A L_{1}$ 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 $x = u v$ takim, że $u \in P A L$ oraz $u$ jest najdłuższy o tej własności. Istnieje prosty algorytm oparty na tablicy prefikso-sufiksów $P$ .

Algorytm Prefikso-Palindrom

oblicz tablicę P dla słowa-kompozycji $x # x^{R}$ (słowo długości $2 n + 1$ ),
jeśli $P (2 n + 1) > 0$ to jest to długość najdłuższego prefikso-palindromu
w przeciwnym przypadku $x$ 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 $O (s)$ , gdzie $s$ 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 $i$ promień palindromu parzystego o środku w $i$ jako:

R a d [i] = \max {j : j = 0 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:

R a d [1], R a d [2], \dots, R a d [i]

Okazuje się, że korzystając z symetrii możemy obliczyć pewne nowe elementy tablicy $R a d$ , nie wykonując żadnych porównań symboli. Wynika to z następującego faktu.

Własność promieni palindromów

1 \leq k \leq R a d [i] oraz R a d [i - k] \neq R a d [i] - k \Rightarrow R a d [i + k] = \min (R a d [i - k], R a d [i] - k)

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

Przypadek (a): $R a d [i - k] < R a d [i] - k$ .

Wówczas palindrom $R a d [i - k]$ o środku w $i - k$ jest całowicie zawarty w dłuższym palindromie o środku 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$ ma taki sam promień jak ten o środku $i - k$ . Zatem w tym przypadku $R a d [i + k] = R a d [i - k]$ .

Przypadek (b): $R a d [i - k] > R a d [i] - k$ .

Sytuacja jest pokazna na rysunku, który przedstawia maksymalne palindromy o środkach $i - k$ , $i$ i $i + k$ . Ponieważ $a \neq b$ (z definicji maksymalności palindromu o środku w $i$ ), zatem $R a d [i + k] = R a d [i] - k$ .

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 $R a d [i + k]$ dla kolejnych $k = 1, 2, \dots$ , dla których $R a d [i - k] \neq R a d [i] - k$ . Jeśli ostatnim takim $k$ jest $k^{'}$ , wtedy zaczynamy całą główną iterację od nowego $i$ równego $i + k^{'}$ .

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ść $s$ 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

$R a d [1] : = 0$ ; $j : = 0$ ;
$i : = 2$ ;

while $i \leq ⌊ n / 2 ⌋$ do
   while $x [i - j] = x [i + 1 + j]$ do $j : = j + 1$ ;
    $R a d [i] : = j$ ;
    $k : = 1$ ;
   while $R a d [i - k] \neq R a d [i] - k$ do
       $R a d [i + k] : = \min (R a d [i - k], R a d [i] - k)$ ; $k : = k + 1$ ;
    $j : = m a x (j - k, 0)$ ; $i : = i + k$ ;

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 $P A L_{0}^{*}, P A L^{*}$ oznaczmy odpowiednio zbiór konkatenacji dowolnej liczby słów należących do $P A L_{0}, P A L$ .

Elementy $P A L^{*}$ nazywamy palstarami a elementy $P A L_{0}^{*}$ nazywamy palstarami parzystymi.

Niech $f i r s t (i)$ , $f i r s 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 P A L$ , $x [i . . j] \in P A L_{0}$ , wartością funkcji zaś jest zero, gdy nie ma takiego $j$ .

Algorytm Parzyste-Palstary

$s : = 0$ ;
while $s < n$ do     $s : = s + 1$ ;
   if $f i r s t_{0} (s) = 0$ then return false;
    $s : = f i r s t (s)$ ;
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 $f i r s t_{0} (i)$ zajmuje czas proporcjonalny do wartości $s = f i r s t (i)$ , zakładając, że $s \neq 0$ . Nietrywialna natomiast jest poprawność algorytmu. Zdefiniujmy

p a r s e_{0} (i) = \min {j : x [i . . j] \in P A L_{0}

oraz

j = n

lub

x [j + 1 . . n] \in P A L_{0}^{*}}

Własność parzystych palstarów: $x [i . . n] \in P A L_{0}^{*} \Rightarrow p a r s e_{0} (i) = f i r s t_{0} (i)$

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

Możemy podobnie zdefiniować funkcję $p a r s e (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.

Własność dowolnych palstarów:

x [i . . n] \in P A L^{*} \Rightarrow p a r s e (i) \in {f i r s t (i), 2 \cdot f i r s t (i) + 1, 2 \cdot f i r s t (i) - 1}

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 $f i r s t$ . Obliczamy tablicę $F I R S T [i] = f i r s t (i)$ w czasie liniowym dla wszystkich $i$ łącznie.

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

Załóżmy teraz, że mamy tablicę FIRST. Funkcja $f i r s t$ 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 P A L^{*}$ . Odpowiedź jest zapisana w tablicy logicznej $P A L$ . Zakładamy, że początkowo tablica $P A L$ ma wartości \mathit{ false}, włącznie z elementami wykraczającymi poza zakres tablicy (dla uproszczenia zapisu).

Algorytm Testowanie-Palstarów

$P A L [n] : =$ true;
for $i : = n - 1$ down to $0$ do     $f : = F I R S T [i]$ ;
   if $f = 0$ then $P A L [i] : =$ false
   else $P A L [i] : = (P A L [i + f]$ or $P A L [i + 2 f - 1]$ or $P A L [i + 2 f + 1])$

Interesującym problemem jest rozkład słowa $x$ w postaci $P A 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 P A L^{2}$ to $x = u v$ , dla pewnych $u, v \in P A L$ gdzie $u$ jest najdłuższym palindromem będącym prefiksem $x$ lub $v$ jest najdłuższym palindromem będącym sufiksem $x$ .

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

Aktualna wersja na dzień 22:15, 11 wrz 2023

Spis treści

Wykrywanie symetrii w tekstach

Kompozycje słów symetrycznych

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ 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.
-== 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 <br>
+==Wykrywanie symetrii w tekstach ==
-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>.
+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.
-Oznaczmy przez <math>LZ(x)</math> faktoryzację <math>x</math>.
+Przykładami palindromów są słowa:
-<center> [[Grafika:ZASD_3_1.jpg]]<br>Rysunek 1:
+ <center>kajak,  atypotopyta,  zagwiżdżiwgaz </center>
-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.
-</center>
-'''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
-. <math>PREF[k]</math>: długość maksymalnego podsłowa zaczynającego się w <math>k</math> i będącego prefiksem <math>v</math>;
-. <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>
+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
-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>.
+najdłuższy  o tej własności. Istnieje prosty algorytm oparty na tablicy prefikso-sufiksów <math>P</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>
-Wtedy <math>x</math> zawiera powtórzenie wtedy i tylko wtedy gdy dla pewnego <math>k</math> zachodzi
+{{algorytm |Prefikso-Palindrom|algorytm_prfikso_palindrom|
-<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>
+#oblicz tablicę P dla słowa-kompozycji <math>x\#x^{R}</math> (słowo długości  <math>2n+1</math>),
-\myskip
+#jeśli  <math>P(2n+1)>0</math> to jest to długość najdłuższego  prefikso-palindromu
-\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ę <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}\\
-\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>;\\
-\hspace*{1.8cm} <math>u2</math> := <math>z_1, z_2\ldots z_{k-1}</math>;\ <math>v2</math> := <math>z_k</math>;\\
-\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.
-\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.
-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>
+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.
-nie wykonując żdnych porównań symboli. Wynika to z następującego faktu. \myskip {\bf Własność promieni
-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:
+<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>
-\begin{description}\itemsep0mm\topsep0mm
-\item[Przypadek (a):] <math>Rad[i-k]<Rad[i]-k</math>.\\
+Uzasadnimy krótko tę własność rozważając dwa przypadki:
-Wówczas palindrom
-<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
+'''Przypadek (a):''' <math>Rad[i-k]<Rad[i]-k</math>.
-środku  <math>i+k</math> m taki sam promień jak ten o środku  <math>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]
+'''Przypadek (b):''' <math>Rad[i-k]>Rad[i]-k</math>.
-\begin{center}
-\includegraphics[width=9.4cm]{teksty_fig22.eps}
+Sytuacja jest pokazna na rysunku, który przedstawia maksymalne palindromy o środkach <math>i-k</math>, <math>i</math> i <math>i+k</math>.
-\caption{
-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>.
-\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.
-\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>.