\input ../sgr.tex
-\prednaska{10}{Suffixové stromy}{}
+\prednaska{10}{Suffixové stromy}{}
-V~této kapitole popí¹eme jednu pozoruhodnou datovou strukturu, pomocí ní¾ doká¾eme problémy týkající
-se øetìzcù pøevádìt na grafové problémy a øe¹it je tak v~lineárním èase.
+V~této kapitole popíšeme jednu pozoruhodnou datovou strukturu, pomocí níž dokážeme problémy týkající
+se řetězců převádět na grafové problémy a řešit je tak v~lineárním čase.
-\h{Øetìzce, trie a suffixové stromy}
+\h{Řetězce, trie a suffixové stromy}
\ss{Definice:}
\nointerlineskip
\halign{\qquad#\dotfill&~#\hfil\cr
\hbox to 0.35\hsize{}\cr
-$\Sigma$ & koneèná abeceda -- mno¾ina znakù \cr
-\omit & (znaky budeme znaèit latinskými písmeny)\cr
-$\Sigma^*$ & mno¾ina v¹ech slov nad $\Sigma$ \cr
-\omit & (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$ \cr
-\omit & (analogicky vlastní suffix a podslovo)\cr
+$\Sigma$ & konečná abeceda -- množina znaků \cr
+\omit & (znaky budeme značit latinskými písmeny)\cr
+$\Sigma^*$ & množina všech slov nad $\Sigma$ \cr
+\omit & (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$ \cr
+\omit & (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{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 mno¾inu slov $X\subset\Sigma^*$ je orientovaný graf $G=(V,E)$, kde:
+\s{Definice:} {\I Trie ($\Sigma$-strom)} pro konečnou množinu slov $X\subset\Sigma^*$ je orientovaný graf $G=(V,E)$, kde:
\itemize\relax
-\:$V = \{\alpha: \alpha\hbox{ je prefixem nìjakého $\beta\in X$} \},$
+\:$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ími prefixy 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$ dávají právì slovo~$\alpha$.
+\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$.
+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$.
-\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 hran vycházejících z~jednoho vrcholu se li¹í v~prvním
-znaku. Vrcholùm \uv{uvnitø hran} (které padly za obì» kompresi) budeme øíkat {\I skryté vrcholy.}
+\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 hran vycházejících z~jednoho vrcholu se liší v~prvním
+znaku. Vrcholům \uv{uvnitř hran} (které padly za oběť kompresi) budeme říkat {\I skryté vrcholy.}
-\s{Definice:} {\I Suffixový strom (ST)} pro slovo $\sigma\in\Sigma^*$ je komprimovaná trie pro $X=\{\alpha: \hbox{$\alpha$ je suffixem $\sigma$}\}$.
+\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$.
+\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. Neprázdné suffixy slova $\sigma\$$ odpovídají suffixùm slova~$\sigma$
-a ¾ádný z~nich nemù¾e být vnoøený. Takový suffixový strom budeme znaèit ST\$.
+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. Neprázdné suffixy slova $\sigma\$$ odpovídají suffixům slova~$\sigma$
+a žádný z~nich nemůže být vnořený. Takový suffixový strom budeme značit ST\$.
-\s{Pøíklad:}
+\s{Příklad:}
-\figure{baraba.eps}{Suffixy slova \uv{baraba}: trie, suffixový strom, ST s~dolarem}{\epsfxsize}
+\figure{baraba.epdf}{Suffixy slova \uv{baraba}: trie, suffixový strom, ST s~dolarem}{\epsfxsize}
-\>Nyní jak je to s~konstrukcí suffixových stromù:
+\>Nyní jak je to s~konstrukcí suffixových stromů:
-\s{Lemma:} Suffixový strom pro slovo $\sigma$ délky $n$ je reprezentovatelný v~prostoru $\O(n)$.
+\s{Lemma:} Suffixový strom pro slovo $\sigma$ délky $n$ je reprezentovatelný v~prostoru $\O(n)$.
-\proof 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 staèí popsat
-poèáteèní a koncovou pozicí v~$\sigma$.
+\proof 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 stačí popsat
+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{Věta:} Suffixový strom pro slovo $\sigma$ délky $n$ lze sestrojit v~čase $\O(n)$.
-\proof Ve~zbytku této kapitoly pøedvedeme dvì rùzné konstrukce v~lineárním èase.
+\proof 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:
+\s{Aplikace} -- co vše dokážeme v~lineárním čase, když umíme lineárně konstruovat ST:
\nobreak
\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\$ 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 v~ST\$ 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; jak moc si ji
-mù¾eme dovolit zvìt¹it, vyplyne z~konkrétních konstrukcí.}
-
-\:{\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} \cite{burrows:bwt} -- jejím základem je lexikografické setøídì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 vypsáním novì vzniklých listù v~poøadí
+\:{\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\$ 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 v~ST\$ 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Ä\9b můžeme sestrojit ST\$ pro libovolnou
+množinu slov.\foot{Jen si musíme dát pozor, abychom si moc nezvětšili abecedu; jak moc si ji
+můžeme dovolit zvětšit, vyplyne z~konkrétních konstrukcí.}
+
+\:{\I NejdelÅ¡Ã palindromické podslovo} (tj. takové $\beta\subset\alpha$, pro nÄ\9bž 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} \cite{burrows:bwt} -- jejím základem je lexikografické setřídě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 vypsáním nově vzniklých listů v~pořadí
\uv{zleva doprava}.
\endlist
-\s{Cvièení:} Zkuste vymyslet co nejlep¹í algoritmy pro tyto problémy bez pou¾ití~ST.
+\s{Cvičení:} Zkuste vymyslet co nejlepší algoritmy pro tyto problémy bez použití~ST.
-\h{Suffixová pole}
+\h{Suffixová pole}
-\>V~nìkterých pøípadech se hodí místo suffixového stromu pou¾ívat kompaktnìj¹í datové struktury.
+\>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]$ znaèit jeho $i$-tý znak (èíslujeme od~nuly),
-$\sigma[i:j]$ pak podslovo $\sigma[i]\sigma[i+1]\ldots\sigma[j-1]$. Libovolnou z~mezí mù¾eme vynechat, proto
-$\sigma[i:{}]$ bude suffix od~$i$ do~konce a $\sigma[{}:j]$ prefix od~zaèátku do~$j-1$.
-Pokud $j\le i$, definujeme $\sigma[i:j]$ jako prázdné slovo, tak¾e prázdný suffix mù¾eme
-napøíklad zapsat jako $\sigma[\vert\sigma\vert:{}].$
+\s{Notace:} Pro slovo $\sigma$ bude $\sigma[i]$ značit jeho $i$-tý znak (číslujeme od~nuly),
+$\sigma[i:j]$ pak podslovo $\sigma[i]\sigma[i+1]\ldots\sigma[j-1]$. Libovolnou z~mezà můžeme vynechat, proto
+$\sigma[i:{}]$ bude suffix od~$i$ do~konce a $\sigma[{}:j]$ prefix od~začátku do~$j-1$.
+Pokud $j\le i$, definujeme $\sigma[i:j]$ jako prázdné slovo, takže prázdný suffix můžeme
+například zapsat jako $\sigma[\vert\sigma\vert:{}].$
-${\rm LCP}(\alpha,\beta)$ bude znaèit délku nejdel¹ího spoleèného prefixu slov $\alpha$ a $\beta$,
-èili nejvìt¹í $i\le \vert\alpha\vert,\vert\beta\vert$ takové, ¾e $\alpha[{}:i]=\beta[{}:i]$.
+${\rm LCP}(\alpha,\beta)$ bude značit délku nejdelšího společného prefixu slov $\alpha$ a $\beta$,
+Ä\8dili nejvÄ\9btÅ¡Ã $i\le \vert\alpha\vert,\vert\beta\vert$ takové, že $\alpha[{}:i]=\beta[{}:i]$.
-\s{Definice:} {\I Suffixové pole (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
-$0,\ldots,n$, pro ní¾ $\sigma[A[0]:{}] < \sigma[A[1]:{}] < \ldots < \sigma[A[n]:{}]$.
+\s{Definice:} {\I Suffixové pole (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
+$0,\ldots,n$, pro nÞ $\sigma[A[0]:{}] < \sigma[A[1]:{}] < \ldots < \sigma[A[n]:{}]$.
-\s{Definice:} {\I Pole nejdel¹ích spoleèných prefixù (Longest Common Prefix Array)} $L_\sigma$ pro slovo $\sigma$ je posloupnost,
-v~ní¾ $L_\sigma[i]:={\rm LCP}(A_\sigma[i],A_\sigma[i+1])$.
+\s{Definice:} {\I Pole nejdelších společných prefixů (Longest Common Prefix Array)} $L_\sigma$ pro slovo $\sigma$ je posloupnost,
+v~nÞ $L_\sigma[i]:={\rm LCP}(A_\sigma[i],A_\sigma[i+1])$.
-\s{Vìta:} Suffixový strom pro slovo $\sigma\$$ a dvojici $(A_\sigma,L_\sigma)$ na sebe lze
-v~lineárním èase pøevádìt.
+\s{Věta:} Suffixový strom pro slovo $\sigma\$$ a dvojici $(A_\sigma,L_\sigma)$ na sebe lze
+v~lineárním čase převádět.
-\proof Kdy¾ projdeme ST($\sigma\$$) do hloubky, poøadí listù odpovídá posloupnosti $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$ (získáme vnitøní vrcholy ST), doplníme do~nìj listy, pøiøadíme jim suffixy podle~$A_\sigma$
-a nakonec podle listù rekonstruujeme nálepky hran.
+\proof Když projdeme ST($\sigma\$$) do hloubky, pořadí listů odpovídá posloupnosti $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$ (získáme vnitřní vrcholy ST), doplníme do~něj listy, přiřadíme jim suffixy podle~$A_\sigma$
+a nakonec podle listů rekonstruujeme nálepky hran.
\qed
-\h{Rekurzivní konstrukce}
+\h{Rekurzivní konstrukce}
-\>Uká¾eme algoritmus, který pro slovo $\sigma\in\Sigma^*$ délky~$n$ sestrojí jeho suffixové pole
-a LCP pole 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 tedy dostaneme lineární konstrukci
-ST($\sigma$) pro libovolnou fixní abecedu.
+\>Ukážeme algoritmus, který pro slovo $\sigma\in\Sigma^*$ délky~$n$ sestrojí jeho suffixové pole
+a LCP pole 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 tedy dostaneme lineární konstrukci
+ST($\sigma$) pro libovolnou fixní abecedu.
-\s{Algoritmus:} (Konstrukce $A$ a $L$ podle Kärkkäinena a Sanderse \cite{karkkainen03simple})
+\s{Algoritmus:} (Konstrukce $A$ a $L$ podle Kärkkäinena a Sanderse \cite{karkkainen03simple})
\algo
-\:Redukujeme abecedu na~$1\ldots n$: ve~vstupním slovu je nejvý¹e $n$ rùzných znakù,
-tak¾e je staèí setøídit a pøeèíslovat.
+\:Redukujeme abecedu na~$1\ldots n$: ve~vstupním slovu je nejvýše $n$ různých znaků,
+takže je stačí setřídit a přečíslovat.
-\:Definujeme slova $\sigma_0$, $\sigma_1$, $\sigma_2$ následovnì:
+\: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
}$$
-V¹echna $\sigma_k$ jsou slova délky $\approx n/3$ nad~abecedou velikosti $n^3$. Dovolíme
-si mírnì zneu¾ívat notaci a pou¾ívat symbol $\sigma_k$ i jejich pøepis do~abecedy pùvodní.
+Všechna $\sigma_k$ jsou slova délky $\approx n/3$ nad~abecedou velikosti $n^3$. Dovolíme
+si mírně zneužívat notaci a používat symbol $\sigma_k$ i jejich přepis do~abecedy původní.
-\:Zavoláme algoritmus rekurzivnì na slovo $\sigma_0\sigma_1$, èím¾ získáme $A_{01}$ a $L_{01}$.
-(Suffixy slova $\sigma_0\sigma_1$ odpovídají suffixùm slov $\sigma_0$ a~$\sigma_1$.)
+\:Zavoláme algoritmus rekurzivně na slovo $\sigma_0\sigma_1$, čímž získáme $A_{01}$ a $L_{01}$.
+(Suffixy slova $\sigma_0\sigma_1$ odpovídají suffixům slov $\sigma_0$ a~$\sigma_1$.)
-\:Spoèítáme pole $P_0$ a $P_1$, která nám budou øíkat, kde se v~$A_{01}$ vyskytuje
-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$.
-Jinými slovy, $P_0$ a~$P_1$ budou èásti inverzní permutace k~$A_{01}$. V¹imnìte si,
-¾e platí $P_i[x] < P_j[y]$ právì tehdy, kdy¾ $\sigma_i[x:{}] < \sigma_j[y:{}]$, tak¾e
-suffixy slov $\sigma_0$ a~$\sigma_1$ od této chvíle umíme porovnávat v~èase~$\O(1)$.
+\:Spočítáme pole $P_0$ a $P_1$, která nám budou říkat, kde se v~$A_{01}$ vyskytuje
+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$.
+Jinými slovy, $P_0$ a~$P_1$ budou části inverzní permutace k~$A_{01}$. Všimněte si,
+že platà $P_i[x] < P_j[y]$ právÄ\9b tehdy, když $\sigma_i[x:{}] < \sigma_j[y:{}]$, takže
+suffixy slov $\sigma_0$ a~$\sigma_1$ od této chvíle umíme porovnávat v~čase~$\O(1)$.
-\: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:{}]$,
-odpovídá lexikografické poøadí suffixù $\sigma_2[i:{}]$ poøadí dvojic $(\sigma[3i+2],P_0[i+1])$.
-Tyto dvojice ov¹em mù¾eme setøídit dvìma prùchody pøihrádkového tøídìní.
+\:VytvoÅ\99Ã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:{}]$,
+odpovídá lexikografické pořadí suffixů $\sigma_2[i:{}]$ pořadí dvojic $(\sigma[3i+2],P_0[i+1])$.
+Tyto dvojice ovšem můžeme setřídit dvěma průchody přihrádkového třídění.
-\:Slijeme $A_{01}$ a~$A_2$ do~$A$: sléváme dvì setøídìné posloupnosti,
-tak¾e staèí umìt jejich prvky v~konstantním èase porovnat:
+\:Slijeme $A_{01}$ a~$A_2$ do~$A$: sléváme dvě setříděné posloupnosti,
+takže stačí umět jejich prvky v~konstantním čase porovnat:
$$\eqalign{
\sigma_0[i:{}] < \sigma_2[j:{}] \Leftrightarrow{} &\sigma[3i:{}] < \sigma[3j+2:{}] \cr
\Leftrightarrow{} &\sigma[3i]\,\sigma_1[i:{}] < \sigma[3j+2]\,\sigma_0[j+1:{}],\cr
\Leftrightarrow{} &\sigma[3i+1]\,\sigma[3i+2]\,\sigma_0[i+1:{}] < \cr
&\sigma[3j+2]\,\sigma[3j+3]\,\sigma_1[j+1:{}].\cr
}$$
-Poka¾dé tedy porovnáme nejvý¹e dvì dvojice znakù a pak dvojici suffixù slov $\sigma_0$ a $\sigma_1$,
-k~èemu¾ nám pomohou pole $P_0$ a~$P_1$.
+Pokaždé tedy porovnáme nejvýše dvě dvojice znaků a pak dvojici suffixů slov $\sigma_0$ a $\sigma_1$,
+k~čemuž nám pomohou pole $P_0$ a~$P_1$.
-\:Dopoèítáme $L$:
- \::Pokud v~$A$ sousedí suffix slova~$\sigma_{0,1}$ se suffixem slova~$\sigma_{0,1}$,
- sousedí tyto dva suffixy i v~$A_{01}$, tak¾e jejich LCP najdeme pøímo v~$L$.
- \::Setkají-li se dva suffixy slova~$\sigma_2$, v¹imneme si, ¾e
+\:Dopočítáme $L$:
+ \::Pokud v~$A$ sousedí suffix slova~$\sigma_{0,1}$ se suffixem slova~$\sigma_{0,1}$,
+ sousedí tyto dva suffixy i v~$A_{01}$, takže jejich LCP najdeme přímo v~$L$.
+ \::SetkajÃ-li se dva suffixy slova~$\sigma_2$, vÅ¡imneme si, že
$\sigma_2[i:{}] = \sigma[3i+2:\nobreak{}] = \sigma[3i+2]\,\sigma_0[i+1:{}]$.
- ${\rm LCP}(\sigma_2[i:{}],\sigma_2[j:{}])$ je tedy buïto~0 (pokud $\sigma[3i+2]\ne\sigma[3j+2]$),
- nebo $1+3\cdot{\rm LCP}(\sigma_0[i+1:{}],\sigma_0[j+1:{}])$, pøípadnì toté¾ zvý¹ené
- o~1 nebo~2, pokud se trojznaky v~$\sigma_0$ následující po LCP zèásti shodují.
- Pøitom ${\rm LCP}(\sigma_0[p:{}],\sigma_0[q:{}])$ spoèítáme pomocí~$L$.
- Je to toti¾ minimum intervalu v~$L$ mezi indexy $P_0[p]$ a~$P_0[q]$. To zjistíme
- v~konstantním èase pomocí struktury pro intervalová minima.
- \::Pokud se setká suffix slova~$\sigma_{0,1}$ se suffixem slova~$\sigma_2$, staèí
- tyto suffixy pøepsat podobnì jako v~6.~kroku a problém tím opìt pøevést
- na výpoèet LCP dvou suffixù slov~$\sigma_{0,1}$.
+ ${\rm LCP}(\sigma_2[i:{}],\sigma_2[j:{}])$ je tedy buďto~0 (pokud $\sigma[3i+2]\ne\sigma[3j+2]$),
+ nebo $1+3\cdot{\rm LCP}(\sigma_0[i+1:{}],\sigma_0[j+1:{}])$, případně totéž zvýšené
+ o~1 nebo~2, pokud se trojznaky v~$\sigma_0$ následující po LCP zčásti shodují.
+ Přitom ${\rm LCP}(\sigma_0[p:{}],\sigma_0[q:{}])$ spočítáme pomocí~$L$.
+ Je to totiž minimum intervalu v~$L$ mezi indexy $P_0[p]$ a~$P_0[q]$. To zjistíme
+ v~konstantním čase pomocí struktury pro intervalová minima.
+ \::Pokud se setká suffix slova~$\sigma_{0,1}$ se suffixem slova~$\sigma_2$, stačí
+ tyto suffixy přepsat podobně jako v~6.~kroku a problém tím opět převést
+ na výpočet LCP dvou suffixů slov~$\sigma_{0,1}$.
\endalgo
-\s{Analýza èasové slo¾itosti:} Tøídìní napoprvé trvá ${\rm Sort}(n,\Sigma)$, ve~v¹ech
-rekurzivních voláních u¾ je lineární (trojice èísel velikosti $\O(n)$ mù¾eme tøídit tøíprùchodovým
-pøihrádkovým tøídìním s~$\O(n)$ pøihrádkami). Z~toho dostáváme:
+\s{Analýza časové složitosti:} Třídění napoprvé trvá ${\rm Sort}(n,\Sigma)$, ve~všech
+rekurzivních voláních už je lineární (trojice čísel velikosti $\O(n)$ můžeme třídit tříprůchodovým
+přihrádkovým tříděním s~$\O(n)$ přihrádkami). Z~toho dostáváme:
$$T(n) = T(2/3\cdot n) + \O(n),~\hbox{a tedy}~T(n)=\O(n).$$
\qed
-\h{Ukkonenova inkrementální konstrukce}
+\h{Ukkonenova inkrementální konstrukce}
-\>Ukkonen popsal algoritmus \cite{ukkonen95line} pro konstrukci suffixového stromu bez dolarù,
-pracující inkrementálnì: Zaène se stromem pro prázdné slovo a postupnì na konec slova pøidává
-dal¹í znaky a pøepoèítává strom. Ka¾dý znak pøitom pøidá v~amortizovanì konstantním èase.
-Pro slovo~$\sigma$ tedy doká¾e sestrojit ST v~èase $\O(\vert\sigma\vert)$.
+\>Ukkonen popsal algoritmus \cite{ukkonen95line} pro konstrukci suffixového stromu bez dolarů,
+pracující inkrementálně: Začne se stromem pro prázdné slovo a postupně na konec slova přidává
+další znaky a přepočítává strom. Každý znak přitom přidá v~amortizovaně konstantním čase.
+Pro slovo~$\sigma$ tedy dokáže sestrojit ST v~čase $\O(\vert\sigma\vert)$.
-Budeme pøedpokládat, ¾e hrany vedoucí z~jednoho vrcholu je mo¾né indexovat jejich
-prvními písmeny -- to bezpeènì platí, pokud je abeceda pevná; není-li, mù¾eme
-si pomoci he¹ováním.
+Budeme předpokládat, že hrany vedoucí z~jednoho vrcholu je možné indexovat jejich
+prvnÃmi pÃsmeny -- to bezpeÄ\8dnÄ\9b platÃ, pokud je abeceda pevná; nenÃ-li, můžeme
+si pomoci hešováním.
-\s{Pozorování:} Kdy¾ slovo~$\sigma$ roz¹íøíme na~$\sigma a$, ST se zmìní následovnì:
+\s{Pozorování:} Když slovo~$\sigma$ rozšíříme na~$\sigma a$, ST se změní následovně:
\numlist\ndotted
-\:V¹echny stávající vrcholy stromu (vèetnì skrytých) odpovídají podslovùm slova~$\sigma$.
- Ta jsou i podslovy $\sigma a$, tak¾e se budou nacházet i v~novém stromu.
-\:Pokud $\beta$ bylo vìtvící slovo, zùstane nadále vìtvící -- tedy vnitøní vrcholy ve~stromu zùstanou.
-\:Ka¾dý nový suffix~$\beta a$ vznikne prodlou¾ením nìjakého pùvodního suffixu~$\beta$. Pøitom:
+\:Všechny stávající vrcholy stromu (včetně skrytých) odpovídají podslovům slova~$\sigma$.
+ Ta jsou i podslovy $\sigma a$, takže se budou nacházet i v~novém stromu.
+\:Pokud $\beta$ bylo větvící slovo, zůstane nadále větvící -- tedy vnitřní vrcholy ve~stromu zůstanou.
+\:Každý nový suffix~$\beta a$ vznikne prodloužením nějakého původního suffixu~$\beta$. Přitom:
\itemize\ibull
- \:Pokud byl~$\beta$ nevnoøený suffix (èili byl reprezentovaný listem), ani $\beta a$
- nebude vnoøený. Z~toho víme, ¾e listy zùstanou listy, pouze jim potøebujeme prodlou¾it
- nálepky. Aby to netrvalo pøíli¹ dlouho, zavedeme {\I otevøené hrany,} jejich¾ nálepka
- øíká \uv{od~pozice~$i$ do konce}. Listy se tak o~sebe postarají samy.
- \:Pokud $\beta$ byl vnoøený suffix (tj. vnitøní èi skrytý vrchol):
+ \:Pokud byl~$\beta$ nevnořený suffix (čili byl reprezentovaný listem), ani $\beta a$
+ nebude vnoÅ\99ený. Z~toho vÃme, že listy zůstanou listy, pouze jim potÅ\99ebujeme prodloužit
+ nálepky. Aby to netrvalo příliš dlouho, zavedeme {\I otevřené hrany,} jejichž nálepka
+ říká \uv{od~pozice~$i$ do konce}. Listy se tak o~sebe postarají samy.
+ \:Pokud $\beta$ byl vnořený suffix (tj. vnitřní či skrytý vrchol):
\itemize\ibull
- \:Buï se $\beta a$ vyskytuje v~$\sigma$, a tím pádem je to vnoøený suffix nového slova
- a strom není nutné upravovat;
- \:nebo se $\beta a$ v~$\sigma$ nevyskytuje -- tehdy pro nìj musíme zalo¾it nový list
- s~otevøenou hranou a pøípadnì i nový vnitøní vrchol, pod ním¾ bude tento list pøipojen.
+ \:Buď se $\beta a$ vyskytuje v~$\sigma$, a tím pádem je to vnořený suffix nového slova
+ a strom není nutné upravovat;
+ \:nebo se $\beta a$ v~$\sigma$ nevyskytuje -- tehdy pro něj musíme založit nový list
+ s~otevřenou hranou a případně i nový vnitřní vrchol, pod nímž bude tento list připojen.
\endlist
\endlist
\endlist
-Víme tedy, co v¹echno je pøi roz¹íøení slova potøeba ve~stromu upravit.
-Zbývá vyøe¹it, jak to udìlat efektivnì.
+Víme tedy, co všechno je při rozšíření slova potřeba ve~stromu upravit.
+Zbývá vyřešit, jak to udělat efektivně.
-\s{Vnoøené suffixy:}
-Pøedev¹ím potøebujeme umìt rozpoznat, které suffixy jsou vnoøené a které nikoliv.
-K~tomu se hodí v¹imnout si, ¾e vnoøené suffixy tvoøí souvislý úsek:
+\s{Vnořené suffixy:}
+Především potřebujeme umět rozpoznat, které suffixy jsou vnořené a které nikoliv.
+K~tomu se hodí všimnout si, že vnořené suffixy tvoří souvislý úsek:
{\narrower
-\s{Lemma:} Je-li $\alpha$ vnoøený suffix slova~$\sigma$ a $\beta$ je suffix slova~$\alpha$,
-pak $\beta$ je v~$\sigma$ také vìtvící.
+\s{Lemma:} Je-li $\alpha$ vnořený suffix slova~$\sigma$ a $\beta$ je suffix slova~$\alpha$,
+pak $\beta$ je v~$\sigma$ také vnořený.
\proof
-Ve~slovì sigma se vyskytuje $\alpha x$ a $\alpha y$ pro nìjaké dva rùzné znaky $x$ a~$y$.
-Ka¾dý z~tìchto výskytù pøitom konèí výskytem slova~$\beta$, jednou následovaným~$x$,
-podruhé~$y$.
+Ve~slově sigma se vyskytuje $\alpha x$ a $\alpha y$ pro nějaké dva různé znaky $x$ a~$y$.
+Každý z~těchto výskytů přitom končí výskytem slova~$\beta$, jednou následovaným~$x$,
+podruhé~$y$.
\qed
}
-\>Staèí si tedy zapamatovat nejdel¹í vnoøený suffix slova~$\sigma$. Tomu budeme øíkat
-{\I aktivní suffix} a budeme ho znaèit $\alpha(\sigma)$. Libovolný suffix~$\beta\subseteq\sigma$
-pak bude vnoøený právì tehdy, kdy¾ $\vert\beta\vert \le \vert\alpha(\sigma)\vert$.
+\>Stačí si tedy zapamatovat nejdelší vnořený suffix slova~$\sigma$. Tomu budeme říkat
+{\I aktivní suffix} a budeme ho značit $\alpha(\sigma)$. Libovolný suffix~$\beta\subseteq\sigma$
+pak bude vnoÅ\99ený právÄ\9b tehdy, když $\vert\beta\vert \le \vert\alpha(\sigma)\vert$.
-Aktivní suffix tedy tvoøí hranici mezi nevnoøenými a vnoøenými suffixy. Jak se tato
-hranice posune, kdy¾ slovo~$\sigma$ roz¹íøíme? Na to je odpovìï snadná:
+Aktivní suffix tedy tvoří hranici mezi nevnořenými a vnořenými suffixy. Jak se tato
+hranice posune, když slovo~$\sigma$ rozšíříme? Na to je odpověď snadná:
{\narrower
-\s{Lemma:} Pro ka¾dé $\sigma$, $a$ platí: $\alpha(\sigma a)$ je suffixem $\alpha(\sigma)a.$
+\s{Lemma:} Pro každé $\sigma$, $a$ platí: $\alpha(\sigma a)$ je suffixem $\alpha(\sigma)a.$
\proof
-$\alpha(\sigma a)$ i $\alpha(\sigma)a$ jsou suffixy slova $\sigma a$, a~proto staèí porovnat jejich délky.
-Slovo $\beta := \hbox{\uv{$\alpha(\sigma a)$ bez koncového~$a$}}$ je vnoøeným suffixem 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$.
+$\alpha(\sigma a)$ i $\alpha(\sigma)a$ jsou suffixy slova $\sigma a$, a~proto stačí porovnat jejich délky.
+Slovo $\beta := \hbox{\uv{$\alpha(\sigma a)$ bez koncového~$a$}}$ je vnoÅ\99eným suffixem 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
}
-\>Hranice se tedy mù¾e posouvat pouze doprava, pøípadnì zùstat na místì.
-Toho lze snadno vyu¾ít.
+\>Hranice se tedy může posouvat pouze doprava, případně zůstat na místě.
+Toho lze snadno využít.
-\s{Idea algoritmu:} Udr¾ujeme si $\alpha=\alpha(\sigma)$ a pøi pøidání znaku $a$ zkontrolujeme,
-zda $\alpha a$ je stále vnoøený suffix. Pokud ano, nic se nemìní, pokud ne, pøidáme nový list
-a pøípadnì také vnitøní vrchol, $\alpha$ zkrátíme zleva o~znak a testujeme dál.
+\s{Idea algoritmu:} Udržujeme si $\alpha=\alpha(\sigma)$ a při přidání znaku $a$ zkontrolujeme,
+zda $\alpha a$ je stále vnořený suffix. Pokud ano, nic se nemění, pokud ne, přidáme nový list
+a případně také vnitřní vrchol, $\alpha$ zkrátíme zleva o~znak a testujeme dál.
-\s{Analýza:} Po~pøidání jednoho znaku na konec slova~$\sigma$ provedeme amortizovanì
-konstantní poèet úprav stromu (ka¾dá úprava slovo $\alpha$ zkrátí, po v¹ech úpravách
-pøidáme k~$\alpha$ jediný znak). Tudí¾ staèí ukázat, jak provést ka¾dou úpravu
-v~(amortizovanì) konstantním èase. K~tomu potøebujeme ¹ikovnou reprezentaci slova~$\alpha$,
-která bude umìt efektivnì prodlu¾ovat zprava, zkracovat zleva a testovat existenci
+\s{Analýza:} Po~přidání jednoho znaku na konec slova~$\sigma$ provedeme amortizovaně
+konstantní počet úprav stromu (každá úprava slovo $\alpha$ zkrátí, po všech úpravách
+přidáme k~$\alpha$ jediný znak). Tudíž stačí ukázat, jak provést každou úpravu
+v~(amortizovaně) konstantním čase. K~tomu potřebujeme šikovnou reprezentaci slova~$\alpha$,
+která bude umÄ\9bt efektivnÄ\9b prodlužovat zprava, zkracovat zleva a testovat existenci
vrcholu ve~stromu.
-\s{Definice:} {\I Referenèní pár} pro slovo $\alpha\subseteq\sigma$ je dvojice
-$(\pi,\tau)$, v~ní¾ $\pi$ je vrchol stromu, $\tau$ libovolné slovo a $\pi\tau=\alpha$.
-Navíc víme, ¾e $\tau\subseteq\sigma$, tak¾e si~$\tau$ staèí pamatovat jako dvojici
-indexù ve~slovì~$\sigma$.
+\s{Definice:} {\I Referenční pár} pro slovo $\alpha\subseteq\sigma$ je dvojice
+$(\pi,\tau)$, v~níž $\pi$ je vrchol stromu, $\tau$ libovolné slovo a $\pi\tau=\alpha$.
+Navíc víme, že $\tau\subseteq\sigma$, takže si~$\tau$ stačí pamatovat jako dvojici
+indexů ve~slově~$\sigma$.
-Referenèní pár je {\I kanonický,} pokud neexistuje hrana vedoucí z~vrcholu~$\pi$ s~nálepkou,
-která by byla prefixem slova~$\tau$. (V¹imnìte si, ¾e taková hrana se pozná podle toho,
-¾e první znak nálepky se shoduje s~prvním znakem slova~$\tau$ a nálepka není del¹í ne¾
-slovo~$\tau$. Shodu ostatních znakù není nutné kontrolovat.)
+Referenční pár je {\I kanonický,} pokud neexistuje hrana vedoucí z~vrcholu~$\pi$ s~nálepkou,
+která by byla prefixem slova~$\tau$. (Všimněte si, že taková hrana se pozná podle toho,
+že prvnà znak nálepky se shoduje s~prvnÃm znakem slova~$\tau$ a nálepka nenà delÅ¡Ã než
+slovo~$\tau$. Shodu ostatních znaků není nutné kontrolovat.)
-\s{Pozorování:} Ke~ka¾dému slovu $\alpha\subseteq\sigma$ existuje právì jeden kanonický
-referenèní pár, který ho popisuje. To je ze~v¹ech referenèních párù pro toto slovo
-ten s~nejdel¹ím~$\pi$ (nejhlub¹ím vrcholem).
+\s{Pozorování:} Ke~každému slovu $\alpha\subseteq\sigma$ existuje právě jeden kanonický
+referenční pár, který ho popisuje. To je ze~všech referenčních párů pro toto slovo
+ten s~nejdelším~$\pi$ (nejhlubším vrcholem).
-\s{Definice:} Zpìtná hrana $\<back>(\pi)$ vede z~vrcholu $\pi$ do~vrcholu,
-který je zkrácením slova~$\pi$ o~jeden znak zleva. (Nahlédneme, ¾e takový
-vrchol musí existovat: pokud je $\pi$ vnitøní vrchol, pak je slovo~$\pi$
-vìtvící, tak¾e ka¾dý jeho suffix musí také být vìtvící, a~tím pádem musí
-odpovídat nìjakého vrcholu.)
+\s{Definice:} Zpětná hrana $\<back>(\pi)$ vede z~vrcholu $\pi$ do~vrcholu,
+který je zkrácením slova~$\pi$ o~jeden znak zleva. (Nahlédneme, že takový
+vrchol musí existovat: pokud je $\pi$ vnitřní vrchol, pak je slovo~$\pi$
+větvící, takže každý jeho suffix musí také být větvící, a~tím pádem musí
+odpovídat nějakého vrcholu.)
-\s{Operace s~referenèními páry:}
-S~referenèním párem $(\pi,\tau)$ popisujícím slovo~$\alpha$ potøebujeme provádìt
-následujicí operace:
+\s{Operace s~referenčními páry:}
+S~referenčním párem $(\pi,\tau)$ popisujícím slovo~$\alpha$ potřebujeme provádět
+následujicí operace:
\itemize\ibull
-\:{\I Pøidání znaku~$a$ na konec:} Pøipí¹eme~$a$ na konec slova~$\tau$.
- To je jistì referenèní pár pro $\alpha a$, ale nemusí být kanonický.
- Pøitom mù¾eme snadno ovìøit, zda se $\alpha a$ ve~stromu nachází,
- a pøípadnì operaci odmítnout.
-\:{\I Odebrání znaku ze~zaèátku:} Pokud $\pi$ není koøen stromu, polo¾íme
- $\pi\leftarrow\<back>(\pi)$ a zachováme~$\tau$. Pokud naopak je~$\pi$
- prázdný øetìzec, odebereme z~$\tau$ jeho první znak (to lze udìlat
- v~konstantním èase, proto¾e~$\tau$ je reprezentované dvojicí indexù do~$\sigma$).
-\:{\I Pøevedení na kanonický tvar:} Obì pøedchozí operace mohou vytvoøit referenèní
- pár, který není kanonický. Poka¾dé proto kanonicitu zkontrolujeme a pøípadnì
- pár upravíme. Ovìøíme, zda hrana z~$\pi$ indexovaná písmenem~$a$ není
- dost krátká na to, aby byla prefixem slova~$\tau$. Pokud je, tak se
- po~této hranì pøesuneme dolù, èím¾~$\pi$ prodlou¾íme a~$\tau$ zkrátíme,
- a proces opakujeme. Jeliko¾ tím poka¾dé $\tau$~zkrátíme a kdykoliv jindy
- se $\tau$ prodlou¾í nejvý¹e o~1, mají v¹echny pøevody na kanonický tvar
- amortizovanì konstantní slo¾itost.
+\:{\I Přidání znaku~$a$ na konec:} Připíšeme~$a$ na konec slova~$\tau$.
+ To je jistě referenční pár pro $\alpha a$, ale nemusí být kanonický.
+ Přitom můžeme snadno ověřit, zda se $\alpha a$ ve~stromu nachází,
+ a případně operaci odmítnout.
+\:{\I Odebrání znaku ze~začátku:} Pokud $\pi$ není kořen stromu, položíme
+ $\pi\leftarrow\<back>(\pi)$ a zachováme~$\tau$. Pokud naopak je~$\pi$
+ prázdný řetězec, odebereme z~$\tau$ jeho první znak (to lze udělat
+ v~konstantním čase, protože~$\tau$ je reprezentované dvojicí indexů do~$\sigma$).
+\:{\I Převedení na kanonický tvar:} Obě předchozí operace mohou vytvořit referenční
+ pár, který není kanonický. Pokaždé proto kanonicitu zkontrolujeme a případně
+ pár upravíme. Ověříme, zda hrana z~$\pi$ indexovaná písmenem~$a$ není
+ dost krátká na to, aby byla prefixem slova~$\tau$. Pokud je, tak se
+ po~této hraně přesuneme dolů, čímž~$\pi$ prodloužíme a~$\tau$ zkrátíme,
+ a proces opakujeme. Jelikož tím pokaždé $\tau$~zkrátíme a kdykoliv jindy
+ se $\tau$ prodlouží nejvýše o~1, mají všechny převody na kanonický tvar
+ amortizovanÄ\9b konstantnà složitost.
\endlist
-\>Nyní ji¾ mù¾eme doplnit detaily, získat celý algoritmus a nahlédnout,
-¾e pracuje v~amortizovanì konstantním èase.
+\>Nyní již můžeme doplnit detaily, získat celý algoritmus a nahlédnout,
+že pracuje v~amortizovaně konstantním čase.
-\s{Algoritmus podrobnìji:}
+\s{Algoritmus podrobněji:}
\algo
-\:{\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$.
-\:Zjistíme, jestli $\alpha a$ je pøítomen ve~stromu, a pøípadnì ho zalo¾íme:
-\::Pokud $\tau=\varepsilon$: ($\alpha=\pi$ je vnitøní vrchol)
-\:::Vede-li z~vrcholu $\pi$ hrana s~nálepkou zaèínající znakem $a$, pak je pøítomen.
-\:::Nevede-li, není pøítomen, a~tak pøidáme novou otevøenou hranu vedoucí z~$\pi$ do~nového listu.
-\::Pokud $\tau\ne\varepsilon$: ($\alpha$ je skrytý vrchol)
-\:::Najdeme hranu, po~ní¾ z~$\pi$ pokraèuje slovo $\tau$ (která to je, poznáme podle prvního znaku slova~$\tau$).
-\:::Pokud v~popisce této hrany po~$\tau$ následuje znak~$a$, pak je $\alpha a$ pøítomen.
-\:::Pokud nenásleduje, tak nebyl pøítomen, èili tuto hranu rozdìlíme: pøidáme na~ni nový vnitøní vrchol,
- do~nìj¾ povede hrana s~popiskou~$\tau$ a z~nìj zbytek pùvodní hrany a otevøená hrana do~nového listu.
-\:Pokud $\alpha a$ nebyl pøítomen, tak $\alpha$ zkrátíme a vrátíme se na~krok~2.
-\:Nyní víme, ¾e $\alpha a$ ji¾ byl pøítomen, tak¾e upravíme referenèní pár, aby popisoval $\alpha a$.
-\:Dopoèítáme zpìtné hrany (viz ní¾e).
-\:{\I Výstup:} $\alpha=\alpha(\sigma a)$ jako kanonický referenèní pár $(\pi,\tau)$, $T$ suffixový strom pro~$\sigma a$
- a jeho zpìtné hrany \<back>.
+\:{\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$.
+\:Zjistíme, jestli $\alpha a$ je přítomen ve~stromu, a případně ho založíme:
+\::Pokud $\tau=\varepsilon$: ($\alpha=\pi$ je vnitřní vrchol)
+\:::Vede-li z~vrcholu $\pi$ hrana s~nálepkou začínající znakem $a$, pak je přítomen.
+\:::Nevede-li, není přítomen, a~tak přidáme novou otevřenou hranu vedoucí z~$\pi$ do~nového listu.
+\::Pokud $\tau\ne\varepsilon$: ($\alpha$ je skrytý vrchol)
+\:::Najdeme hranu, po~níž z~$\pi$ pokračuje slovo $\tau$ (která to je, poznáme podle prvního znaku slova~$\tau$).
+\:::Pokud v~popisce této hrany po~$\tau$ následuje znak~$a$, pak je $\alpha a$ přítomen.
+\:::Pokud nenásleduje, tak nebyl přítomen, čili tuto hranu rozdělíme: přidáme na~ni nový vnitřní vrchol,
+ do~nějž povede hrana s~popiskou~$\tau$ a z~něj zbytek původní hrany a otevřená hrana do~nového listu.
+\:Pokud $\alpha a$ nebyl přítomen, tak $\alpha$ zkrátíme a vrátíme se na~krok~2.
+\:Nyní víme, že $\alpha a$ již byl přítomen, takže upravíme referenční pár, aby popisoval $\alpha a$.
+\:DopoÄ\8dÃtáme zpÄ\9btné hrany (viz nÞe).
+\:{\I Výstup:} $\alpha=\alpha(\sigma a)$ jako kanonický referenční pár $(\pi,\tau)$, $T$ suffixový strom pro~$\sigma a$
+ a jeho zpětné hrany \<back>.
\endalgo
-\s{Zpìtné hrany:}
-Zbývá dodat, jak nastavovat novým vrcholùm jejich zpìtné hrany. To potøebujeme
-jen pro vnitøní vrcholy (na~zpìtné hrany z~listù se algoritmus nikdy neodkazuje).
-V¹imneme si, ¾e pokud jsme zalo¾ili vrchol, odpovídá tento vrchol v¾dy souèasnému~$\alpha$
-a zpìtná hrana z~nìj povede do~zkrácení slova~$\alpha$ o~znak zleva, co¾ je
-pøesnì vrchol, který zalo¾íme (nebo zjistíme, ¾e u¾ existuje) v~pøí¹tí iteraci
-hlavního cyklu. V~dal¹í iteraci je¹tì urèitì nebudeme tuto hranu potøebovat,
-proto¾e $\pi$ v¾dy jen zkracujeme, a~tak mù¾eme vznik zpìtné hrany o~iteraci
-zpozdit. Výroba zpìtné hrany tedy bude také trvat jen konstantnì dlouho.
+\s{Zpětné hrany:}
+Zbývá dodat, jak nastavovat novým vrcholům jejich zpětné hrany. To potřebujeme
+jen pro vnitřní vrcholy (na~zpětné hrany z~listů se algoritmus nikdy neodkazuje).
+Všimneme si, že pokud jsme založili vrchol, odpovídá tento vrchol vždy současnému~$\alpha$
+a zpÄ\9btná hrana z~nÄ\9bj povede do~zkrácenà slova~$\alpha$ o~znak zleva, což je
+přesně vrchol, který založíme (nebo zjistíme, že už existuje) v~příští iteraci
+hlavního cyklu. V~další iteraci ještě určitě nebudeme tuto hranu potřebovat,
+protože $\pi$ vždy jen zkracujeme, a~tak můžeme vznik zpětné hrany o~iteraci
+zpozdit. Výroba zpětné hrany tedy bude také trvat jen konstantně dlouho.
\references
\bye
projects / ga.git / blobdiff