Online konstrukce deterministického zásobníkového automatu pro indexování strom. Bc. Ond ej Brynda

eské vysoké u£ení technické v Praze Fakulta elektrotechnická Katedra po£íta£·

Diplomová práce

Online konstrukce deterministického zásobníkového automatu pro indexování strom· Bc. Ond°ej Brynda

Vedoucí práce:

Doc. Ing. Jan Janou²ek, Ph.D.

Studijní program: Elektrotechnika a informatika, strukturovaný, Navazující magisterský

Obor: Výpo£etní technika

1. kv¥tna 2011

iv

v

Pod¥kování D¥kuji Doc. Ing. Janu Janou²kovi, Ph.D. za vedení této práce a v²em lidem, kte°í m¥ podporovali b¥hem mého studia.

vi

vii

Prohlá²ení Prohla²uji, ºe jsem práci vypracoval samostatn¥ a pouºil jsem pouze podklady uvedené v p°iloºeném seznamu. Nemám závaºný d·vod proti uºití tohoto ²kolního díla ve smyslu 60 Zákona £. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o zm¥n¥ n¥kterých zákon· (autorský zákon).

V Beroun¥ dne 30. 4. 2011

.............................................................

viii

Abstract This thesis deals with the pushdown automata which represent the full indexes of trees for subtrees and tree patterns. These machines accept all complete subtrees or all tree patterns. The goal is to design algorithms which constructs these machines without intermediate step of creating their nondeterministic versions. The inspiration for both algorithms is a similar algorithm from stringology, which is used for online construction of sux automaton. This and the two new proposed algorithms are described in the thesis and the run of new algorithms is presented on an example. Finally, the thesis presents a way of implementing these algorithms.

Abstrakt Práce se zabývá zásobníkovými automaty, které reprezentují úplný index stromu. Tyto automaty p°ijímají v²echny úplné podstromy nebo v²echny stromové vzorky. Cílem práce je navrhnout algoritmy, které by tyto automaty zkonstruovaly bez mezikroku vytvo°ení jejich nedeterministické verze. Inspirací pro oba algoritmy je podobný algoritmus ze stringologie, který se pouºívá k online konstrukci suxového automatu. Tento i oba navrºené algoritmy jsou v práci popsány a u nových algoritm· je jejich b¥h prezentován na p°íkladu. Nakonec je popsán i moºný zp·sob implementace uvedených algoritm·.

ix

x

Obsah 1

Úvod

2

Základní pojmy a algoritmy

2.1 2.2 2.3 2.4 2.5 3

3

Abeceda, strom, stromový vzorek . . . . . . . . . . Jazyk, kone£ný a zásobníkový automat . . . . . . . Suxový a faktorový automat . . . . . . . . . . . . Algoritmus online konstrukce suxového automatu D·leºité vlastnosti strom· v prexové notaci . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. 3 . 5 . 7 . 10 . 19

. . . .

. . . .

. . . .

Zásobníkový automat p°ijímající v²echny podstromy daného stromu

3.1 3.2

4

1

Konstrukce nedeterministického ZA p°ijímajícího v²echny podstromy Online konstrukce DZA p°ijímajícího v²echny podstromy . . . . . . . 3.2.1 Popis algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 P°íklad online konstrukce . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

21

21 25 27 30

Zásobníkový automat p°ijímající stromové vzorky obsaºené v daném strom¥ 39

4.1 4.2 4.3

Konstrukce NZA p°ijímajícího stromové vzorky . . . . Online konstrukce treetop automatu . . . . . . . . . . Online konstrukce DZA p°ijímajícího stromové vzorky 4.3.1 P°íklad online konstrukce . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

39 43 44 54

5

Implementace

65

6

Testování

67

7

Záv¥r

71

A Seznam pouºitých zkratek

75

B Instala£ní p°íru£ka

77

C Obsah p°iloºeného CD

79

xi

xii

OBSAH

Seznam obrázk· 2.1 2.2 2.3

P°íklad stromu t, pref(t) = a2 a2 a0 a0 a2 a0 b1 b0 . . . . . . . . . . . . . . Vzorek p, pref(p) = a2 a0 S . . . . . . . . . . . . . . . . . . . . . . . . . . . . Nedeterministický kone£ný suxový automat pro °et¥zce x = a2 a2 a0 a0 a2 a0 b1 b0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Deterministická verze automatu z obrázku 2.3 . . . . . . . . . . . . . . . . . . 2.5 a) DAWG(aabab), b) gracké znázorn¥ní sux link· . . . . . . . . . . . . . . 2.6 P°íklad p°idávání nových p°echod·, a) DAWG(aab), b) p°íslu²né sux linky . 2.7 Napojení sux linku, a) DAWG(aaba) b) p°íslu²né sux linky . . . . . . . . . 2.8 Situace p°ed rozd¥lením stavu [3], a) nekompletní DAWG(aabab) b) sux linky 2.9 DAWG(aaaa) a sux linky (te£kovan¥) . . . . . . . . . . . . . . . . . . . . . . 2.10 Pomocný obrázek k d·kazu sloºitosti algoritmu 2.1. a) ná£rt situace v obecném kroku b) ná£rt situace v dal²ím kroku . . . . . . . . . . . . . . . . . . . . . . 3.1

Nedeterministický zásobníkový automat p°íjímající v²echny podstromy stromu t, pref(t) = a2 a2 a0 a0 a2 a0 b1 b0 . . . . . . . . . . . . . . . . . . . . . . . 3.2 Deterministický zásobníkový automat ekvivalentní NZA z obrázku 3.1 . . . . 3.3 a) Situace p°ed rozd¥lením stavu v, b) situace po rozd¥lení stavu . . . . . . . 3.4 a) Automat pokud bychom nekontrolovali cpds, b) automat s kontrolou cpds. Sux linky jsou znázorn¥ny te£kovan¥ . . . . . . . . . . . . . . . . . . . . . . 3.5 Kroky 0 aº 3 algoritmu 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Kroky 4 a 5 algoritmu 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Výsledné sux linky vytvo°ené algoritmem 3.1 . . . . . . . . . . . . . . . . . . 3.8 Krok 6 algoritmu 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Krok 7 algoritmu 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 Krok 8 algoritmu 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 4.2 4.3 4.4 4.5 4.6 4.7

Strom z obrázku 2.1 dopln¥ný o p°edstavu p°echod· na symbol S . . Nedeterministický zásobníkový automat p°ijímající v²echny stromové stromu z obr. 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Deterministický zásobníkový automat p°ijímající v²echny stromové stromu z obr. 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Krok 0 aº 2 algoritmu 4.2 . . . . . . . . . . . . . . . . . . . . . . . . Krok 3 algoritmu 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . Krok 4 algoritmu 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . Krok 5 algoritmu 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii

. . . . . vzorky . . . . . vzorky . . . . . . . . . . . . . . . . . . . . . . . . .

4 5 8 9 11 13 15 16 17 18 22 24 28 30 31 33 35 35 36 37 40 41 42 54 55 56 57

xiv

SEZNAM OBRÁZK

4.8 Krok 6 algoritmu 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.9 Krok 7 algoritmu 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.10 Krok 8 algoritmu 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 6.1 6.2

Sux linky v automatu pro strom s prexový zápisem a2 a2 a0 a1 a0 a1 a0 . 68 DZA p°ijímající stromové vzorky obsaºené ve stromu s prexovým zápisem a2 a2 a0 a1 a0 a1 a0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

Seznam tabulek 3.1

Pr·b¥h výpo£tu algoritmu 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.1

Pr·b¥h výpo£tu algoritmu 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

xv

xvi

SEZNAM TABULEK

Kapitola 1

Úvod Mnoho struktur v na²em okolí je logicky uspo°ádáno do stromu. Obecn¥ se jedná o jakýkoliv systém, kde má kaºdý prvek práv¥ jeden nad°azený objekt. S takovýmto £len¥ním se setkáváme denn¥ jednak v b¥ºném ºivot¥, ale stejn¥ tak i v po£íta£ových v¥dách jsou stromy £asto vyuºívaná datová struktura. P°íklady pouºití najdeme velmi snadno. Je to nap°íklad ²iroce pouºívané XML, syntaktický strom v kompilátoru, hierarchie t°íd a objekt· v programovacím jazyce, r·zná pouºití ve vyhledávacích, kompresních a jiných algoritmech a mnoho dal²ího. Vyhledávání výskytu podstrom· a stromových vzork· v daném stromu je tedy velmi d·leºitá úloha. V¥dou, která se zabývá algoritmy pro vyhledávání ve stromech, je arbologie. Podobným oborem je stringologie, která se zabývá vyhledáváním v °et¥zcích. Hlavní motivací arbologie je vyuºití dob°e známých algoritm· ze stringologie p°i °e²ení obdobných problém· u strom·. [1] Základním p°edpokladem vyuºití princip· ze stringologie je to, ºe na strom budeme nahlíºet jako na °et¥zec. Toho lze docílit celkem snadno, nap°íklad tak, ºe strom zapí²eme v prexové notaci. Potom platí, ºe podstrom zapsaný v prexové notaci je pod°et¥zcem v prexovém zápisu celého stromu. Nicmén¥ je z°ejmé, ºe ne kaºdý pod°et¥zec reprezentuje podstrom. [6] Z toho vyplývá, ºe je pot°eba pouºít jiný model výpo£tu neº jsou kone£né automaty, které se pouºívají ve stringologii. V arbologii se místo kone£ných automat· pouºívají zásobníkové automaty. Stejn¥ jako ve stringologii, tak i v arbologii je více zp·sob·, jak vyhledávat vzorky. Jedno ze základních d¥lení by mohlo být, zda p°edzpracováváme vzorek nebo vlastní text. V této práci se zabývám jen moºností, kdy p°edzpracováváme text (respektive strom), ve kterém vyhledáváme. Tento zp·sob má výhodu v tom, ºe doba vyhledávání je pak lineárn¥ závislá jen na délce vzorku a v·bec nezávisí na délce textu. Automat, který vznikne p°edzpracováním textu se nazývá indexovací. Druhým moºným d¥lením m·ºe být to, jak indexovací automat vytvá°íme. Prozatím známá metoda je vytvo°it nejprve nedeterministickou verzi a pak automat zdeterminizovat. Zásobníkový automat sice nejde obecn¥ zdeterminizovat vºdy, ale automaty vznikající v arbologii mají takové vlastnosti, které determinizaci umoº¬ují. Tento postup má tu výhodu, ºe je relativn¥ názorný, ale nevýhoda je v tom, ºe je relativn¥ zdlouhavý a proces determinizace je pom¥rn¥ náro£ný. Lep²í metoda pro praktické pouºité je takzvaná online konstrukce, kde automat vytvá°íme postupn¥ tak, jak £teme vstupní text. Pro vyhledávání v °et¥zcích je 1

2

KAPITOLA 1.

ÚVOD

algoritmus pro online konstrukci znám, nap°íklad v [4] a [2]. P°ínosem této práce by m¥lo být denování obdobného algoritmu i pro konstrukci automat· indexujících stromy. Zbytek práce je organizován následovn¥. V následující kapitole 2 si denujeme základní pojmy z oblasti arbologie a stringologie, spole£n¥ s n¥kolika základními algoritmy. V kapitole 3 se budeme zabývat konstrukcí automat· p°ijímajících v²echny úplné podstromy daného stromu (Subtree PDA) a v kapitole 4 p°edstavíme konstrukci automat· p°ijímajících v²echny stromové vzorky (Tree pattern PDA). Nakonec v kapitole 5 krátce popí²eme implementaci uvedených algoritm· a její testování v kapitole 6.

Kapitola 2

Základní pojmy a algoritmy V této kapitole denujeme n¥kolik základních pojm· pot°ebných pro dal²í práci. Pojmy jsou denovány stejn¥ jako v [6] [10] [7] [8].

2.1 Abeceda, strom, stromový vzorek je kone£ná neprázdná mnoºina symbol·. Ohodnocená abeceda je abeceda, kde má kaºdý symbol p°i°azenu jednozna£nou kladnou aritu (ohodnocení). V dané abeced¥ A ozna£ujeme ohodnocení symbolu arity(a). Mnoºina symbol· s ohodnocením p je ozna£ena Ap . Prvky, které mají aritu 0, 1, 2 ...p ozna£ujeme jako nulární (konstanty), unární, binární atd. P°edpokládáme, ºe A obsahuje alespo¬ jeden nulární symbol. V dal²ím textu se arita symbol· ozna£uje pomocí £íslice za identikátorem symbolu, nap°íklad zápisem a2 se rozumí binární symbol a. P°i zápisu algoritm· si m·ºeme zápis arity(a2) p°edstavit jako volání funkce, která vrací aritu daného symbolu, v tomto p°ípad¥ vrátí 2.

Abeceda

Strom si denujeme pomocí pojm· z teorie graf·. Uspo°ádaný orientovaný graf je dvojice (U, H), kde U je mnoºina uzl· a H je lineárn¥ uspo°ádaná mnoºina hran, kde kaºdý prvek H má formu ((f, g1 ), (f, g2 ), ..., (f, gn )), kde f, g1 , g2 ...gn jsou uzly grafu a n ≥ 0. Tento zápis zna£í, ºe z uzlu f vede n orientovaných hran do uzl· g1 , g2 ...gn v tomto daném po°adí. Cesta délky n je sekvence uzl· (f1 , f2 ...fn ), n ≥ 1, z uzlu f do uzlu fn , pokud existuje hrana, která vede z fi−1 do fi pro v²echny 1 ≤ i ≤ n. Pokud navíc f0 = fn pak se daná cesta nazývá cyklus. Uspo°ádaný DAG (Direct Acyclic Graph) je uspo°ádaný orientovaný graf, ve kterém neexistuje cyklus. Ozna£ení uspo°ádaného grafu G = (U, H) je zobrazení U do mnoºiny zna£ek. Nap°íklad ozna£ení af v dal²ím textu reprezentuje uzel f ozna£ený symbolem a.

M¥jme dán uzel f. Jeho výstupní stupe¬ se rovná po£tu r·zných pár· (f, r) ∈ H . Analogicky vstupní stupe¬ uzlu f je po£et r·zných pár· (g, f ) ∈ H . Nyní jiº m·ºeme denovat ozna£ený, uspo°ádaný, ohodnocený, ko°enový strom nad abeA jako uspo°ádaný DAG t=(U, H) s práv¥ jedním speciálním uzlem, r ∈ U , který se nazývá ko°en, takový ºe pro n¥j platí: cedou

•

r

má vstupní stupe¬ roven 0 3

4

KAPITOLA 2.

ZÁKLADNÍ POJMY A ALGORITMY

• v²echny ostatní uzly mají vstupní stupe¬ 1 • existuje práv¥ jedna cesta z ko°ene

r

do v²ech ostatních f ∈ U a f 6= r

• kaºdý uzel f ∈ U je ozna£en symbolem a ∈ A a výstupní stupe¬ af se rovná Uzly, které jsou ozna£eny nulárními symboly, se nazývají

listy

(nap°íklad

arity(a).

a0 ).

Prexová notace pref(t) ozna£eného, uspo°ádaného, ohodnoceného, ko°enového stromu je zápis stromu, který získáme aplikací následujícího algoritmu Krok rekurzivn¥ na v²echny uzly daného stromu, po£ínaje ko°enem: Krok : Nech´ se tento krok týká uzlu af . Jestliºe je af list, pak vypi² af a skon£i. Jestliºe není af list a jeho potomci jsou af1 , af2 ...afn , pak vypi² af a postupn¥ pouºij krok na af1 , af2 ...afn v tomto po°adí.

Zatím jsme denovali, co je to ozna£ený, uspo°ádaný, ohodnocený, ko°enový strom nad abecedou A. V této práci se zabývám jen takovýmito stromy, takºe se na n¥ budu odkazovat zjednodu²en¥ pouze slovem strom. P°íklad ozna£eného, uspo°ádaného, ohodnoceného, ko°enového stromu je na obrázku 2.1. Ohodnocená abeceda je zde A = {a2, a1, a0, b1, b0}. Strom t = ({a21 , a22 , a03 , a04 , a25 , a06 , b17 , b08 }, H), kde H je následující uspo°ádaná mnoºina hran:

((a21 , a22 ), (a21 , a25 )) ((a22 , a03 ), (a22 , a04 )) ((a25 , a06 ), (a25 , b17 )) ((b17 , b08 ))

Obrázek 2.1: P°íklad stromu t,

pref(t) = a2 a2 a0 a0 a2 a0 b1 b0

Nyní máme denovaný strom, zbývá je²t¥ denovat, co vlastn¥ ve stromu hledáme. Strodenujeme pomocí speciálního nulárního symbolu S, který neleºí v A. Ozna£ený, uspo°ádaný, ohodnocený, ko°enový strom nad abecedou A∪{S} je stromový vzorek. Analogicky stromový vzorek v prexové notaci je zápis tohoto stromu pomocí jiº zmín¥ného algoritmu Krok. P°edpokládáme, ºe stromový vzorek obsahuje alespo¬ jeden symbol z A, to mový vzorek

2.2.

JAZYK, KONENÝ A ZÁSOBNÍKOVÝ AUTOMAT

5

znamená, ºe nap°íklad samotné S není stromový vzorek (vyhledávací úloha by potom byla triviální). Stromový vzorek s alespo¬ jedním symbolem S se nazývá ²ablona stromu. Stromový vzorek p obsahující k ≥ 0 symbol· S je nalezen v daném stromu t v uzlu n, jestliºe ve stromu t existují podstromy t1 , t2 , ..., tn (ne nutn¥ stejné) takové, ºe strom p' získaný z p substitucí podstromu ti pro i-tý výskyt S v p, i = 1, 2, ...,k, je rovný podstromu stromu t s ko°enem v n. Uvaºujme strom t z obrázku 2.1 v prexové notaci zapsaný jako pref(t) = a2 a2 a0 a0 a stromový vzorek p nad abecedou A∪{S}, p = ((a29 , a010 , S11 ), H), kde H je následující se°azená mnoºina pár·:

a2 a0 b1 b0

((a29 , a010 ), (a29 , S11 ))

Obrázek 2.2: Vzorek p,

pref(p) = a2 a0 S

Stromový vzorek p v prexovém zápisu pref(p) = a2 a0 S je zobrazený na obrázku 2.2. Vzorek p je nalezen ve strom¥ t ve dvou výskytech. První výskyt je v uzlu a22 a druhý v a25 . V literatu°e je ob£as vyhledávací problém denován také jako proces rozhodování, zda se daný vzorek v textu, respektive stromu, vyskytuje. Výsledkem je tedy odpov¥¤ ano nebo ne. Tento rozdíl v²ak není úpln¥ podstatný, protoºe obvykle algoritmy poskytují informace o výskytu a pozicích výskytu najednou nebo je lze n¥jakým zp·sobem dodate£n¥ odvodit. Jak je zvykem v pracích podobného typu, rozd¥lím si problém nejprve na vzorky, které neobsahují symbol S, tedy hledání p°esných podstrom· daného stromu a poté budeme uvaºovat i vzorky se symbolem S (²ablony stromu). Nejprve je v²ak je²t¥ pot°eba denovat si n¥kolik pojm· z teorie automat· a jazyk·, které nám poskytnou prost°edky pro popis výpo£tu pomocí kone£ných a zásobníkových automat·.

2.2 Jazyk, kone£ný a zásobníkový automat Pojmy v této kapitole jsou op¥t denovány stejn¥ jako v [6] [10] [7] [8]. nad abecedou A je mnoºina °et¥zc· nad A. Zápis A∗ ozna£uje mnoºinu v²ech °et¥zc· nad A v£etn¥ prázdného °et¥zce. Prázdný °et¥zec je ozna£ován ε. Zápis A+ symbolizuje mnoºinu A∗ bez prázdného °et¥zce, tj. A+ = A∗ \{ε}. Symbolem xm ozna£ujeme m z°et¥zení symbolu x. íslo m je celé kladné £íslo v¥t²í nebo rovno nule, x0 = ε, x1 = x, x2 = xx, atd. Jazyk

(NKA nebo anglicky NFA) je p¥tice M = (Q,A, δ, q0 , F ), kde Q je kone£ná mnoºina stav·, A je vstupní abeceda, δ je zobrazení Q × A do mnoºiny podmnoºin Q, q0 ∈ Q je po£áte£ní stav a F ⊆ Q je mnoºina koncových stav·. Dvojici (q, w) ∈ Nedeterministický kone£ný automat

6

KAPITOLA 2.


