3 \def\leaderfill{\leaders\hbox to .5em{\hss.\hss}\hfill}
4 \def\itemitemitem{\par\indent\indent \hangindent3\parindent \textindent}
7 \def\vs#1#2{#1~{\rm vs.}~#2}
9 \prednaska{9}{Suffixové stromy} {Tomá¹ Mikula \& Jan Král}
12 \+\indent&\hbox to \dimen0 {$\Sigma$\leaderfill}&koneèná abeceda (mno¾ina znakov)\cr
13 \+&$\Sigma^*$\leaderfill&mno¾ina v¹etkých slov nad $\Sigma$\cr
14 \+&$\epsilon$\leaderfill&prázdne slovo\cr
15 \+&$\alpha\beta$\leaderfill&zre»azenie slov $\alpha,\beta\in\Sigma^*$\cr
16 \+&$\alpha^n$\leaderfill&$n=0: \alpha^0=\epsilon$\cr
17 \+&&$n>0: \alpha^n=\alpha\alpha^{n-1}$\cr
18 \+&$\alpha^{\rm R}$\leaderfill&slovo $\alpha$ odzadu\cr
19 \settabs\+\indent&$\alpha$ je {\it (vlastným) podslovom} $\beta$ &\cr
20 \+&$\alpha$ je {\it (vlastným) prefixom} $\beta$ &$\equiv \exists\gamma(\not=\epsilon):\beta=\alpha\gamma$\cr
21 \+&$\alpha$ je {\it (vlastným) sufixom} $\beta$ &$\equiv \exists\gamma(\not=\epsilon):\beta=\gamma\alpha$\cr
22 \+&$\alpha$ je {\it (vlastným) podslovom} $\beta$ &$\equiv \alpha$ je prefixom nejakého sufixu $\beta$ (a $\alpha\not=\beta$)\cr
25 \s{Definícia:} {\it Trie ($\Sigma$-strom)} pre $X\subset\Sigma^*, \vert X\vert<\infty$ je orientovaný graf $G(V,E)$:\par
26 $V = \lbrace\alpha\vert\alpha\hbox{ je prefixom nejakého }\beta\in X\rbrace$\par
27 $(\alpha,\beta)\in E \equiv \exists x\in\Sigma:\beta=\alpha x$\par
29 \s{Pozorovanie:} Trie je strom s koreòom $\epsilon$. Listy sú slová z $X$, ktoré nie sú vlastným prefixom iných slov z $X$.
31 \s{Definícia:} {\it Komprimovaná trie ($\Sigma^+$-strom)} vznikne z trie nahradením nevetviacich sa ciest hranami (oznaèenými zre»azením znakov príslu¹nej cesty).
33 Vrcholom, ktoré padli za obe» kompresii budeme hovori» {\it skryté vrcholy}.\par
34 Mô¾e sa sta», ¾e nejakému slovu z $X$ odpovedá skrytý vrchol. Aby sme sa tomuto vyhli, pridáme na koniec ka¾dého slova ¹peciálny znak $\$\notin\Sigma$. Teraz platí\par
35 \s{Pozorovanie:} Listy (komprimovanej) trie sú práve slová z $X$.
37 \tabskip=0pt plus 1fil
39 \hfil#\hfil&\hfil#\hfil&\hfil#\hfil\cr
40 \epsfbox{trie.eps}&\epsfbox{trie-c.eps}&\epsfbox{trie-cd.eps}\cr
41 Trie pre $\{\hbox{AULA, AUTO, AUTOBUS, BUS}\}$ & \dots komprimovaná & \dots odolarovaná\cr
46 \s{Definícia:} {\it Sufixový strom} pre slovo $\sigma\in\Sigma^*$ je komprimovaná trie pre $X=\lbrace {\rm sufixy~}\sigma\rbrace$.
48 \s{Pozorovanie:} Listy sú sufixy $\sigma$, ktoré nie sú prefixom iného sufixu. Po pridaní znaku \$ na koniec ka¾dého sufixu sú listy práve v¹etky sufixy. Vnútorné vrcholy sú {\it vetviace podslová} $\sigma$ (tj. $\alpha$ podslová $\sigma$, ktoré sú prefixom aspoò dvoch sufixov a $\alpha x$ je prefixom men¹ieho poètu sufixov pre ka¾dé $x\in\Sigma$).
50 V listoch si budeme znaèi» index do $\sigma$, kde daný sufix zaèína.
52 \figure{st-barbara.eps}{Sufixový strom pre slovo BARBARA}{0pt}
54 \s{Lemma:} Sufixový strom pre slovo $\sigma$ då¾ky $n$ je reprezentovateµný v priestore $\O(n)$.\par
55 \s{Dôkaz:} Strom má $\O(n)$ listov a ka¾dý vnútorný vrchol má výstupný stupeò aspoò $2$ a teda v¹etkých vrcholov je $\O(n)$. Keï¾e sa jedná o strom, hrán je tie¾ len $\O(n)$. Nálepky na hranách budú reprezentované ako 2 indexy do $\sigma$ oznaèujúce zaèiatok a koniec nejakého úseku odpovedajúceho písmenkám na hrane.\qed
57 \s{Veta:} Sufixový strom pre slovo då¾ky $n$ sa dá zostroji» v èase $\O(n)$.\par
58 \s{Dôkaz:} Budú uvedené 2 kon¹trukcie v lineárnom èase.\qed
60 \s{Aplikácie} (alebo èo doká¾eme v èase $\O(n)$):\par
61 \item{1.} inverzné vyhµadávanie (tj. vyhµadávanie µubovoµného výrazu v predspracovanom texte (nie predspracovaného výrazu (napr. koneèný automat) v µubovoµnom texte))
62 \itemitem{-}v¹etky výskyty; ak u¾ máme strom postavený, doká¾eme nájs» v¹etkých $k$ výskytov podslova då¾ky $m$ v èase $\O(m+k)$ (vo vnútorných vrcholoch si budeme naviac udr¾iava» pointre na lexikograficky najmen¹í a najväè¹í list podstromu a v listoch pointer na ïal¹í list v lex. poradí)
63 \itemitem{-}poèet výskytov (v ka¾dom vnútornom vrchole budeme ma» predpoèítaný poèet listov, ktoré sa pod ním nachádzajú)
64 \item{2.} najdlh¹ie opakujúce sa podslovo
65 \itemitem{$\cong$} najhlb¹ie vetvenie (písmenkovo najhlb¹í vnútorný vrchol)
66 \item{3.} histogram $k$-podslov (èetnos» slov då¾ky $k$)
67 \itemitem{-} odre¾eme strom v písmenkovej håbke $k$ a spoèítame odrezané vetvièky
68 \item{4.}najdlh¹í spoloèný podre»azec slov $\alpha$ a $\beta$ ($LCS(\alpha, \beta)$)
69 \itemitem{-}postavíme strom pre slovo $\alpha\$_1\beta\$_2$; najhlb¹í vrchol, pod ktorým je $\alpha$-ový i $\beta$-ový sufix ($\$_1$ i $\$_2$) odpovedá $LCS(\alpha,\beta)$
70 \item{5.}najdlh¹ie palindromické podslovo ($\beta$ je palindromické $\equiv \beta = \beta^{\rm R}$)
71 \itemitem{-} Postavíme sufixový strom pre $\alpha\$_1\alpha^R\$_2$. Postupne prechádzame cez v¹etky potenciálne stredy palindromu (je ich $2n-1$) a poèítame:
72 \itemitemitem{$\bullet$}$LCP(\alpha[i:], \alpha^{\rm R}[n-(i+1):])$, keï uva¾ujeme ako stred palindromu $i$-té písmenko (èíslované od 0) (tj. palindrom nepárnej då¾ky)
73 \itemitemitem{$\bullet$}$LCP(\alpha[i+1:], \alpha^{\rm R}[n-(i+1)])$, keï uva¾ujeme stred palindromu medzi $i$-tým a $(i+1)$-vým písmenkom (tj. palindrom párnej då¾ky).
74 \itemitem{}$LCP(\alpha,\beta)$ je najdlh¹í spoloèný prefix $\alpha$ a $\beta$ a v strome je to najhlb¹í spoloèný predchodca ($LCA$) listov odpovedajúcich $\alpha$ a $\beta$.
75 \itemitem{}Pritom treba ¹ikovne liez» po strome, aby nájdenie ïal¹ej odpovedajúcej si dvojice listov bolo kon¹tantné.
76 \itemitem{}Na nájdenie $LCA$ pou¾ijeme nejakú ¹truktúru, ktorá to po lineárnom predvýpoète zvládne v kon¹tantnom èase.
77 \item{6.}Burrows-Wheeler transform (BWT)
79 \h{Rekurzívna kon¹trukcia sufixového stromu v lineárnom èase}
80 \s{Definícia:} {\it Suffix Array} $A$ pre slovo $\sigma$ je permutácia na sufixoch slova $\sigma$, ktorá ich zotriedi lexikograficky:\hfil\break
81 $\sigma[A[i]:]<_{lex}\sigma[A[i+1]:]$, kde $\sigma[j:]$ znaèí podslovo $\sigma$ poènúc $j$-tým písmenkom a¾ do konca.
83 \s{Definícia:} {\it LCP Array} $L$ pre slovo $\sigma$:\hfil\break
84 $L[i]=\vert LCP(\sigma[A[i]:], \sigma[A[i+1]:])\vert$, kde $LCP(\alpha, \beta)$ je najdlh¹í spoloèný prefix $\alpha$ a $\beta$.
86 \s{Definícia:} {\it Kartézsky strom} pre postupnos» kµúèov $x_1\ldots x_n$ je strom, ktorý je haldou podµa hodnôt kµúèov a vyhµadávacím stromom podµa poradia kµúèov v postupnosti. Pritom vrcholy s rovnakou hodnotou, ktoré by spolu susedili, zlúèime do jedného.
88 Niektoré vrcholy majú voµné miesta, kde by mohol by» pripojený podstrom. Týmto voµným miestam budeme hovori» {\it voµné sloty}.
90 \tabskip=0pt plus 1fil
92 \hfil#\hfil&\hfil#\hfil\cr
93 \epsfbox{ct-35120024224.eps}&\epsfbox{ct-35120024224-fs.eps}\cr
94 Kartézsky strom pre $(3,5,1,2,0,0,2,4,2,2,4)$ & \dots s vyznaèenými voµnými slotmi\cr
98 \s{Lemma:} Kartézsky strom pre $x_1\ldots x_n$ sa dá postavi» v èase $\O(n)$.\qed
99 \s{Lemma:} Sufixový strom (ST) pre $\sigma$ a $(A,L)$ pre $\sigma$ sú lineárne izomorfné.\par
101 ${\rm ST}\longrightarrow(A,L)$:
102 \itemitem{}Prechádzame strom zµava doprava (tj. lexikograficky). V¾dy, keï sme v liste, opí¹eme do $A[i]$ index do $\sigma$, ktorý sme v liste na¹li; $i$ inicializujeme na $-1$ a pri ka¾dej náv¹teve listu zväè¹ujeme o $1$ (e¹te pred zápisom do $A[i]$).
103 \itemitem{}Medzi náv¹tevou 2 susedných listov v¾dy najskôr stúpame a potom sa znova ponoríme. Najvy¹¹í vrchol, po ktorý sme vystúpili medzi náv¹tevou listov $\alpha$ a $\beta$, odpovedá $LCP(\alpha,\beta)$, jeho håbka odpovedá $\vert LCP(\alpha, \beta)\vert$. Do $L[i]$ teda zapí¹eme håbku tohto najhlb¹ieho spoloèného predka, ktorú si poèítame v rekurzii.
105 $(A,L)\longrightarrow{\rm ST}$:
106 \itemitem{}Staviame kartézsky strom pre $L$ a do voµných slotov privesujeme listy. Tento strom má tvar sufixového stromu pre $\sigma$. Indexy v listoch urèujeme podµa $A$. Nálepky na hranách urèujeme podµa indexov v listoch podstromu a (písmenkovej) håbky vrcholov (ktorú pre vnútorné vrcholy máme v $L$ a pre listy vypoèítame ako $\vert\sigma\vert - A[i]$).\qed
109 Ná¹ algoritmus bude kon¹truova» $(A,L)$, ktoré u¾ teraz vieme v lineárnom èase previes» na sufixový strom.
112 \:(Z abecedy vyhodíme nepou¾ité znaky.)
113 \itemitem{}Pou¾ité znaky zotriedime priehradkovým triedením v èase $\O(n)$ a premenujeme na $1,\ldots,n'$, $n'\le n$.
115 \:Definujeme slová $\sigma_0$, $\sigma_1$, $\sigma_2$ nasledujúcim spôsobom:
116 %\settabs\+\itemitemitem{}&$\sigma_2[i] := (\sigma[3i+2],$ &$\sigma[3i+3],$ &$\sigma[3i+4])$\cr
118 \sigma_0[i] &:= (\sigma[3i],\sigma[3i+1],\sigma[3i+2])\cr
119 \sigma_1[i] &:= (\sigma[3i+1],\sigma[3i+2],\sigma[3i+3])\cr
120 \sigma_2[i] &:= (\sigma[3i+2],\sigma[3i+3],\sigma[3i+4])\cr
122 \itemitem{}$\sigma_0$, $\sigma_1$, $\sigma_2$ sú slová då¾ky $\approx{n\over3}$ nad abecedou $[n']^3$. (Opä» ale z nej pou¾ijeme najviac $n$ znakov.)
124 \:Zavoláme sa rekurzívne na $\sigma_0\sigma_1$, získame $(A_{01},L_{01})$. Z $A_{01}$ doká¾eme jedným priechodom vyrobi» $A_0$, $A_1$, $A_{01}^{-1}$. ($A_{01}^{-1}$ je inverzná permutácia k $A_{01}$)
126 \:Dopoèítame $A_2$.\par
127 \itemitem{}Vyu¾ijeme, ¾e $\sigma_2[i:]\approx\sigma[3i+2:]=\sigma[3i+2]\sigma[3i+3:]\approx\sigma[3i+2]\sigma_0[i+1:]$.
128 \itemitem{}Pre slová $\sigma_2[i:]\approx\sigma[3i+2]\sigma_0[i+1:]$ máme usporiadanie podµa druhej èasti (tj. podµa $\sigma_0[i+1:]$) v $A_0$. V tomto poradí ich nahád¾eme do priehradok podµa prvého znaku prvého znaku (tj. podµa $\sigma[3i+2]$) a vysypeme do $A_2$.
130 \:$A_0,A_1,A_2\buildrel merge\over\longrightarrow A$
131 \itemitem{}Nech $a$, $b$, $c$, sú aktuálne pozície v $A_0$, $A_1$, $A_2$ (v tomto poradí) pri zlievaní. Nech $i=A_0[a]$, $j=A_1[b]$, $k=A_2[c]$. Potrebujeme porovna» slová $\sigma_0[i:]$, $\sigma_1[j:]$, $\sigma_2[k:]$ v kon¹tantnom èase.
133 \sigma_0[i:] < \sigma_1[j:] &\equiv A_{01}^{-1}[i] < A_{01}^{-1}[\vert\sigma_0\vert+j]\cr
134 \sigma_0[i:] < \sigma_2[k:] &\equiv \sigma[3i]\,\sigma_1[i:] < \sigma[3k+2]\,\sigma_0[k+1:]\cr
135 &\Leftrightarrow (\sigma[3i] < \sigma[3k+2]) \vee (\sigma[3i] = \sigma[3k+2] \wedge \sigma_1[i:] < \sigma_0[k+1:])\cr
136 \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:]
140 \itemitem{} Pripomeòme definíciu $L[i]=\vert LCP(\sigma[A[i]:], \sigma[A[i+1]:])\vert$.
143 \halign{\hfil#\tabskip=0pt&#\hfil&#\hfil\cr
144 $\sigma[A[i]:]$ &$\approx \sigma_0[j:]$,\quad&tj. $A[i]=3j$ pre nejaké $j$,\cr
145 $\sigma[A[i+1]:]$ &$\approx \sigma_0[k:]$,&tj. $A[i+1]=3k$ pre nejaké $k$.\cr
147 \itemitem{} Oznaème tento prípad $\vs{\sigma_0}{\sigma_0}$. Potom $L[i]=L_{01}[A_{01}^{-1}[A[i] \div 3]]$.
148 \itemitem{} Prípad $\vs{\sigma_0}{\sigma_1}$ vyrie¹ime rovnako.
149 \itemitem{} Prípady $\vs{\sigma_1}{\sigma_0}$ a $\vs{\sigma_1}{\sigma_1}$: $L[i]=L_{01}[A_{01}^{-1}[A[i] \div 3 + \vert\sigma_0\vert]]$
150 \+\cleartabs\itemitem{} &$\vs{\sigma_2}{\sigma_2}$: &a$)$ lí¹ia sa prvým znakom $\Rightarrow L[i]=0$\cr
151 \+&&b$)$ $L[i]=1+(\vs{\sigma_0}{\sigma_0})$\cr
152 \+&$\vs{\sigma_2}{\sigma_0}$: &a$)$ lí¹ia sa prvým znakom $\Rightarrow L[i]=0$\cr
153 \+&&b$)$ $L[i]=1+(\vs{\sigma_0}{\sigma_1})$\cr
154 \+&$\vs{\sigma_2}{\sigma_1}$: &a$)$ lí¹ia sa prvým znakom $\Rightarrow L[i]=0$\cr
155 \+&&b$)$ lí¹ia sa druhým znakom $\Rightarrow L[i]=1$\cr
156 \+&&c$)$ $L[i]=2+(\vs{\sigma_1}{\sigma_0})$\cr
160 \s{Odhad èasovej zlo¾itosti}\par
161 $T(n) = T({2\over3}n) + \O(n) = \O(n)$
163 \h{Ukkonenova inkrementální konstrukce}
165 Pomocí Ukkonnenovy konstrukce doká¾eme sestrojit suffixový strom v lineárním èase. Algoritmus je navíc inkrementální, v ka¾dém kroku tak ze stávajícího suffixového stromu ($ST$ pro $\sigma$) vyrobí strom odpovídající roz¹íøenému slovu ($\sigma a$). Vychází pøitom ze stromu pro prázdné slovo (prázdný strom), který postupnì roz¹iøuje.
167 Roz¹íøení suffixového stromu doká¾e algoritmus provést v amortizovanì konstantním èase.
169 \s{Pozorování:}Následující pozorování platí pro roz¹iøování suffixového stromu pro $\sigma$ na suffixový strom pro $\sigma a$:
171 \:Pokud bylo slovo vìtvící v $\sigma$, pak bude stale vìtvící
172 \:Pokud byl uzel nevnoøený, bude stále nevnoøený
173 \:listy zùstávají jako listy (musím na hranu, ktera do nìj vede pøipsat $a$) -- øe¹íme otevøenými hranami (ne nálepka odsud sem, ale odsud dokonce) - slo¾itost - $O(0)$
174 \:vnitøní vrcholy $\to$ vnitøní vrcholy
175 \:Mohou vznikat nové vrcholy (listy i vnitøní), slovo nevìtvící se tak mù¾e stát vìtvícím
178 \s{Definice:Aktivni suffix ($\alpha(\sigma)$)} nazýváme nejdel¹í vnoøený suffix $\sigma$
180 \s{Lemma:} Pro ka¾dé $\sigma$, $a$ platí: $\alpha(\sigma a)$ je suffixem $\alpha(\sigma)a$
182 \s{Dùkaz:} $\alpha(\sigma a)$, $\alpha(\sigma)a$ jsou suffixy $\sigma a$, z toho plyne, ¾e staèí porovnat délky abychom lemma ovìøili.
183 Platí: $ \vert\alpha(\sigma a)\vert \le \vert\alpha(\sigma)a\vert$ (pøidáním písmene nemù¾u prodlou¾it prefix o více ne¾ jeden znak).
185 \s{Definice:Zralé suffixy} jsou ty prefixy $\alpha$, pro ktere platí:
186 $\forall \sigma, a,\beta: \beta a$ suffix $\sigma a$ je {\it zralý} právì kdy¾ $ \vert\alpha(\sigma)a\vert \ge \vert\beta a\vert > \vert\alpha(\sigma a)\vert$
188 Update je $O(1)$ amortizovanì na $1$ roz¹íøení $\sigma$
190 $\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.
192 \s{Definice: $back[v]$} je nejdel¹í vlastní suffix $v$, ke kterému existuje vrchol.
195 \:Vstup: $\sigma, a, (v, \alpha)$
197 // 1. Zalo¾ení listù/Podrozdìlení hran
198 \:if $\alpha = \epsilon$:
199 \::if $\exists (v, a* )$
203 \:else if $\alpha \ne \epsilon$:
204 \::if $\exists (v, \alpha a*)$:
207 \:::podrozdìlím hranu na které le¾í $\alpha$ // za $\alpha$ vlo¾ím odboèku na $a$, kam dám list a pokraèuju
209 // 2. Pøechod na dal¹í vrchol
210 \:zkrátim $\alpha$ zleva o znak
212 \::pøejdu do $( \epsilon, \alpha bez 1. znaku)$
214 \::pøejdu do $( back[v], \alpha )$
217 \:kanonikalizuji // "jdu z $v$ pøes alpha do co nejdal"
221 \s{Èasová slo¾itost:}
223 \:Zalo¾ení listu/Podrozdìlení hrany -- $O(1)$
224 \:Pøechod na dal¹í vrchol -- $O(1)$ za pøedpokladu existence $back(v)$
225 \:Kanonikalizace -- amortizovanì za $O(1)$
226 \: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)$.