[ga.git] / 9-suffix / 9-suffix.tex

\input ../sgr.tex

\prednaska{9}{Suffixové stromy} {Tomá¹ Mikula \& Jan Král}

V~této kapitole popí¹eme jednu datovou strukturu, pomocí které doká¾eme problémy týkající
se øetìzcù pøevádìt na grafové problémy a tak je øe¹it v~lineárním èase.

\h{Øetìzce, trie a suffixové stromy}

\s{Definice:}

\nointerlineskip
\halign{\qquad#\dotfill&~#\hfil\cr
\hbox to 0.3\hsize{}\cr
$\Sigma$                                        & koneèná abeceda (mno¾ina znakù, budeme je znaèit latinskými písmeny)\cr
$\Sigma^*$                                      & mno¾ina v¹ech slov nad $\Sigma$ (slova budeme znaèit øeckými písmeny)\cr
$\varepsilon$                                   & prázdné slovo\cr
$\vert\alpha\vert$                              & délka slova $\alpha$\cr
$\alpha\beta$                                   & zøetìzení slov $\alpha$ a $\beta$ ($\alpha\varepsilon=\varepsilon\alpha=\alpha$)\cr
$\alpha^R$                                      & slovo $\alpha$ napsané pozpátku\cr
$\alpha$ je {\I prefixem} $\beta$               & $\exists\gamma: \beta=\alpha\gamma$ ($\beta$ zaèíná na~$\alpha$)\cr
$\alpha$ je {\I suffixem} $\beta$               & $\exists\gamma: \beta=\gamma\alpha$ ($\beta$ konèí na~$\alpha$)\cr
$\alpha$ je {\I podslovem} $\beta$              & $\exists\gamma,\delta: \beta=\gamma\alpha\delta$ (znaèíme $\alpha \subset \beta$)\cr
$\alpha$ je {\I vlastním prefixem} $\beta$      & je prefixem a $\alpha\ne\beta$ (analogicky vlastní suffix a podslovo)\cr
}

\s{Pozorování:} Prázdné slovo je prefixem, suffixem i podslovem ka¾dého slova vèetnì sebe sama.
Podslova jsou právì prefixy suffixù a také suffixy prefixù.

\s{Definice:} {\I Trie ($\Sigma$-strom)} pro koneènou $X\subset\Sigma^*$ je orientovaný graf $G=(V,E)$, kde:
\itemize\relax
\:$V = \{\alpha: \alpha\hbox{ je prefixem nìjakého $\beta\in X$} \},$
\:$(\alpha,\beta)\in E \equiv \exists x\in\Sigma: \beta=\alpha x$.
\endlist

\s{Pozorování:} Trie je strom s koøenem $\varepsilon$. Jeho listy jsou slova z $X$, která nejsou vlastním prefixem jiných slov z~$X$.
Hrany si mù¾eme pøedstavit popsané písmeny, o~nì¾ prefix roz¹iøují, popisky hran na~cestì z~koøene do~vrcholu~$\alpha$ dají právì slovo~$\alpha$.

\s{Definice:} {\I Komprimovaná trie ($\Sigma^+$-strom)} vznikne z trie nahrazením maximálních nevìtvících se cest hranami. Hrany
jsou tentokrát popsané øetìzci místo jednotlivými písmeny, pøièem¾ popisky v¹ech hrany vycházející z~jednoho vrcholu se li¹í v~prvním
znaku. Vrcholùm \uv{uvnitø hran} (které padly za obìt kompresi) budeme øíkat {\I skryté vrcholy.}

\tabskip=0pt plus 1fil
\halign to\hsize{
\hfil#\hfil&\hfil#\hfil&\hfil#\hfil\cr
\epsfbox{trie.eps}&\epsfbox{trie-c.eps}&\epsfbox{trie-cd.eps}\cr
Trie pre $\{\hbox{AULA, AUTO, AUTOBUS, BUS}\}$ & \dots komprimovaná & \dots odolarovaná\cr
}
\smallskip

