面向千万级规模网络的多模式串匹配算法的优化研究

摘要

随着互联网的日益强大，互联网上数据急剧增多，如何在海量的数据中快速准确的找到所需信息，就显得尤为重要，这就需要多模式串匹配算法。同时越来越多的人使用互联网就会使互联网的安全也变得越来越重要，如何尽可能早的识别出网络攻击行为，就需要对相关的行为进行分析比对，同样需要多模式匹配算法的应用。而且随着时代的发展，多模式串匹配算法在越来越广阔的范围里都有着相当多的运用，比如：信息安全领域中：入侵侦测系统等；在医学领域；数据挖掘，信息检索，文本编辑器，计算生物学和对象识别等等领域中均有广泛的应用。
　　本文通过对现今的几种相对主流的多模式串匹配算法的阐述总结，针对千万规模级网络上数据流的特点，在模式串集合较小的情况下选取了 AC_QS（AhoCorasick_QuickSearch）算法作为探究对象；当模式串集合规模较大，达到上万或者更大级别，或者机器实际的内存开销不足以运行 AC_QS算法时，本文选取了 KR（KarpRabin）算法作为探究对象。AC（AhoCorasick）算法在这样如此多的多模式串字符串匹配算法中是第一个时间消耗为线性的高效算法，其算法处理匹配时间短。AC_QS算法是使用AC算法的所有步骤，但在处理过程中利用 QS（QuickSearch）算法的思想进一步增加字符跳转距离而得到的算法，利用不出现字符的机制，进一步增加了匹配时跳转的字符数，改善优化了算法，提高了算法的运行效率，但其空间占用量也进一步的变高。本文在AC_QS算法的基础上主要针对其在模式串预处理过程，建立字典树和与目标文本的匹配过程三个方面进行了优化改善。对模式串预处理中的优化主要表现在提前比较不在模式串中出现的字符，划分目标段更加方便并行处理，提高访问模式串字符的访问效率。对字典树的优化，主要表现在利用有序树的方式对字典树进行存储，减少字符的比较次数。匹配过程中的优化，是在匹配过程中发现当前匹配的部分字符不可能匹配某个模式串，则将该模式串置为当前不可用状态，使得此模式串中字符变成无关字符，不进行比较，达到减少部分比较次数的目的。
　　本文针对大规模模式串集合提出的另一种基于 KR算法的优化算法，该算法是利用哈希函数的特性对字符串进行哈希计算。本文首先设计了哈希函数，然后将模式串进行合适的分类，按照设计好的哈希函数，求出模式串半段对应的哈希值，然后对目标文本串按照设定的基准长度化分片段，每次比较目标段是否含有模式串的半段。这样算法每次处理目标段的半段即可，这样极大的减少了 KR算法执行过程里的字符匹配个数，使得 KR优化算法的性能得到明显提升。
　　综上，本文设计的多模式匹配算法 AC_QS优化算法和 KR优化算法，都是针对千万级规模网络的来设计。AC_QS优化算法保证了算法的高效运行，但是需要消耗更多的内存。KR优化算法主要适用在无法为AC_QS优化算法提供充足的内存支持的情况下，能够处理相当大的模式串集合，因为算法的内存占用相当小。并通过实验对两个算法都与别的算法进行了实验比对，并分析了算法的时间复杂度和空间复杂度等相关性能指标，检验了算法，得出了最终结论。

目录

第1章 绪论

1.1课题来源与背景

1.2课题研究意义

1.3课题相关内容的国内外研究现状

1.4本文研究内容及章节安排

第2章 常见多模式匹配算法分析

2.1常见的多模式串匹配算法概述

2.2常见的多模式串匹配算法优缺点

2.3本章小结

第3章 基于AC_QS算法的优化算法

3.1引言

3.2 AC_QS算法分析

3.3 AC_QS算法的优化

3.4 DAC_QS算法描述

3.5实验结果与分析

3.6本章小结

第4章 基于KR算法的优化算法

4.1引言

4.2 KR算法的优化

4.3 DKR算法描述

4.4优化算法分析

4.5实验结果与分析

4.6本章小结

结论

参考文献

攻读硕士学位期间发表的论文及其它成果

声明

致谢

个人简历