正则表达式分组的1/(1-1/k)-近似算法

• 作者: 卜东波 孙永 方滨兴 柳厅文 郭莉
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 正则表达式 深度包检测 分组算法 局部搜索 1/(1-1/k)近似
• 年，卷（期）: 2012,（9）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 2261-2272
• 页数: 12页
• 分类号: TP301
• 字数: 9366字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2012.04098

摘要

对正则表达式集合进行分组是解决DFA状态膨胀问题的一种重要方法.已有的分组算法大都是启发式的或蛮力的,分组效果很差.分析了DFA状态膨胀的原因,总结了某些正则表达式间的冲突状况.证明了当冲突非负和冲突独立时,正则表达式集合的最优k分组问题可归结为最大k割问题,从而说明该问题是NP-Hard的.基于局部搜索的思想,提出了一种分组算法GRELS来解决分组问题,并证明对最大k割问题,该算法的近似比是1/(1-1/k)与已有的分组算法相比,当分组数目相同时,GRELS算法分组结果的状态总数最少,并且集合发生变化时所需的更新时间最短.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	卜东波	中国科学院计算技术研究所	13	455	7.0	13.0
2	郭莉	中国科学院计算技术研究所	64	788	14.0	26.0
4	孙永	中国科学院计算技术研究所	9	102	4.0	9.0
6	柳厅文	中国科学院计算技术研究所	8	81	5.0	8.0