 |
 |
|
|
|
基于状态分组的高效i-DFA构造技术
摘要：正则表达式匹配在很多网络安全领域起着非常重要的作用。确定性有限自动机（DFA, deterministic finite automaton）具有线速稳定的匹配性能，因而更适合在高速网络环境下执行正则表达式匹配。但DFA可能由于状态膨胀而占用巨大的内存空间。作为状态膨胀问题的一种经典解决方案，i-DFA在大幅降低内存开销的同时，还能保证最差匹配性能。然而，已有方法狗仔i-DFA时再时间和空间上都是非常低效的，基于状态分组的思想，提出了一种高效的i-DFA构造方法。进一步地，对状态分组进行了形式化描述，并证明了获得最优状态分组是NP困难的，并基于局部搜索的思想提出了一种近优的状态分组算法。实验结果表明，相比经典的i-DFA构造方法，所做的工作在时间和空间上都有极大的改进：i-DFA的状态规模可能只是已有方法的2/3，而构造i-DFA所用时间仅是已有方法的1/16。
关键词：正则表达式；状态膨胀；状态分组；局部搜索
|