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

• 作者: 陈围 陈庶樵
• 来源期刊: 计算机应用研究
• 关键词: 模式匹配 三态内容寻址存储器(TCMA) 集合切分 有限状态机
• 年，卷（期）: 2011,（6）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 2067-2069
• 分类号: TP393
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2011.06.018

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈庶樵		60	190	6.0	9.0
2	陈围		2	2	1.0	1.0