Q×A∗ nazveme kongurace kone£ného automatu M. Kongurace (q0 , w) se nazývá po£áte£ní kongurace a (q, ε), kde q ∈ F , je koncová kongurace kone£ného automatu M. Relaci `M ⊆ (Q × A∗ ) × (Q × A∗ ) nazveme p°echodem automatu M. Jestliºe p ∈ δ(q, a), pak (q, aw) `M (p, w), pro libovolné w ∈ A∗ . ekneme, ºe °et¥zec w ∈ A∗ je p°ijat nedeterministickým kone£ným automatem, pokud existuje posloupnost p°echod· (q0 , w) `∗ (q, ε) pro n¥jaké q ∈ F (z po£áte£ní kongurace do koncové kongurace).[5] Kone£ný automat je deterministický (DKA, anglicky DFA) pokud δ(q, a) nemá více neº jeden prvek pro kaºdé q ∈ Q a a ∈ A. Kaºdý nedeterministický kone£ný automat m·ºe být p°eveden na ekvivalentní (p°ijímající stejný jazyk) deterministický kone£ný automat. Procesu transformace na deterministický automat se °íká determinizace, anglicky také d-subset construction. Algoritmus funguje tak, ºe konstruujeme stavy DKA jako podmnoºiny stav· NKA a vybíráme jen ty stavy, které jsou v dané chvíli dostupné (tzn. existuje p°echod mezi stavy v NKA). Tyto podmnoºiny nazýváme d-subsety a £asto je zapisujeme do hranatých závorek ([ ]) namísto mnoºinového zápisu ({}). Mnoºina cílových stav· (zna£eno Q(a) ) pro n¥jaké a ∈ A jsou v²echny q ⊆ Q, takové, ºe q ∈ δ(p, a) pro v²echny p ∈ Q. Pokud pro v²echny dvojice symbol· a, b ∈A, a 6= b, platí Q(a) ∩ Q(b) = ∅, pak se automat nazývá homogenní. [5] Nedeterministický zásobníkový automat (NZA, anglicky PDA) je sedmice M = (Q,A, G, δ, q0 , Z0 , F ), kde Q je kone£ná mnoºina stav·, A je vstupní abeceda, δ je zobrazení z Q × (A∪{ε}) × G∗ do mnoºiny kone£ných podmnoºin Q × G∗ , q0 ∈ Q je po£áte£ní stav, Z0 ∈ G je po£áte£ní symbol na zásobníku a F ⊆ Q je mnoºina kone£ných (p°ijímajících) stav·. Trojice (q, w, x) ∈ Q×A∗ ×G∗ je kongurace zásobníkového automatu. Podle zvyklostí budeme vrchol zásobníku psát vpravo. Po£áte£ní kongurace ZA je trojice (q0 , w, Z0 ), kde w je vstupní °et¥zec. P°echod zásobníkového automatu je relace na mnoºin¥ kongurací: (q, aw, αβ) ` (p, w, γβ), kdyº (p, γ) ∈ δ(q, a, α). K-tá mocnina relace ` se zna£í `k , tranzitivní uzáv¥r se zna£í `+ , a `∗ je tranzitivní a reexivní uzáv¥r relace `. [5] Zásobníkový automat je deterministický, pokud platí: 1. |δ(q, a, γ)| ≤ 1, pro v²echny q ∈ Q, a ∈ A∪{ε}, γ ∈ G∗ 2. Je-li δ(q, a, α) 6= ∅, δ(q, a, β) 6= ∅ a α 6= β , pak α není p°íponou β a β není p°íponou α 3. Je-li δ(q, a, α) 6= ∅, δ(q, ε, β) 6= ∅, pak α není p°íponou β a β není p°íponou α Zjednodu²en¥ °e£eno, m·ºeme se, podobn¥ jako u kone£ného automatu, vºdy jednozna£n¥ rozhodnout podle vstupního symbolu a obsahu zásobníku, jaký p°echod v daném stavu ud¥lat. U zásobníkových automat· neplatí obecn¥, ºe lze kaºdý nedeterministický ZA p°evést na ekvivalentní deterministický. Moºné je to pouze ve speciálních p°ípadech, jako jsou nap°íklad ZA °ízené vstupem. Zásobníkový automat °ízený vstupem je takový automat, kde lze kaºdou zásobníkovou operaci jednozna£n¥ ur£it pouze podle vstupního symbolu. Jazyk p°ijímaný zásobníkovým automatem lze denovat dv¥mi zp·soby. První moºnost je, ºe p°ijímáme °et¥zce p°echodem do koncového stavu, tzn. ºe existuje posloupnost p°echod· z po£áte£ního stavu do koncového stavu a p°itom nezáleºí na kone£ném obsahu zásobníku. A druhá moºnost je, ºe p°ijímáme °et¥zce prázdným zásobníkem, potom existuje posloupnost p°echod· z po£áte£ního stavu do stavu, kde je obsah zásobníku roven ε. Ve druhém p°ípad¥

2.3.

7

SUFIXOVÝ A FAKTOROVÝ AUTOMAT

je mnoºina kone£ných stav· zásobníkového automatu prázdná. Oba druhy automat· lze vzájemn¥ p°evést, coº je denováno nap°íklad v [5]. V tomto textu jsou pouºívány, stejn¥ jako v [6] [10], pouze zásobníkové automaty p°ijímající prázdným zásobníkem.

2.3 Suxový a faktorový automat Suxové i faktorové automaty jsou vy£erpávajícím zp·sobem popsány nap°íklad v [9], zde se omezím pouze na n¥kolik základních princip·. Máme-li dán °et¥zec s ∈ A∗ , pak suxový automat zkonstruovaný pro °et¥zec s p°ijímá v²echny p°ípony tohoto °et¥zce. Analogicky faktorový automat p°ijímá v²echny pod°et¥zce daného °et¥zce. P°ijetí (vyhledání) pod°et¥zce (nebo p°ípony) probíhá v £ase lineárním k délce pod°et¥zce a v·bec nezávisí na délce °et¥zce s. asová sloºitost je hlavní výhodou tohoto postupu, protoºe logicky délka pod°et¥zce je men²í neº délka °et¥zce. Nevýhodou je velikost vzniklého automatu. To lze £áste£n¥ vyváºit pouºitím oracle automat·, ale to není p°edm¥tem této práce. Je²t¥ bych poznamenal, ºe faktorový automat se li²í od suxového jen tím, ºe v²echny jeho stavy jsou koncové. V této práci se pouºívají jen suxové automaty. Tyto automaty se také ob£as v anglické literatu°e ozna£ují jako DAWG (Direct Acyclic Word Graph). Suxový automat m·ºeme zkonstruovat nap°íklad pomocí algoritmu 3.10 z [9]. Vstupem je °et¥zec x = a1 a2 ...an nad abecedou A a výstupem je deterministický kone£ný automat M = ({0, 1, 2, .., n},A, δ, 0, {0, n}) p°ijímající v²echny suxy °et¥zce x. Mnoºinu δ zkonstruujeme následovn¥: 1. δ(i − 1, ai ) = i, pro v²echny

i

= 1, 2, ... ,

n

2. δ(0, a) = i, pokud δ(i − 1, a) = i, pro v²echny

i

= 2, 3, ... ,

n

A nakonec p°evedeme zkonstruovaný nedeterministický automat na ekvivalentní deterministický. Jak je vid¥t, postup konstrukce tohoto automatu je relativn¥ p°ímo£arý a názorný. Pravidla z bodu 1 nám umoºní p°ijmout celý °et¥zec a poté v bodu 2 p°idáme p°echody, které nám umoºní "p°esko£it"prexy °et¥zce, takºe m·ºeme p°ijmout v²echny p°ípony. Výsledný automat m·ºe být nedeterministický, coº nastane, pokud se v °et¥zci opakuje n¥jaký symbol, takºe pro praktické pouºití musíme automat je²t¥ zdeterminizovat nebo pouºít n¥kterou techniku simulace NKA, nap°. fail funkce, dynamické programování, bitový paralelismus ap. [9]. Uvaºujme nap°íklad, ºe máme °et¥zec x = a2 a2 a0 a0 a2 a0 b1 b0 nad abecedou A = {a2, a1, a0, b1, b0 } (°et¥zec je prexový zápis stromu t z obrázku 2.1, ale to te¤ není d·leºité). Nedeterministický kone£ný automat p°ijímající v²echny p°ípony tohoto °et¥zce, vzniklý pouºitím kroku 1 a 2 z p°edchozího algoritmu, je na obrázku 2.3. Deterministická verze stejného automatu je na obrázku 2.4. V dal²ím textu se nám je²t¥ hodí denovat termín páte° automatu. Páte° suxového (faktorového) automatu je nejdel²í souvislá posloupnost stav· a p°echod· vedoucích z po£áte£ního stavu automatu M. Jinými slovy je to posloupnost stav· a p°echod·, které projdeme, pokud máme na vstupu kompletní °et¥zec, pro který je automat zkonstruován. Na obrázku 2.4 jsou to nap°íklad stavy [0], [1,2,5], [2], [3], [4], [5], [6], [7], [8] a p°echody mezi nimi.

x

= a2 a2 a0 a0 a2 a0 b1 b0

KAPITOLA 2.

Obrázek 2.3: Nedeterministický kone£ný suxový automat pro °et¥zce

8 ZÁKLADNÍ POJMY A ALGORITMY

Obrázek 2.4: Deterministická verze automatu z obrázku 2.3

2.3. SUFIXOVÝ A FAKTOROVÝ AUTOMAT

9

10

KAPITOLA 2.


2.4 Algoritmus online konstrukce suxového automatu V minulé kapitole jsme si popsali, jak zkonstruovat suxový automat pro daný °et¥zec. Nevýhodou popsaného postupu je to, ºe musíme automat determinizovat, coº je £asov¥ a pam¥óv¥ náro£né. Lep²í by bylo zkonstruovat b¥hem na£ítání °et¥zce rovnou deterministický automat. Tomuto postupu se °íká online konstrukce. P°i online konstrukci v kaºdém kroku, tak jak na£ítáme vstupní °et¥zec, upravujeme aktuální automat tak, aby odpovídal deterministickému automatu p°ijímajícímu p°ípony dosud na£tené £ásti °et¥zce. Máme-li °et¥zec x = a1 a2 ...an , tak v i-tém kroku vytvo°íme suxový automat pro °et¥zec a1 a2 ...ai , i ≤ n. Jak uº bylo zmín¥no, i tyto algoritmy jsou známé ([4], [2], [3]), jen ne tak ²iroce jako p·vodní algoritmus. Algoritmus uvedený v £lánku [4] je sice upravený na pouºití pro degenerované °et¥zce (na jedné pozici ve vstupním °et¥zci m·ºe být více symbol·), ale dal by se jednodu²e (vynecháním jednoho cyklu) upravit pro normální °et¥zce. Tento algoritmus má v²ak tu nevýhodu, ºe si p°ímo uchovává d-subsety v²ech stav·, tedy v nejhor²ím p°ípad¥ (nap°íklad p°i °et¥zci aaaa...) se musí v kaºdém kroku aktualizovat v²echny stavy a tak má algoritmus výslednou sloºitost O(n2 ). Výhodou d-subset· je známá vlastnost, ºe identikují konce výskytu daného pod°et¥zce. Vzhledem k asymptotické sloºitosti algoritmu jsem nakonec zvolil algoritmus uvedený ve [2]. Podobný algoritmus je uveden i ve [3]. Algoritmus 2.1 je pseudokód algoritmu z [2] p°epsaný do na²í pouºívané notace. V algoritmu 2.1 jsou stavy identikovány namísto mnoºiny symbol· pomocí jen jednoho symbolu. Je tomu tak, protoºe, jak uº bylo zmín¥no, velikost dsubset· (v [2] nazývány end-pos ) je nelineární k délce °et¥zce. To je také jeden z d·vod·, pro£ je determinizace automatu pam¥óv¥ náro£ná. Samoz°ejm¥ namísto dsubset· je pot°eba jiná dodate£ná struktura, která by nám poskytla ekvivalentní informace. Pro online konstrukci je nap°íklad d·leºité v¥d¥t, z jakých stav· musíme vést nové p°echody, tj. jaké stavy odpovídají sux·m aktuáln¥ zpracované £ásti °et¥zce. Strukturou, která nám toto umoºní, je tzv. tabulka sux link·. Význam sux link· je nejlep²í demonstrovat na p°íklad¥. Nejprve si ho v²ak denujme formáln¥. Hodnotu uzlu v - val(v) je nejdel²í °et¥zec, který vytvo°íme pomocí p°echod· z po£áte£ního stavu do uzlu v. Pak suf[v] se rovná uzlu w takovému, ºe val(w) je nejdel²í sux val(v), který se nerovná val(v) (vlastní sux). Obvykle se suf [q0 ] rovná q0 nebo jiné speciální hodnot¥ (nil, null ap.). Hranu (v, suf[v] ) nazýváme sux link a tabulka suf je tabulka sux link·. Protoºe hodnota suf[v] je ost°e men²í neº hodnota v, pak suf tvo°í stromovou strukturu uzl·. Díky tomu, ºe pro kaºdý uzel v denujeme práv¥ jeden suf[v], tak pam¥óvé nároky pro uloºení tabulky sux link· jsou lineární k po£tu uzl· (na rozdíl od d-subset·). Podívejme se na obrázek 2.5, kde v £ásti a) vidíme DAWG, neboli suxový automat, pro °et¥zec aabab a v £ásti b) gracké znázorn¥ní sux link·. Pro názornost jsem ozna£il stavy sou£asn¥ pomocí d-subset·, aby bylo vid¥t, ºe nám ob¥ konstrukce dávají stejné informace. Vezmn¥me si nap°íklad stav [3], jehoº hodnota je °et¥zec aab. Nejdel²í sux, krom¥ aab, je °et¥zec ab, coº je hodnota stavu [3,5] (p°ipomínám, ºe hodnota je nejdel²í z °et¥zc· reprezentovaných daným stavem), existuje tedy sux link ze stavu [3] do [3,5]. Zárove¬ vidíme, ºe pokud hodnota stavu [3,5] p°edstavuje sux hodnoty stavu [3], tak to znamená, ºe výskyt obou °et¥zc· kon£í na stejné pozici, tedy d-subset stavu [3,5] obsahuje jako svojí podmnoºinu d-subset stavu [3] (coº je vid¥t na první pohled). Toto pozorování nám dává vlastn¥ návod,

2.4.

ALGORITMUS ONLINE KONSTRUKCE SUFIXOVÉHO AUTOMATU

11

jak v p°ípad¥ pot°eby sestavit d-subset daného stavu. Nap°íklad kdybychom se pohybovali z daného stavu po sux lincích opa£ným sm¥rem aº do stavu, který leºí na páte°i a tyto stavy ozna£ili jejich po°adím na páte°i (tak jako je to v p°íkladu), tak d-subset onoho stavu je sjednocením d-subset· stav· na páte°i (jak je vid¥t na p°íkladu stav· [3,5] a [1,2,4]). Pro úplnost se je²t¥ podívejme na zbylé stavy. Stejná situace jako u stavu [3] je i u stavu [5], kde se op¥t jedná o sux ab. U hodnoty stavu [4] je nejdel²í sux jen °et¥zec a, který odpovídá stavu [1,2,4]. Stav [2] má hodnotu aa, tedy nejdel²í sux je op¥t a a sux link vede do uzlu [1,2,4]. Uzel [3,5] má hodnotu ab, sux b sice v automatu existuje, ale sux link by sm¥°oval do stejného uzlu, coº nelze, takºe z [3,5] vede sux link do [0]. U stavu [0] si m·ºeme p°edstavit, ºe reprezentuje sux ε, který je p°íponou libovolného °et¥zce.

Obrázek 2.5: a) DAWG(aabab), b) gracké znázorn¥ní sux link· Zbývá otázka, jak vlastn¥ sux linky zkonstruovat a jak zmín¥né vlastnosti vyuºít p°i online konstrukci suxového (nebo faktorového) automatu. Je tedy vhodná chvíle podívat se na algoritmus 2.1 a popsat si, jak funguje. Prvním krokem je inicializace algoritmu, kterou popisují °ádky 1-3. Inicializace se skládá ze t°í krok·. Na prvním °ádku denujeme prom¥nnou last, která p°edstavuje poslední vytvo°ený uzel na páte°i automatu. V 0-tém kroku je to logicky stav 0, který vytvo°íme na °ádku 2 a p°idáme do mnoºiny stav· Q. Nakonec zbývá je²t¥ inicializovat sux link stavu 0. Protoºe se jedná o po£áte£ní stav, tak suf [0] = nil, kde nil je na²e speciální hodnota, kterou nepouºijeme k ozna£ení ºádného stavu.

12 Algoritmus 2.1

KAPITOLA 2.


Online konstrukce suxového automatu (DAWG)

et¥zec x nad abecedou A, x = a1 a2 ...an , n ≥ 1 Výstup: Deterministický suxový automat M = (Q,A, δ, 0, ∅) 1: last = 0 2: Q.add(last) 3: suf [last] = nil 4: for i = 1 to n do 5: newlast = novyStav() 6: Q.add(newlast) 7: create solid δ(last, ai ) = newlast 8: w = suf [last] 9: while w 6= nil and 6 ∃δ(w, ai ) do 10: create non-solid δ(w, ai ) = newlast 11: w = suf [w]

Vstup:

12: end while 13: v = δ(w, ai ) 14: if w = nil then 15: suf [newlast] = 0 16: else if δ(w, ai ) = v is solid then 17: suf [newlast] = v 18: else 19: newnode = novyStav() 20: Q.add(newnode) 21: update δ(w, ai ) = newnode solid 22: suf [newlast] = newnode 23: suf [newnode] = suf [v] 24: suf [v] = newnode 25: w = suf [w] 26: while w 6= nil and δ(w, ai ) = v is non-solid do 27: update δ(w, ai ) = newnode 28: w = suf [w] 29: end while 30: for each a in A do 31: create non-solid δ(newnode, a) = δ(v, a) 32: end for 33: end if 34: last = newlast 35: end for

{inicializace

automatu }

{nový

{p°idat

{dal²í

stav }

p°echody }

výskyt °et¥zce }

{rozd¥lení

{p°esm¥rovat

{kopie

stavu }

p°echody }

odchozích }

Na °ádku 4 za£íná cyklus, kterým budeme postupn¥ zpracovávat symboly ze vstupního °et¥zce a podle nich p°íslu²ným zp·sobem aktualizovat automat. Pro kaºdý vstupní symbol nejprve vytvo°íme na páte°i nový stav, který si uloºíme do prom¥nné newlast. K vytvo°ení nových stav· budeme pouºívat funkci novyStav(), která jednodu²e vrátí nové unikátní pojmenování stavu. Funkci novyStav() lze realizovat triviáln¥, nap°íklad pomocí jednoduchého £íta£e, který vºdy automaticky zvý²í svojí hodnotu, takºe její pseudokód ani neuvádím.

2.4.


Následn¥ nový stav uloºíme do mnoºiny stav·

Q

13

(°ádek 6).

Nový stav musíme je²t¥ spojit s páte°í tím, ºe vytvo°íme p°echod z last do newlast. P°echod si navíc ozna£íme jako "solid", coº znamená, ºe uº se v budoucnu nem·ºe zm¥nit. Druhá moºnost, která se v pr·b¥hu algoritmu vyskytne je "non-solid", tedy analogicky opa£ný význam, tj. ºe v dal²ích krocích algoritmu se m·ºe p°echod zm¥nit. Tím máme páte° automatu aktualizovanou a m·ºeme pokra£ovat dal²ím krokem (°ádek 8). Dal²í fází algoritmu je (na °ádcích 8-12) vytvo°ení nových p°echod· z n¥kterých stávajících stav· do nového stavu - newlast. Pro lep²í pochopení se podívejme na obrázek 2.6, který zobrazuje situaci po t°etím kroku vytvá°ení DAWG(aabab), tedy DAWG(aab) a p°íslu²né sux linky. V tomto p°ípad¥ uº nezna£íme stavy pomocí d-subset·, ale pouze pomocí po°adí jak vznikly. árkovan¥ jsou ozna£eny p°echody, které v tomto kroku p°idáme. Prom¥nná last má hodnotu [2] a newlast [3].

Obrázek 2.6: P°íklad p°idávání nových p°echod·, a) DAWG(aab), b) p°íslu²né sux linky V cyklu na °ádku 9 postupujeme po sux lincích, dokud nedojdeme do po£áte£ního stavu anebo dokud neobjevíme p°echod na aktuální vstupní symbol. Uzly si p°i°azujeme do prom¥nné w. V tomto p°ípad¥ bude mít w nejprve hodnotu [1], pak [0] a nakonec nil. Kdyº si vzpomeneme na popis toho, jak pomocí sux link· získat d-subsety stav·, tak vlastn¥ v²echny procházené stavy by obsahovaly v d-subsetu hodnotu z prom¥nné last (kdybychom stavy zna£ili d-subsety a ne po°adím, v jakém vznikají). Samoz°ejm¥ výjimkou je stav [0], coº je výjime£ný p°ípad, protoºe jeho d-subset sice neobsahuje last, ale musíme ho vºdy také uvaºovat, protoºe z n¥j musí vést p°echody na v²echny symboly, které se v °et¥zci vyskytují, coº je nejlépe vid¥t z p°íkladu nedeterministické verze suxového automatu, viz obrázek 2.3. Na²t¥stí tomu odpovídá i to, ºe se ve stavu [0] "scházejí"v²echny sux linky, jelikoº, jak uº bylo zmín¥no, m·ºeme si p°edstavit, ºe [0] reprezentuje °et¥zec ε, který je p°íponou v²ech °et¥zc·. Kdyº tedy d-subsety v²ech stav· obsahují last (v tomto p°ípad¥ 2), znamená to, ºe tam kon£í výskyt v²ech °et¥zc·, které jsou hodnotami daných uzl·. Dále víme, ºe za last je dal²í znak, nyní konkrétn¥ b, kterým mají dané pod°et¥zce pokra£ovat. Takºe abychom

14

KAPITOLA 2.


mohli p°ijmout i pod°et¥zce (suxy) prodlouºené o tento nový znak, musíme ve v²ech uzlech p°idat p°echod na tento vstupní symbol. V²echny nové p°echody vedou do uzlu newlast. Sice bychom mohli vytvo°it pro kaºdý p°echod nový kone£ný (a v tu chvíli zárove¬ koncový) stav, ale bylo to zbyte£né, protoºe tyto stavy by byly shodné jako newlast. Zárove¬ to odpovídá tomu, ºe práv¥ tento uzel p°edstavuje nejdel²í sux (p°ipome¬me, ºe páte° je nejdel²í cesta v suxovém automatu) a ostatní cesty jsou jeho suxem. D·leºité je poznamenat, ºe tyto p°echody se mohou po £ase zm¥nit, proto je ozna£íme jako non-solid. Mnoºin¥ uzl·, které procházíme zmín¥ným cyklem, se °íká pracovní cesta. Jak je vid¥t, cyklus m·ºe skon£it dv¥mi moºnými zp·soby. M·ºe nastat w = nil, to znamená, ºe jsme pro²li v²echny uzly na pracovní cest¥ a z kaºdého jsme vytvo°ili p°echod. Mimo jiné to implikuje, ºe jsme museli vytvo°it i p°echod z po£áte£ního stavu [0], coº zna£í, ºe se daný symbol je²t¥ v automatu v·bec nevyskytuje. Díky této informaci m·ºeme nastavit suf[newlast] = [0]. Viz akce provedené na °ádku 14 a 15 algoritmu 2.1. Toto je i situace, která nastane v p°íkladu na obrázku 2.6. V opa£ném p°ípad¥, tj. kdyº w není nil, tak jiº existuje n¥jaký p°echod na aktuální vstupní symbol z n¥jakého uzlu na pracovní cest¥. Jinými slovy, jiº je zaindexovaný n¥jaký krat²í pod°et¥zec doposud zpracované £ásti vstupního °et¥zce. V tomto p°ípad¥ víme, ºe existuje uzel v = δ(w, a), kde a je aktuální symbol na vstupu a w je uzel na pracovní cest¥, do kterého jsme do²li. Nyní nastává klí£ový bod algoritmu a to rozhodnout se, zda rozd¥lit stav v nebo ne. Lépe je v²e vid¥t op¥t z p°íkladu. Nap°íklad na obrázku 2.7 je znázorn¥n dal²í krok konstrukce automatu pro °et¥zce aaba. V tomto p°ípad¥ se last = [3], takºe první hodnota w bude suf [last] = w = [0] (°ádka 8). Protoºe p°echod z [0] na symbol a jiº existuje, neprob¥hne cyklus ani jednou a w z·stane nastaveno na [0]. Uzel v se rovná δ([0], a) = [1]. Vidíme, ºe uzel v p°edstavuje faktor a, který zárove¬ odpovídá nejdel²ímu suxu aaba. To p°esn¥ odpovídá denici sux linku, takºe p°idáme sux link suf [newlast] = v . Popsaná akce je na °ádku 17. Kdyº se vrátíme k p°edstav¥ o tom, ºe pomocí sux link· lze získat d-subsety, tak vlastn¥ touto operací roz²í°íme d-subset stavu v o dal²í výskyt °et¥zce, který je hodnotou tohoto stavu (v p°íkladu je to o výskyt a na pozici 4). M·ºe se v²ak také stát, ºe uzel v p°edstavuje více faktor· (vede do n¥j více cest), ale ne v²echny tyto faktory jsou zárove¬ suxy, takºe bychom vytvo°ili sux link ²patn¥. V takovém p°ípad¥ je pot°eba rozd¥lit uzel v. Podívejme se nap°íklad na obrázek 2.8, který zobrazuje situaci t¥sn¥ p°ed rozd¥lením stavu v = [3] (tedy jsme p°ed spu²t¥ním °ádku 19). Do stavu [3] vedou hned t°i cesty: b, ab, aab, ale cesta aab není suxem aaba. V tomto p°ípad¥ provedeme rozd¥lení stavu v = [3]. Operace rozd¥lení stavu se skládá z n¥kolika krok·. Nejprve si uv¥domme, £eho chceme vlastn¥ docílit. V²echny cesty v automatu chceme zachovat, jenom pot°ebujeme rozli²it cesty pro n¥které suxy. Uºite£ná je op¥t p°edstava roz²i°ování d-subsetu. Kdybychom pouze nastavili sux link, tedy potaºmo p°idali do d-subsetu stavu [3] dal²í výskyt (pozici 5), tak bych °íkali, ºe se na oné pozici vyskytují v²echny faktory, které odpovídají cest¥ do tohoto uzlu. Ale jak je vid¥t na p°íkladu, tak pro pod°et¥zec aab by toto neplatilo (nevyskytuje se na pozici 5). Namísto toho tedy vytvo°íme nový stav, který bude odpovídat "krat²ím"sux·m a stav [3] bude odpovídat jen °et¥zci aab. Prvním krokem operace rozd¥lení stavu je vytvo°ení nového uzlu - °ádek 19 a samoz°ejm¥ jeho p°idání do mnoºiny Q - °ádek 20. Nový stav si ozna£íme prom¥nnou newnode. Potom je pot°eba p°esm¥rovat existující p°echody do nového

2.4.


15

Obrázek 2.7: Napojení sux linku, a) DAWG(aaba) b) p°íslu²né sux linky stavu. To probíhá v cyklu na °ádcích 26-29. Známým zp·sobem procházíme uzly po pracovní cest¥, dokud nedojdeme na konec (w = nil) a zárove¬ dokud existují p°echody ozna£ené non-solid vedoucí z práv¥ zpracovávaného uzlu na aktuální vstupní symbol. Tato podmínka odpovídá tomu, ºe chceme p°esm¥rovat jen p°echody reprezentující aktuální sux. V p°íklad¥ na obrázku 2.8 takto p°esm¥rujeme p°echod z [0] na b. P°echod z [1] na b jsme p°esm¥rovali uº na °ádku 21. Zbývá nám je²t¥ vytvo°it p°echody vedoucí z nového stavu. Protoºe chceme zachovat v²echny cesty, které jsme m¥li p°ed rozd¥lením stavu, p°echody z nového stavu jsou prostou kopií p°echod· z p·vodního stavu. Jediným rozdílem je, ºe jsou ozna£eny jako non-solid. Tuto operaci znázor¬ují °ádky 30-32 v algoritmu 2.1. V na²em p°íkladu se jedná jen o p°echod z [3] do [4] na a. Výsledný automat uº byl prezentován na obrázku 2.5 (v p°ípad¥, ºe bychom pojmenovávali stavy podle po°adí, tak by byl stav [1,2,4] ze zmín¥ného obrázku pojmenován pouze [1] a stav [3,5] bychom pojmenovali [6]). Abychom celou operaci úpln¥ dokon£ili, zbývá je²t¥ aktualizovat p°íslu²né sux linky. V algoritmu 2.1 se jedná o °ádky 22-24, které jsme p°i popisu algoritmu prozatím vynechali. Jak uº bylo zmín¥no, nový stav odpovídá sux·m aktuáln¥ zpracované £ásti pod°et¥zce, tedy i nejdel²ímu z nich (v na²em p°ípad¥ ab ). Nastavíme tedy suf [newlast] = newnode (°ádka 22). Sux link nového stavu newnode povede do stejného stavu jako p·vodní sux link p·vodního stavu v (v tomto p°ípad¥ [0]) viz °ádek 23. A nakonec nový sux link stavu v povede do newnode, protoºe jsme vytvo°ili stav, který p°edstavuje suxy faktoru, který je hodnotou stavu v. Tím pádem je nejdel²í sux zjevn¥ hodnotou nového stavu - newnode (°ádek 24). Nap°íklad v p°ípad¥ uzlu [3] reprezentujícího faktor aab, uzel newnode odpovídá sux·m b a ab, tedy nejdel²í sux, který se nerovná aab je ab a sux link vede stavu, který

16

KAPITOLA 2.

má tuto hodnotu tj.

newnode


([3,5] nebo [6] podle toho jaké pouºíváme zna£ení).

Obrázek 2.8: Situace p°ed rozd¥lením stavu [3], a) nekompletní DAWG(aabab) b) sux linky Tím je operace rozd¥lení stavu hotová a dostáváme se na poslední °ádek (34), kde uº sta£í pouze nastavit last = newlast pro dal²í pr·chod cyklem s dal²ím symbolem ze vstupu. Nakonec bychom m¥li je²t¥ vysv¥tlit, co znamená zna£ení p°echod· solid a non-solid. V p°edchozím textu jsme si ho denovali bez podrobností, jako ty, které se mohou zm¥nit a ty které ne. A navíc jsme se podle tohoto ozna£ení p°echodu rozhodovali, zda stav rozd¥lit nebo ne. Trochu matoucí je to, ºe název solid, popisuje hlavn¥ moºné operace s p°echodem, ale uº mén¥ jeho vlastnosti. To se sice hodí v algoritmu, ale je to trochu mén¥ názorné. Denujme si tedy toto zna£ení p°esn¥. Nejprve zave¤me funkce length(q), pro n¥jaký stav q, která vrací délku nejdel²ího faktoru, který je hodnotou uzlu q. Tedy obdobn¥ jako jsme denovali hodnotu uzlu, jenom vracíme délku (po£et symbol·). Potom p°echod δ(p, a) = q je ozna£en jako solid práv¥ tehdy, kdyº length(q) = length(p) + 1. V opa£ném p°ípad¥ je p°echod ozna£en jako non-solid. Jinými slovy p°echody ozna£ené jako non-solid tvo°í v automatu "zkratky", zatímco p°echody ozna£ené solid jsou nejdel²í moºná cesta. Z toho plyne i pouºívaná vlastnost v algoritmu 2.1. Zatímco nejdel²í cestu uº zm¥nit (prodlouºit) nem·ºeme, tak zkratky se mohou po £ase zm¥nit (prodlouºit), jako se tomu stalo v p°íklad¥ z obrázku 2.8. Stav δ([1], b) = [3] je ozna£ený non-solid, protoºe length([3]) = 3 a length([1]) = 1 tj. 3 6= 1 + 1. V²imn¥me si, ºe t¥mto princip·m odpovídá i postupné zna£ení p°echod· p°i jejich vytvá°ení. Kdyº vytvá°íme p°echody na páte°i tak jsou vºdy solid, zatímco kdyº postupujeme po sux lincích dál, vytvá°íme vlastn¥ vºdy zkratky. Stejn¥ tak, kdyº kopírujeme odchozí p°echody z nového rozd¥leného stavu, jsou to vlastn¥ zkratky do dal²ích stav· na páte°i, respektive tvo°í krat²í faktory neº ty, pokud se pohybujeme nap°íklad po páte°i. Tím jsme vlastn¥ celkem podrobn¥ popsali celý algoritmus online konstrukce DAWG.

2.4.


17

M·ºeme tedy stru£n¥ zmínit jeho výhody a nevýhody. Nevýhodou je to, ºe nemáme v kaºdém kroku denovanou mnoºinu koncových stav·. Ve své podstat¥ je to d·sledek toho, ºe místo d-subset· pouºíváme sux linky. Uvaºujme nap°íklad p°íklad aaaa na obrázku 2.9. V kaºdém kroku jen p°idáme sux link na p°edcházející stav, tedy provedeme operaci s konstantní sloºitostí. Kdybychom m¥li ozna£it v²echny koncové stavy, museli bychom projít celou pracovní cestu. V tomto p°ípad¥ bychom tedy pro²li v²echny stavy. Stejné by to bylo, kdybychom místo sux link· pouºívali d-subsety. Museli bychom projít v²echny stavy a aktualizovat d-subset, protoºe v²echny pod°et¥zce se vyskytují i na poslední pozici. Nevýhody by byly v tom p°ípad¥ hned dv¥. Jednak v kaºdém kroku i bychom museli ud¥lat i operací, takºe celkov¥ by byla £asová asymptotická sloºitost algoritmu O(n2 ) a navíc pro uloºení d-subset· bychom pot°ebovali také nelineárním mnoºství pam¥ti. V p°ípad¥, ºe pouºíváme sux linky, by platila jen první nevýhoda, protoºe pam¥óvá náro£nost jejich uloºení je lineární (pro kaºdý stav jeden sux link). Vzhledem k tomu, ºe se ani nevracíme po pracovní cest¥, tak neplatí ani druhá nevýhoda.

Obrázek 2.9: DAWG(aaaa) a sux linky (te£kovan¥) To, ºe nemáme ozna£ené koncové stavy je svým zp·sobem d·sledek toho, ºe nemáme ani nijak implicitn¥ dané pozice výskyt· °et¥zc·, jako je tomu v p°ípad¥, ºe bychom udrºovali d-subsety. D·vody jsou stejné jako v p°edchozím p°ípad¥. Na²t¥stí uº jsme na za£átku kapitoly popsali, jak pomocí sux link· získat pozice výskyt· odpovídajících sux·. Stejným zp·sobem m·ºeme dodate£n¥ zjistit i koncové stavy tak, ºe projdeme aktuální pracovní cestu. Pokud to ud¥láme jen jednou po skon£ení hlavního for-cyklu, tak tím asymptotickou sloºitost algorimu nezvý²íme. V nejhor²ím p°ípad¥ je to n krok· navíc, tedy n + n krok· je stále asymptoticky O(n). Lineární asymptotická sloºitost O(n) je hlavní výhodou algoritmu 2.1. Pro£ je práv¥ lineární, uº trochu napovídají p°edchozí °ádky, ale tuto vlastnost m·ºeme odvodit i analýzou pseudokódu algoritmu. Inicializace je na první pohled konstantní. Poté následuje cyklus od 1 do n (délka °et¥zce), který zpracovává vstupní °et¥zec. Tomu se samoz°ejm¥ vyhnout nem·ºeme, takºe hlavní otázkou je sloºitost operací uvnit° tohoto cyklu. Uvnit° cyklu jsou samé konstantní operace, aº na t°i cykly - p°idávání p°echod·, p°esm¥rování p°echod· a kopie odchozích p°echod·. Poslední cyklus závisí pouze na po£tu symbol· v abeced¥, coº je konstanta, takºe tento cyklus nás trápit nemusí. Hor²í je situace s prvními dv¥ma cykly, které oba závisí na délce pracovní cesty. Na první pohled se m·ºe zdát, ºe kdyº délka pracovní cesty m·ºe být rovna délce p°e£tené £ásti °et¥zce (tedy v i -tém kroku má délku i ), tak to znamená, ºe sloºitost algoritmu je O(n2 ). Bylo v²ak dokázáno (více £i mén¥ názorn¥), ºe tomu tak není a výsledná sloºitost je lineární, nap°íklad v [2] a [3]. Inspirujme se nap°íklad d·kazem z [3] a popi²me si d·kaz pro první cyklus. P°edpokládejme, ºe máme °et¥zec x a pro n¥j zkonstruovaný suxový automat M pro n¥jaký prex x. Zpracovanou £ást °et¥zce si ozna£me w a p°edpokládejme, ºe na vstupu je nyní n¥jaký symbol a. Dále si ozna£me u, nejdel²í slovo, které je hodnotou uzlu w, který testujeme v podmínce

18

KAPITOLA 2.


cyklu (°ádek 9). Uzel w získáme pomocí sux linku suf[last] (°ádek 8). V²imn¥me si, ºe u je sux w a ºe kone£ná hodnota ua (poté co zastavíme cyklus) je suxem °et¥zce wa, pokud je uzel w denován (není nil ). et¥zec u je sux w, protoºe se na n¥j dostaneme sux linkem a skute£nost, ºe ua je suxem °et¥zce wa odpovídá ukon£ovací podmínce - tj. zastavíme, kdyº p°echod na a existuje. Dále si ozna£me hodnotu k = |w| − |u|. Schéma situace je na obrázku 2.10 a). Mimo jiné k zna£í pozici výskytu u ve w.

Obrázek 2.10: Pomocný obrázek k d·kazu sloºitosti algoritmu 2.1. a) ná£rt situace v obecném kroku b) ná£rt situace v dal²ím kroku Nyní provedeme pozorování, ºe tím jak procházíme cyklem, tj. pohybujeme se po sux lincích blíºe po£áte£nímu stavu, tak se délka u sniºuje a tím pádem se naopak k zvy²uje (|w| je v jednom kroku konstantní). Navíc potom co dokon£íme pr·chod cyklem, nastavíme sux link newlast (coº bude last v dal²ím kroku) na uzel, který odpovídá hodnot¥ ua (uzel v v algoritmu). Sux link z newlast vede tedy nyní n¥kam do £ásti, která byla ozna£ena u (nebo je to p°ímo ua ). V p°í²tím kroku za£neme procházet cyklem práv¥ od tohoto uzlu. Jelikoº délka u se bu¤ sniºovala nebo se jeho délka nem¥nila, tak po£áte£ní hodnota k v dal²ím kroku (ki+1 ) je vºdy v¥t²í nebo rovna kone£né hodnot¥ v sou£asném kroku. Poznámka: neznamená to, ºe kdyº u bude ε, tak uº nikdy nebude v¥t²í, protoºe k n¥mu m·ºeme p°idat aktuální symbol na vstupu (který jakoby "ukrojíme"z k ) - vzhledem k tomu, ºe se ale sou£asn¥ prodlouºí w o jeden symbol, tak k z·stane stejné (odpovídá to situaci, kdy p°ijde sux, který

2.5.

DLEITÉ VLASTNOSTI STROM V PREFIXOVÉ NOTACI

19

jsme je²t¥ neznali a pak z n¥j postupn¥ vytvá°íme del²í suxy). Situace je op¥t nazna£ena na obrázku 2.10 b), který zna£í situaci v následujícím kroku po p°idání symbolu a v £ásti obrázku a) (indexem i + i jsou ozna£eny nové hodnoty prom¥nných). D·sledkem popsaného principu je to, ºe £ást °et¥zce k díky sux linku p°esko£íme a u je to, co musíme teoreticky projít b¥hem cyklu. Pracovní cesta je tedy omezena prom¥nnou, která se neustále zv¥t²uje, tím pádem odpovídá celkový po£et provedených iterací za v²echny pr·b¥hy cyklu |x|. Podobn¥ se dá postupovat i pro od·vodn¥ní po£tu krok· druhého cyklu (p°esm¥rování p°echod·). Jiný pohled na d·kaz m·ºe být ten, ºe si p°edstavíme, ºe chceme dosáhnout nejhor²ího p°ípadu, tedy pracovní cesty délky rovné n. Ze za£átku bychom tedy dostávali po°ád stejný symbol, takºe sux linky by vedly z newlast do last. V tom p°ípad¥ ale neprovedeme t¥lo cyklu ani jednou. Musí p°ijít dal²í symbol, jiný neº p°edchozí, abychom pro²li celou pracovní cestu. Potom v²ak nastavíme sux link newlast na po£áte£ní stav a délka pracovní cesty uº nikdy nebude p°es v²echny uzly. Je²t¥ jednodu²eji si m·ºeme lineárnost od·vodnit tak, ºe po£et p°echod· je lineárn¥ závislý na délce °et¥zce. Tedy abychom vytvo°ili lineární po£et p°echod·, musíme zavolat cyklus, který je vytvá°í, lineárn¥-po£et-krát. Co se tý£e pr·b¥hu algoritmu, v této kapitole jsme si popsali p°edev²ím hlavní situace b¥hem jeho b¥hu. Kompletní p°íklad bude uveden v následující kapitole 3.

2.5 D·leºité vlastnosti strom· v prexové notaci Nakonec této kapitoly se je²t¥ podívejme na n¥které d·leºité vlastnosti strom· v prexové notaci, které uplatníme p°i konstrukci zásobníkových automat·. Z°ejm¥ nejd·leºit¥j²í vlastnost prexového zápisu podstromu je to, ºe tento zápis je pod°et¥zcem prexového zápisu stromu. Naopak v²ak neplatí, ºe kaºdý pod°et¥zec prexového zápisu stromu je podstrom v prexovém zápisu. Tato vlastnost je zd·vodn¥na nap°íklad v [6], [10] tak, ºe pro daný °et¥zec existuje n2 pod°et¥zc·, ale jen n r·zných podstrom· (kaºdý uzel je ko°enem podstromu). Abychom ov¥°ili, zda je daný °et¥zec skute£n¥ prexovým zápisem stromu, denujeme tzv. arity checksum. M¥jme °et¥zec w = a1 a2 ..am , m ≥ 1, nad ohodnocenou abecedou, pak arity checksum ac(w) = arity(a1 ) + arity(a2 ) + ... + arity(am ) − m + 1. Práv¥ tehdy, kdyº ac(w) = 0 a ac(w1 ) ≥ 1 pro v²echny w1 , kde w = w1 x, x 6= ε, tak w je prexový zápis podstromu. Neformáln¥ °e£eno, arity checksum p°edstavuje po£et uzl·, které je pot°eba je²t¥ p°e£íst, aby byl strom kompletní. Druhá podmínka °íká, ºe nesmí existovat prex °et¥zce w, aby tento prex byl sám o sob¥ stromem (tzn. nap°íklad °et¥zec w by byl zápis dvou strom· v prexové notaci za sebou). Pojem arity checksum se nám bude hodit v dal²ích algoritmech. V automatech je arity checksum implementován pomocí zásobníkových operací, kde po£et symbol· na zásobníku reprezentuje aktuální arity checksum. Toto nám vlastn¥ p°ímo dává návod, jak sestavit zásobníkový automat p°ijímající podstrom. Ve chvíli, kdy je arity checksum roven nule, jsme p°e£etli kompletní podstrom. To vysv¥tluje, pro£ pouºíváme zásobníkové automaty p°ijímající prázdným zásobníkem. Dal²ím d·sledkem je mimo jiné to, ºe výsledný automat bude mít mén¥ p°echod· neº klasický suxový automat, protoºe n¥které p°echody není moºno

20

KAPITOLA 2.


provést, kdybychom m¥li prázdný zásobník. Také tento fakt se musí zohlednit v následujících algoritmech.

Kapitola 3

Zásobníkový automat p°ijímající v²echny podstromy daného stromu Zásobníkový automat p°ijímající v²echny podstromy daného stromu se v anglické literatu°e ([6], [10]) ozna£uje jako subtree pushdown automata. Tento automat p°ijímá v²echny úplné podstromy daného stromu zapsané v prexové notaci. V této kapitole si uvedeme jednak algoritmus pro konstrukci zásobníkového automatu p°ijímajícího v²echny podstromy pomocí mezikroku vytvo°ení nedeterministické verze automatu a pak také online algoritmus upravený, tak aby vytvo°il odpovídající zásobníkový automat rovnou deterministický. Zásobníkové automaty p°ijímající podstromy daného stromu jsou p°edstaveny v [6]. Tyto ZA p°edstavují úplný index stromu a deterministická varianta automatu vyhledává výskyt podstromu v £ase lineárním k délce prexového zápisu podstromu a p°itom v·bec nezávisí na délce prexového zápisu p·vodního stromu. Zásobníkové automaty p°ijímající v²echny podstromy daného stromu p°ijímají, jak uº bylo zmín¥no, prázdným zásobníkem, coº zna£í, ºe jsme p°e£etli úplný podstrom.[10] D·leºité vlastnosti prexového zápisu strom· a podstrom· jsem uº nazna£il v p°edchozí kapitole, nezbývá tedy neº uvést vlastní algoritmus.

3.1 Konstrukce nedeterministického ZA p°ijímajícího v²echny podstromy Algoritmus je denovaný stejn¥ jako v [10] a [6]. Vstupem algoritmu je strom t v prexové notaci pref (t) = a1 a2 ...an , n ≥ 1 a výstupem je nedeterministický zásobníkový automat p°ijímající v²echny podstromy daného stromu M = ({0, 1, 2, ..., n},A, {S}, δ, 0, S, ∅) 1. pro v²echny stavy i, kde 1 ≤ i ≤ n, vytvo° nový p°echod δ(i − 1, ai , S) = (i, S arity(ai ) ) 2. pro v²echny stavy i, kde 2 ≤ i ≤ n, vytvo° nový p°echod δ(0, ai , S) = (i, S arity(ai ) ) Automat vzniklý pomocí t¥chto krok· pro strom z obrázku 2.1 je na obrázku 3.1. Pro znázorn¥ní zásobníkových operací je pouºita notace z [6], kde nap°íklad zápis a2|S → SS znamená p°echod na symbol a2 a zásobníkovou operaci S → SS .

21

Obrázek 3.1: Nedeterministický zásobníkový automat p°íjímající v²echny podstromy stromu t,

pref(t) = a2 a2 a0 a0 a2 a0 b1 b0

22KAPITOLA 3. ZÁSOBNÍKOVÝ AUTOMAT PIJÍMAJÍCÍ VECHNY PODSTROMY DANÉHO STROMU

23

3.1. KONSTRUKCE NEDETERMINISTICKÉHO ZA PIJÍMAJÍCÍHO VECHNY PODSTROMY

Jak je vid¥t výsledný automat má p°esn¥ stejné stavy a p°echody jako odpovídající suxový a faktorový automat (viz obrázek 2.3). P°echody mají navíc denované zásobníkové operace, které jdou denované pomocí arity vstupního symbolu. Obsah zásobníku tedy koresponduje s arity checksum. Pro praktické pouºití je pot°eba vzniklý nedeterministický automat zdeterminizovat. Kaºdý nedeterministický zásobníkový automat °ízený vstupem lze p°evést na ekvivalentní determinický zásobníkový automat pomocí algoritmu, který je roz²í°ením standardního algoritmu determinizace.[6] V algoritmu se pouºívá mnoºina cpds(q) (Contents of the PushDown Store), která pro kaºdý stav q obsahuje moºné obsahy zásobníku, kdyº se automat nachází práv¥ ve stavu q. [10] Pomocí mnoºiny cpds(q) provádíme kontrolu, zda lze provést daný p°echod, respektive zásobníkovou operaci s ním spojenou. Algoritmus determinizace vstupem °ízeného zásobníkového automatu je op¥t denovaný stejn¥ jako v [10] a [6]. Na vstupu je acyklický nedeterministický ZA M = ({0, 1, 2, ..., n},A, {S}, δ, 0, S, ∅), kde je navíc po°adí stav· takové, ºe kdyº δ(p, a, α) = (q, β) pak p < q . Výstupem algoritmu je samoz°ejm¥ ekvivalentní deterministický ZA M = (Q0 ,A, {S}, δ 0 , 0, S, ∅). Postup je následující: 1. Na po£átku je q0 = [0], Q0 = {q0 } a cpds(q0 ) = {S} a [0] je neozna£ený stav. 2. (a) Vyber neozna£ený stav q' z Q' takový, ºe q' obsahuje nejmen²í moºné stavy q z Q , kde 0 ≤ q ≤ n. (b) Pokud je v cpds(q') n¥jaké S r , kde r ≥ 1 (tj. nap°íklad S, SS, ale ne ε), tak pro kaºdý vstupní symbol a ∈ A prove¤: i. P°idej p°echod δ 0 (p0 , a, α) = (q 00 , β), kde q 00 = {q : δ(p, a, α) = (q, β) pro v²echny p ∈ q 0 }. (Jinými slovy, vytvo°íme nový stav podle p°echod·, které jsou denovány ze stav·, které jsou v d-subsetu q'. Takto denovaná mnoºina se práv¥ nazývá d-subset stavu). ii. Pokud Q' je²t¥ neobsahuje q , pak p°idáme q do Q' a vytvo°íme cpds(q 00 ) = ∅. iii. Do cpds(q) p°idej v²echny ω takové, ºe δ(q 0 , aγ) ` (q 00 , ε, ω), kde γ ∈ cpds(q 0 ) (Tedy p°idáme moºné obsahy zásobníku, které mohou nastat po p°echodu mezi stavy, kdyº víme, jaký je vstupní symbol a jaké jsou moºné stavy na zásobníku ve stavu, ze kterého vycházíme.) (c) Ozna£ q' jako ozna£ený. 3. Opakuj krok 2 dokud v²echny stavy v

