基于预分类的标签传播分组算法  

Label propagation grouping algorithm based on pre classification

作　　者：陈曦[1] 陈庶樵[1] 刘大虎[2] 张鹏[3] Chen Xi;Chen Shuqiao;Liu Dahu;hang Peng(National Digital Switching System Engineering & Technology Research Center, Zhengzhou 450002, China;68002 Troop of PLA,Lanzhou 730000, China;61062 Troop of PLA, Beijing 100000, China)

机构地区：[1]国家数字交换系统工程技术研究中心 [2]中国人民解放军68002部队 [3]中国人民解放军61062部队

出　　处：《计算机应用研究》2016年第9期2786-2789,2803,共5页Application Research of Computers

基　　金：国家科技支撑计划资助项目(2014BAH30B01);国家"973"计划资助项目(2012CB315901;2013CB329014);国家"863"计划资助项目(2015AA016102;2013AA013505)

摘　　要：针对已有正则表达式分组算法的分组效果与分组时间难以平衡的问题,提出了基于预分类的标签传播分组算法。该算法分析了规则间膨胀特征,基于此对正则表达式集合进行预分类,借鉴标签传播思想对包含克林闭包的正则表达式集合分组,通过改进初始标签分配和传播过程实现快速聚敛。仿真实验证明,该算法与当前的正则表达式分组算法相比,在相同分组数情况下有着较少的状态数和更短的分组时间。Aiming at the existing regular expression grouping algorithm that grouping effect is difficult to balance with the grouping time, this paper proposed a label propagation grouping algorithm based on pre classification (PC-LPG). Firstly, the algorithm pre classified the regular expression set based on the characteristics of the expansion among the rules. Then it drew on the idea of label propagation to group the regular expression set containing Kleene closure. By improving the initial label distribution and dissemination process, it accelerated the speed of execution. Experimental results show that, compared with previous grouping algorithm, PC-LPG algorithm has the minimum number of states and grouping time for the same number of groups.

关 键 词：正则表达式 深度报文检测 分组算法 预分类 标签传播 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]