著录项信息
专利名称 | 基于TCAM的非确定性有限自动机的匹配方法和装置 |
申请号 | CN201210021964.5 | 申请日期 | 2012-01-31 |
法律状态 | 授权 | 申报国家 | 中国 |
公开/公告日 | 2013-07-31 | 公开/公告号 | CN103226551A |
优先权 | 暂无 | 优先权号 | 暂无 |
主分类号 | G06F17/30 | IPC分类号 | G06F17/30查看分类表>
|
申请人 | 中国科学技术大学 | 申请人地址 | 安徽省合肥市包河区金寨路***
变更
专利地址、主体等相关变化,请及时变更,防止失效 |
权利人 | 中国科学技术大学 | 当前权利人 | 中国科学技术大学 |
发明人 | 董群峰;彭坤杨 |
代理机构 | 北京凯特来知识产权代理有限公司 | 代理人 | 郑立明;黄晓军 |
摘要
本发明涉及一种基于TCAM(ternarycontentaddressablememory,三态内容寻址存储器)的NFA(non-deterministicfiniteautomaton,非确定性有限自动机)的匹配方法和装置。该方法主要包括:对NFA的状态和同时活跃的状态子集进行编码,将NFA的每个状态转移边用一个TCAM条目表示,将NFA的源活跃状态子集的编码和输入字符的编码的拼接作为搜索关键词,按照所述搜索关键字在NFA的所有TCAM条目中进行搜索,将获取的目的活跃状态子集的编码作为输出结果,所述源活跃状态子集为NFA当前所有同时活跃的状态的集合,所述目的活跃状态子集为在NFA中输入所述输入字符、进行状态转换后,得到的同时活跃的状态的集合。本发明实施例使得NFA的一次状态转换仅需要一次TCAM并行查找就能完成,实现了和基于DFA的正则表达式匹配技术一样的匹配速度,同时利用TCAM的三态存储能力对NFA的TCAM条目进行压缩,减少了NFA所需的TCAM存储空间。