模式匹配算法在海量数据过滤系统中的应用

模式匹配算法是数据过滤系统中关键的组成部分，匹配算法的效率对整个过滤系统性能有很大的影响。为了保护网络数据安全，在传统的模式匹配算法上进行了改进，并将其应用到海量数据过滤系统中，取得了显著的效果。本文首先对传统 数据匹配算法进行介绍，然后分析在传统算法基础上改进的匹配算法，并探讨其在海量数据过滤系统中的应用，供有关人员参考。

【关键词】模式匹配算法 海量数据过滤系统 应用

信息技术的发展，网络数据量越来越庞大，一些违法分子常常通过互联网进行违法活动，严重影响网络社会秩序，给社会带来很多负能量。为了能够净化网络环境，采用数据过滤系统，但是如果数据过滤系统性能太低，就会影响网络数据过滤的质量，导致一些网络犯罪活动不能及时被制止。本文在传统的模式匹配算法上，提出了AC-BM改进算法，提高了数据过滤的效率与质量，对网络安全的维护效果更佳的明显。

1 模式匹配算法概述

1.1 单模式匹配算法

单模式匹配算法主要包括BM算法、KMP算法等。其中BM算法就是从右到左依次比较待匹配的文本。如果在某次匹配过程中出现失配现象，该算法或利用后缀信息以及坏字符跳跃，降低字符比较次数，提高匹配算法效率。KMP算法说主要是有名字首写字母分别为K、M、P三个人提出的。这种算法是在BF算法的基础上演化而来的，该算法有效的消除了指针回溯，能够利用匹配到的字符确定下次搜索位置，保证了匹配搜索的连续性。

总的两说，BM算法比KMP算法更加简单，匹配的效率也更高，是目前单模式匹配算法中实用性最强的算法。但是在模式集具有较大的规模时，BM算法的优势就显得不那么明显，甚至不能满足实际需求。

1.2 多模式匹配算法

多模式匹配算法主要包括AC算法以及AC-BM算法两种。

AC算法：AC算法是经典的多字符窜匹配算法，是KMP算法的改进模式，该算法能够在匹配前对模式集进行相关的处理，避免了模式集对匹配效率的影响。实际上，对模式集事先处理过程就是创造goto表、fail表以及output表的过程。其中goto表就是模式集状态转换表，当其无法查询时采用fail表，匹配当前位置的常常用output表来表示。这种算法较为简单，匹配的效率较高，只需要通过一次扫描就能完成对模式的匹配工作；匹配工作与待匹配内容没有直接关联；匹配算法使用范围广，对任意字符都能适用。但是这种算法对空间内存有较高的要求，如果模式集规模太大，会占用大量的空间，这样容易导致系统崩溃。

AC-BM算法：AC-BM算法就是将AC算法与BM算法有机的结合起来，不仅具备了AC算法一次扫描就能完成匹配工作的特点，还具备了BM算法能够跳跃字符的特点。AC-BM算法在匹配前也能够对待匹配的模式集进行处理，处理的方式为从后向前，，可以通过自左向右的形式对是否匹配成功进行判断。这一过程中李永乐BM算法跳跃技术。由于该算法集中了AC算法与BM算法两者的优势，所以在模式匹配效率上更加明显，提升了数据过滤系统的性能。但是随着信息技术的发展，网络数据呈现海量模式，AC-BM算法仍然不能适应这种过滤环境，需要对其进行进一步改进。

2 模式匹配算法的改进

对AC-BM算法的主要改进方式就是利用模式串匹配失败时，增大字符跳跃的距离。通过增加跳跃距离，能够简化原来算法的繁杂程序，同时对坏字符跳跃进行了有效的改进，形成改进后的AC-BM模式匹配算法。

改进后的算法中西思想就是通过对待匹配模式集自左向右的对比，在出现字符失配现象后，对后一字符是否存在与模式窜中进行有效的判断，如果不存在，可以直接跳跃模式串长度加1的距离，并进行比较。这种算法比原来的AC-BM算法相比，没有了最大字符长度限制，更加降低了匹配的次数，提高了匹配的效率。在坏字节方面，改进后的AC-BM算法能够在失配发生后，采用双字节对下一个匹配位置记性查找，极大的增加了跳跃的距离，并且简化了前缀跳跃环节，提高了数据过滤系统的性能以及运行效率。

3 改进算法在海量数据过滤系统中的应用

数据过滤系统是网络安全防护体系中一道重要的防线，利用一定的匹配算法对数据内容进行匹配，发现网络数据中存在的违法信息，及时的对其进行处理，防止这些信息在网络间蔓延与传播，净化网络环境，提高网络的安全性。数据过滤系统主要的过滤对象为文本数据，随着信息技术发展，文本数据量十分庞大，所以对过滤系统的性能有较高的要求。

海量数据过滤系统主要有数据采集系统、数据还原系统以及过滤系统三个板块构成。采集模块负责将网络中传输的MAC帧进行处理，还原出TCP和UDP流。TCP和UDP流经过还原模块后得到大量的文本数据，之后发送给过滤模块进行文本过滤。其中过滤办款主要分为两个阶段的工作。第一阶段是匹配算法预处理，就是构建规则串形式的需求信息，并构建失配跳跃skip表；第二个阶段为信息的匹配阶段，这也是过滤系统最重要的环节。通过预处理以及匹配，将最终的匹配结果以客户需求的形式传输给客户。

4 总结

本文在介绍传统模式匹配算法的基础上，提出了一种改进的匹配算法。这种算法集合了传统匹配算法的优势，弥补了传统算法的局限性，增加了匹配跳跃长度，提高了匹配执行速度，使得模式匹配算法效率大大提升。在数据过滤系统中的应用，能够及时有效的过滤客户需求的信息，对维护网络安全，促进网络技术发展具有重要的意义。相信随着我国科技水平的进步，模式匹配算法还会不断的改进与完善，为构建和谐网络、增强网络安全性做出更大的贡献。

参考文献

[1]梁威，叶梦.海量数据过滤系统中匹配算法的研究[J].宽带网络.2013，37（1）：124-125.

[2]王继刚，顾国昌，谢世博，徐立峰.高速骨干网络内容监控系统研究与设计[J].计算机研究与发展，2010，43（15）：343-345.

[3]耿建忠，刘福林.多模式匹配算法以及改进算法在海量数据过滤系统中的应用研究[J].中国科技信息，2013，39（16）：1124-1125.

[4]王刚，纪云.单模式匹配算法与多模式匹配算法的比较与应用[J].信息科技产业，2012，15（7）：166-167.

作者单位

上海交通大学 上海市 200000