X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=10-suffix%2F10-suffix.tex;h=d3590c7762492025031f4673b0f8c51414a2744f;hb=06fec68f809c5c280aaabba1168e86bb3cc707c9;hp=9ebcbc1dc64b8bc968cb57917fc4a6ec0793ed1b;hpb=895c3fb1a80685bee7c016ac4cad0ff3ce5f6d9a;p=ga.git

diff --git a/10-suffix/10-suffix.tex b/10-suffix/10-suffix.tex
index 9ebcbc1..d3590c7 100644
--- a/10-suffix/10-suffix.tex
+++ b/10-suffix/10-suffix.tex
@@ -91,14 +91,14 @@ kolik pod n
 najít vnitøní vrchol s~nejvìt¹í {\I písmenkovou hloubkou} (tj. hloubkou mìøenou ve~znacích
 místo ve~hranách).
 
-\:{\I Histogram èetností podslov délky~$k$} -- rozøízneme ST v~písmenkové hloubce~$k$ a spoèítáme,
+\:{\I Histogram èetností podslov délky~$k$} -- rozøízneme ST\$ v~písmenkové hloubce~$k$ a spoèítáme,
 kolik pùvodních listù je pod ka¾dým novým.
 
 \:{\I Nejdel¹í spoleèné podslovo} slov~$\alpha$ a $\beta$ -- postavíme ST pro slovo $\alpha\$_1\beta\$_2$,
 jeho listy odpovídají suffixùm slov $\alpha$ a $\beta$. Tak¾e staèí pomocí DFS najít nejhlub¹í vnitøní
 vrchol, pod kterým se vyskytují listy pro~$\alpha$ i $\beta$. Podobnì mù¾eme sestrojit ST\$ pro libovolnou
-mno¾inu slov.\foot{Jen si musíme dát pozor, abychom si moc nezvìt¹ili abecedu, ale to bude jasné,
-a¾ pøedvedeme konkrétní konstrukce.}
+mno¾inu slov.\foot{Jen si musíme dát pozor, abychom si moc nezvìt¹ili abecedu; jak moc si ji
+mù¾eme dovolit zvìt¹it, vyplyne z~konkrétních konstrukcí.}
 
 \:{\I Nejdel¹í palindromické podslovo} (tj. takové $\beta\subset\alpha$, pro nì¾ je $\beta^R=\beta$)
 -- postavíme spoleèný ST\$ pro slova $\alpha$ a $\alpha^R$. Postupnì procházíme pøes v¹echny mo¾né støedy
@@ -117,40 +117,41 @@ u
 
 \s{Cvièení:} Zkuste vymyslet co nejlep¹í algoritmy pro tyto problémy bez pou¾ití~ST.
 
-\h{Suffix Array}
+\h{Suffixová pole}
 
 \>V~nìkterých pøípadech se hodí místo suffixového stromu pou¾ívat kompaktnìj¹í datové struktury.
 
-\s{Notace:} Pro slovo $\sigma$ bude $\sigma[i]$ znaèit jeho $i$-tý znak (èíslujeme od~jednièky),
-$\sigma[i:j]$ pak podslovo slo¾ené z~$i$-tého a¾ $j$-tého znaku. Libovolnou z~mezí mù¾eme vynechat, proto
-$\sigma[i:{}]$ bude suffix od~$i$ do~konce a $\sigma[{}:j]$ prefix od~zaèátku do~$j$.
-Pokud $j<i$, definujeme $\sigma[i:j]$ jako prázdné slovo, tak¾e prázdný suffix mù¾eme
-napøíklad zapsat jako $\sigma[\vert\sigma\vert+1:{}].$
+\s{Notace:} Pro slovo $\sigma$ bude $\sigma[i]$ znaèit jeho $i$-tý znak (èíslujeme od~nuly),
+$\sigma[i:j]$ pak podslovo $\sigma[i]\sigma[i+1]\ldots\sigma[j-1]$. Libovolnou z~mezí mù¾eme vynechat, proto
+$\sigma[i:{}]$ bude suffix od~$i$ do~konce a $\sigma[{}:j]$ prefix od~zaèátku do~$j-1$.
+Pokud $j\le i$, definujeme $\sigma[i:j]$ jako prázdné slovo, tak¾e prázdný suffix mù¾eme
+napøíklad zapsat jako $\sigma[\vert\sigma\vert:{}].$
 
 ${\rm LCP}(\alpha,\beta)$ bude znaèit délku nejdel¹ího spoleèného prefixu slov $\alpha$ a $\beta$,
 èili nejvìt¹í $i\le \vert\alpha\vert,\vert\beta\vert$ takové, ¾e $\alpha[{}:i]=\beta[{}:i]$.
 
