基于WM多模式匹配算法的研究

摘要

模式匹配技术是计算机领域的研究热点之一。随着网络的发展，模式匹配技术应用广泛于搜索引擎、网络安全和计算生物学等方面。
　　 本文先介绍了当前模式匹配算法的研究现状以及经典的单模式和多模式匹配算法，分析了各种算法的原理以及时间复杂度，讨论了算法的优缺点，举例说明算法的执行流程，并设计试验对这些算法的时间性能进行了测试。
　　 针对WM算法的不足，对WM算法进行改进。改进算法改变了HASH表的构造方法；去除了PREFIX表，增加了一个SHIFT；并结合滑动窗口右边一个相邻字符，改进的WM算法减少了匹配过程中的比较次数，增大了滑动窗口跳跃的距离，提高了算法的时间性能。
　　 实验部分先介绍了linux防火墙内的netFilter框架以及iptables工具，然后将AC算法、WM算法和改进的WM算法嵌入到防火墙的内容过滤模块中进行对比实验。实验结果显示，改进的WM算法效率显著高于WM算法，在模式串数量多的情况下，效率提高明显。
　　 最后，对本文进行总结和展望。

目录

文摘

英文文摘

论文说明：图表目录

声明

第一章 绪论

第二章 模式匹配技术

第三章 模式匹配算法研究与分析

第四章 改进的WM 算法

第五章 实验与结果分析

第六章 总结与展望

参考文献

攻读硕士学位期间发表的论文

攻读硕士学位期间参与的科研项目

致谢