《机电工程》杂志,月刊( 详细... )
中国标准连续出版物号: ISSN 1001-4551 CN 33-1088/TH
主办单位:浙江省机电集团有限公司
浙江大学
主编:陈 晓
副 主 编:唐任仲、罗向阳(执行主编)
总 经 理:罗向阳
出 版:浙江《机电工程》杂志社有限公司
地 址:杭州市上城区延安路95号浙江省机电集团大楼二楼211、212室
电话Tel:+86-571-87041360、87239525
E-mail:meem_contribute@163.com
国外发行:中国国际图书贸易总公司
订阅:全国各地邮局 国外代号:M3135
国内发行:浙江省报刊发行局
邮发代号:32-68
广告发布登记证:杭上市管广发G-001号
在线杂志 |
当前位置: 机电工程 >>在线杂志 |
一种改进的WM多模式匹配算法
作者:蒋辉,张宇弘 日期:2008-11-03/span> 浏览:3502 查看PDF文档
一种改进的WM多模式匹配算法
蒋辉,张宇弘
(浙江大学 超大规模集成电路设计研究所,浙江 杭州 310027)
摘要:WuManber算法是一种基于后缀搜索的多模式匹配算法,该算法采用查表的方法,通过跳跃不可能匹配的字符来加速匹配,WM算法对最短模式长度敏感,最短模式长度决定了它可以跳过的字符的最大距离。针对WM算法的不足之处,提出了一个改进方法:新增了一个模式串末字符表,取得了比原算法更少的hash计算次数和更大的字符跳跃距离,从而加快了整个匹配过程的速度。最后,进行了设定模式串的最短长度和搜索文本长度的对比实验。实验结果显示,改进后的算法搜索效率明显高于原算法,特别是在模式串长度很短的情况下,效率提高非常明显。
关键词:WM算法;多模式匹配;哈希函数;后缀
中图分类号:TP301文献标识码:A文章编号:1001-4551(2008)09-0025-03
An improved WM algorithm for multipattern match
JIANG Hui, ZHANG Yu-hong
(Institute of VLSI design, Zhejiang University, Hangzhou 310027, China)
Abstract: WuManber algorithm is one of the multipattern match algorithm based on the suffix searching. The algorithm speeds up matching by looking up tables to ignore certain characters that will not be matched. WM algorithm is sensitive to minimum length of pattern which determines the maximum number of characters that can be ignored. Aimed at the shortage of WM algorithm the improvement was proposed. A new table of last character of each pattern was added, the times of hash calculation were reduced, more characters were ignored and the matching process was speeded up. In the contrast experiments that setting the minimum length of pattern and the length of text, the efficiency of improved algorithm is much better than original algorithm, especially when there are very short patterns.
Key words: WuManber(WM) algorithm; multipattern match; hash function; suffix
参考文献(Reference):
[1]AHO A V, CORASICK M J. Efficient string matching: an aid to bibliographic search[J]. Communications of the ACM,1975,18(6):333-340.
[2]WU S, MANBER U. A fast algorithm for multipattern searching[R]. University of Arizona, Tucson,1994.
[3]BOYER R S, MOORE J S. A fast string searching algorithm[J]. Communications of the ACM,1977,20(10):762-772.
[4]陈瑜,陈国龙.WuManber算法性能分析及其改进[J].计算机科学,2006,33(6):203-209.
[5]杨东红,徐恪.改进的WuManber多模式匹配算法[J].清华大学学报:自然科学版,2006,46(4):555-558.
[6]孙晓山,王强.一种改进的WuManber多模式匹配算法以应用[J].中文信息学报,2006,20(2):47-52.
[7]袁世忠,曹F.基于WM算法的多模式匹配改进算法WMN[J].计算机工程与应用,2007,43(15):128-130.
[8]马伟华,刘玉梅.一种改进的WuManber多模式串匹配算法[J].应用科技,2007,34(10):32-34.
友情链接