|
|||||
|
|
| 正则表达式分组的1/(1-1/k)-近似算法 | |
| 引用本文： | 柳厅文,孙永,卜东波,郭莉,方滨兴.正则表达式分组的1/(1-1/k)-近似算法[J].软件学报,2012,23(9):2261-2272. |
| 作者姓名： | 柳厅文 孙永 卜东波 郭莉 方滨兴 |
| 作者单位： | 1. 中国科学院计算技术研究所,北京 100190;中国科学院研究生院,北京 100049;信息内容安全技术国家工程实验室,北京 100190 2. 中国科学院计算技术研究所,北京 100190;信息内容安全技术国家工程实验室,北京 100190 3. 中国科学院计算技术研究所,北京,100190 |
| 基金项目： | 国家自然科学基金(61070026);国家重点基础研究发展计划(973)(2007CB311100);国家高技术研究发展计划(863)(2011AA010703);中国科学院战略性先导科技专项(XDA06030200) |
| 摘 要： | 对正则表达式集合进行分组是解决DFA状态膨胀问题的一种重要方法.已有的分组算法大都是启发式的或蛮力的,分组效果很差.分析了DFA状态膨胀的原因,总结了某些正则表达式间的冲突状况.证明了当冲突非负和冲突独立时,正则表达式集合的最优k分组问题可归结为最大k割问题,从而说明该问题是NP-Hard的.基于局部搜索的思想,提出了一种分组算法GRELS来解决分组问题,并证明对最大k割问题,该算法的近似比是1/(1-1/k)与已有的分组算法相比,当分组数目相同时,GRELS算法分组结果的状态总数最少,并且集合发生变化时所需的更新时间最短. |
| 关 键 词： | 正则表达式 深度包检测 分组算法 局部搜索 1/(1-1/k)近似 |
| 收稿时间： | 2010/9/17 0:00:00 |
| 修稿时间： | 2011/4/28 0:00:00 |
1/(1-1/k)-Optimal Algorithm for Regular Expression Grouping |
|
| LIU Ting-Wen,SUN Yong,BU Dong-Bo,GUO Li and FANG Bin-Xing.1/(1-1/k)-Optimal Algorithm for Regular Expression Grouping[J].Journal of Software,2012,23(9):2261-2272. | |
| Authors: | LIU Ting-Wen SUN Yong BU Dong-Bo GUO Li and FANG Bin-Xing |
| Affiliation: | 1,3 1(Institute of Computing Technology,The Chinese Academy of Sciences,Beijing 100190,China) 2(Graduate University,The Chinese Academy of Sciences,Beijing 100049,China) 3(National Engineering Laboratory for Information Security Technologies,Beijing 100190,China) |
| Abstract: | 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. |
| Keywords: | regular expression deep packet inspection grouping algorithm local searching 1/(1-1/k)-approximation |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
| 点击此处可从《软件学报》浏览原始摘要信息 | |
| 点击此处可从《软件学报》下载全文 | |