《高级数据库马蔚课件》由会员分享，可在线阅读，更多相关《高级数据库马蔚课件（15页珍藏版）》请在装配图网上搜索。
1、高级数据库马蔚高级数据库高级数据库使用负因素提升字符串正则表使用负因素提升字符串正则表达式比对的效率达式比对的效率马蔚2111305056高级数据库马蔚 基础概念基础概念 字符串正则式比对技术字符串正则式比对技术 负因素与负因素与PNS模式模式 使用负因素提升比对效率使用负因素提升比对效率 实验效果实验效果高级数据库马蔚基础概念基础概念 正则表达式正则表达式正则表达式是对字符串操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。给定一个正则表达式和另一个字符串，我们可以达到如下的目的：1. 给定的字
2、符串是否符合正则表达式的过滤逻辑（称作“匹配”）；2. 可以通过正则表达式，从字符串中获取我们想要的特定部分。高级数据库马蔚基础概念基础概念 正则表达式正则表达式 Q = (G|T)AGAT*，我们得出|Q| = 6, 因为有六个字母GTAGAT，RQ=GG, TG, GAG, TAG, GGA, TGA, GGT, TGT,GAGT, . . .。我们得出lmin = 2,因为最短的元素包含两个字母。高级数据库马蔚基础概念基础概念 正则表达式正则表达式设为有限字母集合。A为正则表达式且, |, , , (, ),可以有定义如下： 为正则表达式。可为空字符串。 每一字符串w *也是正则表达式，
3、表示为集合w。 如果e1和e2是正则表达式分别表示为R1和R2，然后： （e1）是正则表达式且与e1表示的集合相同。 （e1e2）是个正则表达式相乘。设字符串集合为x，且当e1为x，e2为y时可写为x=yz。 (e1|e2)表示正则表达式的或运算。 -(e1+)表示以e1字符串的重复，文章中我们以e*表示高级数据库马蔚字符串正则式比对技术字符串正则式比对技术 字首匹配为基础的匹配方法字首匹配为基础的匹配方法主要利用的是正因素，来寻找Q在T中的特例。使用了R(Q)的首字匹配字符串来寻找最大安全位移距离来避免每一个位置都进行测试。这种方法利用了字首的最短子串进行剔除高级数据库马蔚字符串正则式比对技
4、术字符串正则式比对技术 使用尾字符串使用尾字符串-后缀匹配提升字首匹配效率后缀匹配提升字首匹配效率的方法的方法因为不在后缀匹配中出现所以不能产生符合R(Q)的结果。因此，我们可以利用这一点提早结束自动机的验证。高级数据库马蔚字符串正则式比对技术字符串正则式比对技术高级数据库马蔚负因素与负因素与PNS模式模式 高级数据库马蔚负因素与负因素与PNS模式模式 一个PNS模式：直观的来说，我们把一个以Q的前缀匹配子串开头，负因素子串为中间，后缀子串结尾的T这样形式的子串称为PNS模式。高级数据库马蔚使用负因素提升比对效率使用负因素提升比对效率 合并算法合并算法负因素可以分割字符串成为不连接的子串，我们
5、希望对他们分别使用PS算法。记得PS算法验证每一个有效前缀匹配和它对应的每个有效后缀匹配。高级数据库马蔚使用负因素提升比对效率使用负因素提升比对效率 位并行算法位并行算法 在在|N|lmin 条件下的条件下的PNS-BITC算法算法 无条件限制的无条件限制的PNS-BITC算法算法 正正-负因素结合提升剥离效率负因素结合提升剥离效率高级数据库马蔚使用负因素提升比对效率使用负因素提升比对效率 正正-负因素结合提升剥离效率负因素结合提升剥离效率高级数据库马蔚实验效果实验效果图9显示了负因素的好处。每个上标N表示该算法已经使用负因素。由此可以看出，改进后的算法比原来的算法实现了更好的性能。例如，对于DNA数据集，负因素改进了算法性能达3倍左右。图9（a）显示对于查询Q1d， AgrepN比较Agrep把时间从171ms减少到42ms，GNU GrepN比较GNU grep把时间从222ms减少到76ms，NR-grepN比较NR-grep把时间456ms减少到154ms。图9（b）显示，使用负因素查询Q1p和Q2p时，Agrep和Gnu grep分别提高了10倍以上。高级数据库马蔚
高级数据库马蔚课件
