高级数据库马蔚.ppt

高级数据库,使用负因素提升字符串正则表达式比对的效率,马蔚2111305056,基础概念字符串正则式比对技术负因素与PNS模式使用负因素提升比对效率实验效果,基础概念,正则表达式正则表达式是对字符串操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。给定一个正则表达式和另一个字符串，我们可以达到如下的目的：1.给定的字符串是否符合正则表达式的过滤逻辑（称作“匹配”）；2.可以通过正则表达式，从字符串中获取我们想要的特定部分。,基础概念,正则表达式Q=(G|T)AGAT*，我们得出|Q|=6,因为有六个字母GTAGAT，RQ=GG,TG,GAG,TAG,GGA,TGA,GGT,TGT,GAGT,.。我们得出lmin=2,因为最短的元素包含两个字母。,基础概念,正则表达式设为有限字母集合。A为正则表达式且,|,(,),可以有定义如下：为正则表达式。可为空字符串。每一字符串w*也是正则表达式，表示为集合w。如果e1和e2是正则表达式分别表示为R1和R2，然后：（e1）是正则表达式且与e1表示的集合相同。（e1e2）是个正则表达式相乘。设字符串集合为x，且当e1为x，e2为y时可写为x=yz。(e1|e2)表示正则表达式的或运算。-(e1+)表示以e1字符串的重复，文章中我们以e*表示,字符串正则式比对技术,字首匹配为基础的匹配方法主要利用的是正因素，来寻找Q在T中的特例。使用了R(Q)的首字匹配字符串来寻找最大安全位移距离来避免每一个位置都进行测试。这种方法利用了字首的最短子串进行剔除,字符串正则式比对技术,使用尾字符串-后缀匹配提升字首匹配效率的方法因为不在后缀匹配中出现所以不能产生符合R(Q)的结果。因此，我们可以利用这一点提早结束自动机的验证。,字符串正则式比对技术,负因素与PNS模式,负因素与PNS模式,一个PNS模式：直观的来说，我们把一个以Q的前缀匹配子串开头，负因素子串为中间，后缀子串结尾的T这样形式的子串称为PNS模式。,使用负因素提升比对效率,合并算法负因素可以分割字符串成为不连接的子串，我们希望对他们分别使用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倍以上。,谢谢！,