基于簇聚类和游程编码的正则表达式压缩算法  

Regular Expression Compression Algorithm Based on Cluster Clustering and Run-length Encoding

作　　者：杨嘉佳[1] 姜腊林[1] 姜磊[2] 戴琼[3] 谭建龙[3] 

机构地区：[1]长沙理工大学计算机与通信工程学院,长沙410114 [2]中国科学院计算技术研究所,北京100190 [3]中国科学院信息工程研究所,北京100093

出　　处：《计算机工程》2014年第8期282-287,292,共7页Computer Engineering

基　　金：国家"863"计划基金资助项目(2012AA012502);中国科学院战略性先导科技专项基金资助项目(XDA06030602)

摘　　要：基于簇聚类的确定型有穷自动机(DFA)压缩算法,即ClusterFA算法,解决了正则表达式匹配中的空间爆炸问题,但该算法的分组个数取理想值较为困难,且其类中心向量表的每一行中连续重复转移状态出现频率较高。针对该问题,提出一种改善ClusterFA算法的方案En_ClusterFA。提取类中心向量表行与行之间相同的首尾部分,并对其进行游程编码以建立索引表,对类中心向量表余下部分的转移状态进行游程编码。利用该方案对Bro,Snort和L7-filter规则集进行测试,实验结果表明,除了L7_2和L7_6规则集的压缩率分别提高到96.1%和98.1%之外,其他规则集的压缩率都提高到99%以上。与ClusterFA算法的压缩率相比,En_ClusterFA平均提高了4%,证明En_ClusterFA能够有效地提高DFA的压缩效率。In order to solve the Deterministic Finite Automata（DFA） space explosion problem,a DFA algorithm based on clustering,named ClusterFA,is proposed.However,it is difficult to take the ideal value for the number of groups for ClusterFA algorithm.The number in each line of the class center vector table,which is also named CommonTable,is continuously repeated.In order to further improve the clusterFA compression ratio,this paper puts forward a new solution：extracting the same head and tail section between lines of the CommonTable as part of the index table,and using the Run-length Encoding（RLE） technique to code the continuously repeated numbers.This algorithm is tested by Bro,Snort and L7-filter rule sets.Experimental results show that the rule sets compression ratio is up to 99％ or more except that the compression ratio of L7_2 and L7_6 increases to 96.1％ and 98.1％.Compared with the ClusterFA algorithm,the compression ratio of the En_ClusterFA improves an average of 4％.It proves that the En_ClusterFA can effectively improve the compression ratio of the DFA.

关 键 词：正则表达式 ClusterFA算法 确定型有穷自动机 游程编码 压缩率 吞吐率 

分 类 号：TN791[电子电信—电路与系统]