Q'

nejsou ozna£ené.

Kdyº si odmyslíme formát pravidel, je postup determinizace v podstat¥ stejný jako u kone£ných automat·, aº na kontrolu v kroku (b) a úpravy mnoºiny cpds, hlavn¥ v kroku iii. Podívejme se op¥t na p°íklad stromu t, pref(t) = a2 a2 a0 a0 a2 a0 b1 b0, z obrázku 2.1. Nedeterministická verze je na obrázku 3.1 a ekvivalentní deterministická je na obrázku 3.2. P°i konstrukci vzniknou následující mnoºiny cpds :

cpds([0]) = {S} cpds([1, 2, 5]) = {SS} cpds([2]) = {SSS} cpds([3]) = {S, SS}

cpds([3, 4, 6]) = {ε} cpds([3, 6]) = {S} cpds([4]) = {ε, S} cpds([5]) = {SS}

cpds([6]) = {S} cpds([7]) = {S} cpds([8]) = {ε}

Obrázek 3.2: Deterministický zásobníkový automat ekvivalentní NZA z obrázku 3.1


3.2.

ONLINE KONSTRUKCE DZA PIJÍMAJÍCÍHO VECHNY PODSTROMY

25

Jak je vid¥t z p°íkladu, tak ze stavu [3,4,6] nevedou na rozdíl od suxového automatu ºádné p°echody práv¥ kv·li kontrole obsahu zásobníku pomocí mnoºiny cpds(q). To znamená, ºe deterministický zásobníkový automat má mén¥ p°echod· neº kone£ný suxový automat zkonstruovaný pro stejný °et¥zec. Také si m·ºeme v²imnout, ºe cesta do tohoto stavu odpovídá podstromu a0 (p°ijímáme prázdným zásobníkem). Vezm¥me si nap°íklad vzorek p, pref(p) = a2 a0 a0, coº je levý podstrom stromu z obrázku 2.1. Automat provede následující p°echody:

([0], a2a0a0, S) ` ([1, 2, 5], a0a0, SS) ` ([3], a0, S) ` ([4], ε, ε) ` p°ijato

3.2 Online konstrukce DZA p°ijímajícího v²echny podstromy V této sekci popí²eme, jak zkonstruovat deterministický ZA p°ijímající v²echny podstromy bez pouºití mezikroku vytvo°ení nedeterministického automatu. Algoritmus 3.1 je pseudokód navrºeného algoritmu, který je popsán dále v této kapitole. Kdyº se podíváme na suxový automat p°ijímající °et¥zec a automat p°ijímající prexový zápis stromu, zjistíme, ºe se jedná v podstat¥ o totoºné automaty. Rozdíl je, jak uº bylo n¥kolikrát zmín¥no, v tom, ºe automat pro stromy je navíc obohacen o zásobníkové operace a ve výsledném deterministickém automatu mohou chyb¥t n¥které p°echody kv·li roz²í°enému algoritmu determinizace. Díky tomu m·ºeme vyuºít pro online konstrukci zásobníkového automatu p°ijímajícího pref(t) algoritmus známý ze stringologické oblasti, popsaný v kapitole 2.4, pouze je pot°eba zajistit navíc správu mnoºin cpds a p°íslu²né kontroly p°i vytvá°ení p°echod·. Algoritmus je tedy pot°eba upravit na n¥kolika místech. Prvním krokem by nejspí²e m¥l být p°echod od kone£ného automatu k zásobníkovému. To obná²í zaprvé formální zm¥ny - automat je denovaný jako sedmice místo p¥tice. Nicmén¥ p·vodní automat roz²í°íme snadno. Abeceda zásobníku obsahuje jediný symbol {S} a po£áte£ním obsahem zásobníku je op¥t symbol S. Dále musíme denovat zásobníkové operace pro jednotlivé p°echody. Na²t¥stí ty jsou denovány pomocí arity vstupního symbolu (viz kapitola 2.5). Formát pravidel zásobníkových operací tedy bude: S → S arity(ai ) , kde ai je vstupní symbol. Dal²ím rozdíl je, ºe prexový zápis podstromu £í stromu p°ijímáme prázdným zásobníkem namísto kone£ným stavem. Mnoºina kone£ných stav· ve výsledném automatu je prázdná - M = (Q,A, {S}, δ, 0, S, ∅). Nakonec prakticky nejvýrazn¥j²ím rozdílem je to, ºe podobn¥ jako p°i determinizaci ZA musíme navíc kontrolovat, zda je moºno provést p°echod vzhledem k zásobníkové operaci - tedy zda zásobník v danou chvíli obsahuje alespo¬ jeden symbol S. Za tímto ú£elem denujeme stejn¥ jako v algoritmu pro determinizaci pro kaºdý stav mnoºinu cpds. Jak uº bylo zmín¥no, tato mnoºina vyjad°uje moºné obsahy zásobníku v daném stavu, takºe tuto mnoºinu musíme b¥hem online konstrukce postupn¥ po£ítat pro kaºdý stav a aktualizovat ji pokaºdé, kdyº vytvá°íme nový p°echod. Na²t¥stí je to vºdy moºné provést a je moºné ukázat, ºe ani potencionáln¥ nebezpe£né situace, jako rozd¥lení stavu, nám nezp·sobí velké potíºe. Moºné situace a samotný algoritmus jsou popsány v následující kapitole.

26KAPITOLA 3.

ZÁSOBNÍKOVÝ AUTOMAT PIJÍMAJÍCÍ VECHNY PODSTROMY DANÉHO STROMU

Online konstrukce DZA p°ijímajícího v²echny podstromy Vstup: Strom t nad abecedou A zapsaný v prexové notaci pref (t) = a1 a2 ...an , n ≥ 1 Výstup: Deterministický zásobníkový automat M = (Q,A, {S}, δ, 0, S, ∅) 1: last = 0 {inicializace automatu } 2: Q.add(last) 3: cpds(last) = {S} 4: suf [last] = nil 5: for i = 1 to n do 6: newlast = novyStav() {nový stav } 7: Q.add(newlast) 8: create solid δ(last, ai , S) = (newlast, S arity(ai ) ) 9: cpds(newlast) = {β : δ(last, ai , α) ` (newlast, β), α ∈ cpds(last)} 10: w = suf [last] 11: while w 6= nil and 6 ∃δ(w, ai , S) do 12: if cpds(w) 6= {ε} then 13: create non-solid δ(w, ai , S) = (newlast, S arity(ai ) ) {p°idat p°echody } 14: cpds(newlast) = {β : δ(w, ai , α) ` (newlast, β), α ∈ cpds(w)} Algoritmus 3.1

