一种基于双重状态编码的多模式匹配算法

摘要：

基于自动机的多模式匹配算法是网络内容过滤与业务监管的核心技术之一,但随着模式集合的扩大,对存储资源消耗过大.为降低当前匹配算法的空间复杂度,同时保持较低的时间复杂度,提出了一种基于关键字预处理和状态编码的优化方法.关键字预处理用于过滤冗杂内容,大大降低了处理复杂度；而采用状态编码消除了NFA中的大量failure转移,可有效降低其开销.理论分析和实验仿真表明,相对于传统的基于TCAM的匹配算法,该算法在大大减少内存需求的情况下,实现了模式的高效匹配.

关键词：模式匹配、非确定性有限自动机(NFA)、三态内容寻址存储器(TCAM)、状态编码

所属期刊栏目：29

分类号：TP393(计算技术、计算机技术)

资助基金：国家”863”计划资助项目2009 AA01A346

在线出版日期：2012-07-27（万方平台首次上网日期，不代表论文的发表时间）

页码：1887-1890