基于状态分组的高效i-DFA构造技术

• 作者: 乔登科 孙永 柳厅文 王卿 郭莉
• 来源期刊: 通信学报
• 学科: 工学
• 关键词: 正则表达式 状态膨胀 状态分组 局部搜索
• 年，卷（期）: 2013,（8）
• 页码范围: 102-109
• 页数: 8页
• 分类号: TP393.08
• 字数: 7806字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-436x.2013.08.014

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙永	中国科学院信息工程研究所	9	102	4.0	9.0
3	乔登科	中国科学院信息工程研究所	2	9	2.0	2.0
7	王卿		2	6	2.0	2.0
8	柳厅文	中国科学院信息工程研究所	8	81	5.0	8.0