%0 Journal Article
%T 正则表达式分组的1/(1-1/k)-近似算法
%A 柳厅文？
%A 孙永？
%A 卜东波？
%A 郭莉？
%A 方滨兴？
%J 软件学报
%P 2261-2272
%D 2012
%R 10.3724/SP.J.1001.2012.04098
%X 对正则表达式集合进行分组是解决dfa状态膨胀问题的一种重要方法.已有的分组算法大都是启发式的或蛮力的,分组效果很差.分析了dfa状态膨胀的原因,总结了某些正则表达式间的冲突状况.证明了当冲突非负和冲突独立时,正则表达式集合的最优k分组问题可归结为最大k割问题,从而说明该问题是np-hard的.基于局部搜索的思想,提出了一种分组算法grels来解决分组问题,并证明对最大k割问题,该算法的近似比是1/(1-1/k).与已有的分组算法相比,当分组数目相同时,grels算法分组结果的状态总数最少,并且集合发生变化时所需的更新时间最短.
%K 正则表达式
%K 深度包检测
%K 分组算法
%K 局部搜索
%K 1/(1-1/k)近似
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=4098&flag=1