From bce209b8f972bb72ca9aa198b1ec828ea168d3cd Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 24 Jan 2007 20:46:38 +0100 Subject: [PATCH] Suffixove stromy: stylistika a odkaz na clanek o BWT. --- 9-suffix/9-suffix.tex | 60 +++++++++++++++++++++++++------------------ ga.bib | 8 ++++++ 2 files changed, 43 insertions(+), 25 deletions(-) diff --git a/9-suffix/9-suffix.tex b/9-suffix/9-suffix.tex index 0784bbd..71fed8d 100644 --- a/9-suffix/9-suffix.tex +++ b/9-suffix/9-suffix.tex @@ -2,7 +2,7 @@ \prednaska{9}{Suffixové stromy}{} -V~této kapitole popí¹eme jednu datovou strukturu, pomocí ní¾ doká¾eme problémy týkající +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 tak je øe¹it v~lineárním èase. \h{Øetìzce, trie a suffixové stromy} @@ -67,10 +67,12 @@ a \figure{st-barbara.eps}{Suffixový strom pro slovo BARBARA}{0pt} +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)$. \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 si staèí reprezentovat +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 @@ -79,7 +81,9 @@ po \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é @@ -106,23 +110,26 @@ a \:{\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, +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} -- jejím základem je lexikografické setøídìní v¹ech +\:{\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 následným vypsáním listù v~poøadí dle~DFS. +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. + \h{Suffix Array} \>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:j]$ znaèit podslovo slo¾ené z~$i$-tého a¾ $j$-tého -znaku slova~$\sigma$ (znaky èíslujeme od~$1$). Libovolnou z~mezí mù¾eme vynechat, proto +\s{Notace:} Pro slovo $\sigma$ bude $\sigma[i]$ znaèit jeho $i$-tý znak (èíslujeme od~jednièky), +$\sigma[i:j]$ pak podslovo slo¾ené z~$i$-tého a¾ $j$-tého znaku. Libovolnou z~mezí mù¾eme vynechat, proto $\sigma[i:{}]$ bude suffix od~$i$ do~konce a $\sigma[{}:j]$ prefix od~zaèátku do~$j$. Pokud $jTento algoritmus konstruuje pro slovo $\sigma$ délky~$n$ pole $A_\sigma$ a $L_\sigma$ v~èase $\O(n+{\rm Sort}(n,\Sigma))$, +\>Tento algoritmus konstruuje pro slovo $\sigma$ délky~$n$ jeho suffix array a LCP array 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 nám tedy dává lineární konstrukci ST($\sigma$) pro libovolnou fixní abecedu. @@ -164,25 +171,25 @@ $$\eqalign{ \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 }$$ -Slova $\sigma_k$ jsou slova délky $\approx n/3$ nad~abecedou velikosti $n^3$. Dovolíme +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}$. -\:Z~$A_{01}$ a $L_{01}$ vydìlíme $A_0=A_{\sigma_0}$, $A_1$, $L_0$ a $L_1$ a spoèítáme permutace inverzní k~$A_0$ a $A_1$. +\:Z~$A_{01}$ a $L_{01}$ vydìlíme $A_0=A_{\sigma_0}$, $A_1$, $L_0$ a $L_1$. Také si pro ka¾dý prvek +$A_i$ zapamatujeme, kde se v~$A_{01}$ vyskytoval. -\:Dopoèítáme $A_2$: Jeliko¾ $\sigma_2[i:{}] = \sigma[3i+2:{}] = \sigma[3i+2]\sigma[3i+3:{}] = \sigma[3i+2]\sigma_0[i+1:{}]$ +\:Dopoèítáme $A_2$: Jeliko¾ $\sigma_2[i:{}] = \sigma[3i+2:{}] = \sigma[3i+2]\sigma[3i+3:\nobreak{}\nobreak] = \sigma[3i+2]\sigma_0[i+1:{}]$ a v¹echna $\sigma_0[i:{}]$ u¾ máme setøídìná, mù¾eme v¹echna $\sigma_2[i:{}]$ setøídit dvìma prùchody pøihrádkového tøídìní. \:Dopoèítáme $L_2$: Stejným trikem jako $A_2$ -- pokud jsou první písmena rùzná, je spoleèný prefix prázdný, jinak má délku $1+{\rm LCP}(\sigma_0[i+1:{}],\sigma_0[j+1:{}]) = 1+\min_{i+1\le k< j+1} L_0[k]$. Minimum zvládneme pro ka¾dou dvojici $i,j$ spoèítat v~konstantním èase pomocí datové struktury pro intervalová minima. -\todo{Ta je a¾ v~následující kapitole.} \:$A_0,A_1,A_2\buildrel merge\over\longrightarrow A$ -- sléváme tøi setøídìné posloupnosti, tak¾e staèí umìt prvky libovolných dvou posloupností v~konstantním èase porovnat: $$\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_1[j:{}] &~\hbox{podle zapamatovaných pozic v~$A_{01}$} \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 {} \cr&\hphantom{{}\Leftrightarrow{}} (\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:{}] < \cr&\hphantom{{}\equiv{}} \sigma[3k+2]\,\sigma[3k+3]\,\sigma_1[k+1:{}] @@ -223,7 +230,7 @@ z o~sebe postarají samy. \:Pokud $\beta$ bylo vìtvící slovo, zùstane nadále vìtvící -- tedy vnitøní vrcholy ve~stromu zùstanou. \:Pokud $\beta$ byl vnoøený suffix (tj. vnitøní èi skrytý vrchol), pak se $\beta a$ buïto -vyskytuje v~$\sigma$ a tím pádem je to vnoøený suffix nového slova a strom není nutné +vyskytuje v~$\sigma$, a tím pádem je to vnoøený suffix nového slova a strom není nutné upravovat, nebo se v~$\sigma$ nevyskytuje a tehdy pro nìj musíme zalo¾it novou odboèku a nový list s~otevøenou hranou. \endlist @@ -250,16 +257,18 @@ $\vert\beta\vert \le \vert\alpha(\sigma)\vert$, a~tedy tak \s{Lemma:} Suffix $\beta$ je zralý $\Leftrightarrow$ $\vert\alpha(\sigma)a\vert \ge \vert\beta a\vert > \vert\alpha(\sigma a)\vert$. \proof Jeliko¾ $\beta$ je vnoøeným suffixem $\sigma$, musí platit první nerovnost. Aby byl zralý, -musí také nebýt vnoøeným suffixem $\sigma a$, èemu¾ odpovídá druhá nerovnost. +musí také nebýt vnoøeným suffixem $\sigma a$, a~tomu odpovídá druhá nerovnost. \qed -\s{Idea Algoritmu:} Udr¾uji si $\alpha=\alpha(\sigma)$ a pøi pøidání znaku $a$ zkontroluji, zda $\alpha a$ je -stále vnoøený suffix. Pokud ano, nic se nemìní, pokud ne, pøidám vnitøní vrchol, $\alpha$ zkrátím -zleva o~znak a testuji 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 vnitøní vrchol, $\alpha$ zkrátíme +zleva o~znak a testujeme dál. -\s{Analýza:} Úprav stromu provedu $\O(1)$ amortizovanì (ka¾dá úprava slovo $\alpha$ zkrátí, +\s{Analýza:} Úprav stromu provedeme $\O(1)$ amortizovanì (ka¾dá úprava slovo $\alpha$ zkrátí, ka¾dé pøidání znaku ho~prodlou¾í o~znak, tak¾e v¹ech zkrácení je $\O(\vert\sigma\vert)$). Staèí -tedy ukázat, jak provést úpravu v~(amortizovanì) konstantním èase, k~èemu¾ se nám bude hodit: +tedy ukázat, jak provést úpravu v~(amortizovanì) konstantním èase, k~èemu¾ potøebujeme +$\alpha$ reprezentovat ¹ikovnì a také si udr¾ovat pomocné informace (zpìtné hrany), +abychom umìli rychle zkracovat. \s{Definice:} {\I Referenèní pár} je dvojice $(\pi,\tau)$, v~ní¾ $\pi$ je vrchol stromu a $\tau$ libovolné slovo. Tento pár popisuje slovo $\pi\tau$. Referenèní @@ -278,7 +287,7 @@ p pøípadì se \ pro vnitøní vrcholy chová daleko jednodu¹eji (a~na ¾ádné jiné ho potøebovat nebudeme): pokud je $\pi$ vnitøní vrchol, musí to být vìtvící podslovo, a~tím pádem ka¾dé jeho zkrácení zleva musí být také vìtvící -podslovo. Tedy $\(\pi)$ dá~$\pi$ bez prvního znaku, co¾ se nám +podslovo. Tedy $\(\pi)$ dá~$\pi$ bez prvního znaku, a~to se nám bude hodit pøi zkracování suffixù. \s{Algoritmus podrobnìji:} (Doplnili jsme detaily do~pøedchozího algoritmu.) @@ -303,6 +312,7 @@ bude hodit p \:Pokud $\alpha a$ u¾ je pøítomen, zbývá pøidat $a$ k~$\alpha$ a zastavit se: \::$\tau := \tau a$. \::Kanonikalizace stejnì jako v~bodech 12--13.\foot{Dokonce jednodu¹¹í, proto¾e projdeme nejvý¹e jednu hranu.} +\:Dopoèítáme zpìtné hrany (viz ní¾e). \:Výstup: $\alpha=\alpha(\sigma a)$ coby kanonický referenèní pár $(\pi,\tau)$, $T$ suffixový strom pro~$\sigma a$ a jeho funkce \. \endalgo @@ -310,12 +320,12 @@ bude hodit p \s{Èasová slo¾itost:} Kanonikalizace pracuje v~amortizovanì konstantním èase, proto¾e ka¾dá její iterace -zkrátí~$\tau$ a za~celou dobu bìhu algoritmu se~$\tau$ prodlou¾í jen jednou, a~to o~jeden znak. +zkrátí~$\tau$ a za~ka¾dé spu¹tìní algoritmu se~$\tau$ prodlou¾í jen jednou, a~to o~jeden znak. Prùchodù hlavním cyklem je, jak u¾ víme, amortizovanì konstantní poèet a ka¾dý prùchod zvládneme v~konstantním èase. -Je¹tì jsme ale zapomnìli nastavovat novým vrcholùm jejich \. To potøebujeme +Zbývá dodat, jak nastavovat novým vrcholùm jejich \. To potøebujeme jen pro vnitøní vrcholy (na~zpìtné hrany z~listù se algoritmus nikdy neodkazuje) a 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 diff --git a/ga.bib b/ga.bib index 4cc3654..8d05b24 100644 --- a/ga.bib +++ b/ga.bib @@ -441,3 +441,11 @@ year={2004}, publisher={Elsevier} } + +@techreport{ burrows:bwt, + title={{A block-sorting lossless data compression algorithm}}, + author={Burrows, M. and Wheeler, D.J.}, + year={1994}, + number={124}, + institution={Digital Systems Research Center} +} -- 2.39.2