发明名称 |
利用改进的Wu-Manber算法进行多模式串匹配的方法 |
摘要 |
本发明提供一种利用改进的Wu-Manber算法进行多模式串匹配的方法,包括以下步骤:1)预处理模式串:依照某个方式对每个模式串进行HASH处理,计算每个HASH值对应的移动距离;对于HASH到同一个值的多个模式串,采用AVL树存储,以加快匹配速度;2)搜索:每次读取一块字符,并计算其HASH值,取该HASH值对应的移动距离,如果距离大于0,则直接移动比较窗口继续搜索,否则在该HASH值对应的AVL树中搜索,在AVL树中搜索完成后移动比较窗口继续搜索。由此,本发明增大了移动距离,显著加快了匹配过程。 |
申请公布号 |
CN101251845A |
申请公布日期 |
2008.08.27 |
申请号 |
CN200810019727.9 |
申请日期 |
2008.03.13 |
申请人 |
苏州爱迪比科技有限公司;网经科技(苏州)有限公司 |
发明人 |
刘继明;王东泉;谢炜;林恩峰 |
分类号 |
G06F17/30(2006.01) |
主分类号 |
G06F17/30(2006.01) |
代理机构 |
南京苏科专利代理有限责任公司 |
代理人 |
陈忠辉;姚姣阳 |
主权项 |
1.利用改进的Wu-Manber算法进行多模式串匹配的方法,包括以下步骤——1)预处理模式串:计算每个模式串对应的SHIFT数组,并将该串插入对应的链表或AVL树;a)计算SHIFT数组:模式串P,只考虑P的前lmin个字符,每B个字符为一块,计算HASH值,设该HASH值对应的移动距离s1,该字符块到模式串末端的距离为s2,则该HASH值对应的移动距离重新置为s1和s2的最小值;计算P末端的B个字符的HASH值,将该HASH值对应的移动距离最高位置1;b)模式串插入:模式串P,只考虑前lmin个字符,计算P的后B个字符的HASH值,若其对应的模式串个数小于给定值N,则插入模式串链表,否则计算P的前B个字符的HASH值,以此为关键字插入对应的AVL树;2)搜索:比较窗口长度为lmin个字符,在当前比较窗口下,计算后B个字符块的HASH值,取对应的移动距离shift,若最高位不为1,则直接将比较窗口向右移动shift,否则取该HASH值对应的链表或AVL树,在其中搜索,然后将比较窗口向右移动,移动距离为将最高位清0的shift。 |
地址 |
215021江苏省苏州市工业园区机场路328号国际科技园1630-1单元 |