《双数组ppt课件》由会员分享，可在线阅读，更多相关《双数组ppt课件（19页珍藏版）》请在金锄头文库上搜索。
1、数据结构一、二康维鹏2010-10-245阶阶B-树示例树示例 【例】下图给出了一棵包含24个英文字母的5阶B-树的存储结构图。 说明：按照定义，在5阶B-树里，根中的关键字数目可以是14，子树数可以是25；其它的结点中关键字数目可以是24，若该结点不是叶子，则它可以有35棵子树。B-树一棵m(m3)阶的B-树是满足如下性质的m叉树：(1)每个结点至少包含下列数据域： (n，P0，Kl，P1，K2，Ki，Pi) n为关键字总数 Ki(1in)是关键字，关键字序列递增有序：K1 K2Ki。 Pi(0in)是孩子指针。对于叶结点，每个Pi为空指针。keys(P0)K1keys(P1)K2KiMin
2、，则只需删去K及其右指针(*x是叶子，K的右指针为空)即可使删除操作结束。B-树的实现删除关键值情形二：若x-keynum=Min，该叶子中的关键字个数已是最小值，删K及其右指针后会破坏B-树的性质(3)。若*x的左(或右)邻兄弟结点*y中的关键字数目大于Min，则将*y中的最大(或最小)关键字上移至双亲结点*parent中，而将*parent中相应的关键字下移至x中。显然这种移动使得双亲中关键字数目不变；*y被移出一个关键字，故其keynum减1，因它原大于Min，故减少1个关键字后keynum仍大于等于Min；而*x中已移入一个关键字，故删K后*x中仍有Min个关键字。涉及移动关键字的三个
3、结点均满足B-树的性质(3)。上述操作后仍满足B-树的性质(1)。移动完成后，删除过程亦结束。B-树的实现删除关键值情形三：若*x及其相邻的左右兄弟(也可能只有一个兄弟)中的关键字数目均为最小值Min，则上述的移动操作就不奏效，此时须*x和左或右兄弟合并。不妨设*x有右邻兄弟*y(结点取代*x对左邻兄弟的讨论与此类似)，在*x中删去K及其右子树后，将双亲结点*parent中介于*x和*y之间的关键字K，作为中间关键字，与并x和*y中的关键字一起合并为一个新的和*y。Trie树Trie,又称字典树、单词查找树,是一种树形结构，用于保存大量的字符串。它的优点是：利用字符串的公共前缀来节约存储空间，
4、查找速度快。其基本性质可以归纳为：1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。 2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 3. 每个节点的所有子节点包含的字符都不相同。Trie树的缺点：内存消耗非常大因此，往往利用Trie树的一种变形，DoubleArrayTrie。双数组Trie树Double Array Trie是TRIE树的一种变形，它是在保证TRIE树检索速度的前提下，提高空间利用率而提出的一种数据结构，本质上是一个确定有限自动机(deterministic finite automaton，简称DFA)。 双数组Double Arr
5、ay Trie （DAT）是采用两个线性数组(base和check)，base和check数组拥有一致的下标，（下标）即DFA中的每一个状态，也即TRIE树中所说的节点，base数组用于确定状态的转移，check数组用于检验转移的正确性。从状态s输入c到状态t的一个转移必须满足如下条件： bases + c = t ，用于确定转移 checkbases + c = s，用于检验前一状态双数组的一个实例“北京”、“北京大学”、北京市“、“市区”、“大学”、“北京市区”、“北大”、“市大学 “、“大北京“北=1， 京=2，大=3，学=4，市=5，区=6下标下标0 01 12 23 34 45 56
6、 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北北京京大大学学R北北京北京大北京大学next=abs(base0)+idx(0)=1Check1=0next=abs(base1)+idx(1)=7Check7=1next=abs
7、(base7)+idx(2)=14Check14=7next=abs(base14)+idx(3)=17Check17=14base170则baseidxState=-baseidxState,(b)否则baseidxState=-idxState; idx(北)=1， idx(京)=2，idx(大)=3，idx(学)=4，idx(市)=5，idx(区)=6queue：0-北京, 0-北京大学, 0-北京市, 0-北京市区, 0-北大, 0-大北京, 0-大学, 0-市区, 0-市大学(4)顺次扫描排序队列，计算更新队列中各状态的base数组和check数组，并更新队列，直到队列为空。保留状态
8、0为初始化值。计算basecurrState：若basecurrState=bs，则bs满足下面条件：对于队列中任意当前状态是currState的词语w，设其第一个字是w1，则：basebs+idx(w1)=0 & checkbs+idx(w1)=0更新base数组和check数组：更新basecurrState=bs，checkbs+idx(w1)= currState 。更新队列：按队列顺序，依次去掉各个单词的首个字w1，保留单词剩余部分，并且记录按照w1跳转到的下一个状态： currState =basecurrState+idx(w1) ; ramainContent= ramainC
9、ontent.subString(1);双数组Trie树构造 idx(北)=1， idx(京)=2，idx(大)=3，idx(学)=4，idx(市)=5，idx(区)=6queue：0-北京, 0-北京大学, 0-北京市, 0-北京市区, 0-北大, 0-大北京, 0-大学, 0-市区, 0-市大学第一次遍历后结果如下：下标下标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 0chec
10、kcheck0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0北大市(北)京(北)京大学(北)京市(北)京市区(北)大(大)学(大)北京(市)区(市)大学1-京, 1-京大学, 1-京市, 1-京市区, 1-大3-北京, 3-学5-区, 5-大学queue：1-京, 1-京大学, 1-京市, 1-京市区, 1-大, 3-北京, 3-学, 5-区, 5-大学双数组Trie树构造 idx(北)=1， idx(京)=2，idx(大)=3，idx(学)=4，idx(市)=5，idx(区)=6queue： 1-京, 1-京大学, 1-京市,
11、 1-京市区, 1-大, 3-北京, 3-学, 5-区, 5-大学第二次遍历，需要计算状态1、3、5的值。例如，计算base1的bs值。首先，查看那些单词的currState=1，得到1-京, 1-京大学, 1-京市, 1-京市区, 1-大其次，这些单词的第一个字的不同下标有：idx(京)=2，idx(大)=3因此，bs值需要满足条件是：basebs+2=0，basebs+3=0，checkbs+2=0，checkbs+3=0，bs+26一个满足条件的值，为bs=5。更新状态1的base与check数组。得到，base1=5，check5+2=1，check5+3=1同理，得到base3=8；
12、base5=7下标下标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北京北大大北大学市大市区(北京)(北京)大学(北京)市(北京)市区(北大)(大北)京(大学)(市区)北京(北)京(北)京大学(北)京市(北)京市区(北)大大更新后的queue为：qu
13、eue：7-大学, 7-市, 7-市区, 9-京, 10-学(市大)学下标下标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双数组Trie树构造 idx(北)=1， idx(京)=2，idx(大)=3，idx(学)=4，idx(市)=5，idx(区)
14、=6queue：7-大学, 7-市, 7-市区, 9-京, 10-学下标下标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-学, 16-区第四次遍历后：下标下标0 01 12 23 34 45 56 67 78 8
15、9 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)最后遍历词表，标记词语：下标下标0 01 12 23 34 45 56 67 78 89 9101011111212131314141515161617171818basebase0 05 50 08 80 07 70 0-11-11-8
16、-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北京北大大北京大学市区市大学北京市北京市区北京大学Queue为空，步骤(4)结束ThankyouTrie树的另一种变形AC自动机AC自动机分为3步：构造一棵Trie树，构造失败指针和模式匹配过程。AC自动机是用来处理多串匹配问题的，即给你很多字串，再给你一篇文章，让你在文章中找这些串是否出现过，在哪出现。它是结合了trie树与KMP算法思想。cla
17、ssTrieNodeintlen;/表示单词长度booleanisword;/是否为该单词的最后一个节点TrieNodefail;/失败指针TrieNodenext;/Tire子节点（最多个字母）AC自动机在trie树上添加失败指针。失败指针具有KMP算法next数组相同的功能，也就是说当我们的模式串在Tire上进行匹配时，如果与当前节点的关键字不能继续匹配的时候，就应该去当前节点的失败指针所指向的节点继续进行匹配。多模式匹配匹配：北京市、北京、北大、北京大学、市区、大学。R京大市北学市大学区大北北 京京 大大 学学 位位 于于 北北 京京 市市 区区 ， 简简 称称 北北 大大北北京京大大学学北北京京大大学学nullqueue北市大RootRoot
