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

摘要：

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

关键词：正则表达式、深度包检测、分组算法、局部搜索、1/(1-1/k)近似

所属期刊栏目：23

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金61070026;国家重点基础研究发展计划9732007CB311100;国家高技术研究发展计划8632011AA010703;中国科学院战略性先导科技专项XDA06030200

在线出版日期：2013-03-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：2261-2272