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

发布时间：2017-05-03 14:00

  本文关键词：基于跳跃式匹配的多模式匹配算法研究，由笔耕文化传播整理发布。

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

• 致谢7-8
• 摘要8-9
• ABSTRACT9-14
• 第一章 绪论14-17
• 1.1 研究背景与意义14
• 1.2 国内外研究现状14-15
• 1.3 研究内容15
• 1.4 本文的组织结构15-17
• 第二章 模式匹配技术17-21
• 2.1 概述17
• 2.2 模式匹配算法分类17-18
• 2.3 模式匹配技术应用18-19
• 2.4 模式匹配技术研究面临的问题19-20
• 2.5 本章小结20-21
• 第三章 模式匹配算法研究21-39
• 3.1 单模式匹配算法21-29
• 3.1.1 BF算法21
• 3.1.2 KMP算法21-22
• 3.1.3 BM算法22-25
• 3.1.4 BMH算法25-27
• 3.1.5 Sunday算法27-29
• 3.2 多模式匹配算法29-38
• 3.2.1 AC算法29-33
• 3.2.2 AC_BM算法33-35
• 3.2.3 Two-HT算法35-38
• 3.3 本章小结38-39
• 第四章 AC_TE多模式匹配算法39-47
• 4.1 AC改进算法的不足39
• 4.1.1 AC_BM算法的不足39
• 4.1.2 AC_BMH算法的不足39
• 4.1.3 AC_SUNDAY算法的不足39
• 4.2 AC_TE算法39-42
• 4.2.1 基本思想39-40
• 4.2.2 AC_TE算法模式树移动规则40
• 4.2.3 AC_TE算法预处理表40-42
• 4.3 AC_TE算法描述42-45
• 4.3.1 预处理阶段42-43
• 4.3.2 匹配阶段43-45
• 4.4 AC_TE算法匹配过程示例45-46
• 4.5 AC_TE算法分析46
• 4.5.1 模式树最大移动距离46
• 4.5.2 匹配阶段时间复杂度46
• 4.6 本章小结46-47
• 第五章 算法性能测试47-56
• 5.1 实验环境与资源47
• 5.1.1 实验环境47
• 5.1.2 文本串和模式串47
• 5.2 实验目的与内容47
• 5.3 实验结果与分析47-55
• 5.3.1 模式树移动次数47-49
• 5.3.2 模式树平均移动距离49-51
• 5.3.3 字符比较次数51-53
• 5.3.4 匹配时间53-55
• 5.4 本章小结55-56
• 第六章 总结与展望56-57
• 6.1 总结56
• 6.2 展望56-57
• 参考文献57-60
• 附录：AC_TE算法源代码60-73
• 攻读硕士学位期间的学术活动及成果情况73-74

【相似文献】

中国期刊全文数据库 前10条

1 刘磊;;多模式匹配算法的研究与优化[J];潍坊学院学报;2008年02期

2 任丛美;阮冬茹;郭彦颖;;入侵检测模式匹配算法的研究与改进[J];中国新技术新产品;2008年16期

3 张峰;;一种改进的多模式匹配算法[J];福建电脑;2010年08期

4 姚亚锋;蒋毅;;模式匹配算法及其优化[J];南通职业大学学报;2011年04期

5 万姝伊;;关于快速高效的模式匹配算法的剖析与改进[J];数字技术与应用;2011年12期

6 何文华;;基于海量数据的多模式匹配算法研究[J];计算机应用与软件;2012年04期

7 王瑞莹;邱亮;;一种新的应用于数据流关联分析的多模式匹配算法[J];东北电力大学学报;2012年04期

8 周庆勋;高效率的模式匹配算法[J];云南民族学院学报(自然科学版);2000年04期

9 刘建军,武兵,宁玉富;一种新的模式匹配算法的设计与实现[J];德州学院学报(自然科学版);2003年06期

10 程圣宇,白英杰,肖瀛,芦东昕;模式匹配算法性能测试[J];计算机应用;2003年S2期

中国重要会议论文全文数据库 前10条

1 张晓利;周荣辉;;多模式匹配算法在协议识别中的应用[A];中国电子学会第十六届信息论学术年会论文集[C];2009年

2 佟冰;张忠平;宋丽;;一种改进的多源模式匹配算法[A];2005年全国理论计算机科学学术年会论文集[C];2005年

3 王德正;;网络入侵检测系统中模式匹配算法的研究与改进[A];计算机技术与应用进展·2007——全国第18届计算机技术与应用（CACIS）学术会议论文集[C];2007年

4 朱艳;许家s，

本文编号：343105