短规则有效的快速多模式匹配算法

Short-rule-efficient rapid multi-pattern matching algorithm

随着网络技术快速发展,多模式匹配算法所处理的模式集合数目呈爆炸式增长且模式长度不统一,传统的多模式匹配算法已无法有效适应新的模式集合:不同的模式集合,同一算法呈现的性能差异明显。针对模式长度不等且分布不均匀的模式集合,提出一种改进WM的多模式匹配算法(MWM),将模式集合分为长短两个集合并构造各自的长短SHIFT表,辅助WM算法原有SHIFT表验证匹配效果,匹配过程由单一线程完成。该算法不仅减少了模式验证次数,而且提高了算法的平均跳转距离。实验结果表明,所提出的多模式匹配算法(MWM)在模式长度不等且分布不均匀的模式集合下表现出更优的性能,随着模式集合的数目增多,性能提升越明显。在模式集合数目达到100 000时,相比WM算法,该算法性能提升达到了40%。

With the rapid development of network technology,the number of pattern,used in multi-pattern matching algorithms,have experienced explosive growth in recent years,and the length of pattern is not uniform.Traditional multi-patternmatching algorithm cannot meet the newest pattern sets:the characteristic of pattern set plays largely influences onthe performance of algorithms.A novel algorithm enhanced from the Wu-Manber(WM)algorithm,namely the ModifiedWu-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 tohelp the original SHIFT built in WM to verify whether exists pattern matching more deeply under a single thread program.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 distributionand variant length of pattern set,in addition,the larger the pattern set,the better improved performance with new algorithm.Especially,when the number of pattern is100000,it improves performance by more than40percent.