计算机工程与应用2017，Vol.53Issue(7)：1-8,8.DOI:10.3778/j.issn.1002-8331.1610-0356
短规则有效的快速多模式匹配算法
Short-rule-efficient rapid multi-pattern matching algorithm
摘要
Abstract
With the rapid development of network technology, the number of pattern, used in multi-pattern matching algo-rithms, have experienced explosive growth in recent years, and the length of pattern is not uniform. Traditional multi-pat-tern matching algorithm cannot meet the newest pattern sets: the characteristic of pattern set plays largely influences on the performance of algorithms. A novel algorithm enhanced from the Wu-Manber(WM)algorithm, namely the Modified Wu-Manber(MWM)algorithm, is responsible for pattern set which has variant length of pattern and uneven distribution. The new algorithm partitions the pattern set into long and short subset and constructs respective SHIFT table in order to help the original SHIFT built in WM to verify whether exists pattern matching more deeply under a single thread pro-gram. In fact, the new algorithm not only reduces the verification frequency but also increases the average shift distance. Experiments show that the improved multi-pattern algorithm has better performance to deal with the non-uniform distribu-tion and variant length of pattern set, in addition, the larger the pattern set, the better improved performance with new al-gorithm. Especially, when the number of pattern is 100000, it improves performance by more than 40 percent.关键词
模式匹配/字符串匹配/Wu-Manber算法Key words
pattern matching/string matching/Wu-Manber algorithm分类
信息技术与安全科学引用本文复制引用
夏念,嵩天..短规则有效的快速多模式匹配算法[J].计算机工程与应用,2017,53(7):1-8,8.基金项目
国家自然科学基金(No.61672101,No.61272510). （No.61672101,No.61272510）
