10-suffix/10-suffix.tex

   1 \input ../sgr.tex
   2
   3 \prednaska{10}{Suffixové stromy}{}
   4
   5 V~této kapitole popí¹eme jednu pozoruhodnou datovou strukturu, pomocí ní¾ doká¾eme problémy týkající
   6 se øetìzcù pøevádìt na grafové problémy a tak je øe¹it v~lineárním èase.
   7
   8 \h{Øetìzce, trie a suffixové stromy}
   9
  10 \ss{Definice:}
  11
  12 \nointerlineskip
  13 \halign{\qquad#\dotfill&~#\hfil\cr
  14 \hbox to 0.35\hsize{}\cr
  15 $\Sigma$                                        & koneèná abeceda -- mno¾ina znakù \cr
  16 \omit                                           & (znaky budeme znaèit latinskými písmeny)\cr
  17 $\Sigma^*$                                      & mno¾ina v¹ech slov nad $\Sigma$ \cr
  18 \omit                                           & (slova budeme znaèit øeckými písmeny)\cr
  19 $\varepsilon$                                   & prázdné slovo\cr
  20 $\vert\alpha\vert$                              & délka slova $\alpha$\cr
  21 $\alpha\beta$                                   & zøetìzení slov $\alpha$ a $\beta$ ($\alpha\varepsilon=\varepsilon\alpha=\alpha$)\cr
  22 $\alpha^R$                                      & slovo $\alpha$ napsané pozpátku\cr
  23 $\alpha$ je {\I prefixem} $\beta$               & $\exists\gamma: \beta=\alpha\gamma$ ($\beta$ zaèíná na~$\alpha$)\cr
  24 $\alpha$ je {\I suffixem} $\beta$               & $\exists\gamma: \beta=\gamma\alpha$ ($\beta$ konèí na~$\alpha$)\cr
  25 $\alpha$ je {\I podslovem} $\beta$              & $\exists\gamma,\delta: \beta=\gamma\alpha\delta$ (znaèíme $\alpha \subset \beta$)\cr
  26 $\alpha$ je {\I vlastním prefixem} $\beta$      & je prefixem a $\alpha\ne\beta$ \cr
  27 \omit                                           & (analogicky vlastní suffix a podslovo)\cr
  28 }
  29
  30 \s{Pozorování:} Prázdné slovo je prefixem, suffixem i podslovem ka¾dého slova vèetnì sebe sama.
  31 Podslova jsou právì prefixy suffixù a také suffixy prefixù.
  32
  33 \s{Definice:} {\I Trie ($\Sigma$-strom)} pro koneènou mno¾inu slov $X\subset\Sigma^*$ je orientovaný graf $G=(V,E)$, kde:
  34 \itemize\relax
  35 \:$V = \{\alpha: \alpha\hbox{ je prefixem nìjakého $\beta\in X$} \},$
  36 \:$(\alpha,\beta)\in E \equiv \exists x\in\Sigma: \beta=\alpha x$.
  37 \endlist
  38
  39 \s{Pozorování:} Trie je strom s koøenem $\varepsilon$. Jeho listy jsou slova z $X$, která nejsou vlastními prefixy jiných slov z~$X$.
  40 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$ dávají právì slovo~$\alpha$.
  41
  42 \s{Definice:} {\I Komprimovaná trie ($\Sigma^+$-strom)} vznikne z trie nahrazením maximálních nevìtvících se cest hranami. Hrany
  43 jsou tentokrát popsané øetìzci místo jednotlivými písmeny, pøièem¾ popisky v¹ech hran vycházejících z~jednoho vrcholu se li¹í v~prvním
  44 znaku. Vrcholùm \uv{uvnitø hran} (které padly za obì» kompresi) budeme øíkat {\I skryté vrcholy.}
  45
  46 \s{Definice:} {\I Suffixový strom (ST)} pro slovo $\sigma\in\Sigma^*$ je komprimovaná trie pro $X=\{\alpha: \hbox{$\alpha$ je suffixem $\sigma$}\}$.
  47
  48 \s{Pozorování:} Vrcholy suffixového stromu (vèetnì skrytých) odpovídají prefixùm suffixù slova~$\sigma$,
  49 tedy v¹em jeho podslovùm. Listy stromu jsou suffixy, které se v~$\sigma$ ji¾ nikde jinde nevyskytují
  50 (takovým suffixùm budeme øíkat {\I nevnoøené}). Vnitøní vrcholy odpovídají {\I vìtvícím podslovùm,}
  51 tedy podslovùm $\alpha\subset\sigma$ takovým, ¾e $\alpha a\subset\sigma$ i $\alpha b\subset\sigma$
  52 pro nìjaké dva rùzné znaky~$a$,~$b$.
  53
  54 Nìkdy mù¾e být nepraktické, ¾e nìkteré suffixy neodpovídají listùm (proto¾e jsou vnoøené), ale
  55 s~tím se mù¾eme snadno vypoøádat: pøidáme na~konec slova~$\sigma$ nìjaký znak~$\$$, který se nikde
  56 jinde nevyskytuje. Neprázdné suffixy slova $\sigma\$$ odpovídají suffixùm slova~$\sigma$
  57 a ¾ádný z~nich nemù¾e být vnoøený. Takový suffixový strom budeme znaèit ST\$.
  58
  59 \s{Pøíklad:}
  60
  61 \figure{baraba.eps}{Suffixy slova \uv{baraba}: trie, suffixový strom, ST s~dolarem}{\epsfxsize}
  62
  63 \>Nyní jak je to s~konstrukcí suffixových stromù:
  64
  65 \s{Lemma:} Suffixový strom pro slovo $\sigma$ délky $n$ je reprezentovatelný v~prostoru $\O(n)$.
  66
  67 \proof Strom má $\O(n)$ listù a ka¾dý vnitøní vrchol má alespoò $2$ syny, tak¾e vnitøních
  68 vrcholù je také $\O(n)$. Hran je rovnì¾ lineárnì. Nálepky na~hranách staèí popsat
  69 poèáteèní a koncovou pozicí v~$\sigma$.
  70 \qed
  71
  72 \s{Vìta:} Suffixový strom pro slovo $\sigma$ délky $n$ lze sestrojit v~èase $\O(n)$.
  73
  74 \proof Ve~zbytku této kapitoly pøedvedeme dvì rùzné konstrukce v~lineárním èase.
  75 \qed
  76
  77 \s{Aplikace} -- co v¹e doká¾eme v~lineárním èase, kdy¾ umíme lineárnì konstruovat ST:
  78
  79 \nobreak
  80
  81 \numlist\ndotted
  82 \:{\I Inverzní vyhledávání} (tj. pøedzpracujeme si v~lineárním èase text a pak umíme pro libovolné
  83 slovo~$\alpha$ v~èase $\O(\vert\alpha\vert)$ rozhodnout, zda se v~textu vyskytuje)\foot{Èili pøesný
  84 opak toho, co~umí vyhledávací automat -- ten si pøedzpracovává dotaz.} -- staèí sestrojit~ST
  85 a pak jej procházet od~koøene. Také umíme najít v¹echny výskyty (odpovídají suffixùm, které mají
  86 jako prefix hledané slovo, tak¾e staèí vytvoøit ST\$ a vypsat v¹echny listy pod
  87 nalezeným vrcholem) nebo pøímo vrátit jejich poèet (pøedpoèítáme si pomocí DFS pro ka¾dý vrchol,
  88 kolik pod ním le¾í listù).
  89
  90 \:{\I Nejdel¹í opakující se podslovo} -- takové podslovo je v~ST\$ nutnì vìtvící, tak¾e staèí
  91 najít vnitøní vrchol s~nejvìt¹í {\I písmenkovou hloubkou} (tj. hloubkou mìøenou ve~znacích
  92 místo ve~hranách).
  93
  94 \:{\I Histogram èetností podslov délky~$k$} -- rozøízneme ST v~písmenkové hloubce~$k$ a spoèítáme,
  95 kolik pùvodních listù je pod ka¾dým novým.
  96
  97 \:{\I Nejdel¹í spoleèné podslovo} slov~$\alpha$ a $\beta$ -- postavíme ST pro slovo $\alpha\$_1\beta\$_2$,
  98 jeho listy odpovídají suffixùm slov $\alpha$ a $\beta$. Tak¾e staèí pomocí DFS najít nejhlub¹í vnitøní
  99 vrchol, pod kterým se vyskytují listy pro~$\alpha$ i $\beta$. Podobnì mù¾eme sestrojit ST\$ pro libovolnou
 100 mno¾inu slov.\foot{Jen si musíme dát pozor, abychom si moc nezvìt¹ili abecedu, ale to bude jasné,
 101 a¾ pøedvedeme konkrétní konstrukce.}
 102
 103 \:{\I Nejdel¹í palindromické podslovo} (tj. takové $\beta\subset\alpha$, pro nì¾ je $\beta_R=\beta$)
 104 -- postavíme spoleèný ST\$ pro slova $\alpha$ a $\alpha_R$. Postupnì procházíme pøes v¹echny mo¾né støedy
 105 palindromického podslova a v¹imneme si, ¾e takové slovo je pro ka¾dý støed nejdel¹ím spoleèným
 106 prefixem podslova od~tohoto bodu do~konce a podslova od~tohoto bodu pozpátku k~zaèátku,
 107 èili nìjakého suffixu $\alpha$ a nìjakého suffixu $\alpha_R$. Tyto suffixy ov¹em odpovídají
 108 listùm sestrojeného ST a jejich nejdel¹í spoleèný prefix je nejbli¾¹ím spoleèným pøedchùdcem
 109 ve~stromu, tak¾e staèí pro strom vybudovat datovou strukturu pro spoleèné pøedchùdce
 110 a s~její pomocí doká¾eme jeden støed prozkoumat v~konstantním èase.
 111
 112 \:{\I Burrows-Wheelerova Transformace} \cite{burrows:bwt} -- jejím základem je lexikografické setøídìní v¹ech
 113 rotací slova~$\sigma$, co¾ zvládneme sestrojením ST pro slovo~$\sigma\sigma$, jeho
 114 uøíznutím v~písmenkové hloubce~$\vert\sigma\vert$ a vypsáním novì vzniklých listù v~poøadí
 115 \uv{zleva doprava}.
 116 \endlist
 117
 118 \s{Cvièení:} Zkuste vymyslet co nejlep¹í algoritmy pro tyto problémy bez pou¾ití~ST.
 119
 120 \h{Suffix Array}
 121
 122 \>V~nìkterých pøípadech se hodí místo suffixového stromu pou¾ívat kompaktnìj¹í datové struktury.
 123
 124 \s{Notace:} Pro slovo $\sigma$ bude $\sigma[i]$ znaèit jeho $i$-tý znak (èíslujeme od~jednièky),
 125 $\sigma[i:j]$ pak podslovo slo¾ené z~$i$-tého a¾ $j$-tého znaku. Libovolnou z~mezí mù¾eme vynechat, proto
 126 $\sigma[i:{}]$ bude suffix od~$i$ do~konce a $\sigma[{}:j]$ prefix od~zaèátku do~$j$.
 127 Pokud $j<i$, definujeme $\sigma[i:j]$ jako prázdné slovo, tak¾e prázdný suffix mù¾eme
 128 napøíklad zapsat jako $\sigma[\vert\sigma\vert+1:{}].$
 129
 130 ${\rm LCP}(\alpha,\beta)$ bude znaèit délku nejdel¹ího spoleèného prefixu slov $\alpha$ a $\beta$,
 131 èili nejvìt¹í $i\le \vert\alpha\vert,\vert\beta\vert$ takové, ¾e $\alpha[{}:i]=\beta[{}:i]$.
 132
 133 \s{Definice:} {\I Suffix Array} $A_\sigma$ pro slovo $\sigma$ délky~$n$ je posloupnost v¹ech suffixù
 134 slova~$\sigma$ v~lexikografickém poøadí. Mù¾eme ho reprezentovat napøíklad jako permutaci $A$ èísel
 135 $1,\ldots,n+1$, pro ní¾ $\sigma[A[1]:{}] < \sigma[A[2]:{}] < \ldots < \sigma[A[n+1]:]$.
 136
 137 \s{Definice:} {\I Longest Common Prefix Array} $L_\sigma$ pro slovo $\sigma$ je posloupnost,
 138 v~ní¾ $L_\sigma[i]:={\rm LCP}(A_\sigma[i],A_\sigma[i+1])$.
 139
 140 \s{Vìta:} Suffixový strom pro slovo $\sigma\$$ je lineárnì ekvivalentní s~dvojicí $(A_\sigma,L_\sigma)$.
 141 [Jinými slovy, kdy¾ máme jedno, mù¾eme z~toho v~lineárním èase spoèítat druhé, a naopak.]
 142
 143 \proof Kdy¾ projdeme ST($\sigma$) do hloubky, poøadí listù odpovídá $A_\sigma$ a písmenkové hloubky vnitøních
 144 vrcholù v~inorderu odpovídají $L_\sigma$. Naopak ST($\sigma$) získáme tak, ¾e sestrojíme kartézský strom
 145 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$
 146 a nakonec podle listù rekonstruujeme nálepky hran.
 147 \qed
 148
 149 \h{Rekurzivní konstrukce}
 150
 151 \>Tento algoritmus konstruuje pro slovo $\sigma$ délky~$n$ jeho suffix array a LCP array v~èase $\O(n+{\rm Sort}(n,\Sigma))$,
 152 kde ${\rm Sort}(\ldots)$ je èas potøebný pro setøídìní $n$ symbolù z~abecedy~$\Sigma$. V~kombinaci s~pøedchozími
 153 výsledky nám tedy dává lineární konstrukci ST($\sigma$) pro libovolnou fixní abecedu.
 154
 155 \s{Algoritmus:} (Konstrukce $A$ a $L$ podle Kärkkäinena a Sanderse \cite{karkkainen03simple})
 156
 157 \algo
 158 \:Redukujeme abecedu na~$1\ldots n$: ve~vstupním slovu je nejvý¹e $n$ rùzných znakù,
 159 tak¾e je staèí setøídit a pøeèíslovat.
 160
 161 \:Definujeme slova $\sigma_0$, $\sigma_1$, $\sigma_2$ následovnì:
 162 $$\eqalign{
 163 \sigma_0[i] &:= \left<\sigma[3i],\sigma[3i+1],\sigma[3i+2]\right>\cr
 164 \sigma_1[i] &:= \left<\sigma[3i+1],\sigma[3i+2],\sigma[3i+3]\right>\cr
 165 \sigma_2[i] &:= \left<\sigma[3i+2],\sigma[3i+3],\sigma[3i+4]\right>\cr
 166 }$$
 167 V¹echna $\sigma_k$ jsou slova délky $\approx n/3$ nad~abecedou velikosti $n^3$. Dovolíme
 168 si mírnì zneu¾ívat notaci a pou¾ívat symbol $\sigma_k$ i jejich pøepis do~abecedy pùvodní.
 169
 170 \:Zavoláme algoritmus rekurzivnì na slovo $\sigma_0\sigma_1$, èím¾ získáme $A_{01}$ a $L_{01}$.
 171
 172 \: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
 173 $A_i$ zapamatujeme, kde se v~$A_{01}$ vyskytoval.
 174
 175 \: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:{}]$
 176 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í.
 177
 178 \: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
 179 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
 180 dvojici $i,j$ spoèítat v~konstantním èase pomocí datové struktury pro intervalová minima.
 181
 182 \:$A_0,A_1,A_2\buildrel merge\over\longrightarrow A$ -- sléváme tøi setøídìné posloupnosti,
 183 tak¾e staèí umìt prvky libovolných dvou posloupností v~konstantním èase porovnat:
 184 $$\eqalign{
 185 \sigma_0[i:{}] < \sigma_1[j:{}] &~\hbox{podle zapamatovaných pozic v~$A_{01}$} \cr
 186 \sigma_0[i:{}] < \sigma_2[k:{}] &\equiv \sigma[3i]\,\sigma_1[i:{}] < \sigma[3k+2]\,\sigma_0[k+1:{}]\cr
 187 &\Leftrightarrow (\sigma[3i] < \sigma[3k+2]) \vee {} \cr&\hphantom{{}\Leftrightarrow{}} (\sigma[3i] = \sigma[3k+2] \wedge \sigma_1[i:{}] < \sigma_0[k+1:{}])\cr
 188 \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:{}]
 189 }$$
 190
 191 \:Dopoèítáme $L$ -- pokud sousedí suffix ze~$\sigma_{0,1}$ se suffixem ze~$\sigma_{0,1}$,
 192 vyèteme výsledek pøímo z~$L_{01}$. Pokud sousedí $\sigma_2$ se $\sigma_2$, staèí pou¾ít
 193 u¾ spoèítané $L_2$. Pokud sousedí $\sigma_{0,1}$ se $\sigma_2$, odebereme první jeden
 194 nebo dva znaky, ty porovnáme samostatnì a v~pøípadì shody zbude suffix ze~$\sigma_0$
 195 a suffix ze~$\sigma_1$ (stejnì jako pøi slévání) a pro ty doká¾eme $L$ dopoèítat
 196 pomocí struktury pro intervalová minima v~$L_{01}$.
 197
 198 \endalgo
 199
 200 \s{Analýza èasové slo¾itosti:} Tøídìní v~prvním volání trvá ${\rm Sort}(n,\Sigma)$, ve~v¹ech
 201 ostatních voláních je lineární (trojice èísel velikosti $\O(n)$ mù¾eme tøídit tøíprùchodovým
 202 pøihrádkovým tøídìním s~$\O(n)$ pøihrádkami). Z~toho dostáváme:
 203 $$T(n) = T(2/3\cdot n) + \O(n),~\hbox{a tedy}~T(n)=\O(n).$$
 204 \qed
 205
 206 \h{Ukkonenova inkrementální konstrukce}
 207
 208 \>Ukkonenùv algoritmus \cite{ukkonen95line} konstruuje suffixový strom bez dolarù inkrementálnì: zaène se stromem
 209 pro prázdné slovo (ten má jediný vrchol, a to koøen) a postupnì pøidává dal¹í znaky na~konec
 210 slova. To zvládne v~èase $\O(1)$ amortizovanì na~pøidání jednoho znaku.
 211 Pro slovo~$\sigma$ tedy doká¾e sestrojit ST v~èase $\O(\vert\sigma\vert)$.
 212
 213 Budeme pøedpokládat, ¾e hrany vedoucí z~jednoho vrcholu je mo¾né indexovat jejich
 214 prvními písmeny -- to bezpeènì platí, pokud je abeceda pevná; není-li, mù¾eme
 215 si pomoci hashováním.
 216
 217 \s{Pozorování:} Kdy¾ slovo~$\sigma$ roz¹íøíme na~$\sigma a$, ST se zmìní následovnì:
 218
 219 \numlist\ndotted
 220 \:Pokud $\beta$ byl nevnoøený suffix slova~$\sigma$, je i $\beta a$ nevnoøený suffix~$\sigma a$. Z~toho víme, ¾e listy
 221 zùstanou listy, pouze jim potøebujeme prodlou¾it nálepky. Pomù¾eme si snadno: zavedeme
 222 {\I otevøené hrany,} jejich¾ nálepka je \uv{od~pozice~$i$ do konce}. Listy se tak
 223 o~sebe postarají samy.
 224 \:Pokud $\beta$ bylo vìtvící slovo, zùstane nadále vìtvící -- tedy vnitøní vrcholy ve~stromu zùstanou.
 225 \:Pokud $\beta$ byl vnoøený suffix (tj. vnitøní èi skrytý vrchol), pak se $\beta a$ buïto
 226 vyskytuje v~$\sigma$, a tím pádem je to vnoøený suffix nového slova a strom není nutné
 227 upravovat, nebo se v~$\sigma$ nevyskytuje a tehdy pro nìj musíme zalo¾it novou odboèku
 228 a nový list s~otevøenou hranou.
 229 \endlist
 230
 231 Víme tedy, co v¹echno musí algoritmus ve~stromu pøí roz¹íøení slova upravit, zbývá
 232 vyøe¹it, jak to udìlat efektivnì. K~tomu se hodí pár definic a lemmat:
 233
 234 \s{Definice:} {\I Aktivní suffix} $\alpha(\sigma)$ øíkáme nejdel¹ímu vnoøenému suffixu slova~$\sigma$.
 235
 236 \s{Lemma:} Suffix $\beta$ slova $\sigma$ je vnoøený $\Leftrightarrow$ $\vert\beta\vert \le \vert\alpha(\sigma)\vert.$
 237
 238 \proof Ka¾dý suffix vnoøeného suffixu je opìt vnoøený. \qed
 239
 240 \s{Lemma:} Pro ka¾dé $\sigma$, $a$ platí: $\alpha(\sigma a)$ je suffixem $\alpha(\sigma)a.$
 241
 242 \proof $\alpha(\sigma a)$ i $\alpha(\sigma)a$ jsou suffixy slova $\sigma a$, a~proto staèí porovnat jejich délky.
 243 Slovo $\beta := \hbox{\uv{$\alpha(\sigma a)$ bez koncového~$a$}}$ je vnoøeným suffixem v~$\sigma$, tak¾e
 244 $\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$.
 245 \qed
 246
 247 \s{Definice:} Suffix $\beta a$ je {\I zralý} $\equiv$ $\beta$ je vnoøený suffix~$\sigma$, ale $\beta a$ není podslovem~$\sigma$
 248 (tedy musíme pro~nìj pøi pøidávání znaku~$a$ k~aktuálnímu slovu~$\sigma$ zakládat nový vrchol).
 249
 250 \s{Lemma:} Suffix $\beta$ je zralý $\Leftrightarrow$ $\vert\alpha(\sigma)a\vert \ge \vert\beta a\vert > \vert\alpha(\sigma a)\vert$.
 251
 252 \proof Jeliko¾ $\beta$ je vnoøeným suffixem $\sigma$, musí platit první nerovnost. Aby byl zralý,
 253 musí také nebýt vnoøeným suffixem $\sigma a$, a~tomu odpovídá druhá nerovnost.
 254 \qed
 255
 256 \s{Idea algoritmu:} Udr¾ujeme si $\alpha=\alpha(\sigma)$ a pøi pøidání znaku $a$ zkontrolujeme, zda $\alpha a$ je
 257 stále vnoøený suffix. Pokud ano, nic se nemìní, pokud ne, pøidáme vnitøní vrchol, $\alpha$ zkrátíme
 258 zleva o~znak a testujeme dál.
 259
 260 \s{Analýza:} Úprav stromu provedeme $\O(1)$ amortizovanì (ka¾dá úprava slovo $\alpha$ zkrátí,
 261 ka¾dé pøidání znaku ho~prodlou¾í o~znak, tak¾e v¹ech zkrácení je $\O(\vert\sigma\vert)$). Staèí
 262 tedy ukázat, jak provést úpravu v~(amortizovanì) konstantním èase, k~èemu¾ potøebujeme
 263 $\alpha$ reprezentovat ¹ikovnì a také si udr¾ovat pomocné informace (zpìtné hrany),
 264 abychom umìli rychle zkracovat.
 265
 266 \s{Definice:} {\I Referenèní pár} je dvojice $(\pi,\tau)$, v~ní¾ $\pi$ je vrchol
 267 stromu a $\tau$ libovolné slovo. Tento pár popisuje slovo $\pi\tau$. Referenèní
 268 pár je {\I kanonický,} pokud neexistuje hrana vedoucí z~vrcholu $\pi$ s~nálepkou,
 269 která by byla prefixem slova~$\tau$.
 270
 271 \s{Pozorování:} Ke~ka¾dému slovu existuje právì jeden kanonický referenèní pár,
 272 který ho popisuje. V¹imnìte si, ¾e je to ze~v¹ech referenèních párù pro toto slovo
 273 ten s~nejdel¹ím~$\pi$ (nejhlub¹ím vrcholem).
 274
 275 \s{Definice:} Zpìtná hrana $\<back>[\pi]$ vede z~vrcholu $\pi$ do~vrcholu,
 276 který je ze~v¹ech vrcholù nejdel¹ím vlastním suffixem slova~$\pi$.
 277
 278 \s{Pozorování:} Zpìtné hrany jsme sice zavedli stejnì obecnì, jako se to dìlá
 279 pøi konstrukci vyhledávacích automatù podle Aha a McCorasickové, ale v~na¹em
 280 pøípadì se \<back> pro vnitøní vrcholy chová daleko jednodu¹eji (a~na ¾ádné
 281 jiné ho potøebovat nebudeme): pokud je $\pi$ vnitøní vrchol, musí to být
 282 vìtvící podslovo, a~tím pádem ka¾dé jeho zkrácení zleva musí být také vìtvící
 283 podslovo. Tedy $\<back>(\pi)$ dá~$\pi$ bez prvního znaku, a~to se nám
 284 bude hodit pøi zkracování suffixù.
 285
 286 \s{Algoritmus podrobnìji:} (Doplnili jsme detaily do~pøedchozího algoritmu.)
 287
 288 \algo
 289 \:Vstup: $\alpha=\alpha(\sigma)$ reprezentovaný jako kanonický referenèní pár $(\pi,\tau)$, $T$ suffixový strom pro~$\sigma$ a jeho funkce \<back>, nový znak~$a$.
 290 \:Zjistíme, jestli $\alpha a$ je pøítomen ve~stromu, a pøípadnì ho zalo¾íme:
 291 \::Pokud $\tau=\varepsilon$: ($\alpha=\pi$ je vnitøní vrchol)
 292 \:::Vede-li z~vrcholu $\pi$ hrana s~nálepkou zaèínající znakem $a$, pak je pøítomen.
 293 \:::Nevede-li, není pøítomen, a~tak pøidáme novou otevøenou hranu vedoucí z~$\pi$ do~nového listu.
 294 \::Pokud $\tau\ne\varepsilon$: ($\alpha$ je skrytý vrchol)
 295 \:::Najdeme hranu, po~ní¾ z~$\pi$ pokraèuje slovo $\tau$ (která to je, poznáme podle prvního znaku slova~$\tau$).
 296 \:::Pokud v~popisce této hrany po~$\tau$ následuje znak~$a$, pak je $\alpha a$ pøítomen.
 297 \:::Pokud nenásleduje, tak nebyl pøítomen, èili tuto hranu rozdìlíme: pøidáme na~ni nový vnitøní vrchol,
 298     do~nìj¾ povede hrana s~popiskou~$\tau$ a z~nìj zbytek pùvodní hrany a otevøená hrana do~nového listu.
 299 \:Pokud $\alpha a$ byl pøítomen, tak $\alpha$ zkrátíme a test opakujeme:
 300 \::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.
 301 \::Pár $(\pi,\tau)$ u¾ popisuje zkrácené slovo, ale nemusí být kanonický, tak¾e to je¹tì napravíme:
 302 \:::Dokud existuje hrana vedoucí z~$\pi$, její¾ popiska je prefixem slova $\tau$, tak se
 303     po~této hranì posuneme, èili prodlou¾íme $\pi$ o~tuto popisku a zkrátíme o~ni~$\tau$.
 304 \::Zpìt na~krok 2.
 305 \:Pokud $\alpha a$ u¾ je pøítomen, zbývá pøidat $a$ k~$\alpha$ a zastavit se:
 306 \::$\tau := \tau a$.
 307 \::Kanonikalizace stejnì jako v~bodech 12--13.\foot{Dokonce jednodu¹¹í, proto¾e projdeme nejvý¹e jednu hranu.}
 308 \:Dopoèítáme zpìtné hrany (viz ní¾e).
 309 \:Výstup: $\alpha=\alpha(\sigma a)$ coby kanonický referenèní pár $(\pi,\tau)$, $T$ suffixový strom pro~$\sigma a$
 310   a jeho funkce \<back>.
 311 \endalgo
 312
 313 \s{Èasová slo¾itost:}
 314
 315 Kanonikalizace pracuje v~amortizovanì konstantním èase, proto¾e ka¾dá její iterace
 316 zkrátí~$\tau$ a za~ka¾dé spu¹tìní algoritmu se~$\tau$ prodlou¾í jen jednou, a~to o~jeden znak.
 317
 318 Prùchodù hlavním cyklem je, jak u¾ víme, amortizovanì konstantní poèet a ka¾dý prùchod
 319 zvládneme v~konstantním èase.
 320
 321 Zbývá dodat, jak nastavovat novým vrcholùm jejich \<back>. To potøebujeme
 322 jen pro vnitøní vrcholy (na~zpìtné hrany z~listù se algoritmus nikdy neodkazuje)
 323 a v¹imneme si, ¾e pokud jsme zalo¾ili vrchol, odpovídá tento vrchol v¾dy souèasnému~$\alpha$
 324 a zpìtná hrana z~nìj povede do~zkrácení slova~$\alpha$ o~znak zleva, co¾ je
 325 pøesnì vrchol, který zalo¾íme (nebo zjistíme, ¾e u¾ existuje) v~pøí¹tí iteraci
 326 hlavního cyklu. V~dal¹í iteraci urèitì je¹tì nebudeme tuto hranu potøebovat,
 327 proto¾e $\pi$ v¾dy jen zkracujeme, a~tak mù¾eme vznik zpìtné hrany o~iteraci
 328 zpozdit a zvládnout to tak také v~èase $\O(1)$.
 329
 330 Celkovì je tedy èasová slo¾itost inkrementálního udr¾ování suffixového
 331 stromu amortizovanì konstantní.
 332 \qed
 333
 334 \references
 335 \bye