采用集合切分编码的大容量模式匹配算法  

Large-capacity pattern matching algorithm using set-segment coding

作　　者：陈围[1] 陈庶樵[1] 

机构地区：[1]国家数字交换系统工程技术研究中心,郑州450002

出　　处：《计算机应用研究》2011年第6期2067-2069,共3页Application Research of Computers

基　　金：国家"863"计划资助项目(2009AA01A346);国家"973"计划资助项目(20070B307102)

摘　　要：针对现有模式匹配算法无法实现大容量模式集快速搜索的不足,提出了一种基于TCAM多字节状态机的模式匹配算法。利用TCAM的掩码特性,切分具有相同匹配字符串的状态集,提出了一种编号编码压缩机制。通过理论证明,集合切分编码利用状态机的已匹配信息将编号存储改变为编号段存储,大幅压缩了具有相同转移字符串和目的状态的交叉转移路径,减少了TCAM表项数目。经理论分析和实验仿真,该算法不仅具有高搜索速率,而且可以减少大量相似表项,降低TCAM存储资源消耗,从而支持大容量的模式集。In the view of the existing pattern matching algorithms＇ disadvantages on high-speed searching with large-capacity patterns,this paper presented a pattern matching algorithm based on multi-byte finite automata for TCAM.It segmented the set with the same matched string by the mask feature of TCAM,and proposed a number coding method.With the theoretical proof,this method changed the number storage into a range storage by the matched information of finite automata,could reduce the cross transitions which had the same character and purpose state drastically.Through the theoretical analysis and simulation,it comes to a conclusion that this algorithm can not only support high searching speed,but also reduce similar entries and storage resources of TCAM,and has high-capacity of pattern database.

关 键 词：模式匹配 三态内容寻址存储器(TCMA) 集合切分 有限状态机 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]