From 375d08f7ec49f21a462bd03badbb06b8f297489b Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Mon, 12 Jan 2009 18:48:27 +0100
Subject: [PATCH] Prepsan algoritmus pro rekurzivni konstrukci suffixovych
 stromu.

V popisu algoritmu bylo nekolik chyb a byl zbytecne slozity. Nahradil
jsem ho tedy jednodussi variantou a chyby snad vymytil. Mimo to jsem
zmenil znaceni x[i] tak, ze se pozice ve slove cisluji od nuly, a x[i:j]
tak, ze j-ty znak jiz do podslova nepatri. Tak zustanou zachovany vsechny
pekne vlastnosti puvodniho znaceni a zmizi problemy s definici slov
na trojicich znaku v rekurzivnim algoritmu.
---
 10-suffix/10-suffix.tex | 96 +++++++++++++++++++++++------------------
 1 file changed, 54 insertions(+), 42 deletions(-)

diff --git a/10-suffix/10-suffix.tex b/10-suffix/10-suffix.tex
index abdcc72..7fecdfc 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:\nobreak{}],\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
-- 
2.39.2