• 1. ACBM算法摘要 在有限自动机的多模式匹配算法(DFSA算法)的基础上, 在算法中以连续跳跃的思想,给出了另一个更加有效的改进.在一般情况下,这算法不需要匹配目标文本串中的每个字符,并充分利用了匹配过程中本次匹配不成功的信息,跳过尽可能多的字符.
  • 2. 一:建立反向有限自动机 {P}={her,where,redo} 04e1r2e3h5r6e7h8wherwhere9o10d11e12rredo-(e,r,0)
  • 3. 二:计算跳跃函数Goto(s:state,char):根据state,char计算自动机的下一个状态 Skip(char): 1: min{j+1|P[k][m[k]-j]=char (if char 在{P}中) 2: minlen+1 (if char 不在{P}中)
  • 4. {P},Skip表Char , skip(char) d 2 e 1 h 3 o 1 r 1 w 4 其他 4
  • 5. 三:匹配(1) Sregthayeurewherent 04e1r2e3h5r6e7h8w9o10d11e12r
  • 6. 三:匹配(2) Sregthayeurewherent 04e1r2e3h5r6e7h8w9o10d11e12r
  • 7. 三:匹配(3) Sregthayeurewherent 04e1r2e3h5r6e7h8w9o10d11e12r
  • 8. 三:匹配(4) Sregthayeurewherent 04e1r2e3h5r6e7h8w9o10d11e12r
  • 9. 三:匹配(5) Sregthayeurewherent 04e1r2e3h5r6e7h8w9o10d11e12r
  • 10. 王永成2002算法介绍(Wang2002)算法 发表刊物 改进的多模式匹配算法, 王永成 沈州 许一震  《计算机研究与发展》 2002 Vol.39 No.1 其他文献 改进的中文字串多模式匹配算法, 沈 洲 王永成 刘功申 《上海交通大学学报(自然科学版)》 2001 Vol.35 No.9
  • 11. Wang2002算法摘要 在有限自动机的多模式匹配算法(DFSA算法)的基础上,结合QuickSearch算法的优点,提出了一个快速的多模式字符串匹配算法.之后在算法中以连续跳跃的思想,给出了另一个更加有效的改进.在一般情况下,这两个算法不需要匹配目标文本串中的每个字符,并充分利用了匹配过程中本次匹配不成功的信息,跳过尽可能多的字符.
  • 12. Belong函数优化Belong 函数的思想是认为模式串中的字符一般不会在目标文本串中出现。在匹配时先考虑当前字符是否出现在模式中,如果不出现,则跳跃minlen长度。
  • 13. Wang2002优化算法1:预处理belong和Skip函数 2: 搜索(string ,t是下标,n是长度) while(t
  • 14. Wang2002算法作者性能 1:在模式串较长和较短的情况下,算法都有很好的性能.实验表明,在模式串较短时,所提出的算法需要的匹配时间仅为DFSA算法的1/2到1/5,在模式串较长时,所需时间为DFSA算法的1/3至1/7. 2:与FS 算法比较,本文算法在模式串较短,模式串数目少时,性能比FS优越
  • 15. Wang2002算法分析 Wang2002算法是一个Commentz-Walter(1979)类似的基于跳跃,主要贡献在于结合QuickSearch算法的连续跳跃的思想。 Wang2002算法设计了一个belong函数优化计算。
  • 16. Long-Karp-Rabin算法 新设计的Long-Karp-Rabin是一种简洁的实时(on-line)多关键词匹配算法,使用数值处理来解决字符匹配问题的思想很容易推广到其它领域。 Long-Karp-Rabin算法可以在高速网络的实时内容检测、大量攻击模式的入侵检测系统中使用。
  • 17. 设计原理(1)Long-Karp-Rabin算法也是一种跳跃型的算法,设计的主要思路是充分利用硬件多级流水线的效率,使用数值运算代替字节比较。
  • 18. 设计原理(2)流水线说明 如果一条指令3个周期,在4级流水情况8个周期完成6跳指令12345678
  • 19. 设计原理(3)在具有超流水和超标量计算机系统中,一个算法执行的时间主要和流水线长度,执行单位个数, 快速执行引擎(REE,Rapid Execution Engine)等有关。在理想情况下,一条k段线性流水线能在(k+(n-1))个周期中处理完n个任务,我们假设一个数值运算需要п个机器周期,如果п小于k,那么同样可以在(k+(n-1))周期内处理n个任务。
  • 20. 算法介绍一:分解关键词任何一个关键词y,(m=|y|),y分解成多个整数,这些整数彼此相连,同时后面一个整数前面部分和前个整数的后面部分相同。( |Y|=8分解成5个整数)
  • 21. 算法介绍二:计算Check表 通过Create-Check表算法,我们把全部关键词建立的整数集合映射到一个表中。可以看出如果字符片度z[i..i+w-1]表示的整数出现在任何一个关键词片断中,那么Check[H(z[i..i+w-1])]一定指向一个链表结构,不是一个空指针。
  • 22. 算法介绍三:关键词匹配过程 1:计算跳跃步长step= minLen / w –1; 2:size=m /w 3: p从step 到 size开始循环,p=p+ step 4:计算t=Buff[p] mod q 5: 如果Check[t] 等于空,则到第3步 6: 利用Check[t]指向的链表结构,进行完全匹配的比较,如果发现了关键词则报告,p=p+1; 继续循环到第3步
  • 23. 算法示例(1){P}={hero,where,redo} T=Sregthayeurewherent q=37
  • 24. 算法示例(2)Check表{P}={hero,where,redo} check[(‘he’)% 37]->{1,0} check[(‘er’)% 37]->{1,1} ->{2,2} check[(‘ro’)% 37]->{1,2} check[(‘wh’)% 37]->{2,0} check[(‘he’)% 37]->{2,1} check[(‘re’)% 37]->{2,3}->{3,0} check[(‘ed’)% 37]->{3,1} check[(‘do’)% 37]->{3,2}
  • 25. 算法示例(3)SregthayeurewherentCheck[‘eg’%37]->NULLCheck[‘ay’%37]->NULLCheck[‘re’%37]-> {2,3}->{3,0}{P}={hero,where,redo}
  • 26. 算法示例(4)Sregthayeurewherent check[(‘er’)% 37]->{1,1} ->{2,2}
  • 27. 优化:多张Check表 在实际实现Long-Karp-Rabin算法时,可以找到多个合适的素数q1,q2…,建立多张Check表
  • 28. 优化:完全匹配的优化本文中没有介绍使用何种方式实现完全匹配比较,实际系统可以采用比较好的判定算法来实现,即使需要完全匹配多个关键词,也可以在线性时间内完成,比如建立Aho-Corasick算法类似的树结构。我们实现的测试系统只是使用使用链表结构,对链表中的关键词依次使用普通的memcmp函数
  • 29. 合适的整数q 最短关键词长度n ,文本长度m,关键词个数k; 如果要求Long-Karp-Rabin算法的第5步判断时,Check[t]不为空指针的概率低于1%,即要求Check表的填充概率低于1%. q>1*k*(n-w+1)
  • 30. 算法时间复杂度最短关键词长度n ,文本长度m,关键词个数k 当m,n,|∑|,w,比较的次数基本上和k无关。
  • 31. 几种算法比较演示产生测试文本 Text Research Collection Volume 5, April 1997: Foreign Broadcast Information Service (1996) 抽出测试关键词集合 测试算法 Aho-Corasick Commentz-Walter Long-Karp-Rabin1 Long-Karp-Rabin2
  • 32. (本页无文本内容)
  • 33. (本页无文本内容)
  • 34. (本页无文本内容)
  • 35. (本页无文本内容)
  • 36. (本页无文本内容)
  • 37. 总结在TREC2001标准测试集[12],10~500个长度为10的随机关键词上测试,Long-Karp-Rabin比Aho-Corasick[9]快接近400%,比Commentz-Water[10]、SumWu[4]等算法也快200%~400%。当关键词长度在3左右时,SumKim1999[2]是比较快的算法。在关键词个数小于1000,Long-Karp-Rabin算法是一种比较好的选择。而关键词个数大于2000时,MultiBMD[3]是更好的选择。
  • 38. 未来的计划完善散列函数的选择使用Minmal Perfect Hash(最小完美哈希函数) 设计更依靠指令集(SSE)的算法 设计压缩情况下的直接匹配算法 跟踪第7层线性数据处理技术
  • 39. 谢谢 本文工作过程得到白硕、程学旗、 郭莉、 王斌、李栋栋、卜东波、熊锦华和安全组的全体同事等人的建议、帮助和支持,在此表示感谢 ! 谭建龙 2002、4
  • 40. 谢谢! (Question?)