两种高性能多模式匹配算法的设计与实现

发布时间：2017-11-06 18:01

  本文关键词：两种高性能多模式匹配算法的设计与实现

  更多相关文章： 多模式匹配 高匹配性能 MASM算法 ELSM算法 SBT算法

【摘要】：作为计算机研究领域的核心技术之一,模式匹配算法被广泛应用于网络安全,搜索引擎以及生物计算等领域,特别是针对网络安全问题,模式匹配算法的性能更是直接影响了网络安全系统的整体性能。随着计算机网络技术的飞速发展,互联网产生的数据量也呈爆炸式增长,从而导致了模式匹配算法的研究面临着诸多新的挑战,其中主要表现为随着模式集的规模迅速增大,模式匹配算法的性能成为系统的瓶颈所在。因此绝大多数经典的模式匹配算法无法直接有效的运用到大规模模式集环境下,所以研究适用于大规模模式集环境下具有高匹配性能的模式匹配算法是当务之急,具有重要的学术研究意义和广阔的应用前景。论文的主要工作如下:1.提出了一种高匹配性能的较大规模多模式匹配算法,简称为ELSM算法。论文首先分析了一种适用于较大规模模式集而且空间复杂度低的多模式匹配算法:MASM算法,以及MASM算法在预处理阶段用于模式串压缩的Leaf-Attaching算法。虽然MASM算法空间复杂度低,但是算法的时间复杂度高,而且算法的时间复杂度和模式集的数量成正比。本论文提出的ELSM算法在保持MASM算法低空间复杂度性质下又有着较低时间复杂度。ELSM算法在预处理阶段使用改进的Leaf-Attaching算法,保证了算法在压缩大规模模式集的时候不会出现内存不足的情况。ELSM算法在模式匹配阶段对MASM算法提出了如下三种改进策略:(1)使用数组的形式来实现完全二叉搜索树,减少了算法的内存占有量并且加快了访问树节点的速度。(2)采用AC算法作为初步匹配算法,过滤掉文本串中大量不会发生模式匹配的位置,减少了算法的匹配时间。(3)使用哈希表将完全二叉搜索树分组,该策略减少了算法需要遍历的完全二叉搜索树的高度,从而减少了算法的匹配时间。最后通过实验验证ELSM算法在保留了MASM算法具有较低空间复杂度优点的基础上,有着更高的匹配性能。2.提出了一种带失效跳转机制的多模式匹配算法,简称为SBT算法。SBT算法主要基于Burst Tries数据结构实现,论文首先详细分析Burst Tries的数据结构,以及Burst Tries的字符串查找以及字符串插入过程。然后提出将Burst Tries数据结构应用于多模式匹配领域的方法,并针对在应用过程中会出现的空间复杂度过高和匹配效率低下的缺点提出了两种改进策略即空间压缩与失效跳转策略,其具体内容为:(1)SBT算法通过空间压缩策略降低了Burst Tries中节点的内存占用量,从而降低了算法的空间复杂度。(2)SBT算法的失效跳转策略充分利用了模式匹配过程中已经匹配的字符串信息,保证算法能跳过文本串中大量不会发生匹配的位置,从而提高了算法的匹配效率。最后通过设计一系列实验验证了SBT算法在匹配性能上的优越性。
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP391.1;TP393.08

【相似文献】

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

1 刘省贤;;模式匹配算法及其在农作物嫁接中的作用[J];安徽农业科学;2009年19期

2 宋华,戴一奇;入侵检测中一类允许误差的多模式匹配算法[J];清华大学学报(自然科学版);2003年07期

3 伊静,刘培玉;入侵检测中模式匹配算法的研究[J];计算机应用与软件;2005年01期

4 彭诗力,谭汉松;基于特征值的多模式匹配算法及硬件实现[J];计算机工程与应用;2005年01期

5 张春生;张晓英;王国忠;;字符串随机探测模式匹配算法[J];内蒙古民族大学学报(自然科学版);2007年06期

6 林南晖;张国军;;对模式匹配算法的存储优化研究[J];中国海洋大学学报(自然科学版);2008年S1期

7 王杰;刘亚宾;孙珂珂;;一种快速高效的模式匹配算法的应用研究[J];计算机工程与应用;2008年32期

8 周延森;汪永好;;网络入侵检测系统模式匹配算法研究[J];计算机工程与设计;2008年07期

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

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

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

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

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

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

4 朱艳;许家s，

本文编号：1148752