-\s{Definice:} {\I Suffix Array} $A_\sigma$ pro slovo $\sigma$ délky~$n$ je posloupnost v¹ech suffixù
+\s{Definice:} {\I Suffixové pole (Suffix Array)} $A_\sigma$ pro slovo $\sigma$ délky~$n$ je posloupnost v¹ech suffixù
 slova~$\sigma$ v~lexikografickém poøadí. Mù¾eme ho reprezentovat napøíklad jako permutaci $A$ èísel
-$1,\ldots,n+1$, pro ní¾ $\sigma[A[1]:{}] < \sigma[A[2]:{}] < \ldots < \sigma[A[n+1]:]$.
+$0,\ldots,n$, pro ní¾ $\sigma[A[0]:{}] < \sigma[A[1]:{}] < \ldots < \sigma[A[n]:{}]$.
 
-\s{Definice:} {\I Longest Common Prefix Array} $L_\sigma$ pro slovo $\sigma$ je posloupnost,
+\s{Definice:} {\I Pole nejdel¹ích spoleèných prefixù (Longest Common Prefix Array)} $L_\sigma$ pro slovo $\sigma$ je posloupnost,
 v~ní¾ $L_\sigma[i]:={\rm LCP}(A_\sigma[i],A_\sigma[i+1])$.
 
-\s{Vìta:} Suffixový strom pro slovo $\sigma\$$ je lineárnì ekvivalentní s~dvojicí $(A_\sigma,L_\sigma)$.
-[Jinými slovy, kdy¾ máme jedno, mù¾eme z~toho v~lineárním èase spoèítat druhé, a naopak.]
+\s{Vìta:} Suffixový strom pro slovo $\sigma\$$ a dvojici $(A_\sigma,L_\sigma)$ na sebe lze
+v~lineárním èase pøevádìt.
 
-\proof Kdy¾ projdeme ST($\sigma\$$) do hloubky, poøadí listù odpovídá $A_\sigma$ a písmenkové hloubky vnitøních
-vrcholù v~inorderu odpovídají $L_\sigma$. Naopak ST($\sigma$) získáme tak, ¾e sestrojíme kartézský strom
+\proof Kdy¾ projdeme ST($\sigma\$$) do hloubky, poøadí listù odpovídá posloupnosti $A_\sigma$ a písmenkové hloubky vnitøních
+vrcholù v~inorderu odpovídají $L_\sigma$. Naopak ST($\sigma\$$) získáme tak, ¾e sestrojíme kartézský strom
 pro~$L_\sigma$ (získáme vnitøní vrcholy ST), doplníme do~nìj listy, pøiøadíme jim suffixy podle~$A_\sigma$
 a nakonec podle listù rekonstruujeme nálepky hran.
 \qed
 
 \h{Rekurzivní konstrukce}
 
-\>Tento algoritmus konstruuje pro slovo $\sigma$ délky~$n$ jeho suffix array a LCP array v~èase $\O(n+{\rm Sort}(n,\Sigma))$,
-kde ${\rm Sort}(\ldots)$ je èas potøebný pro setøídìní $n$ symbolù z~abecedy~$\Sigma$. V~kombinaci s~pøedchozími
-výsledky nám tedy dává lineární konstrukci ST($\sigma$) pro libovolnou fixní abecedu.
+\>Uká¾eme algoritmus, který pro slovo $\sigma\in\Sigma^*$ délky~$n$ sestrojí jeho suffixové pole
+a LCP pole v~èase $\O(n+{\rm Sort}(n,\Sigma))$, kde ${\rm Sort}(\ldots)$ je èas potøebný pro setøídìní
+$n$~symbolù z~abecedy~$\Sigma$. V~kombinaci s~pøedchozími výsledky tedy dostaneme lineární konstrukci
+ST($\sigma$) pro libovolnou fixní abecedu.
 
 \s{Algoritmus:} (Konstrukce $A$ a $L$ podle Kärkkäinena a Sanderse \cite{karkkainen03simple})
 
