专利详情

专利名称	基于TCAM的确定性有穷状态自动机DFA的匹配方法和装置
申请号	CN201210071338.7	专利类型	发明专利
公开（公告）号	CN103294734A	公开（授权）日	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条目由源状态域、输入字符域和目的状态域三个域组成，所述源状态域由模板ID域和私有ID域两个子域组成，所述目的状态域由模板ID域和私有ID域两个子域组成，以具体的所述源状态域和输入字符域的拼接作为搜索关键词，按照所述搜索关键字在所述DFA的所有TCAM条目中进行搜索，获取搜索得到的目的状态域，将所述目的状态域中的模板ID域的值与所述搜索关键字搜索关键词中的模板ID域的值进行异或，将所述异或结果作为所述目的状态域中的最终的模板ID域的值。本发明实施例可以在不牺牲匹配速度的前提下突破DFA状态数指数膨胀的问题，大大减少了DFA所需的存储空间。