双数组AC自动机(精)PPT课件

1 数据结构一 二 康维鹏2010 10 24 2 5阶B 树示例 例 下图给出了一棵包含24个英文字母的5阶B 树的存储结构图 说明 按照定义 在5阶B 树里 根中的关键字数目可以是1 4 子树数可以是2 5 其它的结点中关键字数目可以是2 4 若该结点不是叶子 则它可以有3 5棵子树 3 B 树一棵m m 3 阶的B 树是满足如下性质的m叉树 1 每个结点至少包含下列数据域 n P0 Kl P1 K2 Ki Pi n为关键字总数Ki 1 i n 是关键字 关键字序列递增有序 K1 K2 Ki Pi 0 i n 是孩子指针 对于叶结点 每个Pi为空指针 keys P0 K1 keys P1 K2 Ki keys Pi 2 所有叶子是在同一层上 叶子的层数为树的高度h 3 每个非根结点中所包含的关键字个数j满足 4 若树非空 则根至少有1个关键字 故若根不是叶子 则它至少有2棵子树 根至多有m 1个关键字 故至多有m棵子树 4 B 树的实现关键值查找插入关键值删除关键值关键值查找 在B 树中查找给定关键字的方法类似于二叉排序树上的查找 不同的是在每个结点上确定向下查找的路径不一定是二路而是keynum 1路的 对结点内的存放有序关键字序列的向量key l keynum 用顺序查找或折半查找方法查找 5 B 树的实现插入关键值 1 首先在树中查找K 若找到则直接返回 2 否则查找操作必失败于某个叶子上 然后将K插入该叶子中 2 a 若该叶子结点原来是非满的 则插入K后并未破坏B 树的性质 故插入K后即完成了插入操作 2 b 若该结点原为满 则K插入后keynum m 违反B 树性质 3 故须调整使其维持B 树性质不变 6 B 树的删除 1 删除操作的两个步骤第一步骤 在树中查找被删关键字K所在的地点第二步骤 进行删去K的操作 2 删去K的操作B 树是二叉排序树的推广 中序遍历B 树同样可得到关键字的有序序列 任一关键字K的中序前趋 后继 必是K的左子树 右子树 中最右 左 下的结点中最后 最前 一个关键字 若被删关键字K所在的结点非树叶 则用K的中序前趋 或后继 K 取代K 然后从叶子中删去K 从叶子 x开始删去某关键字K的三种情形为 情形一 若x keynum Min 则只需删去K及其右指针 x是叶子 K的右指针为空 即可使删除操作结束 7 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个关键字 涉及移动关键字的三个结点均满足B 树的性质 3 上述操作后仍满足B 树的性质 1 移动完成后 删除过程亦结束 8 B 树的实现删除关键值 情形三 若 x及其相邻的左右兄弟 也可能只有一个兄弟 中的关键字数目均为最小值Min 则上述的移动操作就不奏效 此时须 x和左或右兄弟合并 不妨设 x有右邻兄弟 y 结点取代 x对左邻兄弟的讨论与此类似 在 x中删去K及其右子树后 将双亲结点 parent中介于 x和 y之间的关键字K 作为中间关键字 与并x和 y中的关键字一起 合并 为一个新的和 y 9 Trie树 Trie 又称字典树 单词查找树 是一种树形结构 用于保存大量的字符串 它的优点是 利用字符串的公共前缀来节约存储空间 查找速度快 其基本性质可以归纳为 1 根节点不包含字符 除根节点外每一个节点都只包含一个字符 2 从根节点到某一节点 路径上经过的字符连接起来 为该节点对应的字符串 3 每个节点的所有子节点包含的字符都不相同 Trie树的缺点 内存消耗非常大因此 往往利用Trie树的一种变形 DoubleArrayTrie 10 双数组Trie树 DoubleArrayTrie是TRIE树的一种变形 它是在保证TRIE树检索速度的前提下 提高空间利用率而提出的一种数据结构 本质上是一个确定有限自动机 deterministicfiniteautomaton 简称DFA 双数组DoubleArrayTrie DAT 是采用两个线性数组 base 和check base和check数组拥有一致的下标 下标 即DFA中的每一个状态 也即TRIE树中所说的节点 base数组用于确定状态的转移 check数组用于检验转移的正确性 从状态s输入c到状态t的一个转移必须满足如下条件 base s c t 用于确定转移check base s c s 用于检验前一状态 11 双数组的一个实例 北京 北京大学 北京市 市区 大学 北京市区 北大 市大学 大北京 北 1 京 2 大 3 学 4 市 5 区 6 R 北 北京 北京大 北京大学 next abs base 0 idx 0 1Check 1 0 next abs base 1 idx 1 7Check 7 1 next abs base 7 idx 2 14Check 14 7 next abs base 14 idx 3 17Check 17 14 base 17 0 ok 12 双数组Trie树构造 北京 北京大学 北京市 市区 大学 北京市区 北大 市大学 大北京 1 对词表中所有出现的6个汉字进行编码 idx 北 1 idx 京 2 idx 大 3 idx 学 4 idx 市 5 idx 区 6 publicclassDoubleArrayWord publicintcurrState 0 当前状态publicStringramainContent 其余内容 queue 0 北京 0 北京大学 0 北京市 0 北京市区 0 北大 0 大北京 0 大学 0 市区 0 市大学 2 初始化双数组base Size 与check Size 3 按照字符串比较 对词表单词进行排序 北京 北京大学 北京市 北京市区 北大 大北京 大学 市区 市大学 并按序 把词存入DoubleArrayWord的数组queue 中 13 双数组Trie树构造 5 遍历词表 对单词做标记 用负数表示此状态可以输出单词 一词语在某个状态idxState结束 a 如果base idzState 0则base idxState base idxState b 否则base idxState 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数组 并更新队列 直到队列为空 保留状态0为初始化值 计算base currState 若base currState bs 则bs满足下面条件 对于队列中任意当前状态是currState的词语w 设其第一个字是w1 则 base bs idx w1 0 check bs idx w1 0 更新base数组和check数组 更新base currState bs check bs idx w1 currState 更新队列 按队列顺序 依次去掉各个单词的首个字w1 保留单词剩余部分 并且记录按照w1跳转到的下一个状态 currState base currState idx w1 ramainContent ramainContent subString 1 14 双数组Trie树构造 idx 北 1 idx 京 2 idx 大 3 idx 学 4 idx 市 5 idx 区 6queue 0 北京 0 北京大学 0 北京市 0 北京市区 0 北大 0 大北京 0 大学 0 市区 0 市大学 第一次遍历后结果如下 北 大 市 北 京 北 京大学 北 京市 北 京市区 北 大 大 学 大 北京 市 区 市 大学 1 京 1 京大学 1 京市 1 京市区 1 大 3 北京 3 学 5 区 5 大学 queue 1 京 1 京大学 1 京市 1 京市区 1 大 3 北京 3 学 5 区 5 大学 15 双数组Trie树构造 idx 北 1 idx 京 2 idx 大 3 idx 学 4 idx 市 5 idx 区 6queue 1 京 1 京大学 1 京市 1 京市区 1 大 3 北京 3 学 5 区 5 大学 第二次遍历 需要计算状态1 3 5的值 例如 计算base 1 的bs值 首先 查看那些单词的currState 1 得到1 京 1 京大学 1 京市 1 京市区 1 大其次 这些单词的第一个字的不同下标有 idx 京 2 idx 大 3因此 bs值需要满足条件是 base bs 2 0 base bs 3 0 check bs 2 0 check bs 3 0 bs 2 6一个满足条件的值 为bs 5 更新状态1的base与check数组 得到 base 1 5 check 5 2 1 check 5 3 1同理 得到base 3 8 base 5 7 北京 北大 大北 大学 市大 市区 北京 北京 大学 北京 市 北京 市区 北大 大北 京 大学 市区 北 京 北 京 北 京大学 北 京市 北 京市区 北 大 大 更新后的queue为 queue 7 大学 7 市 7 市区 9 京 10 学 市大 学 16 双数组Trie树构造 idx 北 1 idx 京 2 idx 大 3 idx 学 4 idx 市 5 idx 区 6queue 7 大学 7 市 7 市区 9 京 10 学 第三次遍历后 queue 14 学 16 区 第四次遍历后 5 最后遍历词表 标记词语 北京 北大 大北京 大学 市区 市大学 北京市 北京市区 北京大学 Queue为空 步骤 4 结束 17 Thankyou 18 Trie树的另一种变形AC自动机 AC自动机分为3步 构造一棵Trie树 构造失败指针和模式匹配过程 AC自动机是用来处理多串匹配问题的 即给你很多字串 再给你一篇文章 让你在文章中找这些串是否出现过 在哪出现 它是结合了trie树与KMP算法思想 classTrieNode intlen 表示单词长度booleanisword 是否为该单词的最后一个