@@ -169,36 +170,47 @@ si m
 
 \:Zavoláme algoritmus rekurzivnì na slovo $\sigma_0\sigma_1$, èím¾ získáme $A_{01}$ a $L_{01}$.
 
-\:Z~$A_{01}$ a $L_{01}$ vydìlíme $A_0=A_{\sigma_0}$, $A_1$, $L_0$ a $L_1$. Také si pro ka¾dý prvek
-$A_i$ zapamatujeme, kde se v~$A_{01}$ vyskytoval.
+\:Spoèítáme pole $P_0$ a $P_1$, která nám budou øíkat, kde se v~$A_{01}$ vyskytuje
+který suffix slov $\sigma_0$ a~$\sigma_1$. Tedy $A_{01}[P_0[i]]=i$, $A_{01}[P_1[i]] = i+\vert\sigma_0\vert$.
+Jinými slovy, $P_0$ a~$P_1$ budou èásti inverzní permutace k~$A_{01}$. V¹imnìte si,
+¾e platí $P_i[x] < P_j[y]$ právì tehdy, kdy¾ $\sigma_i[x:{}] < \sigma_j[y:{}]$, tak¾e
+suffixy slov $\sigma_0$ a~$\sigma_1$ od této chvíle dovedeme porovnávat v~konstantním èase.
 
-\:Dopoèítáme $A_2$: Jeliko¾ $\sigma_2[i:{}] = \sigma[3i+2:{}] = \sigma[3i+2]\sigma[3i+3:\nobreak{}\nobreak] = \sigma[3i+2]\sigma_0[i+1:{}]$
-a v¹echna $\sigma_0[i:{}]$ u¾ máme setøídìná, mù¾eme v¹echna $\sigma_2[i:{}]$ setøídit dvìma prùchody pøihrádkového tøídìní.
+\:Vytvoøíme~$A_2$: Jeliko¾ $\sigma_2[i:{}] = \sigma[3i+2:{}] = \sigma[3i+2]\sigma[3i+3:\nobreak{}\nobreak] = \sigma[3i+2]\sigma_0[i+1:{}]$,
+odpovídá lexikografické poøadí suffixù $\sigma_2[i:{}]$ poøadí dvojic $(\sigma[3i+2],P_0[i+1])$.
+Tyto dvojice ov¹em mù¾eme setøídit dvìma prùchody pøihrádkového tøídìní.
 
