雙數(shù)組ppt課件

1、數(shù)據(jù)結(jié)構(gòu)一、二康維鵬2010-10-245 5階階b-b-樹示例樹示例 【例】下圖給出了一棵包含24個(gè)英文字母的5階b-樹的存儲(chǔ)結(jié)構(gòu)圖。 說(shuō)明：按照定義，在5階b-樹里，根中的關(guān)鍵字?jǐn)?shù)目可以是14，子樹數(shù)可以是25；其它的結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目可以是24，若該結(jié)點(diǎn)不是葉子，則它可以有35棵子樹。b-樹一棵m(m3)階的b-樹是滿足如下性質(zhì)的m叉樹：(1)每個(gè)結(jié)點(diǎn)至少包含下列數(shù)據(jù)域： (n，p0，kl，p1，k2，ki，pi) n為關(guān)鍵字總數(shù) ki(1in)是關(guān)鍵字，關(guān)鍵字序列遞增有序：k1 k2ki。 pi(0in)是孩子指針。對(duì)于葉結(jié)點(diǎn)，每個(gè)pi為空指針。keys(p0)k1keys(p1)k2k

2、imin，則只需刪去k及其右指針(*x是葉子，k的右指針為空)即可使刪除操作結(jié)束。b-樹的實(shí)現(xiàn)刪除關(guān)鍵值情形二：若x-keynum=min，該葉子中的關(guān)鍵字個(gè)數(shù)已是最小值，刪k及其右指針后會(huì)破壞b-樹的性質(zhì)(3)。若*x的左(或右)鄰兄弟結(jié)點(diǎn)*y中的關(guān)鍵字?jǐn)?shù)目大于min，則將*y中的最大(或最小)關(guān)鍵字上移至雙親結(jié)點(diǎn)*parent中，而將*parent中相應(yīng)的關(guān)鍵字下移至x中。顯然這種移動(dòng)使得雙親中關(guān)鍵字?jǐn)?shù)目不變；*y被移出一個(gè)關(guān)鍵字，故其keynum減1，因它原大于min，故減少1個(gè)關(guān)鍵字后keynum仍大于等于min；而*x中已移入一個(gè)關(guān)鍵字，故刪k后*x中仍有min個(gè)關(guān)鍵字。涉及移動(dòng)關(guān)鍵

3、字的三個(gè)結(jié)點(diǎn)均滿足b-樹的性質(zhì)(3)。上述操作后仍滿足b-樹的性質(zhì)(1)。移動(dòng)完成后，刪除過(guò)程亦結(jié)束。b-樹的實(shí)現(xiàn)刪除關(guān)鍵值情形三：若*x及其相鄰的左右兄弟(也可能只有一個(gè)兄弟)中的關(guān)鍵字?jǐn)?shù)目均為最小值min，則上述的移動(dòng)操作就不奏效，此時(shí)須*x和左或右兄弟合并。不妨設(shè)*x有右鄰兄弟*y(結(jié)點(diǎn)取代*x對(duì)左鄰兄弟的討論與此類似)，在*x中刪去k及其右子樹后，將雙親結(jié)點(diǎn)*parent中介于*x和*y之間的關(guān)鍵字k，作為中間關(guān)鍵字，與并x和*y中的關(guān)鍵字一起合并為一個(gè)新的和*y。trie樹trie,又稱字典樹、單詞查找樹,是一種樹形結(jié)構(gòu)，用于保存大量的字符串。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來(lái)節(jié)約存

4、儲(chǔ)空間，查找速度快。其基本性質(zhì)可以歸納為：1.根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符。2.從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。3.每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。trie樹的缺點(diǎn)：內(nèi)存消耗非常大因此，往往利用trie樹的一種變形，doublearraytrie。雙數(shù)組trie樹double array trie是trie樹的一種變形，它是在保證trie樹檢索速度的前提下，提高空間利用率而提出的一種數(shù)據(jù)結(jié)構(gòu)，本質(zhì)上是一個(gè)確定有限自動(dòng)機(jī)(deterministic finite automaton，簡(jiǎn)稱dfa)。 雙數(shù)組double arra

