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

摘要：

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

关键词：模式匹配、字符串匹配、Wu-Manber算法

所属期刊栏目：53

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金61672101,61272510

在线出版日期：2017-05-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1-8