15: end if 16: w = suf [w] 17: end while 18: v = δ(w, ai , S) 19: if w = nil then 20: suf [newlast] = 0; 21: else if δ(w, ai , S) = (v, S arity(ai ) ) is solid then 22: suf [newlast] = v {dal²í výskyt °et¥zce } 23: else 24: newnode = novyStav() {rozd¥lení stavu } 25: Q.add(newnode) 26: update δ(w, ai , S) = (newnode, S arity(ai ) ) solid 27: cpds(newnode) = {β : δ(w, ai , α) ` (newnode, β), α ∈ cpds(w)} 28: suf [newlast] = newnode 29: suf [newnode] = suf [v] 30: suf [v] = newnode 31: w = suf [w] 32: while w 6= nil and δ(w, ai , S) = (v, S arity(ai ) ) is non-solid do 33: update δ(w, ai , S) = (newnode, S arity(ai ) ) {p°esm¥rovat p°echody } 34: cpds(newnode) = {β : δ(w, ai , α) ` (newnode, β), α ∈ cpds(w)} 35: w = suf [w] 36: end while 37: cpds(v) = ∅ {aktualizace cpds(v) } arity(a) 38: for each p, a, kde δ(p, a, S) = (v, S ) do 39: cpds(v) = {β : δ(p, a, α) ` (v, β), α ∈ cpds(p)} 40: end for 41: if cpds(newnode) 6= {ε} then 42: for each a in A do 43: create non-solid δ(newnode, a, S) = δ(v, a, S) {kopie odchozích } 44: end for 45: end if 46: end if 47: last = newlast 48: end for

3.2.


3.2.1

27

Popis algoritmu

Popi²me si nyní algoritmus 3.1, který je upravený pseudokód navrºeného algoritmu. Nejprve op¥t na °ádcích 14 je inicializace automatu, tj. vytvo°ení po£áte£ního stavu a inicializace jeho sux linku. Zde p°ibyla nová °ádka 3, která inicializuje také cpds po£áte£ního stavu. Z popisu determinizace v p°edchozí kapitole víme, ºe cpds([0]) = {S}. Potom uº se op¥t zano°íme do for-cyklu, který postupn¥ £te symboly ze vstupu a upravuje automat. Stejn¥ jako v algoritmu 2.1 nejprve vytvo°íme nový stav newlast a spojíme ho s páte°í automatu. Kdyº vytvá°íme nový p°echod, musíme nyní denovat i zásobníkovou operaci. Na²t¥stí jí m·ºeme odvodit od arity aktuálního vstupního symbolu, takºe je to jednoduché. Tím, ºe jsme vytvo°ili p°echod do newlast, se zm¥ní jeho cpds a musíme ho aktualizovat. To se d¥je na novém °ádku 9. Princip aktualizace je stejný, jako jsme ho popsali p°i determinizaci NZA. Tedy zkoumáme, jak se zm¥ní obsah zásobníku po p°e£tení aktuálního vstupního symbolu, kdyº víme, jaké jsou moºné obsahy stavu, ze kterého p°echod vychází - last. Potom uº následuje cyklus, který se pohybuje po pracovní cest¥ a vytvá°í nové p°echody. Zde musíme provést kontrolu, zda cpds stavu, ze kterého p°echod vedeme (w ), obsahuje n¥jaké S r , r ≥ 1, jinými slovy, ºe zásobník není prázdný. To provede podmínka na °ádku 12. V p°ípad¥, ºe m·ºeme vytvo°it nový p°echod, tak ho p°idáme a op¥t upravíme cpds(newlast), protoºe práv¥ do n¥j v²echny nové p°echody vedou. Tentokrát v²ak upravujeme podle cpds(w). Kdyº podmínka není spln¥ná, tj. nevytvo°íme p°echod, neznamená to, ºe n¥kde dále na pracovní cest¥ uº ºádný p°echod nevytvo°íme (spí²e naopak), takºe cyklus nezastavujeme a pokra£ujeme dal²í iterací. Dal²í kroky jsou stejné jako v p°edchozím algoritmu aº do £ásti, kde rozd¥lujeme n¥jaký stav (od °ádky 24). Podívejme se na tuto situaci trochu podrobn¥ji. Potom co vytvo°íme nový uzel, tak p°esm¥rujeme p·vodní p°echod (z uzlu w ) do nového uzlu. V tomto kroku nemusíme kontrolovat cpds(w), protoºe uº víme, ºe kdyº tento p°echod existuje, tak cpds(w) neobsahuje pouze ε. Stejné od·vodn¥ní platí i pro cyklus, ve kterém p°esm¥rováváme dal²í p°echody (na °ádcích 32-36). V t¥chto p°ípadech tedy nekontrolujeme cpds stavu, ze kterého vycházíme, ale stále musíme aktualizovat cpds cílového stavu (v tomto p°ípad¥ vºdy newnode ) - to zachycují °ádky 27 a 34. Po p°esm¥rování p°echod· je n¥kolik °ádek, které prozatím p°esko£íme a pak uº je cyklus, který kopíruje odchozí p°echody (°ádky 41-45). Neº vstoupíme do tohoto cyklu musíme op¥t zkontrolovat, jestli to má v·bec smysl, tedy ºe z newnode m·ºeme v·bec n¥jaké p°echody vést. Díky tomu, ºe jsme nejprve p°esm¥rovali p°íchozí p°echody, známe uº kompletní cpds nového stavu a tak ho m·ºeme zkontrolovat klasickým testem. V tuto chvíli nastává zdánliv¥ trochu problematická situace. P°edstavme si cpds jako moºné obsahy zásobníku po vykonání v²ech moºných cest z po£áte£ního stavu. Mnoºina cpds tedy závisí na tom, jaké cesty vedou do daného stavu a nyní jsme p°esm¥rováním p°echod· n¥kolik cest zru²ili a jiné zase vytvo°ili. Situace v²ak není tak komplikovaná, jak se na první pohled zdá. Podívejme se nap°íklad na obrázek 3.3, který zobrazuje a) situaci p°ed rozd¥lením a b) situaci po n¥m. Klí£ové je pozorování, ºe p°esm¥rováváme p°echody, které jsou v²echny na jeden stejný vstupní symbol a fakt, ºe odchozí p°echody kopírujeme. Tím pádem z·stanou zachovány v²echny cesty do stav· a díky zkopírovaným p°echod·m se znovu napojí na zbytek p·vodní cesty. Konkrétn¥ na obrázku 3.3 vidíme nap°íklad libovolné stavy A, B. P°ed rozd¥lením

28KAPITOLA 3.


Obrázek 3.3: a) Situace p°ed rozd¥lením stavu v, b) situace po rozd¥lení stavu stavu vedou do A cesty ab a xb a po rozd¥lení také ab a xb, i kdyº nyní cesta ab vede p°es nový stav (ozna£ený n - newnode ). To ale ni£emu nevadí, protoºe nám jde jen o výsledek cesty tj. obsah zásobníku. Obdobn¥ je tomu i u B. P°ed rozd¥lením existují cesty ay, abz, xy, xbz a stejn¥ tak existují i po rozd¥lení. Celkov¥ to znamená, ºe cpds stav· A, B se nezm¥nilo, takºe jsou stejné i cpds ostatních stav·, které jsme z nich vypo£ítali. To, ºe cesty z·stanou zachovány, je svým zp·sobem logické, protoºe se p°ece nem·ºou n¥které uº zaindexované faktory ztratit. M·ºe se stát, ºe nem·ºeme kv·li obsahu zásobníku newnode (na obrázku n ) zkopírovat odchozí p°echody. To také nevadí, protoºe to znamená, ºe p°ísp¥vek cest (vzniklých p°esm¥rováním p°echod·) do p·vodního cpds byl roven ε, takºe jsme z nich p°i rozhodování o dal²í cest¥ nevycházeli. Tj. pokud dal²í p°echody existují, museli jsme je ud¥lat na základ¥ p°ísp¥vk· z cest, které se nezm¥nily. Tím pádem op¥t z·stávají zachovány uº vytvo°ené p°echody a platí vypo£ítané cpds. V budoucnu se ani nem·ºe stát, ºe by do stavu n, vedl v budoucnu dal²í p°echod. Tato situace by znamenala, ºe se na pozicích ve vstupním °et¥zci (stromu) vyskytují dva r·zné symboly na stejných pozicích a to nelze. D·sledek je mimo jiné to, ºe se jedná o homogenní automat. Souhrnn¥ tedy víme, ºe jsme nezm¥nili cpds následujících stav· po v a newnode, logicky ani p°echázejících stav·, cpds(newnode) jsme postupn¥ vypo£ítali, ale zru²ili jsme n¥kolik cest do uzlu v. Nap°íklad na obrázku 3.3 uº do v nevede cesta a (p°esm¥rovaný p°echod do n ). Tím pádem musíme opravit cpds(v) k £emuº slouºí °ádky 37-40, které jsme v p°edchozím popisu p°esko£ili. Princip pouºitý v pseudokódu je ten, ºe celé cpds vypo£ítáme znovu pomocí p°echod· do v, které z·staly zachovány. Mohli bychom v²ak uvaºovat také tak, ºe se jedná o rozdíl starého cpds(v) a cpds(newnode). Vzhledem k tomu, ºe do cpds obvykle neukládáme duplicitní hodnoty (nap°íklad více ε) nebo si dokonce sta£í pamatovat nejvy²²í hodnotu, tak

3.2.


29

by mohlo p°i interpretaci dojít k nedorozum¥ní a proto je zvolen tento p°ístup. Kdyº se je²t¥ vrátíme k p°edchozím situacím v algoritmu, tak také zjistíme, ºe nijak nep°edvídateln¥ nem¥níme cpds stav·. V cyklu, ve kterém vytvá°íme p°echody, je cílovým stavem vºdy newlast, tedy ten poslední stav na páte°i, takºe z n¥j po£ítáme cpds aº v dal²í iteraci hlavního cyklu, ve které uº jsou v²echny cesty do tohoto stavu známé. Jinde v algoritmu se p°echody nep°idávájí, takºe m·ºeme °íct, ºe mnoºinu cpds je vºdy moºno vypo£ítat a jedná se vºdy (krom¥ opravy cpds(v) ) o operace, které nám zaberou (ideáln¥) konstantní £as, takºe tím ani nijak nezvý²íme asymptotickou sloºitost algoritmu. Samoz°ejm¥ hodn¥ záleºí na tom, jak mnoºinu cpds naimplementujeme. Nap°íklad kdyº si budeme uchovávat jen nejvy²²í moºný po£et symbol· na zásobníku, vypo£ítáme cpds snadno porovnáním a uloºením v¥t²í hodnoty, ale bude sloºit¥j²í aktualizovat cpds rozd¥leného stavu. Naopak kdyº si budeme pamatovat cpds pro v²echny cesty do stavu, bude leh£í odvodit cpds rozd¥leného stavu, ale jeho aktualizace bude trvat déle. Dal²í v¥cí, která by nás m¥la zajímat je, jak to, ºe nevytvo°íme n¥které p°echody, ovlivní p·vodní algoritmus. M·ºe se samoz°ejm¥ stát, ºe díky této omezující podmínce se nevytvo°í i n¥kolik dal²ích stav·, p°ípadn¥ celá £ást automatu. To v²ak v·bec nevadí, protoºe p°esn¥ stejn¥ by dopadl i b¥h algoritmu s mezikrokem determinizace nedeterministického ZA. Jak jsme si ukázali, tak nikdy nevytvo°íme p°echod, který by zp¥tn¥ vytvo°il novou cestu, tedy zm¥nil cpds stav· a tím pádem by se vytvo°ily dodate£n¥ p°echody, které uº jsme p°edtím "zamítli". Zbývá je²t¥ prozkoumat, jak stejná situace ovlivní sux linky. P°íklad moºné situace je na obrázku 3.4. V £ásti a) je, jak by automat vypadal, kdybychom nekontrolovali cpds stavu. V £ásti b) je stejný automat, který vytvo°íme na²ím algoritmem, tedy i s kontrolou cpds. Vidíme, ºe ve druhém p°ípad¥ v·bec nevznikl stav [6]. Samoz°ejm¥ je to kv·li tomu, ºe z [4] nem·ºeme provést dal²í p°echod, jelikoº obsah zásobníku bude vºdy roven ε. V tomto p°ípad¥ vypadá poslední iterace hlavního cyklu následovn¥. Pracovní cesta se skládá z uzl· [3], [4], [0]. V prvním kroku cyklu na °ádcích 11-17 bude w = [4]. Zjistíme, ºe p°echod na a0 neexistuje, coº je rozdíl oproti situaci a). Pokusíme se p°echod vytvo°it a zjistíme, ºe to nelze a pokra£ujeme dal²ím krokem. Pak se w = [0] a p°echod na a0 uº existuje. Ukon£íme tedy cyklus a dostaneme se do °ádku 22. Protoºe v = [4] nastavíme sux link [5] rovno [4]. Kdyby p°echod ze [4] existoval, rozd¥lili bychom stav v = [3], ale sux link nového stavu by vedl také do [4]. Z tohoto p°íkladu je patrné, ºe tím, ºe "vynecháme"kv·li cpds n¥které stavy, vlastn¥ jen vznikne mezi sux linky zkratka. M·ºeme si ov¥°it, ºe d-subset stavu [4] je stejný v obou p°ípadech. Odpovídá to také tomu, ºe a0 a0 a0 a a0 a0 jsou sice suxy prexového zápisu, ale nereprezentují podstrom. R·zné úplné podstromy jsou zde jen dva: a0 a celý strom a3 a0 a0 a0. Nakonec bych je²t¥ zmínil jednu otázkou, která je sice triviální, ale je docela zásadní. Otázkou je, zda se n¥kdy m·ºe p°eru²it páte° automatu. Pokud máme na vstupu skute£n¥ prexový zápis stromu, tak se to samoz°ejm¥ stát nem·ºe. Na za£átku je cpds([0]) = {S} a potom pokaºdé, kdyº se zano°íme do podstromu, bu¤ po£et symbol· S z·stane (arita 1) nebo se zv¥t²í. Ze zásobníku za£nou S ubývat, aº kdyº narazíme na list, tím jakoby uzavíráme podstrom. Jestliºe je na vstupu validní zápis stromu, tak poslední podstrom uzav°eme p°i p°e£tení posledního symbolu a to je jediná situace, kdy stav na páte°i má cpds = {ε} tj. prázdný zásobník. Odpovídá to faktu, ºe jsme p°e£etli celý strom a p°ijímáme ho prázdným zásobníkem, viz také denice arity checksum (kapitola 2.5).

30KAPITOLA 3.


Obrázek 3.4: a) Automat pokud bychom nekontrolovali cpds, b) automat s kontrolou cpds. Sux linky jsou znázorn¥ny te£kovan¥ Tím jsme popsali algoritmus pro online konstrukci ZA p°ijímajícího v²echny podstromy. P°ipome¬me, ºe hlavními rozdíly oproti stringologické verzi je výpo£et mnoºiny cpds a její kontrola p°i vytvá°ení p°echod·. P°i provedených úpravách jsme nijak nezm¥nili asymptotickou sloºitost algoritmu O(n). 3.2.2

P°íklad online konstrukce

Nyní je £as uvést p°íklad postupné konstrukce automatu pro strom = a2 a2 a0 a0 a2 a0 b1 b0. První £ty°i kroky jsou na obrázku 3.5. Krok 0. nil.

- Inicializace algoritmu - vytvo°íme po£áte£ní stav [0],

t

z obrázku 2.1,

cpds(0)

pref(t)

= {S}, suf[0] =

Krok 1. - Vstupní symbol a2. Nejprve vytvo°íme nový stav newlast = [1] a spojíme ho se stavem [0] p°echodem na aktuální vstupní symbol a2. M·ºeme také spo£ítat cpds(newlast ). Známe cpds(0) = {S} a arita vstupního symbolu je 2, takºe zásobníková operace S → SS nám v podstat¥ °íká, ºe p°idáme na zásobník jeden symbol. Tedy cpds(1) = {SS}. Na °ádku 10 nastavíme w = suf [last] = suf [0] = nil. Následující cyklus tedy neprob¥hne ani jednou a dostáváme se rovnou na °ádek 20, kde nastavíme suf [1] = [0], coº je logické, protoºe se symbolem a2 jsme se setkali poprvé, takºe je²t¥ nemá zaindexovaný ºádný sux. Krok 2. - Vstupní symbol a2. Op¥t nejprve vytvo°íme nový stav newlast = [2] a p°idáme ho do mnoºiny stav· Q. Mnoºinu cpds(2) ur£íme stejn¥ jako v p°edchozím p°ípad¥, na zásobníku op¥t p°ibude jeden symbol, takºe cpds(2) = {SSS}. Poté za£neme procházet pracovní cestu. Nejprve w = [0], protoºe suf[1] = [0]. Ze stavu [0] uº jsme v minulém kroku na a2 p°echod vytvo°ili, takºe cyklus ani tentokrát neprob¥hne. Tentokrát se v²ak w 6= nil,

3.2.


31

takºe existuje v = [1], protoºe δ([0], a2, S) = ([1], SS). Zatím v²echny p°echody, které jsme vytvo°ili, byly ozna£eny jako solid, takºe i tento p°echod je tak ozna£en. Tím pádem je spln¥ná podmínka na °ádku 21 a nastavíme suf[2] = [1]. Op¥t je to v souladu s denicí sux linku, nebo´ hodnota uzlu [1] a2 je suxem hodnoty uzlu [2] a2 a2. Kdybychom si nyní ur£ili d-subset stavu [1], obsahoval by £ísla 1 a 2, která také odpovídají výskytu °et¥zce a2 - na pozicích 1 a 2.

Obrázek 3.5: Kroky 0 aº 3 algoritmu 3.1 Krok 3. - Vstupní symbol a0. Nový stav je newlast = [3]. Tentokrát je arita vstupního symbolu rovna 0, takºe pravidlo S → ε ve své podstat¥ °íká, ºe máme ze zásobníku vybrat jeden symbol. Na °ádku 9 tedy vezmeme cpds(2) = {SSS} a ubereme jeden symbol. Vznikne cpds(3) = {SS}. Poté za£neme procházet pracovní cestu, která je v tomto p°ípad¥ nejdel²í moºná, tj. [2], [1], [0]. Protoºe symbol a0 £teme poprvé, tak neexistuje ºádný p°echod na tento symbol a vºdy tedy vytvo°íme p°echod z aktuálního stavu na pracovní cest¥. Rozdíl bude vºdy v tom, co p°idáme do cpds(3), protoºe stavy na pracovní cest¥ mají cpds r·zné. Nicmén¥ ºádné cpds se nerovná ε, takºe p°echod m·ºeme vºdy p°idat. Výsledné cpds(3) bude {ε, S, SS}. V²imn¥me si, ºe cpds obsahuje ε, takºe m·ºe nastat p°ípad, ºe v tomto stavu p°ijmeme n¥jaký podstrom, konkrétn¥ nyní ten nejjednodu²²í a0. Jak uº bylo °e£eno, symbol a0 byl

32KAPITOLA 3.


na vstupu poprvé, tím pádem jist¥ nenajdeme ºádný krat²í sux a sux link newlast povede do stavu [0]. P°esn¥ to ud¥lá i algoritmus, protoºe cyklus na °ádcích 11-17 ukon£í aº podmínka w = nil tj. dál se spustí °ádek 20. Krok 4. - Vstupní symbol a0. Nejprve p°idáme jiº popsaným zp·sobem nový stav newlast = [4] a ur£íme jeho cpds. Protoºe op¥t ze zásobníku symbol ubíráme a vycházíme z cpds(3), bude výsledek {ε, S}. Pak se op¥t vydáme po pracovní cest¥. Prvním uzlem je w = suf [last] = [0]. P°echod δ([0], a0, S) jiº existuje, takºe cyklus na °ádcích 11-17 neprob¥hne ani jednou. Tento p°echod jsme vytvo°ili v minulém kroku a p°itom jsme si ho ozna£ili jako non-solid (°ádek 13). Nastane tedy nová situace - rozd¥lení stavu. Tuto situaci uº jsme si popsali d°íve, nap°íklad na obrázku 3.3. Stav [3] nyní reprezentuje t°i moºné °et¥zce - a2 a2 a0, a2 a0 a a0. Kdybychom nyní nastavili sux link stavu [4] na [3], pak by to znamenalo, ºe v²echny tyto faktory jsou suxy a2 a2 a0 a0. To v²ak zjevn¥ neplatí. Suxem je jen a0. Rozd¥líme tedy stav [3] tak, aby nový stav reprezentoval jen sux a0 a do nového stavu povedeme sux link stavu [4]. V tuto chvíli se v algoritmu nacházíme na °ádku 24. Vytvo°íme tedy nový stav a ozna£íme ho [5]. Potom p°esm¥rujeme p·vodní p°echod z [0] do [5] (°ádka 26) a upravíme cpds(5). Na dal²ích t°ech °ádcích vy°e²íme sux linky. Na²ím cílem bylo, aby sux link newlast vedl do stavu, které p°edstavuje faktor a0. Takovým stavem je nyní newnode = [5]. P°esn¥ podle toho nastavíme sux link na °ádku 28. Jelikoº sux link pro v²echny °et¥zce, které odpovídají stavu [3], m¥l stejnou hodnotu, tak hodnotu sux linku zkopírujeme do sux linku stavu newnode. Jinak °e£eno nastavíme suf[newnode] na sou£asnou hodnotu suf[3], tedy [0] (°ádek 29). A nakonec, protoºe vznikl stav, který reprezentuje sux hodnoty stavu [3], tak také aktualizujeme suf[3] = [5] (°ádek 30). Tím máme vy°e²ené sux linky a m·ºeme p°ejít k p°esm¥rování dal²ích p°echod· cyklem na °ádcích 32-36. Je²t¥ p°edtím v²ak do w dosadíme sux [0], tj. hodnotu nil, takºe cyklus neprob¥hne ani jednou. Jak uº jsme se na za£átku zmínili, suxu a2 a2 a0 a0 odpovídal jen jeden sux, který reprezentoval stav v, takºe není pot°eba m¥nit více p°echod·. Pak je na °ad¥ upravení cpds(v). V cyklu na °ádcích 38-40 se projdou v²echny p°echody, které vedou do v a podle nic se znovu ur£í celé cpds(v), konkrétn¥ v tomto p°ípad¥ z·staly p°echody ze stavu [1] a [2], takºe nám vyjde cpds(3) = {S, SS}. Vidíme, ºe z cpds zmizelo ε, které je nyní cpds(5). To znamená, ºe sjednocení t¥chto cpds dá op¥t p·vodní cpds a také to, ºe ve stavu [3] nyní nekon£í ºádný podstrom. Nyní uº tedy známe cpds v²ech stav·, hlavn¥ stavu [5], takºe p°istoupíme k poslednímu kroku operace rozd¥lení stavu. Tím je zkopírování odchozích p°echod·. V tomto p°ípad¥ v²ak cpds(5) = {ε}, takºe ºádné p°echody uº p°idat nem·ºeme a cyklus kv·li podmínce na °ádku 41 neprob¥hne. Zase to odpovídá tomu, ºe a0 je úplný podstrom, takºe ho prázdným zásobníkem p°ijmeme. Nakonec si m·ºeme ov¥°it, ºe cpds stavu [4] z·stalo stejné, jak jsme ho vypo£ítali je²t¥ p°ed rozd¥lením stavu. Cestou p°es [0], [1], [2], [3], [4] dostáváme obsah zásobníku S 1+1+1−1−1 = S , a cestou p°es [0], [1], [3], [4] vyjde S 1+1+−1−1 = ε, celkov¥ tady cpds([4]) = {ε, S} jak nám vy²lo na za£átku. Tento krok a následující krok 5 jsou na obrázku 3.6.

- Vstupní symbol a2. Analogicky s p°edchozími kroky p°idáme nový stav newlast = [6] do Q, spojíme ho s páte°í p°echodem a vypo£ítáme jeho cpds podle stavu [4], tj. vyjde {SS}. Potom budeme op¥t procházet pracovní cestu, která se v tomto kroku rovná {[5],[0]}. Nejprve w = [5] a zano°íme se do cyklu na °ádcích 11-17. P°echod z [5] na a2 sice je²t¥ neexistuje, ale kv·li podmínce na °ádce 12 nem·ºeme p°echod vytvo°it, protoºe cpds(5) = {ε}. Pokra£ujeme tedy dál a w = [0]. P°echod z w na a2 uº existuje takºe cyklus zastavíme. Krok 5.

3.2.


33

Tento p°echod je ozna£en jako solid, takºe se spustí °ádek 22, který nastaví suf [6] = [1], protoºe v = δ([0], a2, S) = [1]. M·ºeme zkontrolovat, ºe je to správn¥. Nejdel²í zaindexovaný sux a2 a2 a0 a0 a2 je skute£n¥ a2, £emuº odpovídá stav [1], viz op¥t obrázek 3.6.

Obrázek 3.6: Kroky 4 a 5 algoritmu 3.1 Krok 6. - Vstupní symbol a0. Toto je op¥t zajímavý krok, protoºe dojde k dal²ímu rozd¥lení stavu. Nicmén¥ na za£átku op¥t vytvo°íme nový stav newlast = [7] a ur£íme jeho cpds podle stavu last = [6], tedy z mnoºiny {SS}. Protoºe arita vstupního symbolu je nula, tak op¥t jeden symbol ze zásobníku ubereme, £ímº vznikne cpds(7) = {S}. Poté op¥t postupujeme po pracovní cest¥ - [6], [1], [0]. V prvním kroku (na °ádku 10) nastavíme w = [1]. Vidíme, ºe p°echod δ([1], a0, S) = ([3], ε) uº existuje, takºe cyklus na °ádcích 11-17 neprob¥hne ani jednou. Protoºe w není nil, ani není p°echod ozna£en jako solid (viz krok 3), tak se dostaneme do situace rozd¥lení stavu (od °ádku 24). M·ºeme op¥t zkontrolovat situaci z pohledu sux·. Stav [3] nyní reprezentuje faktory a2 a2 a0 a a2 a0, nicmén¥ suxem a2 a2 a0 a0 a2 a0 je jen a2 a0. Vytvo°íme tedy op¥t nový stav, p°edstavující a2 a0 a sux link newlast povede do n¥j. Stejn¥ jako v kroku 4 se d¥lí stav [3], to je v²ak náhoda, obecn¥ se samoz°ejm¥ ned¥lí vºdy jen jeden stav, ale jak vidíme, m·ºe se stát, ºe se jeden rozd¥lí vícekrát. Algoritmus postupuje následovn¥. Na °ádce 24 vytvo°í nový stav - jeho ozna£ení bude [8]. P°esm¥ruje p°echod z [1] na a0 do nového stavu [8] - °ádek 26. P°itom na °ádku 27 zárove¬ ur£í cpds(8) z cpds(1), vyjde cpds(8) = {S}, protoºe cpds(1) = {SS} a jeden symbol odebíráme. Dál nastavíme správn¥ sux linky - na °ádku 28. Poºadovaný suf [7] = [8], tj. stavu [8] odpovídá jiº zmín¥ný sux a2 a0. Dál suf [8] = suf [3] = [5] (suxem stavu [8] respektive a2 a0 je faktor a0, reprezentovaný stavem [5]) a nakonec nový suf[3] = [8] (a2

34KAPITOLA 3.


je del²ím suxem a2 a2 a0, neº p·vodní a0 ). To byly °ádky 28-30. Nyní na °ádku 31 nastavíme w = suf [1] = [0]. Z w sice p°echod na a0 vychází, ale je ozna£en jako solid a navíc cílovým stavem není v = [3], takºe podmínka cyklu na °ádku 32 spln¥ná není. Stejn¥ jako p°edtím to odpovídá tomu, ºe ºádný dal²í p°echod p°esm¥rovat nechceme - nový stav má p°edstavovat jen jeden °et¥zec. Potom op¥t opravíme cpds(3). Uº zbyl jen jediný p°echod, které vede do [3], takºe cpds spo£ítáme jednodu²e podle n¥j cpds(3) = {SS} (°ádky 37-40). Nyní na rozdíl od prvního rozd¥lení je cpds nového stavu rovno {S}, to znamená, ºe je spln¥ná podmínka na °ádku 41 a zkopírujeme tedy odchozí p°echody [3], tak aby byly stejné jako odchozí [8]. Protoºe p°echody mohou být na r·zné symboly, postupujeme cyklem p°es celou abecedu. Zkopíruje se jen p°echod na a0 do stavu [4]. Nakonec m·ºeme je²t¥ zkontrolovat cpds stav· [4] a dal²ích, ale op¥t zjistíme, ºe z·staly stejné, tak jak jsme je vypo£ítali je²t¥ p°ed rozd¥lením stavu [3]. Nap°íklad do stavu [4] nyní vedou dv¥ cesty - cestou po páte°i je výsledek na zásobníku {S} a krat²í cesta p°idá ε. Automat vzniklý v tomto kroku je na obrázku 3.8. Krok 7. - Vstupní symbol b1. Situace v tomto kroku je jednodu²²í neº v tom p°edcházejícím. Protoºe se jedná o symbol, který se na vstupu je²t¥ neobjevil, povede nový sux link do po£áte£ního stavu (°ádka 20). Nebudeme tedy rozd¥lovat ºádný stav, ale musíme projít celou pracovní cestu a z kaºdého stavu vytvo°it p°echod na b1 do nového stavu newlast = [9]. Pracovní cesta se skládá ze stav· - [7], [8], [5] a [0]. Sou£asn¥ s tím budeme aktualizovat cpds stavu [9]. Protoºe arita vstupního symbolu je jedna, coº odpovídá zásobníkové operaci S → S , tak se po£et S na zásobníku nezm¥ní, tedy výsledné cpds je sjednocením jednotlivých cpds. V cyklu na °ádcích 11-17 nesmíme navíc zapomenout na kontrolu cpds stavu, ze které bude nový p°echod vycházet. P°echody nakonec vytvo°íme ze v²ech stav· na pracovní cest¥, krom¥ stavu [5]. Jinak je p°ísp¥vek v²ech cest roven S, takºe výsledné cpds(7) = {S}. Výsledný automat je na obrázku 3.9. Krok 8. - Vstupní symbol b0. Zde je situace stejná jako v minulém kroku, jelikoº je to první výskyt symbolu, tak budeme op¥t jen p°idávat p°echody do nového stavu newlast = [10]. Navíc se jedná o poslední symbol, tak by nám m¥lo vyjít cpds tohoto stavu rovno ε, coº odpovídá p°ijetí kompletního stromu. Pracovní cesta obsahuje jen stavy [9] a [0]. Shodn¥ cpds obou dvou je rovno S. Arita vstupního symbolu zp·sobí, ºe odebereme i poslední symbol S ze zásobníku, takºe skute£n¥ vyjde cpds(8) = {ε}. Výsledný automat je zobrazen na obrázku 3.10 a m·ºeme si v²imnout, ºe nám vy²el stejný automat, jaký vznikl i pomocí determinizace p·vodního nedeterministického automatu, viz obrázek 3.2. Zobrazení stav·, které toto odhalí je [3,6] = [8], [3,4,6] = [5], [1,2,5] = [1], [5] = [6], [6] = [7], [7] = [9], [8] = [10]. Gracké zobrazení výsledných sux link· je na obrázku 3.7. Pr·b¥h výpo£tu je pro p°ehlednost shrnut je²t¥ v tabulce 3.1. a0

Obrázek 3.8: Krok 6 algoritmu 3.1

Obrázek 3.7: Výsledné sux linky vytvo°ené algoritmem 3.1

3.2. ONLINE KONSTRUKCE DZA PIJÍMAJÍCÍHO VECHNY PODSTROMY

35



36KAPITOLA 3.



3.2.

37

ai a2 a2

a0

a0

a2

a0

b1

b0

i 1 2

3

4

5

6

7

8

[10]

[9]

[7]

[6]

[4]

[3]

newlast [1] [2]

[9], [0]

[7], [8], [5], [0]

[6], [1], [0]

[4], [5], [0]

[3], [0]

[2], [1], [0]

Pracovní cesta [0] [1], [0]

= = = =

= = = = [8] [5] [8] [0]

[5] [0] [5] [1]

suf[10] = [0]

suf[7] suf[8] suf[3] suf[9]

suf[4] suf[5] suf[3] suf[6]

suf[3] = [0]

Sux linky suf[1] = [0] suf[2] = [1]

Tabulka 3.1: Pr·b¥h výpo£tu algoritmu 3.1

p°idat p°echod δ([7], b1, S) = ([9], S) p°idat p°echod δ([8], b1, S) = ([9], S) nelze p°idat δ([5], b1, S) p°idat p°echod δ([0], b1, S) = ([9], S) p°idat p°echod δ([9], b0, S) = ([10], ε) p°idat p°echod δ([0], b0, S) = ([10], ε)

p°idat p°echod δ([6], a0, S) = ([7], ε) rozd¥lit stav [3], nový stav [8]

p°idat p°echod δ([4], a2, S) = ([6], SS) nelze p°idat δ([5], a2, S)

p°idat p°echod δ([2], a0, S) = ([3], ε) p°idat p°echod δ([1], a0, S) = ([3], ε) p°idat p°echod δ([0], a0, S) = ([3], ε) p°idat p°echod δ([3], a0, S) = ([4], ε) rozd¥lit stav [3], nový stav [5]

Operace p°idat p°echod δ([0], a2, S) = ([1], SS) p°idat p°echod δ([0], a2, S) = ([1], SS)

= = = =

= = = =

{S} {S} {SS} {S}

{ε, S} {S, SS} {ε} {SS}

cpds([10]) = {ε}

cpds([7]) cpds([8]) cpds([3]) cpds([9])

cpds([4]) cpds([3]) cpds([5]) cpds([6])

cpds([3]) = {ε, S, SS}

Cpds cpds(1) = {SS} cpds([2]) = {SSS}


Kapitola 4

Zásobníkový automat p°ijímající stromové vzorky obsaºené v daném strom¥ V této kapitole popí²eme zásobníkový automat p°ijímající v²echny stromové vzorky daného stromu v prexové notaci. V anglické literatu°e se automat ozna£uje jako tree pattern pushdown automaton ([6], [10]). Tento automat je roz²í°ením ZA p°ijímajícího v²echny podstromy o p°echody na speciální symbol S, který p°edstavuje úplný podstrom. Kv·li tomu vzniknou jednak nové p°echody, ale mohou vzniknout i nové stavy.

4.1 Konstrukce NZA p°ijímajícího stromové vzorky Algoritmus konstrukce nedeterministické verze automatu je denován stejn¥ jako v [6], s tím, ºe n¥kolik krok· je spojeno do jednoho algoritmu. Na vstupu máme stejn¥ jako v p°edchozím p°ípad¥ strom t nad ohodnocenou abecedou A a jeho prexový zápis pref (t) = a1 a2 ...an , n ≥ 1. Výstupem je nedeterministický automat M = ({0, 1, 2, ..., n},A∪{S}, {S}, δ, 0, S, ∅) p°ijímající v²echny stromové vzorky a postup je následující: 1. pro v²echny stavy i, kde 1 ≤ i ≤ n, vytvo° nový p°echod δ(i − 1, ai , S) = (i, S arity(ai ) ) 2. vytvo° mnoºinu srms = {i : 1 ≤ i ≤ n, δ(i−1, a, S) = (i, ε), a ∈A0 }. Jinými slovy, je to mnoºina stav·, do kterých vede p°echod na nulární symbol, takºe se jedná o stavy, které reprezentují listy stromu. Zkratka srms znamená Subtree RightMost State (nejprav¥j²í stavy v podstromu). 3. pro v²echny stavy i, kde i = n − 1, n − 2...1, δ(i, a, S) = (i + 1, S p ) a a ∈ A, vytvo° nový p°echod δ(i, S, S) = (l, ε), kde l je ur£eno následovn¥: Pokud p = 0, pak l = i + 1. Jinak, pokud je p ≥ 1, je l rovno p -tému nejmen²ímu £íslu, takovému, ºe l ∈ smrs a l > i. Odstra¬ ze srms v²echny j takové, ºe j ∈ smrs a i < j < l. 4. pro v²echny stavy i, kde 2 ≤ i ≤ n, vytvo° nový p°echod δ(0, ai , S) = (i, S arity(ai ) ) 39

40KAPITOLA 4.

ZÁSOBNÍKOVÝ AUTOMAT PIJÍMAJÍCÍ STROMOVÉ VZORKY OBSAENÉ V DANÉM S

M·ºeme si v²imnout, ºe kroky 1 a 4 jsou stejné jako u automatu p°ijímajícím podstromy. P°echody na symbol S vytvo°íme pomocí krok· 2 a 3. Automatu vzniklému v krocích 1 aº 3 se °íká treetop. Automat treetop pro strom t s ko°enem r p°ijímá v²echny stromové vzorky v jejich prexové notaci, které mají ko°en v r. Na tomto míst¥ je d·leºité si uv¥domit, co nám vlastn¥ algoritmus °íká, v kontextu toho £eho chceme docílit. Na²ím cílem je, aby p°e£tení symbolu S bylo ekvivalentní s p°e£tením n¥jakého úplného podstromu, viz denice symbolu S. V automatu tedy chceme jakoby p°esko£it na stav, který reprezentuje konec tohoto podstromu, abychom mohli pokra£ovat £tením dal²ích symbol·. Stav, ve kterém kon£í podstrom, je vºdy logicky list, odtud dostáváme denici mnoºiny srms. Zbývá uº jen ur£it, do kterého listu máme "sko£it", tj. kam má vést p°echod na S. Je to logicky vºdy ten uzel, který p°edstavuje konec podstromu, který má ko°en v uzlu, ze kterého vycházíme. Jinak °e£eno, hledáme nejprav¥j²í uzel v levém podstromu daného uzlu. V levém podstromu, protoºe vstup £teme zleva a nejprav¥j²í uzel, protoºe máme prexový zápis. Podívejme se nap°íklad na obrázek 4.1, který zobrazuje strom z obrázku 2.1, a kde jsou te£kovan¥ nazna£eny p°echody na S. Nap°íklad pro uzel a21 je levý podstrom a22 a03 a04 a nejprav¥j²í uzel je a04 , p°esko£íme tedy na tento uzel. Podobná situace je i mezi listy. Nap°íklad uzel a04 - za ním se nachází podstrom a25 a06 b17 b08 , takºe p°echod na S povede aº do posledního uzlu b08 . Podobn¥ m·ºeme uvaºovat i pro ostatní uzly.

Obrázek 4.1: Strom z obrázku 2.1 dopln¥ný o p°edstavu p°echod· na symbol

S

Kdybychom zakreslili p°echody na S z tohoto obrázku k odpovídajícím stav·m nedeterministického automatu p°ijímajícího podstromy na obrázku 3.1, získali bychom p°esn¥ automat vzniklý algoritmem, který jsme popsali na za£átku této kapitoly. P°esn¥ to ukazuje obrázek 4.2. Pro úplnost mnoºina srms = {3, 4, 6, 8}. Nakonec, kdyº uº máme sestrojenou nedeterministickou verzi automatu, nezbývá neº stejným postupem jako v p°edchozí kapitole automat determinizovat. Automat je op¥t °ízený vstupem, takºe je to moºné [6]. Výsledný automat je zobrazen na obrázku 4.3. Jak je vid¥t, oproti ZA, který p°ijímá podstromy, je automat p°ijímající stromové vzorky o poznání sloºit¥j²í. P°ibyl úpln¥ nový stav [4,8] a p°echody na vstupní symbol S. Díky p°echodu δ([1, 2, 5], S, S) se navíc zm¥nilo cpds stavu [3,4,6] tak, ºe je moºné z n¥j ud¥lat dal²í p°echody, které jsme v p°edchozím p°ípad¥ provést nemohli.

Obrázek 4.2: Nedeterministický zásobníkový automat p°ijímající v²echny stromové vzorky stromu z obr. 2.1

4.1. KONSTRUKCE NZA PIJÍMAJÍCÍHO STROMOVÉ VZORKY

41

Obrázek 4.3: Deterministický zásobníkový automat p°ijímající v²echny stromové vzorky stromu z obr. 2.1

42KAPITOLA 4. ZÁSOBNÍKOVÝ AUTOMAT PIJÍMAJÍCÍ STROMOVÉ VZORKY OBSAENÉ V DANÉM S

4.2.

ONLINE KONSTRUKCE TREETOP AUTOMATU

43

4.2 Online konstrukce treetop automatu Jelikoº není z deterministické verze automatu p°ijímajícího stromové vzorky na první pohled patrné, jak se k n¥mu dopracovat postupnou online konstrukcí a nem·ºeme se nyní op°ít o stringologickou verzi algoritmu, tak se pokusme nejprve navrhnout algoritmus pro online konstrukci treetop automatu. Treetop automat tvo°í £ást nedeterministické verze automatu, p°esn¥ji jeho páte° a p°echody na symbol S. Vý²e, na obrázku 4.1, jsme si popsali, co vlastn¥ p°echody na S znamenají, zbývá tedy jen otázka, jak tento fakt promítnout do vlastního algoritmu. Uº bylo °e£eno, ºe p°echodem na S, chceme "p°esko£it"na nejprav¥j²í uzel v levém podstromu. Kdybychom vytvá°eli strom postupn¥ tak, jak na£ítáme jeho prexový zápis, tak nejprav¥j²í uzel je vºdy ten poslední vytvo°ený. Pro konkrétní uzel, jehoº podstrom hledáme, to platí ale jen do chvíle, neº p°e£teme celý jeho podstrom. Jinak °e£eno, p°echod na S posouváme (prodluºujeme) vºdy z daného uzlu do posledního vytvo°eného aº do okamºiku, kdy tento stav p°edstavuje skute£ný konec podstromu v kompletním stromu. Dostali jsme se tedy k otázce, jak poznat, ºe se jedná o skute£ný konec aktuálního podstromu. Pro kontrolu, ºe jsme p°e£etli strom, mám obecn¥ slouºí arity checksum (viz kapitola 2.5). Protoºe podstrom je samoz°ejm¥ také strom, m·ºeme arity checksum pouºít i pro kontrolu, ºe jsem p°e£etli kompletní podstrom. Protoºe arity checksum budeme pot°ebovat po£ítat pr·b¥ºn¥ s kaºdým na£teným symbolem, upravíme p·vodní vzorec do vhodn¥j²í podoby. Pro °et¥zec w = a1 a2 ..am , m ≥ 1 má vzorec podobu: ac(w) = arity(a1 ) + arity(a2 ) + ... + arity(am ) − m + 1, coº m·ºeme p°epsat na ac(w) = arity(a1 ) + (arity(a2 ) − 1) + (arity(a3 ) − 1)... + (arity(am ) − 1). Jednotlivé £leny (arity(ai ) − 1) vlastn¥ odpovídají zásobníkovým operacím, které postupn¥ d¥láme, tj. jeden symbol vºdy odebereme a p°idáme po£et odpovídající arit¥ vstupního symbolu. U prvního £lenu neode£ítáme jedni£ku, protoºe p°edpokládáme, ºe na za£átku máme na zásobníku jeden symbol S, vzorec by tedy byl (1 + arity(a1 ) − 1) = arity(a1 ). Jeden kompletní strom (podstrom) p°e£teme, kdyº se arity checksum rovná nule. Hledaná podmínka pro ukon£ení "prodluºování"p°echodu na S tedy bude spo£ívat v kontrole arity checksum mezi dv¥mi danými stavy. Pro zajímavost si m·ºeme je²t¥ v²imnout jiné moºnosti, jak poznat, ºe p°echod na S je kompletní. Ze vzorce arity checksum vyplývá, ºe jeden podstrom dokon£íme práv¥ tehdy, kdyº ze zásobníku odebereme jeden symbol S. Je to ve shod¥ s tím, co vlastn¥ symbol S p°edstavuje - práv¥ jeden úplný strom (podstrom). Zajímavé je to z toho pohledu, ºe pokud v treetop automatu existuje p°echod na S mezi dv¥ma stavy, pak díky p°echodu na S odebereme ze zásobníku jeden symbol (S má aritu nula) a stejn¥ tak odebereme také práv¥ jeden symbol, pokud p·jdeme cestou mezi t¥mito stavy po páte°i. To mimo jiné znamená, ºe p°echody na S v treetop automatu nijak neovlivníme cpds stav·. Z praktického hlediska v²ak není toto pozorování aº tolik d·leºité, protoºe jednak treetop automat sám o sob¥ nepouºíváme a také pro online algoritmus se hodí spí²e jiná reprezentace této vlastnosti arity checksum, protoºe se dá jednodu²e po£ítat pr·b¥ºn¥. Není v²ak vylou£eno, ºe se to m·ºe hodit p°i návrhu jiného algoritmu. Nyní uº se podívejme na pseudokód algoritmu 4.1 pro online konstrukci treetop automatu, který implementuje práv¥ popsaný princip postupného prodluºování p°echod· na S.

44KAPITOLA 4.


V algoritmu si denujeme pole AC(i, j), kde i, j jsou stavy automatu a hodnotou je aktuální arity checksum mezi t¥mito dv¥ma stavy. Algoritmus si stru£n¥ popi²me. Vstup tradi£n¥ procházíme for-cyklem od 1 do n, kde n je délka °et¥zce (°ádek 1). Na °ádku 2 p°idáme nový p°echod na aktuální vstupní symbol. Tím tvo°íme páte° automatu. Na dal²ím °ádku (3) inicializujeme novou hodnotu v poli AC. Podle vzorce je první £len roven arit¥ vstupního symbolu. Na °ádku 4 vytvo°íme nový p°echod na S. Víme, ºe z p°edposledního stavu na páte°i musí nutn¥ vést do posledního. Poté projdeme ostatní stavy a aktualizujeme jejich p°echody na S. Ze stavu [0] ºádný p°echod na S nikdy nevede a z kaºdého dal²ího stavu vede práv¥ jeden. P°itom ze stavu [i-1] uº jsme p°echod vytvo°ili na °ádku 4, takºe cyklus b¥ºí od stavu [1] do stavu [i-2]. Nejprve ur£íme, do jakého stavu vede p°echod na S nyní - °ádek 6 a ten uloºíme do prom¥nné j. Pak provedeme porovnání aktuální hodnoty arity checksum s nulou. Jak uº jsme popsali, pokud je arity checksum nula, tak je p°echod hotový a uº ho nem¥níme. V opa£ném p°ípad¥ prodlouºíme p°echod na S do posledního vytvo°eného stavu [i] - °ádek 8 a aktualizujeme hodnotu v poli AC podle vý²e uvedeného vzorce - °ádka 9. Online konstrukce treetop automatu Strom t nad abecedou A zapsaný v prexové notaci pref (t) = a1 a2 ...an , n ≥ 1 Výstup: Treetop automat M = ({0, 1, 2, ..., n},A, {S}, δ, 0, S, ∅) 1: for i = 1 to n do 2: add δ(i − 1, ai , S) = (i, S arity(ai ) ) 3: add AC(i − 1, i) = arity(ai ) 4: add δ(i − 1, S, S) = (i, ε) 5: for k = 1 to i - 2 do 6: j = δ(n, S, S) 7: if AC(k, j) 6= 0 then 8: update δ(k, S, S) = (i, ε) 9: AC(k, i) = AC(k, j) + arity(ai ) − 1

Algoritmus 4.1 Vstup:

10: end if 11: end for 12: end for

Jak uº jsem zmínil, tento algoritmus není sám o sob¥ aº tak d·leºitý, ale demonstruje princip vytvá°ení p°echod· na symbol S, který pouºijeme i v dal²ím algoritmu. I z tohoto d·vodu nemá smysl zde uvád¥t konkrétní p°íklad. Pr·b¥h algoritmu je celkem jednoduchý a bude z°ejmý z p°íkladu u dal²ího algoritmu.

4.3 Online konstrukce DZA p°ijímajícího stromové vzorky Nyní uº se v¥nujme algoritmu, který zkonstruuje online zásobníkový automat p°ijímající v²echny stromové vzorky. Uº na obrázku 4.3 jsme si mohli v²imnout, ºe tento automat má, oproti automatu p°ijímajícímu jen úplné podstromy, daleko více stav· a p°echod·. Nicmén¥ m·ºeme vyjít z algoritmu 3.1 pro online konstrukci ZA p°ijímajícího podstromy, protoºe výsledný automat musí p°ijímat podstromy také. Tento algoritmus upravíme tak, aby zkonstruovaný ZA mohl p°ijímat i stromové vzorky. Jinými slovy to znamená, ºe musíme im-

4.3.

ONLINE KONSTRUKCE DZA PIJÍMAJÍCÍHO STROMOVÉ VZORKY

45

plementovat vytvá°ení p°echod· na symbol S a tím pádem i správu stav·, které díky tomu vzniknou navíc a dal²í p°echody z nich. Postupné vytvá°ení p°echod· na S uº jsme popsali v algoritmu 4.1, kterým lze online vytvo°it treetop automat. M·ºeme si v²imnout, ºe treetop automat je sám o sob¥ vlastn¥ deteministický, protoºe z kaºdého stavu vede práv¥ jeden p°echod na S. Stejným zp·sobem bychom tedy mohli vytvá°et p°echody na S i v celkovém automatu. Tento postup by v²ak fungoval samoz°ejm¥ jen do chvíle, neº bychom narazili na stav, jehoº d-subset obsahuje více neº jedno £íslo (stav v p·vodním nedeterministickém automatu). V tom p°ípad¥ je d-subset stavu, do kterého vede výsledný p°echod na S, roven sjednocení d-subset· jednotlivých stav·, do kterých by vedl p°echod na S v p·vodním nedeterministickém automatu. Výsledný stav tedy zjistíme p°esn¥ tak, jak bychom to ud¥lali p°i standardním procesu determinizace. K tomu ale pot°ebujeme v¥d¥t p·vodní p°echody na S z treetop automatu a také vlastní d-subset stavu, ze kterého vycházíme. Tím se dostávám k prvním zm¥nám, které musíme v algoritmu ud¥lat. Z d°ív¥j²ích kapitol sice víme, ºe d-subset stavu se dá reprezentovat jako mnoºina sux-link·, ale v tomto p°ípad¥ je lep²í mít uloºené rovnou d-subsety. P°i zji²óvání d-subsetu jednoho konkrétního stavu bychom se bez p°ímého uloºení d-subset· je²t¥ obe²li, ale v algoritmu také pot°ebujeme rychle zjistit, jestli stav, do kterého vede vytvá°ený p°echod na S, uº existuje nebo ne. Dva stavy jsou shodné, kdyº mají stejné d-subsety. Porovnání dvou stav· pomocí jejich sux link· by se je²t¥ realizovat dalo, ale hledání stejného stavu v mnoºin¥ stav· uº by bylo docela obtíºné. I kdyº je to také moºné °e²ení, tak bychom si tím algoritmus zbyte£n¥ zkomplikovali a tém¥° nic bychom tím neu²et°ili, spí²e naopak. asová sloºitost by jist¥ nebyla konstantní, jako je tomu, kdyº je stav identikován p°ímo d-subsetem. A protoºe tuto kontrolu provádíme £asto, pravd¥podobn¥ by bylo toto zpomalení znatelné. Z tohoto pohledu se tedy jedná spí²e o optimalizaci, i kdyº samoz°ejm¥ nás to stojí pam¥óvé nároky. Druhou výhradou oproti p°ímému uloºení d-subset· byl £as pot°ebný k jejich pr·b¥ºné údrºb¥. V tomto sm¥ru neztratíme uº v·bec nic, protoºe, jak si ukáºeme pozd¥ji, stejnou cestu musíme projít i kdybychom d-subsety neaktualizovali. Prvním rozdílem oproti algoritmu 3.1 je tedy p°ímé ukládání d-subset·. Druhá mnoºina informací, kterou je pot°eba reprezentovat, jsou p·vodní p°echody na symbol S z treetop automatu. Pomocí nich totiº m·ºeme ur£it cílový stav p°echodu na S nejen v jednoduchých p°ípadech, ale i kdyº d-subset obsahuje více stav·. Na²t¥stí, jak jsme demonstrovali v algoritmu 4.1, treetop automat lze relativn¥ jednodu²e postupn¥ konstruovat a pam¥óvé nároky pro uloºení této informace jsou lineární k délce °et¥zce. Za tímto ú£elem si denujeme pole AC(i), pro i ≥ 1, kde i je stav v treetop automatu a hodnotou bude dvojice hodnot (j, ac), kde j bude cílový uzel p°echodu na S v treetop automatu a ac bude aktuální arity checksum mezi t¥mito dv¥ma stavy (viz p°edchozí kapitola). Tímto máme tedy k dispozici v²e, co budeme pot°ebovat p°i vytvo°ení nebo aktualizaci p°echodu na S z n¥jakého stavu. Je²t¥ m·ºeme omezit mnoºinu stav·, jejichº p°echody na S je v daném kroku pot°eba aktualizovat. K tomu slouºí mnoºina UncomplS a postupn¥ si budeme vytvá°et mnoºinu UncomplSnext, coº bude UncomplS v dal²ím kroku. Nyní uº si popi²me vlastní algoritmus. Protoºe je algoritmus trochu rozsáhlej²í, tak je rozd¥len do n¥kolika funkcí, které si popí²eme postupn¥. Hlavní £ást algoritmu je pseudokód 4.2, odkud voláme ostatní funkce. Princip celého algoritmu je následující. Nejprve funkcí UpdateS zpracujeme stavy, ze kterých je pot°eba aktualizovat p°echod na S. B¥hem této

46KAPITOLA 4.


funkce mohou postupn¥ vznikat nové stavy. Ke kaºdému novému stavu vytvo°íme p°echod na S a zapamatujeme si, ºe jsme ho v tomto kroku takto vytvo°ili. Pak spustíme algoritmus, který vytvá°í ZA p°ijímající podstromy. P°itom se m·ºe stát, ºe v £ásti, která rozd¥luje stav, vytvo°íme stejný uzel, jako vznikl uº díky p°echodu na S. V tom p°ípad¥ se tyto stavy slou£í, vytvo°íme p°echody na a ∈ A podle p·vodního algoritmu a zru²íme ozna£ení, ºe tento stav je nov¥ vzniklý stav. Na konci algoritmu nám z·stane mnoºina stav·, které nov¥ vznikly, ale nespojily se s jiným stavem, takºe u t¥chto stav· je²t¥ dodate£n¥ ur£íme p°echody na a ∈ A. Online konstrukce DZA p°ijímajícího stromové vzorky Vstup: Strom t nad abecedou A zapsaný v prexové notaci pref (t) = a1 a2 ...an , n ≥ 1 Výstup: Deterministický zásobníkový automat M = (Q,A, {S}, δ, 0, S, ∅) 1: last = 0 {inicializace automatu } 2: Q.add(last) 3: cpds(last) = {S} 4: suf [last] = nil 5: for i = 1 to n do 6: newlast = novyStav(i) {nový stav } 7: Q.add(newlast) 8: U ncomplSnext.add(newlast) 9: create solid δ(last, ai , S) = (newlast, S arity(ai ) ) 10: cpds(newlast) = {β : δ(last, ai , α) ` (newlast, β), α ∈ cpds(last)} 11: UpdateS() {volání funkce UpdateS } 12: w = suf [last] 13: while w 6= nil and 6 ∃δ(w, ai , S) do 14: if cpds(w) 6= {ε} then 15: create non-solid δ(w, ai , S) = (newlast, S arity(ai ) ) {p°idat p°echody } 16: cpds(newlast) = {β : δ(w, ai , α) ` (newlast, β), α ∈ cpds(w)} Algoritmus 4.2

17: end if 18: w = suf [w] 19: end while 20: v = δ(w, ai , S) 21: if w = nil then 22: suf [newlast] = 0; 23: else if δ(w, ai , S) = (v, S arity(ai ) ) is solid then 24: suf [newlast] = v 25: updateDsubsets(v) 26: else 27: SplitNode(v) 28: end if 29: UpdateA() 30: last = newlast 31: U ncomplS = U ncomplSnext 32: end for

{dal²í

{aktualizovat {volání

výskyt °et¥zce }

v²echny d-subsety }

funkce, která rozd¥lí stav }

{volání

funkce UpdateA}

Kdyº se podíváme na algoritmus 4.2, zjistíme, ºe prvním rozdílem oproti algoritmu 3.1 je °ádek 8. Na tomto °ádku uloºíme do mnoºiny UncomplSnext stav newlast, abychom z n¥j

4.3.

47


v dal²ím kroku vytvo°ili p°echod na S. Druhým rozdílem je volání funkce UpdateS na °ádku 11, která projde mnoºinu UncomplS a aktualizuje p°echody na symbol S stav·m, které jsou v ní. D·vod, pro£ voláme tuto funkci uº zde, je snaha znát v okamºiku, kdy budeme p°ípadn¥ vytvá°et nový stav p°i d¥lení n¥jakého stavu, uº v²echny p°echody do tohoto stavu, abychom mohli ur£it jeho cpds a tím pádem rozhodnout, zda z n¥j vést dal²í p°echody. M·ºeme si totiº v²imnout, ºe stavy a p°echody nep°ibývají v tomto automatu jen kv·li p°echod·m na S, ale i kv·li tomu, ºe tyto p°echody vytvo°í novou cestu mezi p·vodními stavy a zm¥ní tím jejich cpds tak, ºe je moºné z nich ud¥lat p°echod navíc. Proto tedy voláme funkci UpdateS d°íve, neº d¥líme stav. P°inese nám to v²ak jeden problém, ale k tomu se dostaneme pozd¥ji. Nyní uº se podrobn¥ji podívejme na funkci UpdateS, jejíº pseudokód je algoritmus 4.3. První, co musí funkce ud¥lat, je aktualizace tabulky AC, která, jak uº jsme zmínili, reprezentuje p°echody na S v treetop automatu. AC za£ínáme vytvá°et aº od 2. kroku, protoºe ze stavu [0] p°echod na S nevede. Pokud je tedy i > 1, tak vytvo°íme nový záznam AC(i − 1) = (i, arity(ai )), coº odpovídá prvnímu £lenu ze vzorce pro výpo£et arity checksum. V algoritmu 4.3 toto reprezentují °ádky 1 a 2. Poté stejn¥ jako p°i konstrukci treetop automatu aktualizujeme ostatní poloºky tabulka AC. Konkrétn¥ cyklem na °ádku 4 projdeme celé pole AC a kdyº se arity checksum nebude rovnat nule (°ádka 6), tak upravíme záznam tak, ºe cílový stav bude i, coº reprezentuje prodlouºení p°echodu v treetop automatu do posledního stavu a vypo£ítáme arity checksum op¥t podle vzorce, takºe p°i£teme arity(ai ) − 1 (°ádka 7). Procedura UpdateS - aktualizování p°echod· na symbol S Vstup: V²echny prom¥nné z hlavní funkce Výstup: Upravený automat M 1: if i > 1 then 2: AC(i − 1) = (i, arity(ai )) {nová Algoritmus 4.3

3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20:

poloºka AC }

end if

k = 1 ... i - 2 do (j, ac) = AC(k) if ac > 0 then AC(k) = (i, ac + arity(ai ) − 1)

for

{aktualizace

AC

}

end if end for

not UncomplS is empty do q = U ncomplS.Dequeue() if cpds(q) 6= {ε} then p = δ(q, S, S) remove δ(q, S, S) N ewST ransition(q) if incoming(p) = 0 then remove p

while

end if end if end while

{procházení

{vytvo°ení {starý

mnoºinou }

nového p°echodu }

stav je nedostupný }

48KAPITOLA 4.


Dál funkce UpdateS prochází mnoºinu UncomplS, v níº jsou stavy, z kterých máme aktualizovat p°echod na S (°ádka 10). Stejn¥ jako v p·vodním algoritmu, ani tady nesmíme zapomenout na kontrolu cpds stavu, ze kterého má p°echod vést - °ádka 12. Aktuální stav je ozna£ený q (°ádka 11). Poté si zjistíme stav, do kterého nyní p°echod na S vede a ozna£íme ho p. M·ºe se stát, ºe takový stav neexistuje, ale to není pot°eba rozli²ovat. Tento stav totiº pot°ebujeme jen pro kontrolu, ºe kdyº aktualizovaný p°echod na S povede do jiného stavu, tak se stav p nestane nedostupný, viz kontrola na °ádku 16. Tento p°ípad se týká situace, kdy jeden p°echod na S má nejprve cílový stav nap°. [3,4] a pak se postupným prodluºování jednoho p°echodu na S v treetop automatu z n¥j postupn¥ stává [3,5], [3,6] atd. Mohli bychom na tuto situaci nahlíºet tak, ºe stav postupn¥ aktualizujeme, ale místo sloºitého rozhodování je lep²í vºdy vytvo°it nový stav a starý nedostupný stav p°ípadn¥ smazat. Tím jsme narazili na dal²í rozdíl oproti algoritmu 3.1 a to, ºe v n¥kterých krocích se mohou vyskytovat stavy, které potom nejsou ve výsledném automatu. Tento problém jsme vy°e²ili vý²e zmín¥ným zp·sobem a zbývá uº jen vlastní vytvo°ení p°echodu na S, coº má na starost funkce NewSTransition, kterou si te¤ popí²eme. Procedura NewSTransition - vytvo°ení nového p°echodu na symbol S Vstup: Stav q, ze kterého má p°echod vycházet a v²echny prom¥nné z hlavní funkce Výstup: Upravený automat M 1: kam = novyStav() {nový stav s prázdným d-subsetem } 2: sumAC = 0 {vytvo°ení d-subsetu } 3: for each k in dsubset(q) do 4: (j, ac) = AC(k) 5: dsubset(kam).add(j) 6: sumAC = sumAC + ac Algoritmus 4.4

7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17:

end for

add δ(q, S, S) = (kam, ε) sumAC 6= 0 or i in dsubset(q) U ncomplSnext.add(q)

if

{p°idat

p°echod }

then

{rozhodnout

zda je p°echod hotový }

end if

cpds(kam) = {β : δ(q, S, α) ` (kam, β), α ∈ cpds(q)} if not kam in Q then U ncomplS.add(kam) Q.add(kam) N oveStavy.add(kam)

