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

被引：11

作者：

柳厅文 ^{[1
,2
,3
]}

孙永 ^{[1
,3
]}

卜东波 ^{[1
]}

郭莉 ^{[1
,3
]}

方滨兴 ^{[1
,3
]}

机构：

[1] 中国科学院计算技术研究所

[2] 中国科学院研究生院

[3] 信息内容安全技术国家工程实验室

来源：

软件学报 | 2012年 / 23卷 / 09期

关键词：

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

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

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

引用

页码：2261 / 2272

页数：12

共 6 条

[1] 深度包检测中一种高效的正则表达式压缩算法
徐乾
鄂跃鹏
葛敬国
钱华林
[J]. 软件学报, 2009, 20 (08) : 2214 - 2226
[2] An Improved DFA for Fast Regular Expression Matching
Ficara, Domenico
Giordano, Stefano
Procissi, Gregorio
Vitucci, Fabio
Antichi, Gianni
Di Pietro, Andrea
[J]. ACM SIGCOMM COMPUTER COMMUNICATION REVIEW, 2008, 38 (05) : 31 - 40
[3] Algorithms to accelerate multiple regular expressions matching for deep packet inspection
Kumar, Sailesh
Dharmapurikar, Sarang
Yu, Fang
Crowley, Patrick
Turner, Jonathan
[J]. ACM SIGCOMM COMPUTER COMMUNICATION REVIEW, 2006, 36 (04) : 339 - 350
[4] Improved approximation algorithms for MAX k-CUT and MAX BISECTION
Frieze, A
Jerrum, M
[J]. ALGORITHMICA, 1997, 18 (01) : 67 - 81
[5] A Four Russians algorithm for regular expression pattern matching[J] . Gene Myers.Journal of the ACM （JACM） . 1992 (2)
[6] Programming Techniques: Regular expression search algorithm[J] . Ken Thompson.Communications of the ACM . 1968 (6)

← 1 →