5、y trie （dat）是采用兩個(gè)線性數(shù)組(base和check)，base和check數(shù)組擁有一致的下標(biāo)，（下標(biāo)）即dfa中的每一個(gè)狀態(tài)，也即trie樹中所說(shuō)的節(jié)點(diǎn)，base數(shù)組用于確定狀態(tài)的轉(zhuǎn)移，check數(shù)組用于檢驗(yàn)轉(zhuǎn)移的正確性。從狀態(tài)s輸入c到狀態(tài)t的一個(gè)轉(zhuǎn)移必須滿足如下條件： bases + c = t ，用于確定轉(zhuǎn)移 checkbases + c = s，用于檢驗(yàn)前一狀態(tài)雙數(shù)組的一個(gè)實(shí)例“北京”、“北京大學(xué)”、北京市“、 “市區(qū)”、“大學(xué)”、“北京市區(qū)”、“北大”、 “市大學(xué) “、 “大北京“北=1， 京=2，大=3，學(xué)=4，市=5，區(qū)=6下標(biāo)下標(biāo)0 01 12 23 34 45

6、56 67 78 89 9101011111212131314141515161617171818basebase0 05 50 08 80 07 70 0-11-11-8-89 91111-11-11-12-12-13-131313-15-15-12-12-17-17-18-18checkcheck0 00 00 00 00 00 00 01 11 13 35 59 93 35 57 710107 714141616北北京京大大學(xué)學(xué)r北北京北京大北京大學(xué)next=abs(base0)+idx(0)=1check1=0next=abs(base1)+idx(1)=7check7=1next=a

7、bs(base7)+idx(2)=14check14=7next=abs(base14)+idx(3)=17check17=14base170則baseidxstate=-baseidxstate,(b)否則baseidxstate=-idxstate; idx(北)=1， idx(京)=2，idx(大)=3，idx(學(xué))=4，idx(市)=5，idx(區(qū))=6queue：0-北京, 0-北京大學(xué), 0-北京市, 0-北京市區(qū), 0-北大, 0-大北京, 0-大學(xué), 0-市區(qū), 0-市大學(xué)(4)順次掃描排序隊(duì)列，計(jì)算更新隊(duì)列中各狀態(tài)的base數(shù)組和check數(shù)組，并更新隊(duì)列，直到隊(duì)列為空。保留

8、狀態(tài)0為初始化值。計(jì)算basecurrstate：若basecurrstate=bs，則bs滿足下面條件：對(duì)于隊(duì)列中任意當(dāng)前狀態(tài)是currstate的詞語(yǔ)w，設(shè)其第一個(gè)字是w1，則：basebs+idx(w1)=0 & checkbs+idx(w1)=0更新base數(shù)組和check數(shù)組：更新basecurrstate=bs，checkbs+idx(w1)= currstate 。更新隊(duì)列：按隊(duì)列順序，依次去掉各個(gè)單詞的首個(gè)字w1，保留單詞剩余部分，并且記錄按照w1跳轉(zhuǎn)到的下一個(gè)狀態(tài)： currstate =basecurrstate+idx(w1) ; ramaincontent= ramai

9、ncontent.substring(1);雙數(shù)組trie樹構(gòu)造 idx(北)=1， idx(京)=2，idx(大)=3，idx(學(xué))=4，idx(市)=5，idx(區(qū))=6queue：0-北京, 0-北京大學(xué), 0-北京市, 0-北京市區(qū), 0-北大, 0-大北京, 0-大學(xué), 0-市區(qū), 0-市大學(xué)第一次遍歷后結(jié)果如下：下標(biāo)下標(biāo)0 01 12 23 34 45 56 67 78 89 9101011111212131314141515161617171818basebase0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0ch

10、eckcheck0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0北大市(北)京(北)京大學(xué)(北)京市(北)京市區(qū)(北)大(大)學(xué)(大)北京(市)區(qū)(市)大學(xué)1-京, 1-京大學(xué), 1-京市, 1-京市區(qū), 1-大3-北京, 3-學(xué)5-區(qū), 5-大學(xué)queue：1-京, 1-京大學(xué), 1-京市, 1-京市區(qū), 1-大, 3-北京, 3-學(xué), 5-區(qū), 5-大學(xué)雙數(shù)組trie樹構(gòu)造 idx(北)=1， idx(京)=2，idx(大)=3，idx(學(xué))=4，idx(市)=5，idx(區(qū))=6queue： 1-京, 1-京大學(xué), 1-京