{vznikl

nový stav }

end if

Pseudokód funkce NewSTransition() je algoritmus 4.4. Vstupem funkce je stav q, ze kterého má nový p°echod na S vést, hlavn¥ pak jeho d-subset. Nejprve si na °ádku 1 vytvo°íme nový stav "kam", který bude mít prozatím prázdný d-subset. Poté budeme postupn¥ procházet d-subset stavu q a v tabulce AC hledat odpovídající cílové stavy, které p°idáme do d-subsetu stavu kam, a takto vytvo°íme cílový stav (°ádky 3-7). Nyní nastává zajímavý okamºik, protoºe se musíme rozhodnout, zda je tento stav uº nální nebo ne. Uº d°íve jsme se zmínili, ºe jednotlivé p°echody na S jsou hotové, kdyº je arity checksum mezi po£áte£ním a cílovým stavem roven nule. Pokud budou uº dokon£ené v²echny jednotlivé p°echody v treetop automatu, tak víme, ºe v dal²ím kroku uº nebudeme aktualizovat odpovídající poloºky v poli

4.3.


49

AC a stav, který jsme pomocí nich vytvo°ili, je tak hotový. Toto m·ºeme implementovat nap°íklad tak, ºe budeme po£ítat sou£et jednotlivých arity checksum a pokud na konci vyjde nula, tak to zna£í, ºe i v²echny £áste£né byly nula (záporný být nem·ºe). V algoritmu si sou£et ukládáme do prom¥nné sumAC na °ádku 6. Za pov²imnutí stojí, co nám tato úvaha °íká z pohledu stromu. Máme-li uzel s d-subsetem [i,j] jemuº ve stromu odpovídají uzly i a j, tak p°echodem na S se dostaneme do stavu [m,n], kde m a n odpovídají konci obou dvou podstrom·, které mají ko°en v i a j. M·ºe se stát, ºe m a n jsou stejné, tj. ºe oba podstromy kon£í ve stejném uzlu, pak cílový stav odpovídá jen tomuto jednomu uzlu (d-subset je uspo°ádaná mnoºina bez opakování). Tím máme hotovou první £ást podmínky na °ádku 9. Druhou £ástí je kontrola, ºe d-subset stavu ze kterého vycházíme neobsahuje i. V takovém p°ípad¥ by se mohlo stát, ºe je sou£et arity checksum roven nula, ale stále není p°echod na S kompletní, protoºe zatím nevíme, kam vede p°echod ze stavu i (v treetop automatu). P°ípad, ºe by d-subset stavu obsahoval i, sice nem·ºe nastat, kdyº voláme funkci NewSTransition() z funkce UpdateS, protoºe v tu chvíli je²t¥ ºádný stav nemá v d-subsetu i, ale m·ºe se to stát dále v algoritmu, kde tuto funkci také voláme. Tím jsme vysv¥tlili celou podmínku na °ádku 9 a podle ní tedy bu¤ uloºíme nov¥ vzniklý stav do mnoºiny UncomplSnext nebo ne - °ádek 10. Zbývá nám je²t¥ vytvo°it nový p°echod na S - °ádka 8, ur£it známým zp·sobem cpds cílového stavu - °ádka 12 a také zkontrolovat, jestli stav kam není novým stavem - °ádka 13. Kdybychom vytvo°ili nový stav, p°idáme ho do n¥kolika mnoºin. Nejprve ho p°idáme do mnoºiny UncomplS, abychom je²t¥ v tomto kroku z n¥j vytvo°ili jeho p°echod na S (práv¥ popisovaným zp·sobem). Dále nový stav logicky p°idáme i do mnoºiny v²ech stav· Q a nakonec do mnoºiny NoveStavy, ve které si pamatujeme nové stavy, které vznikly v tomto kroku, protoºe je budeme muset zpracovat dále. Tím máme funkce NewSTransition a UpdateS popsané a m·ºeme se vrátit k hlavnímu algoritmu 4.2. V algoritmu 4.2 jsme byli na °ádku 11. Dál pokra£ujeme stejn¥ jako p°i konstrukci automatu, který p°ijímá podstromy, aº do °ádky 25, kde ur£ujeme sux link newlast. Jak uº jsem popsal d°íve, tak takto zm¥níme vlastn¥ d-subsety v²ech dal²ích stav· na pracovní cest¥. Protoºe si nyní udrºujeme d-subsety explicitn¥, tak zavoláme funkci, která projde zbytek pracovní cesty a aktualizuje d-subsety stav· na ní. Tato funkce d¥lá je²t¥ n¥co navíc, ale k tomu se dostaneme pozd¥ji. Zatím si p°edstavme, ºe jen aktualizuje d-subsety. Dále v algoritmu následuje £ást, která d¥lí stav (°ádka 27). V tomto p°ípad¥ jsme tuto £ást p°epsali do samostatné funkce, jejíº pseudokód je algoritmus 4.5. Algoritmus 4.5 je samoz°ejm¥ velmi podobný tomu p·vodnímu, ale je v n¥m také n¥kolik zm¥n. Na za£átku (°ádek 1) vytvo°íme nový stav tak, ºe vezmeme d-subset stavu v a p°idáme k n¥mu aktuální i. Principem to stále odpovídá sux link·m, viz kapitola 2.4. Nyní musíme na rozdíl od p·vodního algoritmu, kde jsme v¥d¥li, ºe vytvá°íme nový stav, zjistit, jestli uº tento stav neexistuje, tedy jestli ho nevytvo°ila funkce UpdateS. Tím, ºe máme stav identikovaný p°ímo d-subsetem, tak je to jednoduché. Na °ádku 2 tedy provedeme kontrolu a p°ípadn¥ nový stav uloºíme do mnoºiny v²ech stav· Q. Poté pokra£ujeme v podstat¥ stejn¥ jako v p·vodním algoritmu. Op¥t voláme funkci pro aktualizaci d-subsetu stav· na zbytku pracovní cesty - °ádek 11. M·ºeme za£ít aº od suf [newnode], protoºe newnode uº i obsahuje. Dále pokra£ujeme podle p·vodního algoritmu aº do °ádku 26. Na tomto °ádku jsme v situaci, ºe vytvá°íme p°echody z nového stavu. Krom¥ kopie p·vodních odchozích p°echod· musíme nyní vytvo°it i p°echod na S. Nejprve v²ak zkontrolujeme, ºe se newnode nenachází v mnoºin¥