\s{Definice:} {\I Suffixový strom (ST)} pro slovo $\sigma\in\Sigma^*$ je komprimovaná trie pro $X=\{\alpha: \hbox{$\alpha$ je suffixem $\sigma$}\}$.

\s{Pozorování:} Vrcholy suffixového stromu (vèetnì skrytých) odpovídají prefixùm suffixù slova~$\sigma$,
tedy v¹em jeho podslovùm. Listy stromu jsou suffixy, které se v~$\sigma$ ji¾ nikde jinde nevyskytují
(takovým suffixùm budeme øíkat {\I nevnoøené}). Vnitøní vrcholy odpovídají {\I vìtvícím podslovùm,}
tedy podslovùm $\alpha\subset\sigma$ takovým, ¾e $\alpha a\subset\sigma$ i $\alpha b\subset\sigma$
pro nìjaké dva rùzné znaky~$a$,~$b$.

Nìkdy mù¾e být nepraktické, ¾e nìkteré suffixy neodpovídají listùm (proto¾e jsou vnoøené), ale
s~tím se mù¾eme snadno vypoøádat: pøidáme na~konec slova~$\sigma$ nìjaký znak~$\$$, který se nikde
jinde nevyskytuje. Suffixy slova $\sigma\$$ odpovídají suffixùm slova~$\sigma$ (kdy¾ pomineme
prázdný suffix) a ¾ádný z~nich nemù¾e být vnoøený.

\figure{st-barbara.eps}{Sufixový strom pre slovo BARBARA}{0pt}

\s{Lemma:} Suffixový strom pro slovo $\sigma$ délky $n$ je reprezentovatelný v~prostoru $\O(n)$.

\s{Dùkaz:} Strom má $\O(n)$ listù a ka¾dý vnitøní vrchol má alespoò $2$ syny, tak¾e vnitøních
vrcholù je také $\O(n)$. Hran je rovnì¾ lineárnì. Nálepky na~hranách si staèí reprezentovat
poèáteèní a koncovou pozicí v~$\sigma$.
\qed

\s{Vìta:} Suffixový strom pro slovo $\sigma$ délky $n$ lze sestrojit v~èase $\O(n)$.

\s{Dùkaz:} Ve~zbytku této kapitoly pøedvedeme dvì rùzné konstrukce v~lineárním èase.
\qed

\s{Aplikace:} (co v¹e doká¾eme v~lineárním èase, kdy¾ umíme lineárnì konstruovat ST)

\numlist\ndotted
\:{\I Inverzní vyhledávání} (tj. pøedzpracujeme si v~lineárním èase text a pak umíme pro libovolné
slovo~$\alpha$ v~èase $\O(\vert\alpha\vert)$ rozhodnout, zda se v~textu vyskytuje.\foot{Èili pøesný
opak toho, co~umí vyhledávací automat -- ten si pøedzpracovává dotaz.} -- staèí sestrojit~ST
a pak jej procházet od~koøene. Také umíme najít v¹echny výskyty (odpovídají suffixùm, které mají
jako prefix hledané slovo, tak¾e staèí vytvoøit ST s~dolarem a vypsat v¹echny listy pod
nalezeným vrcholem) nebo pøímo vrátit jejich poèet (pøedpoèítáme si pomocí DFS pro ka¾dý vrchol,
kolik pod ním le¾í listù).

\:{\I Nejdel¹í opakující se podslovo} -- takové podslovo je nutnì vìtvící, tak¾e staèí
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,
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.}

