| 一种获得有限自动机状态间关系的高效算法 |
| |
| 引用本文： | 乔登科,柳厅文,孙永,郭莉.一种获得有限自动机状态间关系的高效算法[J].计算机研究与发展,2012(Z2):138-144. |
| |
| 作者姓名： | 乔登科 柳厅文 孙永 郭莉 |
| |
| 作者单位： | 中国科学院信息工程研究所;中国科学院大学;信息内容安全技术国家工程实验室;中国科学院计算技术研究所 |
| |
| 基金项目： | 国家“八六三”高技术研究发展计划基金项目(2011AA010703,2011AA010705);国家自然科学基金项目(61070026,61003295) |
| |
| 摘 要： | 正则表达式匹配在网络安全应用中发挥着重要的作用.确定有限自动机(deterministic finite automaton,DFA)具有高速稳健的性能,因而更适合于在骨干网络环境下执行正则表达式匹配.然而,DFA存在状态膨胀的问题.很多研究工作基于状态关系来解决DFA的状态膨胀问题.然而目前对如何获得状态间的关系仍然缺少一种时空高效的解决办法.提出了一个通过有限自动机(finite automaton,FA)的活跃状态集来准确计算状态关系的算法,并给出了一个高效的获取所有活跃状态集的方法.实验结果证明,该方法不仅能准确地得到状态关系,而且其空间占用和时间消耗仅是已有方法的1?256和15%左右.
|
| 关 键 词： | 正则表达式 状态膨胀 状态关系 活跃状态集 |
An Efficient Algorithm to Obtain Relations between States of Finite Automata |
| |
| Qiao Dengke,Liu Tingwen,Sun Yong,and Guo Li.An Efficient Algorithm to Obtain Relations between States of Finite Automata[J].Journal of Computer Research and Development,2012(Z2):138-144. |
| |
| Authors: | Qiao Dengke Liu Tingwen Sun Yong and Guo Li |
| |
| Affiliation: | 1,4 1(Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093) 2(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190) 3(University of Chinese Academy of Sciences, Beijing 100049) 4(National Engineering Laboratory for Information Security Technologies, Beijing 100190) |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
|