50KAPITOLA 4.


NoveStavy,

coº by znamenalo, ºe tento stav vznikl uº b¥hem funkce UpdateS a p°echod na S uº jsme tím pádem z tohoto stavu vytvo°ili. V p°ípad¥, ºe p°echod na S je²t¥ neexistuje, tak ho vytvo°íme zavoláním jiº popsané funkce NewSTransition. Nemusíme se bát, ºe bychom nevytvo°ili n¥jaké dal²í stavy, protoºe funkce NewSTransition p°idá p°ípadné nov¥ vzniklé stavy do mnoºiny NoveStavy, kterou je²t¥ zpracujeme na konci algoritmu funkcí UpdateA. Na konci funkce SplitNode (°ádek 30) m·ºeme stav newnode odstranit z mnoºiny NoveStavy, protoºe v²echny jeho odchozí p°echody jsme jiº vytvo°ili v této funkci a nemusíme se jimi tedy zabývat dál. Procedura SplitNode - rozd¥lení stavu Vstup: Stav v, který se má rozd¥lit a v²echny prom¥nné z hlavní funkce Výstup: Upravený automat M 1: newnode = novyStav(v, i) 2: if not newnode in Q then 3: Q.add(newnode) {kontrola jestli Algoritmus 4.5

4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30:

{nový

stav }

uº neexistuje }

end if

U ncomplSnext.add(newnode) update δ(w, ai , S) = (newnode, S arity(ai ) ) solid cpds(newnode) = {β : δ(w, ai , α) ` (newnode, β), α ∈ cpds(w)} suf [newlast] = newnode suf [newnode] = suf [v] suf [v] = newnode updateDsubsets(suf [newnode]) {aktualizovat d-subsety } w = suf [w] while w 6= nil and δ(w, ai , S) = (v, S arity(ai ) ) is non-solid do update δ(w, ai , S) = (newnode, S arity(ai ) ) {p°esm¥rovat p°echody } cpds(newnode) = {β : δ(w, ai , α) ` (newnode, β), α ∈ cpds(w)} w = suf [w] end while

cpds(v) = ∅ for each p, a, kde δ(p, a, S) = (v, S arity(a) ) do cpds(v) = {β : δ(p, a, α) ` (v, β), α ∈ cpds(p)}

{aktualizace

cpds(v) }

end for if

cpds(newnode) 6= {ε} then a in A do create non-solid δ(newnode, a, S) = δ(v, a, S)

for each

{kopie

odchozích }

end for if

not newnode in NoveStavy then N ewST ransition(newnode)

{vytvo°it

p°echod na S }

end if end if

N oveStavy.remove(newnode)

Nyní uº je £as si popsat funkci updateDsubsets. Její pseudokód je v algoritmu 4.6. Jak uº jsme zmínili d°íve, tato funkce musí krom¥ aktualizace d-subset· d¥lat je²t¥ n¥co navíc.

4.3.

51


P°edev²ím kdyº do d-subsetu p°idáme novou poloºku, konkrétn¥ £íslo i, tak musíme v dal²ím kroku aktualizovat p°echod na S. V tomto kroku se je²t¥ p°echod na S nezm¥ní, protoºe ze stavu [i] nevede v treetop automatu ºádný p°echod, ale v dal²ím kroku uº tomu tak bude. Tyto první dv¥ funkce za°ídíme v algoritmu snadno. Na °ádku 2 je p°idání £ísla do d-subsetu a na °ádku 22 je p°idání stavu do mnoºiny UncomplSnext (pro aktualizaci p°echodu na S v dal²ím kroku). Procedura updateDsubsets - aktualizuje d-subsety stav· na pracovní cest¥ Stav p od kterého za£ít a v²echny prom¥nné z hlavní funkce Výstup: Upravený automat M 1: clone = p 2: dsubset(p).add(i) {p°ejmenování stavu } 3: if ∃q : δ(q, S, S) = (p, ε) then 4: Q.add(clone) {opravit p°echod na S } 5: update δ(q, S, S) = (clone, ε) {v podstat¥ rozd¥lení stavu } 6: cpds(clone) = {β : δ(q, S, α) ` (clone, β), α ∈ cpds(q)} 7: if cpds(clone) 6= {ε} then 8: for each a in A ∪{S} do 9: create δ(clone, a, S) = δ(p, a, S) {kopie odchozích p°echod· }

Algoritmus 4.6 Vstup:

10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26:

end for end if

cpds(p) = ∅ for each r, a, kde δ(r, a, S) = (p, S arity(a) ) do cpds(p) = {β : δ(r, a, α) ` (p, β), α ∈ cpds(r)}

{aktualizace

cpds(p) }

end for if

cpds(p) = {ε} then a in A ∪{S} remove δ(p, a, S)

for each

do

{odebrání

odchozích p°echod· }

end for end if end if

U ncomplSnext.add(p) p = suf [p] if p 6= [0] then updateDsubsets(p)

{rekurzivní

volání }

end if

P°i aktualizaci d-subsetu v²ak m·ºe dojít k jednomu problému. Protoºe p°echody na S vytvá°íme je²t¥ p°edtím, neº aktualizujeme d-subsety, m·ºe se stát, ºe nap°íklad p°echod na S vede do stavu [3,5], ale my nyní zm¥níme d-subset tohoto stavu na nap°íklad [3,5,7] a v tu chvíli by byl p°echod na S ²patn¥. Nezbývá tedy neº kontrolovat, ºe do stavu, jehoº d-subset m¥níme, nevede ºádný p°echod na S a v p°ípad¥, ºe ano, tak provést operaci podobnou rozd¥lení stavu. K tomu slouºí ostatní °ádky funkce z algoritmu 4.6. Nejprve si na °ádku 1 zapamatujeme p·vodní stav (ozna£íme ho clone ), protoºe jeho d-subset je pro p°echod na S vytvo°ený správn¥. Potom na °ádku 3 p°ichází kontrola, jestli do stavu vede p°echod na S. V p°ípad¥ ºe ano, provedeme jiº zmín¥né rozd¥lení stavu. Stav clone

52KAPITOLA 4.


p°idáme do mnoºiny Q a p·vodní p°echod na S povedeme do tohoto stavu (°ádky 4 a 5). Poté m·ºeme známým zp·sobem ur£it cpds a tím pádem i rozhodnout zda ze stavu povedou n¥jaké p°echody (°ádky 6 a 7). Pokud lze p°echody provést, tak zkopírujeme p·vodní p°echody ze stavu na v²echny symboly z abecedy i S, protoºe ty jsou ur£ené správn¥ (°ádky 8-10). Dál stejn¥ jako p°i rozd¥lení stavu opravíme cpds druhého stavu, viz °ádky 12-15. Nyní se m·ºe stát, ºe cpds tohoto stavu bude rovno ε a v tom p°ípad¥ musíme odstranit p°echody z tohoto stavu - °ádky 16-20. Tím je operace hotová. Je²t¥ bych zmínil, pro£ tuto kontrolu nemusíme provád¥t i v procedu°e SplitNode, respektive pro£ ji provádíme aº od dal²ího stavu na pracovní cest¥. Na za£átku funkce SplitNode uº totiº máme d-subset nového stavu pln¥ ur£ený a porovnáváme tak uº reálný stav se stavy, které vznikly díky p°echod·m na S. To znamená, ºe kdyº se stavy spojí, tak uº je to správn¥. Nakonec funkce updateDsubsets pokra£uje svým vlastním rekurzivním voláním na dal²í uzel na pracovní cest¥, dokud nedojdeme na její konec tj. do stavu [0]. Nakonec se dostáváme k poslední funkci UpdateA, jejíº pseudokód je algoritmus 4.7. Tuto funkci voláme v hlavním algoritmu na °ádku 29 a jejím úkolem je zpracovat nové stavy, které vznikly kv·li p°echod·m na S a b¥hem b¥hu algoritmu se nespojily s jiným stavem, takºe nemají ur£ené p°echody na a ∈ A. Procedura UpdateA - vytvo°ení dodate£ných p°echod· na symboly z A V²echny prom¥nné z hlavní funkce Výstup: Upravený automat M 1: while not NoveStavy is empty do 2: q = U ncomplS.Dequeue() {procházení mnoºinou } 3: if cpds(q) 6= {ε} then 4: for each a in A do 5: kam = novyStav() 6: for each k in dsubset(q) do 7: if k < i then 8: if ak+1 = a then 9: dsubset(kam).add(k + 1) {ur£ení d-subsetu nového stavu } Algoritmus 4.7 Vstup:

10: end if 11: end if 12: end for 13: if not dsubset(kam) is empty then 14: if not kam in Q then 15: Q.add(kam) {kdyby vznikl nový stav } 16: N ewST ransition(kam) 17: N oveStavy.add(kam) 18: end if 19: add δ(q, a, S) = (kam, S arity(ai ) {vytvo°ený p°echod } 20: cpds(kam) = {β : δ(q, a, α) ` (kam, β), α ∈ cpds(q)} 21: end if 22: end for 23: end if 24: end while

4.3.


53

