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

本站小编为你精心准备了网络信息监控中的多模式匹配算法参考范文，愿这些范文能点燃您思维的火花，激发您的写作灵感。欢迎深入阅读并收藏。

随着网络技术的发展，网络信息安全的重要性变得日益突出，现有网络信息监控系统，在网络协议还原和分析方面的性能比较低，达不到信息监控的需要。在网络信息监控系统中，多模式匹配算法是解决对敏感内容过滤的最佳的选择，然而模式匹配在整个检测过程中需要花费大量时间，因此，模式匹配算法的性能将影响整个网络信息监控系统的工作效率。本文在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算法大大提高了匹配速度，具有明显的优势。

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