网络信息监控中的多模式匹配算法范文

随着网络技术的发展，网络信息安全的重要性变得日益突出，现有网络信息监控系统，在网络协议还原和分析方面的性能比较低，达不到信息监控的需要。在网络信息监控系统中，多模式匹配算法是解决对敏感内容过滤的最佳的选择，然而模式匹配在整个检测过程中需要花费大量时间，因此，模式匹配算法的性能将影响整个网络信息监控系统的工作效率。本文在AC算法的基础上，结合BM算法，提出快速的多模式匹配算法，在匹配中，跳过无用的字符，使用匹配中失败的信息，实现文本串的快速匹配，减少算法的时间复杂度。

1AC算法

AC算法是多模式匹配算法，利用有限自动机把字符比较转化为状态转移。首先，对模式串集合预处理，构成树型有限状态自动机，它包含一组状态，每个状态用一个数字来表示。状态机读取文本串中的字符，通过产生状态转移的方式或发送输出来处理文本，只需扫描一次文本串就能够找出与其匹配的模式串。

2BM算法

BM算法是一种精确字符串匹配算法。该算法将文本串和模式串的最左端对齐，然后从模式串的最后一个字符与文本串开始比较，若匹配失败，模式串则向右滑动一段距离。

3快速的多模式匹配算法———N_AC_BM算法

为了提高速度，利用模式匹配失败时所在的位置和距离，增加跳跃的距离，这就是快速的多模式匹配算法———N_AC_BM算法[1]。

3.1算法的基本思想给定一个文本串要查找模式串，从最右向左对模式串进行匹配，若找到模式串尾字符，则再从右向左比较剩余字符，最后将指针跳过尾字符所对应的距离。

3.2算法详细描述详细算法如下。

4实验结果分析

为了验证本算法，选5Mbit的一个文本串，与AC算法和BM算法进行比较，测试环境为操作系统WinXP，CPU4．8GHz、内存4GB。实验结果如表1、表2所示。通过实验可知：本文的算法，花费时间大约是BM算法的1／5，AC算法的1／3[4]。随着模式串长度的增加、模式串数目的增多，本文所设计的算法所花时间更少有很大的优势。

5结束语

在网络信息监控中模式匹配的速度是非常重要的。本文的快速的模式匹配算法———N_AC_BM算法，结合有限状态自动机的工作原理，利用单模式匹配的BM算法和多模式匹配的AC算法优点，实现了一种快速的多模式匹配算法，N_AC_BM算法通过对匹配失效字符的判断，减少了无效的跳转和匹配。实验证明，N_AC_BM算法大大提高了匹配速度，具有明显的优势。

作者：雷赟 吕静 单位：江西理工大学 图书馆 江西省图书馆