\:{\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
palindromického podslova a v¹imneme si, ¾e takové slovo je pro ka¾dý støed nejdel¹ím spoleèným
prefixem podslova od~tohoto bodu do~konce a podslova od~tohoto bodu (pozpátku) k~zaèátku,
èili nìjakého suffixu $\alpha$ a nìjakého suffixu $\alpha_R$. Tyto suffixy ov¹em odpovídají
listùm sestrojeného ST a jejich nejdel¹í spoleèný prefix je nejbli¾¹ím spoleèným pøedchùdcem
ve~stromu, tak¾e staèí pro strom vybudovat datovou strukturu pro spoleèné pøedchùdce
a s~její pomocí doká¾eme jeden støed prozkoumat v~konstantním èase.

\:{\I Burrows-Wheelerova Transformace} -- jejím základem je lexikografické setøidìní v¹ech
rotací slova~$\sigma$, co¾ zvládneme sestrojením ST pro slovo~$\sigma\sigma$, jeho
uøíznutím v~písmenkové hloubce~$\vert\sigma\vert$ a následným vypsáním listù v~poøadí dle~DFS.
\endlist

\h{Suffix Array}

\>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:j]$ znaèit podslovo slo¾ené z~$i$-tého a¾ $j$-tého
znaku slova~$\sigma$ (znaky èíslujeme od~$1$). Navíc $\sigma[i:{}]$ bude suffix od~$i$ do~konce
a $\sigma[{}:j]$ prefix od~zaèátku do~$j$. Prázdný suffix mù¾eme znaèit jako $\sigma[\vert\sigma\vert+1:{}].$

\s{Definice:} {\I 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]:]$.

\s{Definice:} {\I Longest Common Prefix Array} $L_\sigma$ pro slovo $\sigma$ je posloupnost,
v~ní¾ $L_\sigma[i]$ udává délku nejdel¹ího spoleèného prefixu slov $A_\sigma[i]$ a $A_\sigma[i+1]$.

\s{Vìta:} Suffixový strom pro slovo $\sigma$ s~dolarem je lineárnì ekvivalentní s~dvojicí $(A_\sigma,L_\sigma)$.
[Jinými slovy, kdy¾ máme jedno, mu¾eme z~toho v~lineárním èase spoèítat druhé a naopak.]

\s{Dùkaz:} 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
pro~$L_\sigma$ (to jsou vnitøní vrcholy ST), doplníme do~nìj listy a pøiøadíme jim suffixy podle~$A_\sigma$
a nakonec podle listù rekonstruujeme nálepky hran.

\h{Rekurzivní konstrukce}

\>Tento algoritmus konstruuje pro slovo $\sigma$ délky~$n$ pole $A_\sigma$ a $L_\sigma$ 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.

\s{Algoritmus:} (Konstrukce $A$ a $L$ podle Kärkkäinena a Sanderse)

\algo
\:Redukujeme abecedu na~$1\ldots n$: ve~vstupním slovu je nejvý¹e $n$ rùzných znakù,
tak¾e je staèí setøidit a pøeèíslovat.

\:Definujeme slova $\sigma_0$, $\sigma_1$, $\sigma_2$ následovnì:
$$\eqalign{
\sigma_0[i] &:= \left<\sigma[3i],\sigma[3i+1],\sigma[3i+2]\right>\cr
\sigma_1[i] &:= \left<\sigma[3i+1],\sigma[3i+2],\sigma[3i+3]\right>\cr
\sigma_2[i] &:= \left<\sigma[3i+2],\sigma[3i+3],\sigma[3i+4]\right>\cr
}$$
Slova $\sigma_k$ jsou slova délky $\approx n/3$ nad~abecedou velikosti $n^3$. Dovolíme
si mírnì zneu¾ívat notaci a znaèit $\sigma_k$ i jejich pøepis do~abecedy pùvodní.

\:Zavoláme se 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$ a spoèítáme permutace inverzní k~$A_0$ a $A_1$.

