摘要
正则表达式匹配在网络安全应用中发挥着重要的作用.确定有限自动机(deterministic finite automaton,DFA)具有高速稳健的性能,因而更适合于在骨干网络环境下执行正则表达式匹配.然而,DFA存在状态膨胀的问题.很多研究工作基于状态关系来解决DFA的状态膨胀问题.然而目前对如何获得状态间的关系仍然缺少一种时空高效的解决办法.提出了一个通过有限自动机(finite automaton,FA)的活跃状态集来准确计算状态关系的算法,并给出了一个高效的获取所有活跃状态集的方法.实验结果证明,该方法不仅能准确地得到状态关系,而且其空间占用和时间消耗仅是已有方法的1?256和15%左右.
正则表达式匹配在网络安全应用中发挥着重要的作用.确定有限自动机(deterministic finite automaton,DFA)具有高速稳健的性能,因而更适合于在骨干网络环境下执行正则表达式匹配.然而,DFA存在状态膨胀的问题.很多研究工作基于状态关系来解决DFA的状态膨胀问题.然而目前对如何获得状态间的关系仍然缺少一种时空高效的解决办法.提出了一个通过有限自动机(finite automaton,FA)的活跃状态集来准确计算状态关系的算法,并给出了一个高效的获取所有活跃状态集的方法.实验结果证明,该方法不仅能准确地得到状态关系,而且其空间占用和时间消耗仅是已有方法的1?256和15%左右.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2012年第S2期138-144,共7页
Journal of Computer Research and Development
基金
国家"八六三"高技术研究发展计划基金项目(2011AA010703
2011AA010705)
国家自然科学基金项目(61070026
61003295)
关键词
正则表达式
状态膨胀
状态关系
活跃状态集
regular expression
state explosion
relationship between states
active state set
