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

摘要

模式匹配技术广泛应用于生物信息学、网络搜索引擎、内容过滤防火墙、入侵检测系统等领域，是信息科学领域中重要的研究方向之一。随着计算机网络技术的飞速发展，网络中的信息量呈现爆炸式增长。如何提高模式匹配效率成为人们研究的热点。
　　本文介绍了模式匹配技术的国内外研究现状，探讨了模式匹配及其应用技术，研究了几种典型的模式匹配算法，包括单模式匹配BM算法、BMH算法、Sunday算法等及多模式匹配AC算法、AC_BM算法等，分析了他们的时间性能，并比较了各自的优缺点。针对AC_BM等算法的不足之处，提出一种改进的多模式匹配算法——AC_TE，该算法具有以下特点:
　　(1)基于跳跃式匹配思想，根据当前匹配窗口前两个字符确定模式树跳跃距离，保证在不发生漏检的情况下，使得模式树最大移动距离达到最短模式串长度minlen加2，从而减少匹配次数。
　　(2)构建首字符表、minlen层字符表和字符串跳跃哈希表，分别存储模式树首层字符、minlen层字符和模式树中两两相邻字符组成的字符串的跳跃值，采用多层跳跃规则查找这三个表，快速获取模式树跳跃距离，提高算法的时间效率。
　　分析了AC_TE算法模式树最大移动距离和时间复杂度。对算法进行性能测试，测试结果表明，与AC_ BMH、AC_SUNDAY算法相比，AC_TE算法具有较好时间性能。

目录

声明

致谢

摘要

第一章 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．3 研究内容

1．4 本文的组织结构

第二章 模式匹配技术

2．1 概述

2．2 模式匹配算法分类

2．3 模式匹配技术应用

2．4 模式匹配技术研究面临的问题

2．5 本章小结

第三章 模式匹配算法研究

3．1 单模式匹配算法

3．1．1 BF算法

3．1．2 KMP算法

3．1．3 BM算法

3．1．4 BMH算法

3．1．5 Sunday算法

3．2 多模式匹配算法

3．2．1 AC算法

3．2．2 AC_BM算法

3．2．3 Two-HT算法

3．3 本章小结

第四章 AC_TE多模式匹配算法

4．1 AC改进算法的不足

4．1．1 AC_BM算法的不足

4．1．2 AC_BMH算法的不足

4．1．3 AC_SUNDAY算法的不足

4．2 AC_TE算法

4．2．1 基本思想

4．2．2 AC_TE算法模式树移动规则

4．2．3 AC_TE算法预处理表

4．3 AC_TE算法描述

4．3．1 预处理阶段

4．3．2 匹配阶段

4．4 AC_TE算法匹配过程示例

4．5 AC_TE算法分析

4．5．1 模式树最大移动距离

4．5．2 匹配阶段时间复杂度

4．6 本章小结

第五章 算法性能测试

5．1 实验环境与资源

5．1．1 实验环境

5．1．2 文本串和模式串

5．2 实验目的与内容

5．3 实验结果与分析

5．3．1 模式树移动次数

5．3．2 模式树平均移动距离

5．3．3 字符比较次数

5．3．4 匹配时间

5．4 本章小结

第六章 总结与展望

6．1 总结

6．2 展望

参考文献

附录

攻读硕士学位期间的学术活动及成果情况