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

摘要：

基于簇聚类的确定型有穷自动机(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的压缩效率.

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

所属期刊栏目：40

分类号：TN791(基本电子电路)

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

在线出版日期：2014-09-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：282-287,292