文档介绍：多模式匹配算法研究
multiple patterns match algorithm research
作者姓名朱俊
学位类型高校教师
学科、专业计算机应用技术
研究方向网络安全
导师及职称侯整风教授
2010 年 5 月
1
合肥工业大学
本论文经答辩委员会全体委员审查,确认符合合肥工业大
学硕士学位论文质量要求。
答辩委员会签名:(工作单位、职称)
主席:熊焰中国科学技术大学教授
委员:沈明玉合肥工业大学副教授
昂志敏合肥工业大学副教授
魏振春合肥工业大学副教授
王文联省地矿局科技信息处高级工程师
导师: 侯整风合肥工业大学教授
2
独创性声明
本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所
知,除了文中特别加以标志和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,
也不包含为获得合肥工业大学或其他教育机构的学位或证书而使用过的材料。与我一同工作
的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。
学位论文作者签字:朱俊签字日期: 2010 年 7 月 5 日
学位论文版权使用授权书
本学位论文作者完全了解合肥工业大学有关保留、使用学位论文的规定,有权保留并向国家
有关部门或机构送交论文的复印件和磁盘,允许论文被查阅或借阅。本人授权合肥工业大学可
以将学位论文的全部或部分论文内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复
制手段保存、汇编学位论文。
(保密的学位论文在解密后适用本授权书)
学位论文者签名:朱俊导师签名: 侯整风
签字日期: 2010 年 7 月 5 日签字日期:2010 年 7 月 5 日
学位论文作者毕业后去向:
工作单位: 电话:
通讯地址: 邮编:
3
多模式匹配算法研究
摘要
字符串模式匹配算法是计算机科学中一个重点领域,广泛应用于搜索引擎、
计算机病毒特征码匹配、网络入侵检测等领域中。
首先,本文介绍了模式匹配研究的背景、意义和研究现状,概述了模式匹配
技术,包括模式匹配原理,模式匹配检测规则,模式匹配系统特点,模式匹配
算法分类等。
本文接下来综述了经典模式匹配算法,包括单模式匹配算法 BM 算法、BF
算法等和多模式匹配算法 AC 算法、AC-BM 算法等。分析了 AC 算法,提出了一
种改进的多模式匹配算法 IAC 算法,描述了改进算法的基本思想,分析了改进
算法的预处理阶段、匹配阶段和移动规则,并对改进算法的时间复杂度和空间
复杂度进行了分析,最后对改进算法进行了测试。测试结果表明,与标准 AC
算法相比,改进算法在比较次数上有一定的减少,在时间性能上有所提高。
最后,本文对模式匹配算法做了总结和展望。
关键词: 网络安全;模式匹配;AC 算法
4
multiple patterns match algorithm research
ABSTRACT
The character string pattern matching algorithm is in puter science a key field,
widely applies in the search engine, computer virus domains and so on condition code
match, network invasion examination.
First, this dissertation introduced the pattern matching research's background, the
significance and the research present situation, have outlined the pattern matching
technology, including pattern matching principle, pattern matching examination rule,
pattern matching system characteristic, pattern matching