改进的K步长多模式匹配算法

杭州电子科技大学电子信息学院　焦鹏飞　李训根



改进的K步长多模式匹配算法

杭州电子科技大学电子信息学院焦鹏飞李训根

【摘要】K步长状态机存在失效函数，一部分存储空间被用来存储失效状态。为了提高K步长状态机的空间性能，该文通过K步长状态机的转移函数和失效函数f构建了新的转移函数，消除了K步长状态机的“失效链”。对改进算法进行性能分析表明，模式串数量和长度越大，改进后算法的空间优化效果越明显。

【关键词】多模式匹配；K步长状态机；失效链

0　引言

网络通信的高速发展使得网络安全防范显得愈加重要，模式匹配成为当前的研究热点。K步长算法的设计原理是基于Aho-Corasick状态机，以下简称AC状态机。AC状态机的匹配步长是每次一个字符，而K步长状态机则是每次K个，如果不考虑其他因素，K步长状态机性能是AC状态机的K倍。但是K步长状态机存在失效函数，一部分存储空间被用来存储失效状态。当模式串集合中出现长度很长的模式串时，则可能出现失效链很长的情况，在为存储转移表分配空间时，只能以失效链最长的那条记录为参照开辟空间。基于K步长状态机存储方面的这个缺陷，本文提出了一种消除失效链的改进K步长多模式匹配算法。

1　K步长匹配算法

K步长算法生成状态机过程如下：把待匹配的模式串按照从左向右的顺序，顺次分割成若干个长度一样的、包含K个字符的单元，如果最后少于K个字符，则补齐通配符*当作K个字符处理；分割完毕，参照AC状态机的生成方法，生成K步长状态机。K步长状态机产生失效函数f、转移函数goto和输出函数output。表示当前状态为s，输入状态为a，则当前状态会转移到；表示当前状态为s，当匹配失败时，当前状态会转移到；表示当前状态为s，输入状态为a，匹配成功，输出状态为p。goto函数、f函数、output函数经过整合，得到状态机的状态转移表。

2　改进方法

K步长匹配算法不仅要对尾部的字符进行单独处理，而且还存在“失效链”。当模式串集合中出现长度很长的模式串时，则可能出现失效链很长的情况，在为存储转移表分配空间时，只能以失效链最长的那条记录为参照开辟空间，这无疑很大地浪费了有限的存储资源。为了降低存储空间，本文对K步长状态机的转移函数进行了重定义，生成消除了“失效链”的K步长状态机。

2.1改进思想

定义：M为按步长K将模式串分割后组成的集合；Q表示用来存放状态机中状态的队列；状态转移函数表示：当前状态为s，输入状态为a，则当前状态会转移到。

{

}

while Q≠empty //遍历Q中的所有状态

{

{

图1　改进后的 K 步长状态机及状态存储结构

{

//状态s移入队列Q

}

}}

由以上分析可以得到，改进算法的空间优化率q与模式串长度n以及模式串数目m成正比。当m=200，n=30时，节省的内存开销能够达到11%左右。实际上，随着模式串数量和模式串长度的继续增大，改进算法的空间优化效果将更加明显。

3　算法性能和结果分析

测试环境：Windows 7操作系统，CPU为Intel T6670 2.20G，内存为4.00GB的个人PC机。搜索文本为VC6.0随机生成的20.4M的英文文本。令K=4，选取50到200条长度在5到30字节之间的模式串，与原始的K步长算法进行比较。测试结果如表1所示。

表1　算法空间性能比较　　单位：MB

参考文献

[1]Dharmapurikar S,Lockwood J.Fast and scalable pattern matching for content filtering. In:Berenbaum A,ed. Proc.of the 2005 Symp.on Architecture for Networking and Communications Systems.New York:ACM Press,2005. 183-192.

[2]舒银东.基于有限状态自动机的多模式匹配算法研究[D].合肥工业大学,2011.

[3]王培凤,李莉.基于Aho-Corasick算法的多模式匹配算法研究[J].计算机应用研究,2011,04:1251-1253+1259.