 |
 |
|
|
|
摘 要：正则表达式匹配在网络安全应用中发挥着重要的作用。确定性有限自动机(Deterministic Finite Automaton，DFA)具有高速稳健的性能，因而更适合于在骨干网络环境下执行正则表达式匹配。然而，DFA 存在状态膨胀的问题。很多研究工作基于状态关系来解决DFA 的状态膨胀问题。然而目前对如何获得状态间的关系仍然缺少一种时空高效的解决办法。我们提出了一个通过有限自动机(Finite Automaton, FA)的活跃状态集来准确计算状态关系的算法，并给出了一个高效的获取所有活跃状态集的方法。实验结果证明，该方法不仅能准确地得到状态关系，而且其空间占用和时间消耗仅是已有方法的1/256 和15%左右。
关键词： 正则表达式; 状态膨胀; 状态关系; 活跃状态集
|