-\:Dopoèítáme $L_2$: Stejným trikem jako $A_2$ -- pokud jsou první písmena rùzná, je spoleèný prefix prázdný, jinak
-má délku $1+{\rm LCP}(\sigma_0[i+1:{}],\sigma_0[j+1:{}]) = 1+\min_{i+1\le k< j+1} L_0[k]$. Minimum zvládneme pro ka¾dou
-dvojici $i,j$ spoèítat v~konstantním èase pomocí datové struktury pro intervalová minima.
-
-\:$A_0,A_1,A_2\buildrel merge\over\longrightarrow A$ -- sléváme tøi setøídìné posloupnosti,
-tak¾e staèí umìt prvky libovolných dvou posloupností v~konstantním èase porovnat:
+\:Slijeme $A_{01}$ a~$A_2$ do~$A$: sléváme dvì setøídìné posloupnosti,
+tak¾e staèí umìt jejich prvky v~konstantním èase porovnat:
 $$\eqalign{
-\sigma_0[i:{}] < \sigma_1[j:{}] &~\hbox{podle zapamatovaných pozic v~$A_{01}$} \cr
-\sigma_0[i:{}] < \sigma_2[k:{}] &\equiv \sigma[3i]\,\sigma_1[i:{}] < \sigma[3k+2]\,\sigma_0[k+1:{}]\cr
-&\Leftrightarrow (\sigma[3i] < \sigma[3k+2]) \vee {} \cr&\hphantom{{}\Leftrightarrow{}} (\sigma[3i] = \sigma[3k+2] \wedge \sigma_1[i:{}] < \sigma_0[k+1:{}])\cr
-\sigma_1[j:{}]<\sigma_2[k:{}] &\equiv \sigma[3j+1]\,\sigma[3j+2]\,\sigma_0[j+1:{}] < \cr&\hphantom{{}\equiv{}} \sigma[3k+2]\,\sigma[3k+3]\,\sigma_1[k+1:{}]
+\sigma_0[i:{}] < \sigma_2[k:{}] \Leftrightarrow{} &\sigma[3i:{}] < \sigma[3k+2:{}] \cr
+                                \Leftrightarrow{} &\sigma[3i]\,\sigma_1[i:{}] < \sigma[3k+2]\,\sigma_0[k+1:{}],\cr
+\sigma_1[i:{}] < \sigma_2[k:{}] \Leftrightarrow{} &\sigma[3i+1:{}] < \sigma[3k+2:{}] \cr
+                                \Leftrightarrow{} &\sigma[3i+1]\,\sigma[3i+2]\,\sigma_0[i+1:{}] < \cr
+                                                  &\sigma[3k+2]\,\sigma[3k+3]\,\sigma_1[k+1:{}].\cr
 }$$
-
-\:Dopoèítáme $L$ -- pokud sousedí suffix ze~$\sigma_{0,1}$ se suffixem ze~$\sigma_{0,1}$,
-vyèteme výsledek pøímo z~$L_{01}$. Pokud sousedí $\sigma_2$ se $\sigma_2$, staèí pou¾ít
-u¾ spoèítané $L_2$. Pokud sousedí $\sigma_{0,1}$ se $\sigma_2$, odebereme první jeden
-nebo dva znaky, ty porovnáme samostatnì a v~pøípadì shody zbude suffix ze~$\sigma_0$
-a suffix ze~$\sigma_1$ (stejnì jako pøi slévání) a pro ty doká¾eme $L$ dopoèítat
-pomocí struktury pro intervalová minima v~$L_{01}$.
+Poka¾dé tedy porovnáme nejvý¹e dvì dvojice znakù a pak dvojici suffixù slov $\sigma_0$ a $\sigma_1$,
+k~èemu¾ nám pomohou pole $P_0$ a~$P_1$.
+
+\:Dopoèítáme $L$:
+   \::Pokud v~$A$ sousedí suffix ze~$\sigma_{0,1}$ se suffixem ze~$\sigma_{0,1}$,
+      sousedí tyto dva suffixy i v~$A_{01}$, tak¾e jejich LCP najdeme pøímo v~$L$.
+   \::Setkají-li se dva suffixy ze~$\sigma_2$, v¹imneme si, ¾e
+      $\sigma_2[i:{}] = \sigma[3i+2:\nobreak{}] = \sigma[3i+2]\,\sigma_0[i+1:{}]$.
+      ${\rm LCP}(\sigma_2[i:{}],\sigma_2[j:{}])$ je tedy buïto~0 (pokud $\sigma[3i+2]\ne\sigma[3j+2]$),
+      nebo $1+3\cdot{\rm LCP}(\sigma_0[i+1:{}],\sigma_0[j+1:{}])$, pøípadnì toté¾ zvý¹ené
+      o~1 nebo~2, pokud se trojznaky v~$\sigma_0$ následující po LCP zèásti shodují.
+      Pøitom ${\rm LCP}(\sigma_0[p:{}],\sigma_0[q:{}])$ spoèítáme pomocí~$L$.
+      Je to toti¾ minimum intervalu v~$L$ mezi indexy $P_0[p]$ a~$P_0[q]$. To zjistíme
+      v~konstantním èase pomocí struktury pro intervalová minima.
+   \::Pokud se setká suffix ze~$\sigma_{0,1}$ se suffixem ze~$\sigma_2$, staèí
+      tyto suffixy pøepsat podobnì jako v~6.~kroku a problém tak opìt pøevést
+      na výpoèet LCP dvou suffixù slov~$\sigma_{0,1}$.
 
 \endalgo
 
