专利详情

专利名称	基于TCAM的确定性有穷状态自动机DFA的匹配方法和装置
申请号	CN201210071502.4	专利类型	发明专利
公开（公告）号	CN103294735A	公开（授权）日	2013.09.11
申请（专利权）人	中国科学技术大学	发明（设计）人	董群峰;彭坤杨
主分类号	G06F17/30(2006.01)I	IPC主分类号	G06F17/30(2006.01)I
专利有效期	基于TCAM的确定性有穷状态自动机DFA的匹配方法和装置至基于TCAM的确定性有穷状态自动机DFA的匹配方法和装置	法律状态	实质审查的生效
说明书摘要	本发明涉及一种基于TCAM(ternary?content?addressable?memory，三态内容寻址存储器)的DFA的匹配方法和装置。该方法主要包括：将DFA的每个状态用若干TCAM条目表示，每个TCAM条目由源状态域、输入字符域和目的状态域三个域组成，基于生成所述DFA的非确定性有穷状态自动机NFA中的链式结构，以及所述NFA和所述DFA之间的内在链式结构特征，识别出所述DFA中的链式结构；根据所述DFA中的链式结构对所述DFA的状态进行重新编号和编码，在TCAM中对所述DFA的状态转移边进行重新编码；以具体的所述源状态域和输入字符域的拼接作为搜索关键词，按照所述搜索关键字在所述DFA的所有TCAM条目中进行搜索，将搜索得到的目的状态域作为输出结果。本发明实施例通过在TCAM中通过对DFA的状态转移边进行编码和压缩，使得DFA中的副本链式结构在TCAM中能够被合并，以达到减少存储空间的目的。