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 řešit je tak 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; jak moc si ji
 101 můžeme dovolit zvětšit, vyplyne z~konkrétních konstrukcí.}
 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{Suffixová pole}
 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~nuly),
 125 $\sigma[i:j]$ pak podslovo $\sigma[i]\sigma[i+1]\ldots\sigma[j-1]$. 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-1$.
 127 Pokud $j\le 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:{}].$
 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 Suffixové pole (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 $0,\ldots,n$, pro níž $\sigma[A[0]:{}] < \sigma[A[1]:{}] < \ldots < \sigma[A[n]:{}]$.
 136
 137 \s{Definice:} {\I Pole nejdelších společných prefixů (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\$$ a dvojici $(A_\sigma,L_\sigma)$ na sebe lze
 141 v~lineárním čase převádět.
 142
 143 \proof Když projdeme ST($\sigma\$$) do hloubky, pořadí listů odpovídá posloupnosti $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 \>Ukážeme algoritmus, který pro slovo $\sigma\in\Sigma^*$ délky~$n$ sestrojí jeho suffixové pole
 152 a LCP pole v~čase $\O(n+{\rm Sort}(n,\Sigma))$, kde ${\rm Sort}(\ldots)$ je čas potřebný pro setřídění
 153 $n$~symbolů z~abecedy~$\Sigma$. V~kombinaci s~předchozími výsledky tedy dostaneme lineární konstrukci
 154 ST($\sigma$) pro libovolnou fixní abecedu.
 155
 156 \s{Algoritmus:} (Konstrukce $A$ a $L$ podle Kärkkäinena a Sanderse \cite{karkkainen03simple})
 157
 158 \algo
 159 \:Redukujeme abecedu na~$1\ldots n$: ve~vstupním slovu je nejvýše $n$ různých znaků,
 160 takže je stačí setřídit a přečíslovat.
 161
 162 \:Definujeme slova $\sigma_0$, $\sigma_1$, $\sigma_2$ následovně:
 163 $$\eqalign{
 164 \sigma_0[i] &:= \left<\sigma[3i],\sigma[3i+1],\sigma[3i+2]\right>\cr
 165 \sigma_1[i] &:= \left<\sigma[3i+1],\sigma[3i+2],\sigma[3i+3]\right>\cr
 166 \sigma_2[i] &:= \left<\sigma[3i+2],\sigma[3i+3],\sigma[3i+4]\right>\cr
 167 }$$
 168 Všechna $\sigma_k$ jsou slova délky $\approx n/3$ nad~abecedou velikosti $n^3$. Dovolíme
 169 si mírně zneužívat notaci a používat symbol $\sigma_k$ i jejich přepis do~abecedy původní.
 170
 171 \:Zavoláme algoritmus rekurzivně na slovo $\sigma_0\sigma_1$, čímž získáme $A_{01}$ a $L_{01}$.
 172 (Suffixy slova $\sigma_0\sigma_1$ odpovídají suffixům slov $\sigma_0$ a~$\sigma_1$.)
 173
 174 \:Spočítáme pole $P_0$ a $P_1$, která nám budou říkat, kde se v~$A_{01}$ vyskytuje
 175 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$.
 176 Jinými slovy, $P_0$ a~$P_1$ budou části inverzní permutace k~$A_{01}$. Všimněte si,
 177 že platí $P_i[x] < P_j[y]$ právě tehdy, když $\sigma_i[x:{}] < \sigma_j[y:{}]$, takže
 178 suffixy slov $\sigma_0$ a~$\sigma_1$ od této chvíle umíme porovnávat v~čase~$\O(1)$.
 179
 180 \:Vytvoříme~$A_2$ (suffixové pole pro~$\sigma_2$): Jelikož $\sigma_2[i:{}] = \sigma[3i+2:{}] = \sigma[3i+2]\sigma[3i+3:\nobreak{}\nobreak] = \sigma[3i+2]\sigma_0[i+1:{}]$,
 181 odpovídá lexikografické pořadí suffixů $\sigma_2[i:{}]$ pořadí dvojic $(\sigma[3i+2],P_0[i+1])$.
 182 Tyto dvojice ovšem můžeme setřídit dvěma průchody přihrádkového třídění.
 183
 184 \:Slijeme $A_{01}$ a~$A_2$ do~$A$: sléváme dvě setříděné posloupnosti,
 185 takže stačí umět jejich prvky v~konstantním čase porovnat:
 186 $$\eqalign{
 187 \sigma_0[i:{}] < \sigma_2[j:{}] \Leftrightarrow{} &\sigma[3i:{}] < \sigma[3j+2:{}] \cr
 188                                 \Leftrightarrow{} &\sigma[3i]\,\sigma_1[i:{}] < \sigma[3j+2]\,\sigma_0[j+1:{}],\cr
 189 \sigma_1[i:{}] < \sigma_2[j:{}] \Leftrightarrow{} &\sigma[3i+1:{}] < \sigma[3j+2:{}] \cr
 190                                 \Leftrightarrow{} &\sigma[3i+1]\,\sigma[3i+2]\,\sigma_0[i+1:{}] < \cr
 191                                                   &\sigma[3j+2]\,\sigma[3j+3]\,\sigma_1[j+1:{}].\cr
 192 }$$
 193 Pokaždé tedy porovnáme nejvýše dvě dvojice znaků a pak dvojici suffixů slov $\sigma_0$ a $\sigma_1$,
 194 k~čemuž nám pomohou pole $P_0$ a~$P_1$.
 195
 196 \:Dopočítáme $L$:
 197    \::Pokud v~$A$ sousedí suffix slova~$\sigma_{0,1}$ se suffixem slova~$\sigma_{0,1}$,
 198       sousedí tyto dva suffixy i v~$A_{01}$, takže jejich LCP najdeme přímo v~$L$.
 199    \::Setkají-li se dva suffixy slova~$\sigma_2$, všimneme si, že
 200       $\sigma_2[i:{}] = \sigma[3i+2:\nobreak{}] = \sigma[3i+2]\,\sigma_0[i+1:{}]$.
 201       ${\rm LCP}(\sigma_2[i:{}],\sigma_2[j:{}])$ je tedy buďto~0 (pokud $\sigma[3i+2]\ne\sigma[3j+2]$),
 202       nebo $1+3\cdot{\rm LCP}(\sigma_0[i+1:{}],\sigma_0[j+1:{}])$, případně totéž zvýšené
 203       o~1 nebo~2, pokud se trojznaky v~$\sigma_0$ následující po LCP zčásti shodují.
 204       Přitom ${\rm LCP}(\sigma_0[p:{}],\sigma_0[q:{}])$ spočítáme pomocí~$L$.
 205       Je to totiž minimum intervalu v~$L$ mezi indexy $P_0[p]$ a~$P_0[q]$. To zjistíme
 206       v~konstantním čase pomocí struktury pro intervalová minima.
 207    \::Pokud se setká suffix slova~$\sigma_{0,1}$ se suffixem slova~$\sigma_2$, stačí
 208       tyto suffixy přepsat podobně jako v~6.~kroku a problém tím opět převést
 209       na výpočet LCP dvou suffixů slov~$\sigma_{0,1}$.
 210
 211 \endalgo
 212
 213 \s{Analýza časové složitosti:} Třídění napoprvé trvá ${\rm Sort}(n,\Sigma)$, ve~všech
 214 rekurzivních voláních už je lineární (trojice čísel velikosti $\O(n)$ můžeme třídit tříprůchodovým
 215 přihrádkovým tříděním s~$\O(n)$ přihrádkami). Z~toho dostáváme:
 216 $$T(n) = T(2/3\cdot n) + \O(n),~\hbox{a tedy}~T(n)=\O(n).$$
 217 \qed
 218
 219 \h{Ukkonenova inkrementální konstrukce}
 220
 221 \>Ukkonen popsal algoritmus \cite{ukkonen95line} pro konstrukci suffixového stromu bez dolarů,
 222 pracující inkrementálně: Začne se stromem pro prázdné slovo a postupně na konec slova přidává
 223 další znaky a přepočítává strom. Každý znak přitom přidá v~amortizovaně konstantním čase.
 224 Pro slovo~$\sigma$ tedy dokáže sestrojit ST v~čase $\O(\vert\sigma\vert)$.
 225
 226 Budeme předpokládat, že hrany vedoucí z~jednoho vrcholu je možné indexovat jejich
 227 prvními písmeny -- to bezpečně platí, pokud je abeceda pevná; není-li, můžeme
 228 si pomoci hešováním.
 229
 230 \s{Pozorování:} Když slovo~$\sigma$ rozšíříme na~$\sigma a$, ST se změní následovně:
 231
 232 \numlist\ndotted
 233 \:Všechny stávající vrcholy stromu (včetně skrytých) odpovídají podslovům slova~$\sigma$.
 234   Ta jsou i podslovy $\sigma a$, takže se budou nacházet i v~novém stromu.
 235 \:Pokud $\beta$ bylo větvící slovo, zůstane nadále větvící -- tedy vnitřní vrcholy ve~stromu zůstanou.
 236 \:Každý nový suffix~$\beta a$ vznikne prodloužením nějakého původního suffixu~$\beta$. Přitom:
 237   \itemize\ibull
 238   \:Pokud byl~$\beta$ nevnořený suffix (čili byl reprezentovaný listem), ani $\beta a$
 239     nebude vnořený. Z~toho víme, že listy zůstanou listy, pouze jim potřebujeme prodloužit
 240     nálepky. Aby to netrvalo příliš dlouho, zavedeme {\I otevřené hrany,} jejichž nálepka
 241     říká \uv{od~pozice~$i$ do konce}. Listy se tak o~sebe postarají samy.
 242   \:Pokud $\beta$ byl vnořený suffix (tj. vnitřní či skrytý vrchol):
 243     \itemize\ibull
 244       \:Buď se $\beta a$ vyskytuje v~$\sigma$, a tím pádem je to vnořený suffix nového slova
 245         a strom není nutné upravovat;
 246       \:nebo se $\beta a$ v~$\sigma$ nevyskytuje -- tehdy pro něj musíme založit nový list
 247         s~otevřenou hranou a případně i nový vnitřní vrchol, pod nímž bude tento list připojen.
 248     \endlist
 249   \endlist
 250 \endlist
 251
 252 Víme tedy, co všechno je při rozšíření slova potřeba ve~stromu upravit.
 253 Zbývá vyřešit, jak to udělat efektivně.
 254
 255 \s{Vnořené suffixy:}
 256 Především potřebujeme umět rozpoznat, které suffixy jsou vnořené a které nikoliv.
 257 K~tomu se hodí všimnout si, že vnořené suffixy tvoří souvislý úsek:
 258
 259 {\narrower
 260 \s{Lemma:} Je-li $\alpha$ vnořený suffix slova~$\sigma$ a $\beta$ je suffix slova~$\alpha$,
 261 pak $\beta$ je v~$\sigma$ také vnořený.
 262
 263 \proof
 264 Ve~slově sigma se vyskytuje $\alpha x$ a $\alpha y$ pro nějaké dva různé znaky $x$ a~$y$.
 265 Každý z~těchto výskytů přitom končí výskytem slova~$\beta$, jednou následovaným~$x$,
 266 podruhé~$y$.
 267 \qed
 268
 269 }
 270
 271 \>Stačí si tedy zapamatovat nejdelší vnořený suffix slova~$\sigma$. Tomu budeme říkat
 272 {\I aktivní suffix} a budeme ho značit $\alpha(\sigma)$. Libovolný suffix~$\beta\subseteq\sigma$
 273 pak bude vnořený právě tehdy, když $\vert\beta\vert \le \vert\alpha(\sigma)\vert$.
 274
 275 Aktivní suffix tedy tvoří hranici mezi nevnořenými a vnořenými suffixy. Jak se tato
 276 hranice posune, když slovo~$\sigma$ rozšíříme? Na to je odpověď snadná:
 277
 278 {\narrower
 279 \s{Lemma:} Pro každé $\sigma$, $a$ platí: $\alpha(\sigma a)$ je suffixem $\alpha(\sigma)a.$
 280
 281 \proof
 282 $\alpha(\sigma a)$ i $\alpha(\sigma)a$ jsou suffixy slova $\sigma a$, a~proto stačí porovnat jejich délky.
 283 Slovo $\beta := \hbox{\uv{$\alpha(\sigma a)$ bez koncového~$a$}}$ je vnořeným suffixem v~$\sigma$, takže
 284 $\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$.
 285 \qed
 286
 287 }
 288
 289 \>Hranice se tedy může posouvat pouze doprava, případně zůstat na místě.
 290 Toho lze snadno využít.
 291
 292 \s{Idea algoritmu:} Udržujeme si $\alpha=\alpha(\sigma)$ a při přidání znaku $a$ zkontrolujeme,
 293 zda $\alpha a$ je stále vnořený suffix. Pokud ano, nic se nemění, pokud ne, přidáme nový list
 294 a případně také vnitřní vrchol, $\alpha$ zkrátíme zleva o~znak a testujeme dál.
 295
 296 \s{Analýza:} Po~přidání jednoho znaku na konec slova~$\sigma$ provedeme amortizovaně
 297 konstantní počet úprav stromu (každá úprava slovo $\alpha$ zkrátí, po všech úpravách
 298 přidáme k~$\alpha$ jediný znak). Tudíž stačí ukázat, jak provést každou úpravu
 299 v~(amortizovaně) konstantním čase. K~tomu potřebujeme šikovnou reprezentaci slova~$\alpha$,
 300 která bude umět efektivně prodlužovat zprava, zkracovat zleva a testovat existenci
 301 vrcholu ve~stromu.
 302
 303 \s{Definice:} {\I Referenční pár} pro slovo $\alpha\subseteq\sigma$ je dvojice
 304 $(\pi,\tau)$, v~níž $\pi$ je vrchol stromu, $\tau$ libovolné slovo a $\pi\tau=\alpha$.
 305 Navíc víme, že $\tau\subseteq\sigma$, takže si~$\tau$ stačí pamatovat jako dvojici
 306 indexů ve~slově~$\sigma$.
 307
 308 Referenční pár je {\I kanonický,} pokud neexistuje hrana vedoucí z~vrcholu~$\pi$ s~nálepkou,
 309 která by byla prefixem slova~$\tau$. (Všimněte si, že taková hrana se pozná podle toho,
 310 že první znak nálepky se shoduje s~prvním znakem slova~$\tau$ a nálepka není delší než
 311 slovo~$\tau$. Shodu ostatních znaků není nutné kontrolovat.)
 312
 313 \s{Pozorování:} Ke~každému slovu $\alpha\subseteq\sigma$ existuje právě jeden kanonický
 314 referenční pár, který ho popisuje. To je ze~všech referenčních párů pro toto slovo
 315 ten s~nejdelším~$\pi$ (nejhlubším vrcholem).
 316
 317 \s{Definice:} Zpětná hrana $\<back>(\pi)$ vede z~vrcholu $\pi$ do~vrcholu,
 318 který je zkrácením slova~$\pi$ o~jeden znak zleva. (Nahlédneme, že takový
 319 vrchol musí existovat: pokud je $\pi$ vnitřní vrchol, pak je slovo~$\pi$
 320 větvící, takže každý jeho suffix musí také být větvící, a~tím pádem musí
 321 odpovídat nějakého vrcholu.)
 322
 323 \s{Operace s~referenčními páry:}
 324 S~referenčním párem $(\pi,\tau)$ popisujícím slovo~$\alpha$ potřebujeme provádět
 325 následujicí operace:
 326
 327 \itemize\ibull
 328 \:{\I Přidání znaku~$a$ na konec:} Připíšeme~$a$ na konec slova~$\tau$.
 329   To je jistě referenční pár pro $\alpha a$, ale nemusí být kanonický.
 330   Přitom můžeme snadno ověřit, zda se $\alpha a$ ve~stromu nachází,
 331   a případně operaci odmítnout.
 332 \:{\I Odebrání znaku ze~začátku:} Pokud $\pi$ není kořen stromu, položíme
 333   $\pi\leftarrow\<back>(\pi)$ a zachováme~$\tau$. Pokud naopak je~$\pi$
 334   prázdný řetězec, odebereme z~$\tau$ jeho první znak (to lze udělat
 335   v~konstantním čase, protože~$\tau$ je reprezentované dvojicí indexů do~$\sigma$).
 336 \:{\I Převedení na kanonický tvar:} Obě předchozí operace mohou vytvořit referenční
 337   pár, který není kanonický. Pokaždé proto kanonicitu zkontrolujeme a případně
 338   pár upravíme. Ověříme, zda hrana z~$\pi$ indexovaná písmenem~$a$ není
 339   dost krátká na to, aby byla prefixem slova~$\tau$. Pokud je, tak se
 340   po~této hraně přesuneme dolů, čímž~$\pi$ prodloužíme a~$\tau$ zkrátíme,
 341   a proces opakujeme. Jelikož tím pokaždé $\tau$~zkrátíme a kdykoliv jindy
 342   se $\tau$ prodlouží nejvýše o~1, mají všechny převody na kanonický tvar
 343   amortizovaně konstantní složitost.
 344 \endlist
 345
 346 \>Nyní již můžeme doplnit detaily, získat celý algoritmus a nahlédnout,
 347 že pracuje v~amortizovaně konstantním čase.
 348
 349 \s{Algoritmus podrobněji:}
 350
 351 \algo
 352 \:{\I Vstup:} $\alpha=\alpha(\sigma)$ reprezentovaný jako kanonický referenční pár $(\pi,\tau)$, $T$ suffixový strom pro~$\sigma$ spolu s~hranami \<back>, nový znak~$a$.
 353 \:Zjistíme, jestli $\alpha a$ je přítomen ve~stromu, a případně ho založíme:
 354 \::Pokud $\tau=\varepsilon$: ($\alpha=\pi$ je vnitřní vrchol)
 355 \:::Vede-li z~vrcholu $\pi$ hrana s~nálepkou začínající znakem $a$, pak je přítomen.
 356 \:::Nevede-li, není přítomen, a~tak přidáme novou otevřenou hranu vedoucí z~$\pi$ do~nového listu.
 357 \::Pokud $\tau\ne\varepsilon$: ($\alpha$ je skrytý vrchol)
 358 \:::Najdeme hranu, po~níž z~$\pi$ pokračuje slovo $\tau$ (která to je, poznáme podle prvního znaku slova~$\tau$).
 359 \:::Pokud v~popisce této hrany po~$\tau$ následuje znak~$a$, pak je $\alpha a$ přítomen.
 360 \:::Pokud nenásleduje, tak nebyl přítomen, čili tuto hranu rozdělíme: přidáme na~ni nový vnitřní vrchol,
 361     do~nějž povede hrana s~popiskou~$\tau$ a z~něj zbytek původní hrany a otevřená hrana do~nového listu.
 362 \:Pokud $\alpha a$ nebyl přítomen, tak $\alpha$ zkrátíme a vrátíme se na~krok~2.
 363 \:Nyní víme, že $\alpha a$ již byl přítomen, takže upravíme referenční pár, aby popisoval $\alpha a$.
 364 \:Dopočítáme zpětné hrany (viz níže).
 365 \:{\I Výstup:} $\alpha=\alpha(\sigma a)$ jako kanonický referenční pár $(\pi,\tau)$, $T$ suffixový strom pro~$\sigma a$
 366   a jeho zpětné hrany \<back>.
 367 \endalgo
 368
 369 \s{Zpětné hrany:}
 370 Zbývá dodat, jak nastavovat novým vrcholům jejich zpětné hrany. To potřebujeme
 371 jen pro vnitřní vrcholy (na~zpětné hrany z~listů se algoritmus nikdy neodkazuje).
 372 Všimneme si, že pokud jsme založili vrchol, odpovídá tento vrchol vždy současnému~$\alpha$
 373 a zpětná hrana z~něj povede do~zkrácení slova~$\alpha$ o~znak zleva, což je
 374 přesně vrchol, který založíme (nebo zjistíme, že už existuje) v~příští iteraci
 375 hlavního cyklu. V~další iteraci ještě určitě nebudeme tuto hranu potřebovat,
 376 protože $\pi$ vždy jen zkracujeme, a~tak můžeme vznik zpětné hrany o~iteraci
 377 zpozdit. Výroba zpětné hrany tedy bude také trvat jen konstantně dlouho.
 378
 379 \references
 380 \bye