-\s{Analýza èasové slo¾itosti:} Tøídìní v~prvním volání trvá ${\rm Sort}(n,\Sigma)$, ve~v¹ech
-ostatních voláních je lineární (trojice èísel velikosti $\O(n)$ mù¾eme tøídit tøíprùchodovým
+\s{Analýza èasové slo¾itosti:} Tøídìní napoprvé trvá ${\rm Sort}(n,\Sigma)$, ve~v¹ech
+rekurzivních voláních u¾ je lineární (trojice èísel velikosti $\O(n)$ mù¾eme tøídit tøíprùchodovým
 pøihrádkovým tøídìním s~$\O(n)$ pøihrádkami). Z~toho dostáváme:
 $$T(n) = T(2/3\cdot n) + \O(n),~\hbox{a tedy}~T(n)=\O(n).$$
 \qed
@@ -266,7 +278,8 @@ abychom um
 \s{Definice:} {\I Referenèní pár} je dvojice $(\pi,\tau)$, v~ní¾ $\pi$ je vrchol
 stromu a $\tau$ libovolné slovo. Tento pár popisuje slovo $\pi\tau$. Referenèní
 pár je {\I kanonický,} pokud neexistuje hrana vedoucí z~vrcholu $\pi$ s~nálepkou,
-která by byla prefixem slova~$\tau$.
+která by byla prefixem slova~$\tau$. Navíc $\tau\subseteq\sigma$, tak¾e si~$\tau$
+staèí pamatovat jako dvojici indexù v~$\sigma$.
 
 \s{Pozorování:} Ke~ka¾dému slovu existuje právì jeden kanonický referenèní pár,
 který ho popisuje. V¹imnìte si, ¾e je to ze~v¹ech referenèních párù pro toto slovo
@@ -296,13 +309,13 @@ bude hodit p
 \:::Pokud v~popisce této hrany po~$\tau$ následuje znak~$a$, pak je $\alpha a$ pøítomen.
 \:::Pokud nenásleduje, tak nebyl pøítomen, èili tuto hranu rozdìlíme: pøidáme na~ni nový vnitøní vrchol,
     do~nìj¾ povede hrana s~popiskou~$\tau$ a z~nìj zbytek pùvodní hrany a otevøená hrana do~nového listu.
-\:Pokud $\alpha a$ byl pøítomen, tak $\alpha$ zkrátíme a test opakujeme:
+\:Pokud $\alpha a$ nebyl pøítomen, tak $\alpha$ zkrátíme a test opakujeme:
 \::Je-li $\pi\ne\varepsilon$, nastavíme $\pi := \<back>(\pi)$. V~opaèném pøípadì (jsme v~koøeni) zkrátíme $\tau$ o~znak zleva.
 \::Pár $(\pi,\tau)$ u¾ popisuje zkrácené slovo, ale nemusí být kanonický, tak¾e to je¹tì napravíme:
 \:::Dokud existuje hrana vedoucí z~$\pi$, její¾ popiska je prefixem slova $\tau$, tak se
     po~této hranì posuneme, èili prodlou¾íme $\pi$ o~tuto popisku a zkrátíme o~ni~$\tau$.
 \::Zpìt na~krok 2.
-\:Pokud $\alpha a$ u¾ je pøítomen, zbývá pøidat $a$ k~$\alpha$ a zastavit se:
+\:Pokud $\alpha a$ ji¾ byl pøítomen, zbývá pøidat $a$ k~$\alpha$ a zastavit se:
 \::$\tau := \tau a$.
 \::Kanonikalizace stejnì jako v~bodech 12--13.\foot{Dokonce jednodu¹¹í, proto¾e projdeme nejvý¹e jednu hranu.}
 \:Dopoèítáme zpìtné hrany (viz ní¾e).
@@ -310,6 +323,8 @@ bude hodit p
   a jeho funkce \<back>.
 \endalgo
 
+\goodbreak
+
 \s{Èasová slo¾itost:}
 
 Kanonikalizace pracuje v~amortizovanì konstantním èase, proto¾e ka¾dá její iterace