11、市, 1-京市區(qū), 1-大, 3-北京, 3-學(xué), 5-區(qū), 5-大學(xué)第二次遍歷，需要計(jì)算狀態(tài)1、3、5的值。例如，計(jì)算base1的bs值。首先，查看那些單詞的currstate=1，得到1-京, 1-京大學(xué), 1-京市, 1-京市區(qū), 1-大其次，這些單詞的第一個(gè)字的不同下標(biāo)有：idx(京)=2，idx(大)=3因此，bs值需要滿足條件是：basebs+2=0，basebs+3=0，checkbs+2=0，checkbs+3=0，bs+26一個(gè)滿足條件的值，為bs=5。更新狀態(tài)1的base與check數(shù)組。得到，base1=5，check5+2=1，check5+3=1同理，得到base3=

12、8；base5=7下標(biāo)下標(biāo)0 01 12 23 34 45 56 67 78 89 9101011111212131314141515161617171818basebase0 05 50 08 80 07 70 00 00 00 00 00 00 00 00 00 00 00 00 0checkcheck0 00 00 00 00 00 00 01 11 13 35 50 03 35 50 00 00 00 00 0北京北大大北大學(xué)市大市區(qū)(北京)(北京)大學(xué)(北京)市(北京)市區(qū)(北大)(大北)京(大學(xué))(市區(qū))北京(北)京(北)京大學(xué)(北)京市(北)京市區(qū)(北)大大更新后的queue為：

13、queue：7-大學(xué), 7-市, 7-市區(qū), 9-京, 10-學(xué)(市大)學(xué)下標(biāo)下標(biāo)0 01 12 23 34 45 56 67 78 89 9101011111212131314141515161617171818basebase0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0checkcheck0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0雙數(shù)組trie樹構(gòu)造 idx(北)=1， idx(京)=2，idx(大)=3，idx(學(xué))=4，idx(市)=5，idx(

14、區(qū))=6queue：7-大學(xué), 7-市, 7-市區(qū), 9-京, 10-學(xué)下標(biāo)下標(biāo)0 01 12 23 34 45 56 67 78 89 9101011111212131314141515161617171818basebase0 05 50 08 80 07 70 011110 09 911110 00 00 00 00 00 00 00 0checkcheck0 00 00 00 00 00 00 01 11 13 35 59 93 35 57 710107 70 00 0第三次遍歷后：queue：14-學(xué), 16-區(qū)第四次遍歷后：下標(biāo)下標(biāo)0 01 12 23 34 45 56 67 78

15、 89 9101011111212131314141515161617171818basebase0 05 50 08 80 07 70 011110 09 911110 00 00 013130 012120 00 0checkcheck0 00 00 00 00 00 00 01 11 13 35 59 93 35 57 710107 714141616(5)最后遍歷詞表，標(biāo)記詞語(yǔ)：下標(biāo)下標(biāo)0 01 12 23 34 45 56 67 78 89 9101011111212131314141515161617171818basebase0 05 50 08 80 07 70 0-11-11

16、-8-89 91111-11-11-12-12-13-131313-15-15-12-12-17-17-18-18checkcheck0 00 00 00 00 00 00 01 11 13 35 59 93 35 57 710107 714141616北京北大大北京大學(xué)市區(qū)市大學(xué)北京市北京市區(qū)北京大學(xué)queue為空，步驟(4)結(jié)束thank youtrie樹的另一種變形ac自動(dòng)機(jī)ac自動(dòng)機(jī)分為3步：構(gòu)造一棵trie樹，構(gòu)造失敗指針和模式匹配過(guò)程。ac自動(dòng)機(jī)是用來(lái)處理多串匹配問(wèn)題的，即給你很多字串，再給你一篇文章，讓你在文章中找這些串是否出現(xiàn)過(guò)，在哪出現(xiàn)。它是結(jié)合了trie樹與kmp算法思想。classtrienodeintlen;/表示單詞長(zhǎng)度booleanisword;/是否為該單詞的最后一個(gè)節(jié)點(diǎn)trienodefail;/失敗指針trienode