Celá funkce UpdateA se skládá z cyklu, který prochází mnoºinu NoveStavy. Práv¥ v této mnoºin¥ máme stavy, kterým jsme ur£ili jen p°echod na S, ale uº ne p°echody na ostatní symboly z A. Aktuální stav si ozna£íme op¥t q (°ádka 2) a neº se pustíme do vytvá°ení p°echodu, tak tradi£n¥ zkontrolujeme cpds tohoto stavu (°ádka 3). Protoºe nevíme, pro jaké symboly budou p°echody denované, tak spustíme cyklus pro v²echny symboly z abecedy (°ádka 4). Pak postupujeme podobn¥ jako p°i tvorb¥ p°echodu na S. Procházíme d-subset stavu q a p°itom tvo°íme d-subset cílového stavu "kam ". Tentokrát si pom·ºeme následujícím trikem. Pokud máme stav [k], tak víme, ºe v nedeterministickém automatu za ním následuje vºdy stav [k+1] a do d-subsetu cílového stavu ho p°idáme práv¥ tehdy, kdyº (k+1)-tý symbol na vstupu je roven symbolu, pro který p°echod práv¥ vytvá°íme. Op¥t je to princip shodný s postupem p°i determinizaci automatu. Nap°íklad máme °et¥zec ab, takºe páte° automatu vypadá tak, ºe ze stavu [1] existuje p°echod do [2] na b. Takºe pokud vytvá°íme nap°íklad p°echod na b pro stav, kde je v d-subsetu k = 1, podíváme se, jestli existuje p°echod z [1] na b, jinými slovy, jestli je (k+1)-tý symbol b. To platí, takºe pokud víme, ºe p°echod existuje, tak musí vést do [2] a do výsledného d-subsetu tedy p°idáme [2]. Pokud se k = i, kde i je £íslo kroku, tak rovnou víme, ºe z posledního stavu ºádný p°echod nevede - proto podmínka na °ádku 7. ádek 8 je implementací popsaného principu. A dostáváme se na °ádek 13, kde kontrolujeme, ºe jsme v·bec n¥jaký stav do d-subsetu p°idali, je totiº jist¥ moºné, ºe pro n¥který vstupní symbol není p°echod denovaný. Pokud jsme skute£n¥ získali n¥jaký cílový stav, m·ºeme pro jistotu zkontrolovat, jestli se nejedná o nový stav. V tom p°ípad¥ by bylo pot°eba vytvo°it mu p°echod na S a v dal²ím pr·chodu ho op¥t stejným zp·sobem zpracovat - viz °ádky 14-18. Nakonec jiº jednodu²e p°idáme nový p°echod a upravíme cpds cílového stavu. V hlavním funkci algoritmu 4.2 jsme se dostali uº na °ádky 30 a 31, coº je konec jedné iterace, takºe nezbývá jen klasicky nastavit last = newlast a také mnoºinu UncomplSnext p°ekopírovat do UncomplS, abychom podle ní mohli op¥t upravit p°echody ve funkci UpdateS v dal²ím kroku. Nakonec bychom se m¥li je²t¥ zmínit o sloºitosti prezentovaného algoritmu. Je jisté, ºe není ur£it¥ lineární jako tomu bylo v p°ípad¥ algoritm· 2.1 a 3.1. Uº jsme zmínili, ºe v nejhor²ím p°ípad¥ je pot°eba aktualizovat jednak v²echny p°echody na S a nebo také v²echny d-subsety. Cestu, kterou provádíme aktualizace d-subset· v²ak musíme projít, i kdybychom d-subsety neaktualizovali, jak jsme popsali u funkce updateDsubsets a p°echody na S také aktualizovat jednodu²e musíme. Celková sloºitost algoritmu bude nejspí² úm¥rná po£tu stav· a p°echod· v deterministickém automatu p°ijímajícím stromové vzorky. Tato závislost v²ak není zatím obecn¥ známá, takºe je nejspí² zbyte£né se tím zde zabývat. M·ºeme jenom poznamenat, ºe pam¥óvé nároky jsou nelineární kv·li ukládání d-subset·, ale na druhou stranu nám to usnad¬uje zji²óvání jestli stejný stav uº existuje. Dobrá zpráva je, ºe uloºení informací pro tvorbu p°echodu na S - pole AC, je lineární k délce °et¥zce. D-subsety cílových stav· pro p°echody, které vytvá°íme ve funkcích UpdateS a UpdateA jsme schopni zjistit v £ase rovném délce d-subsetu. Z tohoto pohledu se zdá, ºe navrºený algoritmus pracuje celkem úsporn¥, ale nelze vylou£it, ºe existuje n¥jaké jiné lep²í °e²ení.

54KAPITOLA 4.

4.3.1


P°íklad online konstrukce

V této kapitole si uvedeme pr·b¥h algoritmu 4.2 na p°íkladu, který jsme pouºili i u algoritmu 3.1 pro strom t z obrázku 2.1, jehoº prexový zápis je pref(t) = a2 a2 a0 a0 a2 a0 b1 b0. Protoºe jsme jiº stejný p°íklad jednou d¥lali, budeme se tentokrát soust°edit hlavn¥ na rozdíly oproti prvnímu algoritmu. První t°i kroky jsou na obrázku 4.4 a m·ºeme si v²imnout, ºe první dva kroky (0 a 1) jsou úpln¥ stejné jako v minulém p°ípad¥. - Na inicializaci algoritmu se nic nezm¥nilo, takºe jen vytvo°íme stav [0] a p°íslu²né záznamy o cpds a sux linku. Krok 0.

- Vstupní symbol a2. Nový stav p°idáme do mnoºiny UncomplSnext, abychom z n¥j v p°í²tím kroku vytvo°ili p°echod na S, a pokra£ujeme dál do funkce UpdateS. Protoºe je mnoºina UncomplS na za£átku prázdná, tak nemáme ve funkci UpdateS ºádnou práci. Není pot°eba ani aktualizovat pole AC, protoºe z [0] ºádný p°echod na S nevede, tj. neplatí podmínka ve funkci UpdateS na °ádku 1 ani 4. Dále se v algoritmu jen vytvo°í p°echod z [0] do [1] a nastaví se sux link opa£ným sm¥rem, coº je stejné jako v minulém p°ípad¥. Krok 1.

Krok 2. - Vstupní symbol a2. Tento krok uº je zajímav¥j²í. Protoºe mnoºina UncomplS obsahuje stav [1], budeme z n¥j muset vytvo°it p°echod na S. Nejprve se v²ak ve funkci UpdateS spustí °ádek 2 a jelikoº tentokrát platí podmínka, ºe i > 1 inicializujeme hodnotu AC(1) = (2, 2), protoºe arita i = 1 a arita vstupního symbolu je 2. Potom uº se dostaneme do funkce NewSTransition s parametrem q = [1], coº je uzel, ze kterého budeme vytvá°et p°echod na S. Stav má v d-subsetu jediné £íslo k = 1. Kdyº se podíváme na hodnotu AC(1), vrátí se nám dvojice (2, 2). P°echod na S tedy povede do stavu [2] a sou£et arity checksum je sumAC = 2, takºe tento p°echod není kompletní a stav [1] znovu vloºíme do mnoºiny UncomplSnext. Stav [2] uº existuje a tak nejsou pot°eba dal²í dodate£né kroky. Po návratu do hlavní funkce se dál dostaneme na nový °ádek 25, kde je volání funkce updateDsubsets. V tomto p°ípad¥ je situace jednoduchá - sta£í jen p°ejmenovat stav [1] na [1,2] a protoºe do stavu [1] nevede nikdy p°echod na S, nenastane ani situace, ºe bychom pot°ebovali rozd¥lit stav. V dal²ím rekurzivním volání uº by byl stav roven [0], takºe funkci znova nevoláme. Dále uº v hlavní procedu°e jen zkopíruje prom¥nné, takºe m·ºeme p°ejít k dal²ímu kroku.

Obrázek 4.4: Krok 0 aº 2 algoritmu 4.2

4.3.


55

Krok 3. - Vstupní symbol a0. V tomto kroku jsme poprvé dostali na vstupu symbol a0, takºe hlavn¥ vytvá°íme p°echody, ale tentokrát také aktualizujeme p°echody na S, protoºe mnoºina UncomplS obsahuje stavy [1,2] a [2]. Podívejme se op¥t, jak bude pracovat funkce UpdateS. Nejprve vytvo°íme dal²í poloºku v poli AC - AC(2) = (3, 0) (°ádek 2) a poté cyklem na °ádcích 4-9 aktualizujeme pole AC. Jediná poloºka, která se aktualizuje je AC(1) = (3, 1). Pak uº se op¥t ocitáme v cyklu, který aktualizuje p°echody na S. Nejprve budeme uvaºovat stav [1,2]. Zru²íme sou£asný p°echod, který vede do [2], ale stav [2] nemaºeme, protoºe má je²t¥ dal²í p°íchozí p°echody. Pak zavoláme funkci, která vytvo°í nový p°echod na S. Ve funkci NewSTransition bude prom¥nná k v cyklu na °ádcích 3-7 nabývat postupn¥ hodnot 1 a 2 (d-subset je 1,2). V prvním p°ípad¥ je v poli AC hodnota (3, 1) a v druhém (3, 0). D-subset cílového stavu bude tedy [3] (hodnoty neopakujeme) a sou£et díl£ích arity checksum je sumAC = 1. Stav [1,2] tedy op¥t p°idáme do mnoºiny UncomplSnext. Stav [3] op¥t uº existuje, takºe se jím dál nemusíme zabývat a pokra£ujeme dal²ím stavem. Druhý stav pro který budeme vytvá°et p°echod na S je [2]. Potom, co op¥t dob¥hne cyklus ve funkci NewSTransition na °ádcích 3-7, bude mít cílový stav op¥t hodnotu [3], ale sumAC bude tentokrát rovno nule. To znamená, ºe tento p°echod na S uº je kompletní a nebudeme tak p°idávat stav [2] do mnoºiny UncomplSnext. Situace je to logická, coº je dob°e vid¥t z obrázku 4.1. Levý podstrom uzlu a22 tvo°í jen jeden uzel a to je práv¥ ten, který odpovídá práv¥ p°e£tenému a03 . Podobn¥ je tomu i u stavu [1,2]. Vzpome¬me, ºe musíme uzav°ít oba podstromy - jednak ten s ko°enem v a21 , ale i ten s ko°enem a22 . Zatímco druhý jmenovaný jsme práv¥ uzav°eli, tak první je²t¥ uzav°ený není, protoºe nám chybí je²t¥ je²t¥ jeden list. To odpovídá tomu, ºe arity checksum bude roven nule potom, co ode£teme je²t¥ jeden symbol (nyní je 1) a to se stane práv¥ tehdy, kdyº p°ijde na vstup nulární symbol (list). Nakonec v hlavní funkci jen nastavíme sux link na [0], takºe funkce updateDsubsets se nepouºije ani jednou. V tomto kroku jsme tedy vytvo°ili nový p°echod na S, který uº byl rovnou nální a prodlouºili jsme jiný p°echod. Výsledný automat je na obrázku 4.5.

Obrázek 4.5: Krok 3 algoritmu 4.2 - Vstupní symbol a0. Tento krok byl zajímavý i v prvním algoritmu, protoºe zde do²lo k prvnímu rozd¥lení stavu, a tím pádem se nyní podíváme do funkce SplitNode. Nejprve se v²ak op¥t spustí funkce UpdateS, ve které aktualizujeme pole AC a p°echody na S. Nový Krok 4.

56KAPITOLA 4.


záznam, který vytvo°íme bude AC(3) = (4, 0) a p°i aktualizaci se zm¥ní op¥t jen záznam AC(1) = (4, 0). Nyní uº jsou v²echny £áste£né arity checksum rovny nule, takºe vytvo°ené p°echody by m¥ly být rovnou nální. Stavy, které máme ve funkci UpdateS zpracovat, jsou v tomto kroku [1,2] a [3]. Pro jednoduchost uvaºujeme nejprve stav [3]. U tohoto stavu je situace jednoduchá, protoºe podle poloºky v poli AC je cílový stav [4] a sumAC je rovno nule, takºe je p°echod jiº hotový, jak jsme p°edpokládali. Zajímav¥j²í je situace u stavu [1,2]. Kdyº dáme dohromady poloºky z pole AC, vyjde nám stav [3,4] coº je v tuto chvíli úpln¥ nový stav. Tento stav si tedy zapamatujeme tak, ºe ho uloºíme do mnoºiny NoveStavy. Také ho vloºíme do mnoºiny v²ech stav· Q a do mnoºiny UncomplS (°ádky 14-16 ve funkci NewSTransition ). Tím, ºe jsme stav [3,4] vloºili do UncomplS, tak prob¥hne pot°etí cyklus ve funkci UpdateS. Ve funkci NewSTransition tedy nyní vytvá°íme nový p°echod na S ze stavu [3,4]. V poli AC je hodnota jen pro k = 3 a to dvojice (4,0). Cílový stav tím pádem bude [4] a i p°esto, ºe sou£et arity checksum je nula, musíme stav [3,4] uloºit do mnoºiny UncomplSnext, protoºe nyní nevíme, kam povede p°echod na S ze stavu [4]. Tím je hotová funkce UpdateS a postupn¥ se dostaneme k rozd¥lení stavu [3] (viz první p°íklad). Na °ádku 1 funkce SplitNode vnikne stav, který bude mít d-subset [3,4]. Vidíme, ºe je to stejný stav, který vznikl, kdyº jsme vytvá°eli p°echod na S ze stavu [1,2]. Stav [3,4] tedy podruhé nep°idáváme do Q a pokra£ujeme dál funkcí SplitNode. Zde je patrné, pro£ funkci updateDsubset pouºíváme aº na dal²í stav na pracovní cest¥. D-subset stavu [3,4] totiº zaprvé nemusíme roz²i°ovat o i a zárove¬ víme, ºe p°echod na S, který do n¥j vede uº je takto vytvo°en správn¥, protoºe jsme porovnávali stav uº proti nálnímu d-subsetu v tomto kroku. Dal²ím stavem na pracovní cest¥ je nula, takºe neaktualizujeme ºádný dal²í d-subset.

Obrázek 4.6: Krok 4 algoritmu 4.2 Zajímavá situace nastane na °ádku, kde kontrolujeme cpds nového stavu (°ádka 22 funkce Vzpome¬me, ºe v prvním p°íkladu jsme nemohli nyní zkopírovat odchozí p°echody, protoºe cpds bylo rovno ε. To v²ak tentokrát neplatí díky p°echodu na S, který vytvo°il novou cestu do stavu [3,4] p°es stav [1,2]. Tím pádem je moºno zkopírovat p°echod na a0 do stavu [4] (°ádky 23-25). Nyní se také ukazuje, pro£ nap°ed vytvá°íme p°echody na S. Díky SplitNode ).

4.3.


57

tomu známe celé cpds stavu [3,4] a p°echody m·ºeme jednodu²e zkopírovat. Jinak bychom je museli vypo£ítávat zvlá²´ ve funkci UpdateA. Dále na °ádku 26 zjistíme, ºe stav [3,4] leºí v mnoºin¥ NoveStavy, coº zna£í, ºe jsme ho vytvo°ili ve funkci UpdateS a tím pádem má uº vytvo°ený p°echod na S, tak ho nemusíme vytvá°et nyní. Nakonec stav [3,4] z mnoºiny NoveStavy odstraníme, abychom se jím nezabývali ve funkci UpdateA. P°edstavme si v²ak, ºe to neud¥láme a zku²ebn¥ se podívejme, jak by prob¥hla funkce UpdateA. Zabývali bychom se zde jen stavem [3,4]. P°echod ze stavu [4] je²t¥ neznáme, takºe v cyklu na °ádcích 12 funkce UpdateA bude záleºet jen na k = 3. Symbol ak+1 = a4 = a0, takºe podmínka na °ádku 8 bude platit jen pokud a = a0. Vytvo°il by se tedy p°echod na a0 do stavu [4], coº je p°esn¥ to samé, £eho jsme dosáhli prostým zkopírováním tohoto p°echodu ve funkci SplitNode. Výsledný automat v tomto kroku je na obrázku 4.6. Krok 5. - Vstupní symbol a2. Na za£átku funkce UpdateS vloºíme do pole AC novou poloºku AC(4) = (5, 2). Ostatní poloºky v poli AC uº mají hodnotu arity checksum rovnu nula, takºe ºádnou poloºku neaktualizujeme. Dostáváme se tedy rovnou k aktualizaci p°echod· na S. Z minulého kroku máme v mnoºin¥ UncomplS stavy [4] a [3,4]. U stavu [4] op¥t jednodu²e vytvo°íme p°echod do stavu [5] a poznamenáme si, ºe je²t¥ není kompletní, protoºe sou£et arity checksum je 2. Pro stav [3,4] máme v poli AC nyní uº hodnoty pro ob¥ £ísla z d-subsetu. Z hodnot (4, 0) a (5, 2) vznikne nový stav [4,5]. Sou£et arity checksum bude 2, takºe tento p°echod budeme aktualizovat i v dal²ím kroku. Stav [4,5] má cpds rovno ε, takºe z n¥j uº nem·ºe vést dal²í p°echod a tím pádem skon£í i volání funkce UpdateS. Dále se v hlavním algoritmu dostaneme do situace, ºe pouze nastavíme sux link stavu [5] na stav [1,2] (°ádka 24). Oproti prvnímu algoritmu v²ak je²t¥ zavoláme funkci, která aktualizuje d-subsety na pracovní cest¥. Konkrétn¥ se tím zm¥ní stav [1,2] na [1,2,5] a p°itom si ho uloºíme do mnoºiny UncomplSnext, protoºe s tím, ºe je v d-subsetu stavu £íslo 5, jsme p°edtím nepo£ítali (viz p°edchozí krok). A to je konec tohoto kroku.

Obrázek 4.7: Krok 5 algoritmu 4.2 Je²t¥ poznamenejme, ºe p°echod δ([3, 4], a2, S) = ([5], SS) vznikl na °ádku 15 hlavní funkce v cyklu, kde vytvá°íme p°echody ze stav· na pracovní cest¥, coº se stalo díky tomu,

58KAPITOLA 4.


ºe na rozdíl od prvního p°íkladu se cpds stavu [3,4] nyní nerovná ε. Automat vzniklý v tomto kroku je na obrázku 4.7. - Vstupní symbol a0. Podívejme se op¥t hlavn¥ na funkci UpdateS. Na za£átku vloºíme do pole AC novou hodnotu AC(5) = (6, 0). Poté aktualizujeme star²í poloºky. Jediná, která nemá arity checksum roven nule, je ta s indexem 4, takºe se zm¥ní na AC(4) = (6, 1). V mnoºin¥ UncomplS máme stavy [5] (newlast v minulém kroku), [1,2,5] (protoºe jsme zm¥nili jeho d-subset), [4] (protoºe p°echod na S stále není kompletní) a stav [3,4] (kde také není p°echod hotový). U stavu [5] je situace jednoduchá, jelikoº p°echod vede do stavu [6], jak nám °íká nov¥ vytvo°ená poloºka v AC. Tento p°echod je rovnou hotový, protoºe arity checksum je roven nule. Podobná situace je u stavu [4], kde bude cílový stav také [6], ale p°echod je²t¥ není nální kv·li tomu, ºe sou£et arity checksum je 1. P°echod ze [4] tedy budeme aktualizovat i v dal²ím kroku. Dal²í postup je závislý na tom, v jakém po°adí budeme stavy zpracovávat, ale výsledek je stejný v obou p°ípadech. Vyberme si tedy nap°íklad nejprve stav [1,2,5]. Výsledný stav sloºíme z poloºek v AC - AC(1) = (4, 0), AC(2) = (3, 0) a AC(5) = (6, 0). Dostaneme nový cílový stav [3,4,6] a sumAC = 0. Protoºe je tento stav nový, p°idáme ho do mnoºiny UncomplS a NoveStavy. Poté máme na výb¥r, zda pokra£ovat práv¥ stavem [3,4,6] nebo [3,4], ale protoºe víme, ºe z 6 zatím ºádný p°echod nevede, tak cílový stav bude u obou volání stejný. Z pole AC zjístíme, ºe tento p°echod má cílový stav [4,6], coº je op¥t nový stav. Navíc p°i zpracování stavu [3,4] se dostaneme poprvé do situace, ºe odstran¥ní p·vodního p°echodu na S zp·sobí nedostupnost stavu [4,5]. Proto tento stav odstraníme a místo n¥j uvaºujeme nový stav [4,6]. Protoºe stav [4,6] má cpds rovno ε, tak uº ºádné dal²í p°echody nevytvo°íme a funkce UpdateS skon£í. Pro zopakování, nyní existují stavy [3,4] i [3,4,6], ale algoritmus pokra£uje dál. Stejn¥ jako v prvním algoritmu se dostame k tomu, ºe máme znovu rozd¥lit stav [3]. Nový stav, který vznikne, je [3,6]. Pak se zavolá funkce pro aktualizaci v²ech d-subset· na pracovní cest¥. První stavem, který budeme aktualizovat je [3,4], ze kterého se má stát [3,4,6]. V tomto p°ípad¥ se tedy aktualizovaný stav spojí s jiným stavem. Na druhou stranu se ale vyhneme rozd¥lení stavu v této funkci, protoºe ve chvíli, kdy p°ejmenováváme stav [3,4] do n¥j uº ºádný p°echod nevede. To, ºe do stavu [3,4,6] vede p°echod na S, to je v po°ádku, protoºe p°esn¥ tak jsme to cht¥li, kdyº jsme ho vytvá°eli p°i zpracování stavu [1,2,5]. M·ºeme si ale v²imnout, ºe kdybychom do d-subsetu p°idávali jiné £íslo, tak by p°ípadný p°echod na S uº neodpovídal tomu, který jsme vytvo°ili a museli bychom provést uº zmín¥né rozd¥lení stavu. To se ale nestane a neprob¥hne ani dal²í rekurzivní volání funkce UpdateDsubsets, protoºe jsme se dostali do stavu [0] a m·ºeme se tak vrátit do funkce SplitState, kde následuje kopie odchozích p°echod·. P°echody stejn¥ jako v prvním p°íkladu zkopírovat m·ºeme a navíc nyní musíme vytvo°it i p°echod na S, protoºe stav [3,6] vznikl jen za pomoci d¥lení stavu [3] (není v mnoºin¥ NoveStavy ). Nový p°echod povede do stavu [4], coº zjistíme stejn¥ jako v p°edchozích p°ípadech z pole AC. Arity checksum je v tomto p°ípad¥ sice roven nule, ale stav [4,6] má ve svém d-subsetu aktuální i, takºe p°echod je²t¥ hotový není. Nakonec se dostáváme do funkce UpdateA. Mnoºina NoveStavy sice obsahuje stav [4,6] ale jeho cpds nám neumoº¬uje vytvo°it dal²í p°echody, takºe to je z tohoto kroku v²e. Výsledný automat je na obrázku 4.8. Krok 6.

Krok 7. - Vstupní symbol b1. V prvním p°íklad¥ byl tento krok celkem jednoduchý, protoºe jsme jen p°idávali p°echody ze stav· na pracovní cest¥. Tentokrát p°idáme p°echody také, ale navíc je²t¥ musíme aktualizovat n¥kolik p°echod· na S. P°ed vlastní aktualizací upravíme stejn¥ jako v minulých krocích pole AC. P°ibude nová poloºka AC(6) = (7, 1) a

4.3.


59

aktualizujeme AC(4) = (7, 1). V mnoºin¥ UncomplS máme stavy [3,6] (vzniklý d¥lením), [3,4,6] (aktualizovaný d-subset), [4] (nekompletní p°echod na S ) a [6] (nemá p°echod na S ). Postupujme op¥t nap°íklad od nejjednodu²²ího. Ze stavu [6] vytvo°íme snadno p°echod na S, protoºe d-subset obsahuje jen £íslo 6 a to odpovídá v poli AC poloºce (7, 1), takºe cílový stav je [7] a p°echod není kompletní. Stejná situace je i u stavu [4]. Zde v²ak p°echod existuje, takºe starý p°echod smaºeme a nahradíme ho novým. Zajímav¥j²í je situace u stavu [3,6]. Podle pole AC vznikne nový stav [4,7] a tento p°echod není kompletní (sumAC = 1). Stav [4,7] si tedy uloºíme do mnoºin UncomplS, Q a NoveStavy. P°i zpracování stavu [3,4,6] vnikne stejný stav - [4,7]. Tentokrát je v²ak rozdíl v tom, ºe tím, ºe odstraníme p·vodní p°echod, se stane stav [4,6] nedostupný, takºe ho smaºeme. Na p°íkladu stavu [4,7] je vid¥t situace, ºe se v podstat¥ stále jedná o ten stejný stav, ale tím, jak se prodluºuje p°echod ze stavu [4] se stále m¥ní jeho d-subset. V poslední iteraci cyklu ve funkci UpdateS bude stav [4,7]. Ten v²ak má cpds rovno ε, takºe z n¥j p°echod nevytvo°íme a ze stejného d·vodu nevytvo°íme ani dal²í p°echod ve funkci UpdateA. Automat na konci tohoto kroku je na obrázku 4.9. Krok 8. - Vstupní symbol b0. V tomto kroku je situace podobná jako v tom p°edchozím. P·vodní algoritmus bude jen p°idávat p°echody, takºe se rovnou podívejme na funkci UpdateS. Protoºe £teme poslední symbol, který by m¥l uzav°ít prexový zápis stromu, tak by nám m¥ly vyjít v²echny £áste£né arity checksum rovny nule, coº zna£í, ºe v²echny vytvo°ené p°echody budou kompletní. Tomu odpovídá i aktualizace pole AC, protoºe jediné nenulové arity checksum jsou pro poloºky s indexy 4 a 6 a rovnají se jedna. Tím, ºe je na vstupu nulární symbol, aktualizace zp·sobí vynulování i t¥chto dvou hodnot. Nová hodnota arity checksum pro AC(7) je nulová rovnou - (8, 0). Dál se m·ºeme pustit do aktualizace p°echod· na symbol S. Mnoºina UncomplS obsahuje uº p¥t stav· - [3,6], [7], [3,4,6], [4] a [6]. U stav· [4], [6] a [7] je situace celkem jednoduchá. Cílovým stavem je spole£n¥ stav [8] a díky sou£t·m arity checksum vidíme, ºe jsou p°echody uº hotové. Trochu sloºit¥j²í je to u stav· [3,6] a [3,4,6]. A´ jiº vezmeme první kterýkoliv, tak nejprve vznikne nový stav [4,8]. P°i zpracování druhého stavu nám vyjde stejný cílový stav a navíc se nedostupným stane stav [4,7], takºe ho smaºeme. Ze stavu [4,8] uº nepovedou dal²í p°echody, takºe algoritmus je hotový a výsledný automat je na obrázku 4.10. Na obrázku 4.3 si m·ºeme zkontrolovat, ºe jsme dostali stejný automat, jako kdyº jsme postupovali s mezikrokem vytvo°ení nedeterministické verze automatu. Pro p°ehlednost je b¥h algoritmu 4.2 shrnut je²t¥ v tabulce 4.1. V sedmém kroku algoritmu nastala zajímavá situace, ºe p°echody na S ze stav· [3,6] a [3,4,6] vedou do stejného stavu - nakonec [4,8]. Pohledem na obrázek 4.1 m·ºeme ov¥°it, ºe platí úvaha, ze které jsme vycházeli p°i tvorb¥ p°echod· na S. Konkrétn¥ by m¥lo platit, ºe následující podstromy za uzly s po°adím 3, 4 a 6, kon£í shodn¥ v uzlech s po°adím 4 a 8. To platí, protoºe za uzlem 3 je podstrom, který kon£í ve stavu 4 - a04 , za uzlem 4 následuje podstrom a25 a06 b17 b08 kon£ící ve stavu 8 a za uzlem 6 je podstrom b08 , který kon£í také v uzlu s po°adím 8. Nakonec se je²t¥ podívejme teoreticky na poslední krok jiného p°íkladu, protoºe jsme se nesetkali se situací, kdy je pot°eba rozd¥lit stav ve funkci UpdateDsubset. Máme strom v prexovém zápisu a2 a2 a0 a1 a0 a1 a0. V kroku 7 je stav [3,5] roz²í°en na [3,5,7] (výskyty symbolu a0 ), jenºe ze do stavu [3,5] vede zárove¬ p°echod na S ze stavu [1,2]. Tím pádem z·stane i stav [3,5], kterému zkopírujeme v²echny odchozí p°echody a stavu [3,5,7] odchozí p°echody musíme smazat, protoºe kdyº zru²íme p°echod na S, bude jeho cpds rovno ε.



