Bugfix.

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

\input ../sgr.tex

\def\leaderfill{\leaders\hbox to .5em{\hss.\hss}\hfill}
\def\itemitemitem{\par\indent\indent \hangindent3\parindent \textindent}
\dimen0 = \hsize
\divide \dimen0 by 6
\def\vs#1#2{#1~{\rm vs.}~#2}

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

\s {Definícia:}
\+\indent&\hbox to \dimen0 {$\Sigma$\leaderfill}&koneèná abeceda (mno¾ina znakov)\cr
\+&$\Sigma^*$\leaderfill&mno¾ina v¹etkých slov nad $\Sigma$\cr
\+&$\epsilon$\leaderfill&prázdne slovo\cr
\+&$\alpha\beta$\leaderfill&zre»azenie slov $\alpha,\beta\in\Sigma^*$\cr
\+&$\alpha^n$\leaderfill&$n=0: \alpha^0=\epsilon$\cr
\+&&$n>0: \alpha^n=\alpha\alpha^{n-1}$\cr
\+&$\alpha^{\rm R}$\leaderfill&slovo $\alpha$ odzadu\cr
\settabs\+\indent&$\alpha$ je {\it (vlastným) podslovom} $\beta$ &\cr
\+&$\alpha$ je {\it (vlastným) prefixom} $\beta$ &$\equiv  \exists\gamma(\not=\epsilon):\beta=\alpha\gamma$\cr
\+&$\alpha$ je {\it (vlastným) sufixom} $\beta$ &$\equiv  \exists\gamma(\not=\epsilon):\beta=\gamma\alpha$\cr
\+&$\alpha$ je {\it (vlastným) podslovom} $\beta$ &$\equiv  \alpha$ je prefixom nejakého sufixu $\beta$ (a $\alpha\not=\beta$)\cr

\h{Trie}
\s{Definícia:} {\it Trie ($\Sigma$-strom)} pre $X\subset\Sigma^*, \vert X\vert<\infty$ je orientovaný graf $G(V,E)$:\par
$V = \lbrace\alpha\vert\alpha\hbox{ je prefixom nejakého }\beta\in X\rbrace$\par
$(\alpha,\beta)\in E \equiv \exists x\in\Sigma:\beta=\alpha x$\par

\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$.

\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).

Vrcholom, ktoré padli za obe» kompresii budeme hovori» {\it skryté vrcholy}.\par
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
\s{Pozorovanie:} Listy (komprimovanej) trie sú práve slová z $X$.

\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

\h{Sufixové stromy}
\s{Definícia:} {\it Sufixový strom} pre slovo $\sigma\in\Sigma^*$ je komprimovaná trie pre $X=\lbrace {\rm sufixy~}\sigma\rbrace$.

\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$).

V listoch si budeme znaèi» index do $\sigma$, kde daný sufix zaèína.

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

\s{Lemma:} Sufixový strom pre slovo $\sigma$ då¾ky $n$ je reprezentovateµný v priestore $\O(n)$.\par
\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

\s{Veta:} Sufixový strom pre slovo då¾ky $n$ sa dá zostroji» v èase $\O(n)$.\par
\s{Dôkaz:} Budú uvedené 2 kon¹trukcie v lineárnom èase.\qed

\s{Aplikácie} (alebo èo doká¾eme v èase $\O(n)$):\par
\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))
\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í)
\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ú)
\item{2.} najdlh¹ie opakujúce sa podslovo
\itemitem{$\cong$} najhlb¹ie vetvenie (písmenkovo najhlb¹í vnútorný vrchol)
\item{3.} histogram $k$-podslov (èetnos» slov då¾ky $k$)
\itemitem{-} odre¾eme strom v písmenkovej håbke $k$ a spoèítame odrezané vetvièky
\item{4.}najdlh¹í spoloèný podre»azec slov $\alpha$ a $\beta$ ($LCS(\alpha, \beta)$)
\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)$
\item{5.}najdlh¹ie palindromické podslovo ($\beta$ je palindromické $\equiv \beta = \beta^{\rm R}$)
\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:
\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)
\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).
\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$.
\itemitem{}Pritom treba ¹ikovne liez» po strome, aby nájdenie ïal¹ej odpovedajúcej si dvojice listov bolo kon¹tantné.
\itemitem{}Na nájdenie $LCA$ pou¾ijeme nejakú ¹truktúru, ktorá to po lineárnom predvýpoète zvládne v kon¹tantnom èase.
\item{6.}Burrows-Wheeler transform (BWT)

\h{Rekurzívna kon¹trukcia sufixového stromu v lineárnom èase}
\s{Definícia:} {\it Suffix Array} $A$ pre slovo $\sigma$ je permutácia na sufixoch slova $\sigma$, ktorá ich zotriedi lexikograficky:\hfil\break
$\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.

\s{Definícia:} {\it LCP Array} $L$ pre slovo $\sigma$:\hfil\break
$L[i]=\vert LCP(\sigma[A[i]:], \sigma[A[i+1]:])\vert$, kde $LCP(\alpha, \beta)$ je najdlh¹í spoloèný prefix $\alpha$ a $\beta$.

\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.

Niektoré vrcholy majú voµné miesta, kde by mohol by» pripojený podstrom. Týmto voµným miestam budeme hovori» {\it voµné sloty}.

