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

摘要

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.%针对现有模式匹配算法无法实现大容量模式集快速搜索的不足,提出了一种基于TCAM多字节状态机的模式匹配算法.利用TCAM的掩码特性,切分具有相同匹配字符串的状态集,提出了一种编号编码压缩机制.通过理论证明,集合切分编码利用状态机的已匹配信息将编号存储改变为编号段存储,大幅压缩了具有相同转移字符串和目的状态的交叉转移路径,减少了TCAM表项数目.经理论分析和实验仿真,该算法不仅具有高搜索速率,而且可以减少大量相似表项,降低TCAM存储资源消耗,从而支持大容量的模式集.