From 69bb6f1a8d08f5b6fd921ed3e70e8bf5b4d4feec Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 9 Jan 2013 01:16:32 +0100 Subject: [PATCH] Suffixove stromy: Lepsi vyklad Ukkonenova algoritmu --- 10-suffix/10-suffix.tex | 189 +++++++++++++++++++++++----------------- 1 file changed, 109 insertions(+), 80 deletions(-) diff --git a/10-suffix/10-suffix.tex b/10-suffix/10-suffix.tex index 7bb902c..cba1792 100644 --- a/10-suffix/10-suffix.tex +++ b/10-suffix/10-suffix.tex @@ -218,89 +218,138 @@ $$T(n) = T(2/3\cdot n) + \O(n),~\hbox{a tedy}~T(n)=\O(n).$$ \h{Ukkonenova inkrementální konstrukce} -\>Ukkonenùv algoritmus \cite{ukkonen95line} konstruuje suffixový strom bez dolarù inkrementálnì: zaène se stromem -pro prázdné slovo (ten má jediný vrchol, a to koøen) a postupnì pøidává dal¹í znaky na~konec -slova. To zvládne v~èase $\O(1)$ amortizovanì na~pøidání jednoho znaku. +\>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 hashováním. +si pomoci he¹ováním. \s{Pozorování:} Kdy¾ slovo~$\sigma$ roz¹íøíme na~$\sigma a$, ST se zmìní následovnì: \numlist\ndotted -\:Pokud $\beta$ byl nevnoøený suffix slova~$\sigma$, je i $\beta a$ nevnoøený suffix~$\sigma a$. Z~toho víme, ¾e listy -zùstanou listy, pouze jim potøebujeme prodlou¾it nálepky. Pomù¾eme si snadno: zavedeme -{\I otevøené hrany,} jejich¾ nálepka je \uv{od~pozice~$i$ do konce}. Listy se tak -o~sebe postarají samy. +\: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. -\: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é -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. +\: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): + \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$ 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 musí algoritmus ve~stromu pøí roz¹íøení slova upravit, zbývá -vyøe¹it, jak to udìlat efektivnì. K~tomu se hodí pár definic a lemmat: +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{Definice:} {\I Aktivní suffix} $\alpha(\sigma)$ øíkáme nejdel¹ímu vnoøenému suffixu slova~$\sigma$. +\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{Lemma:} Suffix $\beta$ slova $\sigma$ je vnoøený $\Leftrightarrow$ $\vert\beta\vert \le \vert\alpha(\sigma)\vert.$ +{\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í. -\proof Ka¾dý suffix vnoøeného suffixu je opìt vnoøený. \qed +\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$. +\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$. +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.$ -\proof $\alpha(\sigma a)$ i $\alpha(\sigma)a$ jsou suffixy slova $\sigma a$, a~proto staèí porovnat jejich délky. +\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$. \qed -\s{Definice:} Suffix $\beta a$ je {\I zralý} $\equiv$ $\beta$ je vnoøený suffix~$\sigma$, ale $\beta a$ není podslovem~$\sigma$ -(tedy musíme pro~nìj pøi pøidávání znaku~$a$ k~aktuálnímu slovu~$\sigma$ zakládat nový vrchol). +} -\s{Lemma:} Suffix $\beta$ je zralý $\Leftrightarrow$ $\vert\alpha(\sigma)a\vert \ge \vert\beta a\vert > \vert\alpha(\sigma a)\vert$. +\>Hranice se tedy mù¾e posouvat pouze doprava, pøípadnì zùstat na místì. +Toho lze snadno vyu¾ít. -\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$, a~tomu odpovídá druhá nerovnost. -\qed +\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 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 +vrcholu ve~stromu. -\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¾ 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} 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} je dvojice $(\pi,\tau)$, v~ní¾ $\pi$ je vrchol -stromu a $\tau$ libovolné slovo. Tento pár popisuje slovo $\pi\tau$. Referenèní -pár je {\I kanonický,} pokud neexistuje hrana vedoucí z~vrcholu $\pi$ s~nálepkou, -která by byla prefixem slova~$\tau$. Navíc $\tau\subseteq\sigma$, tak¾e si~$\tau$ -staèí pamatovat jako dvojici indexù v~$\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.) -\s{Pozorování:} Ke~ka¾dému slovu existuje právì jeden kanonický referenèní pár, -který ho popisuje. V¹imnìte si, ¾e je to ze~v¹ech referenèních párù pro toto slovo +\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 $\[\pi]$ vede z~vrcholu $\pi$ do~vrcholu, -který je ze~v¹ech vrcholù nejdel¹ím vlastním suffixem slova~$\pi$. +\s{Definice:} Zpìtná hrana $\(\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 také +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: + +\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\(\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. +\endlist -\s{Pozorování:} Zpìtné hrany jsme sice zavedli stejnì obecnì, jako se to dìlá -pøi konstrukci vyhledávacích automatù podle Aha a Corasickové \cite{ahomcc}, ale v~na¹em -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, a~to se nám -bude hodit pøi zkracování suffixù. +\>Nyní ji¾ mù¾eme doplnit detaily, získat celý algoritmus a nahlédnout, +¾e pracuje v~amortizovanì konstantním èase. -\s{Algoritmus podrobnìji:} (Doplnili jsme detaily do~pøedchozího algoritmu.) +\s{Algoritmus podrobnìji:} \algo -\:Vstup: $\alpha=\alpha(\sigma)$ reprezentovaný jako kanonický referenèní pár $(\pi,\tau)$, $T$ suffixový strom pro~$\sigma$ a jeho funkce \, nový znak~$a$. +\:{\I Vstup:} $\alpha=\alpha(\sigma)$ reprezentovaný jako kanonický referenèní pár $(\pi,\tau)$, $T$ suffixový strom pro~$\sigma$ spolu s~hranami \, 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. @@ -310,42 +359,22 @@ bude hodit p \:::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 test opakujeme: -\::Je-li $\pi\ne\varepsilon$, nastavíme $\pi := \(\pi)$. V~opaèném pøípadì (jsme v~koøeni) zkrátíme $\tau$ o~znak zleva. -\::Pár $(\pi,\tau)$ u¾ popisuje zkrácené slovo, ale nemusí být kanonický, tak¾e to je¹tì napravíme: -\:::Dokud existuje hrana vedoucí z~$\pi$, její¾ popiska je prefixem slova $\tau$, tak se - po~této hranì posuneme, èili prodlou¾íme $\pi$ o~tuto popisku a zkrátíme o~ni~$\tau$. -\::Zpìt na~krok 2. -\:Pokud $\alpha a$ ji¾ byl 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.} +\: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). -\:Výstup: $\alpha=\alpha(\sigma a)$ coby kanonický referenèní pár $(\pi,\tau)$, $T$ suffixový strom pro~$\sigma a$ - a jeho funkce \. +\:{\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 \. \endalgo -\goodbreak - -\s{Èasová slo¾itost:} - -Kanonikalizace pracuje v~amortizovanì konstantním èase, proto¾e ka¾dá její iterace -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. - -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$ +\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 urèitì je¹tì nebudeme tuto hranu potøebovat, +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 a zvládnout to tak také v~èase $\O(1)$. - -Celkovì je tedy èasová slo¾itost inkrementálního udr¾ování suffixového -stromu amortizovanì konstantní. -\qed +zpozdit. Výroba zpìtné hrany tedy bude také trvat jen konstantnì dlouho. \references \bye -- 2.39.2