\:Dopoèítáme $A_2$: Jeliko¾ $\sigma_2[i:{}] = \sigma[3i+2:{}] = \sigma[3i+2]\sigma[3i+3:{}] = \sigma[3i+2]\sigma_0[i+1:{}]$
a v¹echna $\sigma_0[i:{}]$ u¾ máme setøidìná, mù¾eme v¹echna $\sigma_2[i:{}]$ setøídit dvìma prùchody pøíhrá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:{}]) = \min_{i+1\le k< j+1} L_0[k]$. To zvládneme v~konstantním
èase na~operaci pomoci datové struktuy pro intervalová minima.
\todo{Ta je a¾ v~následující kapitole, co¾ není pìkné.}

\:$A_0,A_1,A_2\buildrel merge\over\longrightarrow A$ -- sléváme tøi setøidìné posloupnosti,
tak¾e staèí umìt prvky libovolných dvou posloupností v~konstantním èase porovnat:
$$\eqalign{
\sigma_0[i:{}] < \sigma_1[j:{}] &\equiv A_{01}^{-1}[i] < A_{01}^{-1}[\vert\sigma_0\vert+j]\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 (\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:{}] < \sigma[3k+2]\,\sigma[3k+3]\,\sigma_1[k+1:{}]
}$$

\:Dopoèítame $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$.

\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
pøíhrádkovým tøídìním s~$\O(n)$ pøíhrádkami). Dostáváme tedy:
$$T(n) = T(2/3\cdot n) + \O(n),~\hbox{a tedy}~T(n)=\O(n).$$
\qed

\h{Ukkonenova inkrementální konstrukce}

\>Ukkonenùv algoritmus konstruuje suffixový strom bez dolarù inkrementálnì: zaène se stromem
pro prázdné slovo (ten má jediný vrchol, a to koøen) a postupnì pøidává dal¹í znaky na~konec
slova. To zvládne v~èase $\O(1)$ amortizovanì na~pøidání jednoho znaku.
Pro slovo~$\sigma$ tedy doká¾e sestrojit ST v~èase $\O(\vert\sigma\vert)$.

\s{Pozorování:} Kdy¾ slovo~$\sigma$ roz¹íøíme na~$\sigma a$, ST se zmìní následovnì:

\numlist\ndotted
\:Pokud $\beta$ byl nevnoøený suffix $\sigma$, je i $\beta a$ nevnoøený suffix -- listy
zùstanou listy, pouze jim potøebujeme prodlou¾it nálepky. Pomu¾eme si snadno: zavedeme
{\I otevøené hrany,} jejich¾ nálepka je \uv{od~pozice~$i$ do konce}. Listy se tedy
o~sebe postarají samy.
\:Pokud $\beta$ bylo vìtvící slovo, zùstane nadále vìtvící -- vnitøní vrcholy tedy zùstanou.
\:Pokud $\beta$ byl vnoøený suffix (tj. vnitøní èi skrytý vrchol), je $\beta a$ buïto
také vnoøený (a postará se o~sebe sám), nebo se vùbec nevyskytuje v~$\sigma$ a musíme
pro~nìj zalo¾it novou odboèku a nový list s~otevøenou hranou.
\endlist

\s{Definice:} {\I Aktivní suffix} $\alpha(\sigma)$ øíkáme nejdel¹ímu vnoøenému suffixu slova~$\sigma$.

\s{Lemma:} Suffix $\beta$ slova $\sigma$ je vnoøený $\Leftrightarrow$ $\vert\beta\vert \le \vert\alpha(\sigma)\vert.$

\s{Dùkaz:} Ka¾dý suffix vnoøeného suffixu je opìt vnoøený. \qed

\s{Lemma:} Pro ka¾dé $\sigma$, $a$ platí: $\alpha(\sigma a)$ je suffixem $\alpha(\sigma)a.$

\s{Dùkaz:} $\alpha(\sigma a)$ i $\alpha(\sigma)a$ jsou suffixy slova $\sigma a$, a~proto staèí porovnat jejich délky.
Slovo $\beta := \hbox{$\alpha(\sigma a)$ bez koncového~$a$}$ je vnoøený suffix v~$\sigma$, tak¾e
$\vert\beta\vert \le \vert\alpha(\sigma)\vert$, a~tedy také $\vert\alpha(\sigma a)\vert = \vert\beta a\vert \le \vert\alpha(\sigma)a\vert$.
\qed