\tabskip=0pt plus 1fil
\halign to\hsize{
\hfil#\hfil&\hfil#\hfil\cr
\epsfbox{ct-35120024224.eps}&\epsfbox{ct-35120024224-fs.eps}\cr
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
}
\smallskip

\s{Lemma:} Kartézsky strom pre $x_1\ldots x_n$ sa dá postavi» v èase $\O(n)$.\qed
\s{Lemma:} Sufixový strom (ST) pre $\sigma$ a $(A,L)$ pre $\sigma$ sú lineárne izomorfné.\par
\s{Dôkaz:}\par
${\rm ST}\longrightarrow(A,L)$:
\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]$).
\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.

$(A,L)\longrightarrow{\rm ST}$:
\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

\medskip
Ná¹ algoritmus bude kon¹truova» $(A,L)$, ktoré u¾ teraz vieme v lineárnom èase previes» na sufixový strom.

\algo
\:(Z abecedy vyhodíme nepou¾ité znaky.)
\itemitem{}Pou¾ité znaky zotriedime priehradkovým triedením v èase $\O(n)$ a premenujeme na $1,\ldots,n'$, $n'\le n$.

\:Definujeme slová $\sigma_0$, $\sigma_1$, $\sigma_2$ nasledujúcim spôsobom:
%\settabs\+\itemitemitem{}&$\sigma_2[i] := (\sigma[3i+2],$ &$\sigma[3i+3],$ &$\sigma[3i+4])$\cr
$$\eqalign{
\sigma_0[i] &:= (\sigma[3i],\sigma[3i+1],\sigma[3i+2])\cr
\sigma_1[i] &:= (\sigma[3i+1],\sigma[3i+2],\sigma[3i+3])\cr
\sigma_2[i] &:= (\sigma[3i+2],\sigma[3i+3],\sigma[3i+4])\cr
}$$
\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.)

\: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}$)

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

\:$A_0,A_1,A_2\buildrel merge\over\longrightarrow A$
\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.
$$\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$.
\itemitem{} Pripomeòme definíciu $L[i]=\vert LCP(\sigma[A[i]:], \sigma[A[i+1]:])\vert$.
\itemitem{} Nech
\tabskip=3\parindent
\halign{\hfil#\tabskip=0pt&#\hfil&#\hfil\cr
$\sigma[A[i]:]$ &$\approx \sigma_0[j:]$,\quad&tj. $A[i]=3j$ pre nejaké $j$,\cr
$\sigma[A[i+1]:]$ &$\approx \sigma_0[k:]$,&tj. $A[i+1]=3k$ pre nejaké $k$.\cr
}
\itemitem{} Oznaème tento prípad $\vs{\sigma_0}{\sigma_0}$. Potom $L[i]=L_{01}[A_{01}^{-1}[A[i] \div 3]]$.
\itemitem{} Prípad $\vs{\sigma_0}{\sigma_1}$ vyrie¹ime rovnako.
\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]]$
\+\cleartabs\itemitem{} &$\vs{\sigma_2}{\sigma_2}$: &a$)$ lí¹ia sa prvým znakom $\Rightarrow L[i]=0$\cr
\+&&b$)$ $L[i]=1+(\vs{\sigma_0}{\sigma_0})$\cr
\+&$\vs{\sigma_2}{\sigma_0}$: &a$)$ lí¹ia sa prvým znakom $\Rightarrow L[i]=0$\cr
\+&&b$)$ $L[i]=1+(\vs{\sigma_0}{\sigma_1})$\cr
\+&$\vs{\sigma_2}{\sigma_1}$: &a$)$ lí¹ia sa prvým znakom $\Rightarrow L[i]=0$\cr
\+&&b$)$ lí¹ia sa druhým znakom $\Rightarrow L[i]=1$\cr
\+&&c$)$ $L[i]=2+(\vs{\sigma_1}{\sigma_0})$\cr

\endalgo

\s{Odhad èasovej zlo¾itosti}\par
$T(n) = T({2\over3}n) + \O(n) = \O(n)$

\h{Ukkonenova inkrementální konstrukce}

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.

Roz¹íøení suffixového stromu doká¾e algoritmus provést v amortizovanì konstantním èase.

\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$:
\numlist\ndotted
\:Pokud bylo slovo vìtvící v $\sigma$, pak bude stale vìtvící
\:Pokud byl uzel nevnoøený, bude stále nevnoøený
\: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)$
\:vnitøní vrcholy $\to$ vnitøní vrcholy
\:Mohou vznikat nové vrcholy (listy i vnitøní), slovo nevìtvící se tak mù¾e stát vìtvícím
\endlist

\s{Definice:Aktivni suffix ($\alpha(\sigma)$)} nazýváme nejdel¹í vnoøený suffix $\sigma$

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

\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.
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).

\s{Definice:Zralé suffixy} jsou ty prefixy $\alpha$, pro ktere platí:
$\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$

Update je $O(1)$ amortizovanì na $1$ roz¹íøení $\sigma$

$\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 = \epsilon$:
\::if $\exists (v, a* )$
\:::konec
\::else:
\:::zalo¾ím list
\:else if $\alpha \ne \epsilon$:
\::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 = \epsilon$:
\::pøejdu do $( \epsilon, \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