基于TCAM的非确定性有限自动机的匹配方法和装置

发明专利有效专利

申请号：
CN201210021964.5
IPC分类号：G06F17/30
申请日期：
2012-01-31
申请人：
中国科学技术大学

基础信息

权利要求

说明书

PDF全文

法律信息

引证文献

著录项信息

专利名称	基于TCAM的非确定性有限自动机的匹配方法和装置
申请号	CN201210021964.5	申请日期	2012-01-31
法律状态	授权	申报国家	中国
公开/公告日	2013-07-31	公开/公告号	CN103226551A
优先权	暂无	优先权号	暂无
主分类号	G06F17/30 ? IPC结构图谱： G 物理 G0 仪器 G06 计算；推算；计数 G06F 电数字数据处理（基于特定计算模型的计算机系统入G06N） G06F17/00 特别适用于特定功能的数字计算设备或数据处理设备或数据处理方法〔6〕 G06F17/30 信息检索；及其数据库结构〔6〕	IPC分类号	G06F17/30查看分类表>
申请人	中国科学技术大学	申请人地址	安徽省合肥市包河区金寨路*** 变更专利地址、主体等相关变化，请及时变更，防止失效
权利人	中国科学技术大学	当前权利人	中国科学技术大学
发明人	董群峰;彭坤杨
代理机构	北京凯特来知识产权代理有限公司	代理人	郑立明;黄晓军

摘要

本发明涉及一种基于TCAM(ternarycontentaddressablememory，三态内容寻址存储器)的NFA(non-deterministicfiniteautomaton，非确定性有限自动机)的匹配方法和装置。该方法主要包括：对NFA的状态和同时活跃的状态子集进行编码，将NFA的每个状态转移边用一个TCAM条目表示，将NFA的源活跃状态子集的编码和输入字符的编码的拼接作为搜索关键词，按照所述搜索关键字在NFA的所有TCAM条目中进行搜索，将获取的目的活跃状态子集的编码作为输出结果，所述源活跃状态子集为NFA当前所有同时活跃的状态的集合，所述目的活跃状态子集为在NFA中输入所述输入字符、进行状态转换后，得到的同时活跃的状态的集合。本发明实施例使得NFA的一次状态转换仅需要一次TCAM并行查找就能完成，实现了和基于DFA的正则表达式匹配技术一样的匹配速度，同时利用TCAM的三态存储能力对NFA的TCAM条目进行压缩，减少了NFA所需的TCAM存储空间。