快速高效多模式匹配算法的研究与实现

摘要

模式匹配算法是计算机科学领域的一个经典的研究方向，被广泛地应用在信息检索、入侵检测系统、病毒检测、信息过滤以及生物计算等众多领域中。多模式匹配算法通过遍历一次文本串找到模式集中所有模式出现的位置。近年来，多模式匹配已经成为模式匹配的研究热点。WM算法是多模式匹配算法中效果最好的算法之一。它的性能很大程度上依赖于预处理阶段构建的三张表，PREFIX表、SHIFT表和HASH表。WM算法构建的这三张表存在明显缺陷，有很大的改进空间。本文对WM算法进行了改进，主要工作如下：
　　1、通过改进PREFIX表、SHIFT表和HASH表，设计了一个自适应哈希的WM算法：AHWM算法，提高了WM算法的时间性能。其基本改进策略为：
　　1）、将PREFIX表存储的模式串B位前缀的哈希值改进为lsp位前缀的哈希值，更大程度地过滤掉了不匹配的模式串；
　　2)、建立了两个跳转表SHIFT1表和SHIFT2表，SHIFT1表和WM算法中的SHIFT表功能一样，用于记录在一次匹配之前字符块对应的跳转距离。SHIFT2表用于记录一次匹配结束后滑动窗口可以跳转的最大安全距离，可使算法跳过很多没有必要比较的字符，加快了模式匹配过程；
　　3)、将HASH表表项数据结构由链表转换为自适应哈希子结构HASH_STRUCT。HASH_STRUCT可以根据当前哈希表槽中模式串的个数，动态地选择一种合适的数据结构来存储模式串。当模式集规模很大的时候，与链表相比，HASH_STRUCT在保证尽量少占用内存的情况下，减少了在HASH表中查找模式消耗的时间。
　　2、对AHWM算法进行了改进，提出了一种高效并行的多模式匹配算法EPPM算法。虽然AHWM算法有着很好的时间性能，但是当模式集最短模式串长度比较小时，算法的性能变差。EPPM算法克服了这个缺陷，它按照模式串长度将原来的模式集划分为四个模式子集SET1、SET2、SET3和SET4。对于每一个模式子集，使用合适的模式匹配算法，各个匹配算法之间相互独立，并发执行。SET1和SET2利用构建的TABLE1和TABLE2进行模式匹配。SET3使用AC算法进行模式匹配。SET4使用AHWM算法进行模式匹配。这样，不管最短模式串长度是大是小，都拥有较高的时间性能。
　　3、对两个算法进行了实验验证，结果表明了它们的有效性。

目录

声明

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪论

1.1 研究背景与意义

1.2 模式匹配研究现状

1.3 论文研究内容

1.4 论文组织结构

第二章 模式匹配算法综述

2.1 模式匹配定义

2.2 单模式匹配算法

2.3 多模式匹配算法

2.4 本章小结

第三章 基于自适应哈希的WM改进算法（AHWM算法）

3.1 WM算法的缺陷

3.2 WM算法的改进策略

3.3 AHWM算法流程

3.4 实验测试和结果分析

3.5 本章小结

第四章 一种高效的并行多模式匹配算法（EPPM算法）

4.1 AHWM算法的缺陷

4.2 EPPM算法改进策略

4.3 EPPM算法流程

4.4 实验测试和结果分析

4.5 本章小结

第五章 总结与展望

5.1 总结

5.2 展望

参考文献

致谢

作者简介