[发明专利]基于TCAM的非确定性有限自动机的匹配方法和装置有效
| 申请号： | 201210021964.5 | 申请日： | 2012-01-31 |
| 公开（公告）号： | CN103226551A | 公开（公告）日： | 2013-07-31 |
| 发明（设计）人： | 董群峰;彭坤杨 | 申请（专利权）人： | 中国科学技术大学 |
| 主分类号： | G06F17/30 | 分类号： | G06F17/30 |
| 代理公司： | 北京凯特来知识产权代理有限公司 11260 | 代理人： | 郑立明;黄晓军 |
| 地址： | 230026 安*** | 国省代码： | 安徽;34 |
| 权利要求书： | 查看更多 | 说明书： | 查看更多 |
| 摘要： | 本发明涉及一种基于TCAM(ternary content addressable memory，三态内容寻址存储器)的NFA(non-deterministic finite automaton，非确定性有限自动机)的匹配方法和装置。该方法主要包括：对NFA的状态和同时活跃的状态子集进行编码，将NFA的每个状态转移边用一个TCAM条目表示，将NFA的源活跃状态子集的编码和输入字符的编码的拼接作为搜索关键词，按照所述搜索关键字在NFA的所有TCAM条目中进行搜索，将获取的目的活跃状态子集的编码作为输出结果，所述源活跃状态子集为NFA当前所有同时活跃的状态的集合，所述目的活跃状态子集为在NFA中输入所述输入字符、进行状态转换后，得到的同时活跃的状态的集合。本发明实施例使得NFA的一次状态转换仅需要一次TCAM并行查找就能完成，实现了和基于DFA的正则表达式匹配技术一样的匹配速度，同时利用TCAM的三态存储能力对NFA的TCAM条目进行压缩，减少了NFA所需的TCAM存储空间。 | ||
| 搜索关键词： | 基于 tcam 确定性 有限 自动机 匹配 方法 装置 | ||
【主权项】：
一种基于TCAM的非确定性有穷状态自动机的匹配方法，其特征在于，包括：对非确定性有穷状态自动机NFA的状态和活跃状态子集进行编码，将所述NFA的每个状态转移边用一个三态内容寻址存储器TCAM条目表示，每个TCAM条目由匹配域和目的域组成，所述匹配域包括：源状态域、输入字符域，所述目的域包括目的状态域或者包括目的状态域和掩码域；将所述NFA的源活跃状态子集的编码和输入字符的编码的拼接作为搜索关键词，按照所述搜索关键字在所述NFA的所有TCAM条目的匹配域中进行搜索，将获取的目的活跃状态子集的编码作为输出结果，所述源活跃状态子集为所述NFA当前所有同时活跃的状态的集合，所述目的活跃状态子集为在所述NFA中输入所述输入字符、进行状态转换后，得到的同时活跃的状态的集合。
下载完整专利技术内容需要扣除积分，VIP会员可以免费下载。
该专利技术资料仅供研究查看技术是否侵权等信息，商用须获得专利权人授权。该专利全部权利属于中国科学技术大学，未经中国科学技术大学许可，擅自商用是侵权行为。如果您想购买此专利、获得商业授权和技术合作，请联系【客服】
本文链接：http://www.vipzhuanli.com/patent/201210021964.5/，转载请声明来源钻瓜专利网。
- 上一篇：访问数据库的方法和装置以及数据库管理系统
- 下一篇：隔离型高速数据采集卡