\s{Definice:} Suffix $\beta a$ je {\I zralý} (musíme pro~nìj pøi pøidávání znaku~$a$ k~aktuálnímu
slovu~$\sigma$ zakládat nový vrchol) $\equiv$ $\beta$ je vnoøený suffix~$\sigma$, ale $\beta a$ není podslovem~$\sigma$.

\s{Lemma:} Suffix $\beta$ je zralý $\Leftrightarrow$ $\vert\alpha(\sigma)a\vert \ge \vert\beta a\vert > \vert\alpha(\sigma a)\vert$.

\s{Dùkaz:} Jeliko¾ $\beta$ je vnoøeným suffixem $\sigma$, musí platit první nerovnost. Aby byl zralý,
musí také nebýt vnoøeným suffixem $\sigma a$, èemu¾ odpovídá druhá nerovnost.
\qed

\s{Algoritmus:} Udr¾uji si $\alpha=\alpha(\sigma)$ a pøi pøidání znaku $a$ zkontroluji, zda $\alpha a$ je
stále vnoøený suffix. Pokud ano, nic se nemìní, pokud ne, pøidám vnitøní vrchol, $\alpha$ zkrátím
zleva o~znak a testuji dál.

\s{Èasová slo¾itost:} Úprav stromu provedu $\O(1)$ amortizovanì (ka¾dá úprava $\alpha$ zkrátí,
ka¾dé pøidání znaku ho~prodlou¾í o~1, tak¾e v¹ech zkrácení je $\O(\vert\sigma\vert)$). Staèí
tedy ukázat, jak provést úpravu v~(amortizovanì) konstantním èase.

\todo{Zbytek dosud nezrevidován.}

$\alpha(\sigma)$ reprezentuji jako kanonický (neexistuje jiný referenèní pár s krat¹ím $\alpha$) referenèní pár $(v, \alpha)$ kde $v$ je vrchol $ST$ a $\alpha$ ke cesta kudy dál.

\s{Definice: $back[v]$} je nejdel¹í vlastní suffix $v$, ke kterému existuje vrchol.

\algo
\:Vstup: $\sigma, a, (v, \alpha)$

// 1. Zalo¾ení listù/Podrozdìlení hran
\:if $\alpha = \varepsilon$:
\::if $\exists (v, a* )$
\:::konec
\::else:
\:::zalo¾ím list
\:else if $\alpha \ne \varepsilon$:
\::if $\exists (v, \alpha a*)$:
\:::konec
\::else:
\:::podrozdìlím hranu na které le¾í $\alpha$ // za $\alpha$ vlo¾ím odboèku na $a$, kam dám list a pokraèuju

// 2. Pøechod na dal¹í vrchol
\:zkrátim $\alpha$ zleva o znak
\:if $v = \varepsilon$:
\::pøejdu do $( \varepsilon, \alpha bez 1. znaku)$
\:else:
\::pøejdu do $( back[v], \alpha )$

// 3.
\:kanonikalizuji // "jdu z $v$ pøes alpha do co nejdal"
\endalgo


\s{Èasová slo¾itost:}
\numlist\ndotted
\:Zalo¾ení listu/Podrozdìlení hrany -- $O(1)$
\:Pøechod na dal¹í vrchol -- $O(1)$ za pøedpokladu existence $back(v)$
\:Kanonikalizace -- amortizovanì za $O(1)$
\:Update $back[v]$ -- jen pro vnitøní vrcholy, které vznikly v 1. podrozdìlením hrany. Ta hrana vede do vrcholu, který nav¹tíví pøí¹tí update v kroku 2. a buï tam ten vrchol je, nebo ho v tom kroku zakláda, tedy -- $O(1)$.
\endlist

\bye