[本文摘要]

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