60KAPITOLA 4.



4.3.

61



62KAPITOLA 4.

ai a2 a2 a0

a0

a2

a0

b1

b0

i 1 2 3

4

5

6

7

8

AC(4, 8) = 0 AC(6, 8) = 0 AC(7, 8) = 0

AC(4, 7) = 1 AC(6, 7) = 1

AC(4, 6) = 1 AC(5, 6) = 0

AC(4, 5) = 2

zm¥ny AC AC(1, 2) = 2 AC(1, 3) = 1 AC(2, 3) = 0 AC(1, 4) = 0 AC(3, 4) = 0

[3,6] [3,4,6] [4] [6] [3,6] [3,4,6] [4] [6] [7]

[3,4] [4] [1,2,5] [3,4] [4] [5]

UncomplS [1] [1,2] [2] [1,2] [3]

Tabulka 4.1: Pr·b¥h výpo£tu algoritmu 4.2

Operace nový p°echod δ([1, 2], S, S) = ([2], ε) aktualizovaný p°echod δ([1, 2], S, S) = ([3], ε) nový p°echod δ([2], S, S) = ([3], ε) aktualizovaný p°echod δ([1, 2], S, S) = ([3, 4], ε) nový p°echod δ([3, 4], S, S) = ([4], ε) nový p°echod δ([3], S, S) = ([4], ε) aktualizovaný p°echod δ([3, 4], S, S) = ([4, 5], ε) nový p°echod δ([4], S, S) = ([5], ε) nový p°echod δ([1, 2, 5], S, S) = ([3, 4, 6], ε) nový p°echod δ([3, 4, 6], S, S) = ([4, 6], ε) aktualizovaný p°echod δ([4], S, S) = ([6], ε) nový p°echod δ([5], S, S) = ([6], ε) nový p°echod δ([3, 6], S, S) = ([4], ε) aktualizovaný p°echod δ([3, 6], S, S) = ([4, 7], ε) aktualizovaný p°echod δ([3, 4, 6], S, S) = ([4, 7], ε) aktualizovaný p°echod δ([4], S, S) = ([7], ε) aktualizovaný p°echod δ([6], S, S) = ([7], ε) aktualizovaný p°echod δ([3, 6], S, S) = ([4, 8], ε) aktualizovaný p°echod δ([3, 4, 6], S, S) = ([4, 8], ε) aktualizovaný p°echod δ([4], S, S) = ([8], ε) aktualizovaný p°echod δ([6], S, S) = ([8], ε) aktualizovaný p°echod δ([7], S, S) = ([8], ε) [4,8]

[4,7]

[3,4,6] [4,6]

[4,5]

[3,4]

NoveStavy -

4.3. ONLINE KONSTRUKCE DZA PIJÍMAJÍCÍHO STROMOVÉ VZORKY

63

64KAPITOLA 4.


Kapitola 5

Implementace Nakonec si popi²me jeden moºný zp·sob implementace uvedených algoritm·. Pro implementaci jsem zvolil jazyk Java, protoºe pro m¥ byla prioritní názorná, rychlá a pohodlná implementace. Nesnaºil jsem se tedy ²et°it kaºdý bit, ale spí²e jsem cht¥l, aby se implementace co nejvíce podobala navrºenému pseudokódu algoritmu a byly tak patrné souvislosti mezi t¥mito dv¥ma zápisy. Za tímto ú£elem jsem vytvo°il n¥kolik objekt·, které slouºí k abstrakci jednotlivých £ástí automatu, nap°íklad stavy, p°echody, vstupní symboly ap. Vlastní t°ídy jsou popsány dále. Kdyº jsem m¥l naimplementovány tyto objekty, dalo se relativn¥ jednodu²e p°epsat navrºené algoritmy do syntaxe Javy. V algoritmech tedy není ºádná zásadní zm¥na, takºe se podívejme jen na n¥které implementa£ní detaily. P°i implementaci automatu a v·bec celého algoritmu je asi nejpodstatn¥j²í zachovat konstantní sloºitost n¥kterých operací, jako je nap°íklad p°ístup do mnoºiny pravidel nebo stav·. Bylo tedy pot°eba zvolit vhodné kolekce pro ukládání navrºených objekt·. P°i implementaci jsem pouºíval hlavn¥ HashMap a pokud jsem pot°eboval p°idávat set°íd¥n¥, tak TreeSet a jinak klasicky ArrayList. D·leºitou vlastností konstruovaných automat· pro implementaci je, ºe zásobníková abeceda obsahuje pouze jeden symbol. Tím pádem m·ºeme zásobník reprezentovat jako jedno £íslo (int), které vyjad°uje po£et t¥chto symbol· na zásobníku. Podobn¥ je tomu u mnoºiny cpds. Op¥t se m·ºe jednat o mnoºinu £ísel a dokonce si m·ºeme vybrat, jestli uchovávat jen nejv¥t²í moºné £íslo nebo i ostatní. Pro názornost jsem jako kompromis zvolit uchovávání jen r·zných hodnot. Nyní uº si popi²me vlastní strukturu programu. Grackou stránku programu má na starost t°ída main. GUI je dost jednoduché, obsahuje jen pole pot°ebná pro zadání vstupu, pole pro výstup a jedno tla£ítko, které spou²tí výpo£et. Pro vytvo°ení grackých prvk· se pouºívá knihovna Swing. Do GUI se vrací textový výstup algoritmu v pomocném objektu SOutput. Vlastní algoritmus se spou²tí ve t°íd¥ Program, konkrétn¥ v metod¥ run, která má jako parametry údaje ze vstupu a vrací jiº zmín¥ný objekt SOutput. Tato metoda volá funkce ostatních objekt·, hlavn¥ Parser a t°ídy, která reprezentuje automat. T°ída Parser slouºí k na£ítání vstupu, který je zadaný jako °et¥zec. Pouºívá se pro zápis stromu, vzorku i abecedy a v¥t²inou vrací objekt Symbol, který reprezentuje jeden vstupní symbol, tedy v£etn¥ jeho arity, popisu a po°adí. Speciálním p°ípadem je symbol s p°íznakem, ºe se jedná o chybu nebo o konec vstupu. Parser je relativn¥ jednoduchý, implementuje malý 65

66

KAPITOLA 5.

IMPLEMENTACE

automat, který reprezentuje gramatiku prexového zápisu stromu - tj. ºe symbol za£íná libovolným po£tem znak· a-Z krom¥ vyhrazeného S a dál následuje libovolný po£et £íslic a symbol je ukon£en mezerou nebo koncem vstupu. V hlavní funkci tedy nejprve naparsujeme abecedu a pokud to skon£í úsp¥chem, tak vytvo°íme instanci objektu, který reprezentuje automat. V programu je jednak abstraktní t°ída Automaton, která obsahuje základní prom¥nné automatu jako je mnoºina stav·, pravidel atd. Abstraktní metoda se jmenuje update a je p°epsána ve t°íd¥ SubtreePDA, která reprezentuje automat p°ijímající podstromy. Ve funkci update je hlavní algoritmus konstrukce tohoto automatu a voláme ji pro kaºdý symbol ze vstupu. Dále jsou ve t°íd¥ pomocné funkce, nap°íklad pro vytvo°ení nového stavu nebo ur£ení cpds. Druhou t°ídou reprezentující automat je TreePatternPDA, která d¥dí od SubtreePDA a slouºí k vytvo°ení automatu, který p°ijímá stromové vzorky. Op¥t je zda p°epsána metoda update a jsou zde také ostatní funkce navrºené v kapitole 4. Ostatní objekty jsou spí²e pomocné: ACPair reprezentuje poloºku v poli AC, Konfigurace je aktuální kongurace automatu p°i testování vzorku, TransitionLeft je levé strana pravidla δ a analogicky TransitionRight je strana pravá. Jediná malá odli²nost od pseudokód· je, ºe jsem si vytvo°il pomocnou mnoºinu incoming, ve které je pro kaºdý stav uloºeno, jaké do n¥j vedou p°echody. Tato mnoºina se tedy musí navíc postupn¥ aktualizovat a pro uloºení slouºí pomocný objekt IncomingTrans. Pomocí této mnoºiny se usnadnil pohyb v mnoºin¥ pravidel podle jejich pravé strany, coº v algoritmech pouºíváme nap°íklad v úprav¥ cpds stavu. Nakonec, kdyº se povede konstrukce automatu, tak spustíme automat pro zadaný vzorek. K tomu slouºí metoda getNextConf, která je v abstraktní t°íd¥ Automaton a vrací dal²í konguraci. Je vid¥t, ºe pro její b¥h nejsou pot°eba prom¥nné, které pouºíváme p°i konstrukci automatu. Vlastní kódy jsou na p°iloºeném CD.

Kapitola 6

Testování Implementaci jsem otestoval na n¥kolika p°íkladech. Pro automatické testování jsem pouºil knihovnu JUnit. Code coverage se poda°ilo dosáhnout 90%. Hlavním problémem je v unit testech otestování GUI, ale to je v tomto p°ípad¥ tak jednoduché, ºe sta£ilo jeho ru£ní otestování. První p°íklad, který jsem pouºil pro testování, byl ten, na kterém jsem popisoval b¥h obou dvou nových algoritm·, tj. strom z obrázku 2.1s prexovým zápisem a2 a2 a0 a0 a2 a0 b1 b0. Druhý p°íklad byl z £lánku [6], kde je pouºitý strom s prexovým zápisem a2 a2 a0 a1 a0 a1 a0. Na druhý p°íklad se podívejme z pohledu testování podrobn¥ji. Nejprve uvaºujme, ºe konstruujeme automat, který bude p°ijímat v²echny podstromy daného stromu. První t°i kroky jsou stejné jako v prvním p°íklad¥, protoºe na vstupu jsou stejné symboly - a2 a2 a0. V prvním kroku jen vytvo°íme stav [1] a v druhém kroku vznikne stav [2], jehoº sux link napojíme na stav [1]. Ve t°etím kroku p°idáváme p°echody ze v²ech stav· na a0 do nového stavu [3]. Mnoºina cpds stavu [3] bude mít hodnoty {ε, S, SS}. Krok £ty°i se jiº li²í od prvního p°íkladu, ale je o dost jednodu²²í. Protoºe a1 je v tuto chvíli nový vstupní symbol, tak op¥t jen p°idáme p°echody. Tentokrát nejd°íve ze stavu [3] a pak z dal²ího stavu na pracovní cest¥, kterým je [0], protoºe práv¥ tam vede sux link [3]. V pátém kroku nastává situace, ºe musíme rozd¥lit stav [3]. Aktuální zpracovaná £ást °et¥zce je a2 a2 a0 a1 a0 a chceme vytvo°it sux link do stavu, který by odpovídal °et¥zci a0, coº je stav [3], ale ten navíc reprezentuje i °et¥zce a2 a0 a a2 a2 a0, coº ale nejsou suxy a2 a2 a0 a1 a0. Vznikne tedy nový stav [6] do kterého povede sux link [5] a p°íslu²n¥ upravíme i ostatní sux linky. Stav [5] má cpds rovno ε, takºe ºádné dal²í p°echody z n¥j jiº nepovedou. Situace v ²estém kroku je podobná. Tentokrát vznikne mimo páte° nový stav [8], do kterého vede p°echod z [0] na a1, takºe cpds je rovno S a tím pádem m·ºeme zkopírovat odchozí p°echody stavu [4], který v tomto kroku d¥líme. Nakonec v posledním sedmém kroku také d¥líme stav, tentokrát [5]. Pro správné nastavení sux linku pot°ebuje osamostatnit cestu pro °et¥zec a1 a0. Ta povede p°es stav [8], který vznikl v p°edchozím kroku. Zkopírovaný p°echod na a0 se tedy p°esm¥ruje do nového stavu [10]. Z n¥j uº dal²í p°echody nepovedou, protoºe jeho cpds bude rovno ε. Oproti prvnímu p°íkladu se tento p°íklad li²í v tom, ºe se vºdy d¥lí jiný stav a stane se to vícekrát. Navíc p°echod ze stavu, který neleºí na páte°i, vedou do jiného stavu, který také 67

68

KAPITOLA 6.

Obrázek 6.1: Sux linky v automatu pro strom s prexový zápisem

TESTOVÁNÍ

a2 a2 a0 a1 a0 a1 a0

vznikl d¥lením, coº se v prvním p°íkladu nestalo, ale nic se tím nem¥ní. Gracké znázorn¥ní výsledné struktury sux link· je na obrázku 6.1. Nyní se je²t¥ podívejme, jak prob¥hne algoritmus, kdyº budeme chtít sestrojit automat, který bude p°ijímat stromové vzorky, které se vyskytují v tomto strom¥. První kroky op¥t probíhají podobn¥ jako v podrobn¥ji popsaném p°íklad¥. Tentokrát jiº udrºujeme i d-subsety, takºe v druhém kroku p°ejmenujeme stav [1] na [1,2]. Ve stejném kroku také vytvo°íme první p°echod na S z [1,2] do [2]. V dal²ím kroku tento p°echod prodlouºíme, protoºe arity checksum je roven 2 a vytvo°íme dal²í p°echod na S z [2] do [3], tentokrát v²ak jiº kompletní. Ve £tvrtém kroku nastane zajímavá situace. Vznikne totiº nový stav díky p°echodu na S ze stavu [1,2]. Je to stav [3,4] a protoºe v tomto kroku jinak nedojde k rozd¥lení stavu, tak se nespojí s dal²ím stavem a musíme mu tak ur£it p°echody na a ∈ A i symbol S. Dojdeme k tomu, ºe p°echod na a1 a S povedou shodn¥ do stavu [4]. V tomto kroku tedy otestujeme funkci UpdateA. Pátý krok je také zajímavý, ale podobnou situaci jsme jiº testovali i v p°edchozím p°íkladu. Na za£átku vznikne díky aktualizaci p°echod· na S nový stav [3,5] a tím pádem se kv·li odstran¥ní p·vodního p°echodu na S stane stav [3,4] nedostupný a tak ho smaºeme. V tomto kroku dojde také k d¥lení stavu [3], kterým by vznikl shodn¥ stav [3,5]. Stav [3,5] se tedy spojí s tím, který jsme vytvo°ili na za£átku tohoto kroku. Na rozdíl od p°edchozího p°íkladu tentokrát není cpds tohoto stavu rovno ε (díky p°echodu na S p°es stav [1,2]), takºe m·ºeme zkopírovat odchozí p°echody p·vodního stavu a také vytvo°it p°echod na S. V ²estém kroku vznikne dal²í úpln¥ nový stav. P°i aktualizaci p°echodu na S ze stavu [3,5] vznikne stav [5,6] a p·vodní p°echod do [5] zru²íme. Stavu [3,5] aktualizujeme i p°echod na a1, ale to je díky tomu, ºe d¥líme stav [4] a tím vznikne stav [4,6]. Je vid¥t, ºe stav [5,6] se s tímto stavem nespojí, ale jeho cpds je rovno ε, takºe se nemusíme zat¥ºovat vytvá°ením odchozích p°echod·. Nakonec se dostáváme do posledního, sedmého, kroku. Tento krok jsme si popsali jiº d°íve, ale podívejme se na operace postupn¥. Nejprve aktualizujeme p°echod na S ze stavu [3,5]. Tím vznikne stav [5,7]. Starý stav [5,6] smaºeme, protoºe se touto aktualizací stal nedostupným. Poté následuje rozd¥lení stavu, ve kterém se slou£í stavy s d-subsety [5,7]. P°itom nastává zajímavá £ást aktualizace d-subset·. Prvním stavem na pracovní cest¥ je

69 [3,5], který se má zm¥nit na [3,5,7]. Do tohoto stavu ale jiº vede p°echod na S ze [1,2], takºe musíme stav [3,5] rozd¥lit. Pro stav [3,5] z·stane zachovaný p°íchozí p°echod na S a odchozí p°echody. Ostatní p°echody, které vedly do tohoto stavu, tedy konkrétn¥ ten ze stavu [0] na a0 p°esm¥rujeme do nového stavu [3,5,7]. Tento stav nebude mít ºádné odchozí p°echody, respektive je musíme smazat, protoºe opravené cpds tohoto stavu je ε. Tímto tedy otestujeme celou funkci UpdateDsubset() v£etn¥ £ásti, jeº rozd¥luje stav, kterou jsme v minulém p°ípad¥ otestovat nemohli. Výsledný automat z tohoto p°íkladu je na obrázku 6.2. Krom¥ t¥chto dvou p°íklad·, které jsou promítnuty v unit testech, jsem samoz°ejm¥ zkusil i n¥kolik dal²ích p°íklad· z literatury nebo vymy²lených a i na t¥chto p°íkladech fungovaly oba algoritmy dob°e.

Obrázek 6.2: DZA p°ijímající stromové vzorky obsaºené ve stromu s prexovým zápisem

a2 a2 a0 a1 a0 a1 a0

70 KAPITOLA 6. TESTOVÁNÍ

Kapitola 7

Záv¥r Práce m¥la n¥kolik hlavních cíl·. Nejprve jsem se musel seznámit se zásobníkovými automaty, které p°edstavují úplný index stromu, hlavn¥ pak s postupem, jakým je konstruujeme, ale i s dal²ími principy v arbologii. P°i návrhu algoritmu online konstrukce t¥chto automat· jsem se inspiroval podobným algoritmem ze stringologie, který se pouºívá pro online konstrukci suxových automat·. Myslím, ºe p°ínosem této práce je i popsání tohoto algoritmu v kapitole 2.4. Dále jsem si rozd¥lil práci tak, ºe jsem nejprve popsal algoritmus online konstrukce zásobníkového automatu p°ijímajícího v²echny úplné podstromy (subtree PDA) v kapitole 3 a pak jsem algoritmus roz²í°il v kapitole 4, aby výsledný automat p°ijímal v²echny stromové vzorky (tree pattern PDA). U obou algoritm· jsem navíc uvedl p°íklad jejich b¥hu. Oproti stringologické verzi algoritmu je v prvním p°ípad¥ hlavní rozdíl ten, ºe jsem k p°echod·m p°idal zásobníkové operace a ke v²em stav·m mnoºinu cpds, která reprezentuje moºné obsahy zásobníku. Pomocí této mnoºiny jsem rozhodoval, zda je moºné ud¥lat p°echod z onoho stavu. V druhém p°ípad¥ jsem musel implementovat navíc vytvá°ení p°echod· na vstupní symbol S, který reprezentuje úplný podstrom. V tomto p°ípad¥ jsem si pomohl pomocným polem AC, ve kterém jsem si ukládal p°echody na S, jak by se postupn¥ vytvá°ely v treetop automatu, spole£n¥ s hodnotou arity checksum, pomocí které jsem ur£oval, zda je p°echod jiº hotový nebo ne. Zatímco v prvním p°ípad¥ z·stala sloºitost algoritmu konstrukce automatu lineární, v druhém p°ípad¥ musí být minimáln¥ polynomiální, ale je spí²e vy²²í. Moºným pokra£ováním této by mohlo být práv¥ p°esné ur£ení sloºitosti tohoto algoritmu, £i její vylep²ení. Na práci by bylo podle mého názoru zajímavé navázat také pokusem o n¥jaké praktické nasazení prezentovaných algoritm·. Jak uº jsem zmínil v úvodu práce, hlavní výhodou výsledných automat· je, ºe vyhledávají vzorek v £ase lineárním k délce vzorku, coº by mohlo být velmi výhodné. P°edpokladem v²ak je, ºe by se vstupní strom £asto nem¥nil, protoºe ke konstrukci automatu pot°ebuje £as závislý na délce vstupu, ale t°eba by sta£ilo, aby byl vstup konstantní pro n¥kolik vyhledávání a pak bychom si mohli dovolit automat p°ed¥lat. To uº v²ak závisí na konkrétní situaci. Nabízí se nap°íklad pouºití v oblasti XML. Celkov¥ si myslím, ºe se poda°ilo splnit v²echny cíle práce a je moºné i její pokra£ování do budoucna.

71

72

KAPITOLA 7.

ZÁVR

Literatura [1] Webové stránky arbologie. http://www.arbology.org/, stav z 31. 1. 2011. [2] CROCHEMORE, M. RYTTER, W.

Jewels of Stringology.

World Scientic, 2002.

[3] CROCHEMORE, M. HANCART, C. Automata for Matching Patterns. [4] FLOURI, T. Indexing Factors in DNA/RNA Sequences. 2008. [5] HOLUB, J. Jazyky a p°eklady. 2010. [6] JANOUEK, J. MELICHAR, B. Subtree Pushdown Automata and Tree Pattern Pushdown Automata for Trees in Prex Notation. 2009. [7] KOVÁ, R. Paralelní vyhledávání ve stromech. 2009. [8] MÁCA, M. P°ibliºné vyhledávání ve stromech. 2011. [9] MELICHAR, B. Text Searching Algorithms. 2005. [10] PLICKA, M. JANOUEK, J. MELICHAR, B. Oracle Pushdown Automata for Trees in Prex Notation. 2010.

73

74

LITERATURA

P°íloha A

Seznam pouºitých zkratek AC

Arity Checksum Contents of the PushDown Store

CPDS DAG

Directed Acyclic Graph

DAWG DFA

Directed Acyclic Word Graph

Deterministic Finite Automaton

DKA

Deterministický kone£ný automat

DZA

Deterministický zásobníkový automat

GUI

Graphical User Interface

NFA

Nondeterministic Finite Automaton

NKA

Nedeterministický kone£ný automat

NZA

Nedeterministický zásobníkový automat

SRMS PDA ZA

Subtree RightMost State

Pushdown Automaton

Zásobníkový automat

75

76

PÍLOHA A.

SEZNAM POUITÝCH ZKRATEK

P°íloha B

Instala£ní p°íru£ka Program spus´te bu¤ dvojklikem na soubor dipjava.jar nebo z p°íkazové °ádky nap°íklad p°íkazem java -jar dipjava.jar. Pro vlastní zkompilování kódu lze pouºít nap°íklad p°íkaz javac cesta/ke/zdrojovymkodum nebo pouºitím IDE NetBeans a p°iloºeného projektu. Samotný program se ovládá velmi jednodu²e. V horní £ásti okna jsou t°i textová pole pro vstup abecedy, stromu v prexové notaci a vzorku v prexové notaci. Zápis symbol· je vºdy <£íslice> a následuje mezera nebo konec °et¥zce. Výjimkou je symbol S, který se zapisuje bez £íslice (arity) a nesmí být sou£ástí abecedy ani zápisu stromu. Algoritmus se spustí pomocí tla£ítka "Spustit"a do dolního pole se vypí²e textový výpis prom¥nných algoritmu v kaºdém kroku a pokud byl zadán vzorek a nedo²lo k chyb¥ (²patný vstup), tak i postupné p°echody automatu. P°epínátkem se nastavuje, jestli zkonstruovat automat pouze pro podstromy nebo i pro stromové vzorky.

77

78

PÍLOHA B.

INSTALANÍ PÍRUKA

P°íloha C

Obsah p°iloºeného CD index.html

výchozí stránka projektu

readme.txt

popis adresá°ové struktury CD

install.txt dipjava

popis instalace programu

implementace v Jav¥ (projekt NetBeans IDE)

dist / dipjava.jar dist / javadoc src test text

spustitelný jar soubor

javadoc projektu

zdrojové kódy projektu unit testy

text práce v PDF a zdrojové soubory LATEX

79

Online konstrukce deterministického zásobníkového automatu pro indexování strom. Bc. Ond ej Brynda

Recommend Documents