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

1/(1-1/k)-Optimal Algorithm for Regular Expression Grouping

作　　者：柳厅文[1,2,3] 孙永[1,3] 卜东波[1] 郭莉[1,3] 方滨兴[1,3] 

机构地区：[1]中国科学院计算技术研究所,北京100190 [2]中国科学院研究生院,北京100049 [3]信息内容安全技术国家工程实验室,北京100190

出　　处：《软件学报》2012年第9期2261-2272,共12页Journal of Software

基　　金：国家自然科学基金(61070026);国家重点基础研究发展计划(973)(2007CB311100);国家高技术研究发展计划(863)(2011AA010703);中国科学院战略性先导科技专项(XDA06030200)

摘　　要：对正则表达式集合进行分组是解决DFA状态膨胀问题的一种重要方法.已有的分组算法大都是启发式的或蛮力的,分组效果很差.分析了DFA状态膨胀的原因,总结了某些正则表达式间的冲突状况.证明了当冲突非负和冲突独立时,正则表达式集合的最优k分组问题可归结为最大k割问题,从而说明该问题是NP-Hard的.基于局部搜索的思想,提出了一种分组算法GRELS来解决分组问题,并证明对最大k割问题,该算法的近似比是1/(1-1/k).与已有的分组算法相比,当分组数目相同时,GRELS算法分组结果的状态总数最少,并且集合发生变化时所需的更新时间最短.Dividing regular expression sets into multiple groups is an important process to solve the problem of DFA state explosion. Previous grouping algorithms are heuristic or are done by brute-force, which have poor grouping results. This paper analyzes the reasons of states explosion and summarizes conflicting relationship among regular expressions of some types. When conflicts are non-negative and independent, the optimum k-grouping problem of regular expression sets can be reduced to the maximum k-cut problem, which is NP-hard. Based on the idea of local searching, a new grouping algorithm named GRELS is introduced to solve the problem efficiently, which is 1/（1-1/k） -approximation for maximum k-cut problem. Comparing with previous grouping algorithms, GRELS has the minimum number of states for the same number of groups, and requires the least time to update grouping results when pattern sets change.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]