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

• 作者: 姜磊 姜腊林 戴琼 杨嘉佳 谭建龙
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 正则表达式 ClusterFA算法 确定型有穷自动机 游程编码 压缩率 吞吐率
• 年，卷（期）: 2014,（8）
• 所属期刊栏目: 开发研究与工程应用
• 页码范围: 282-287,292
• 页数: 7页
• 分类号: TN791
• 字数: 4506字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2014.08.054

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	姜磊	中国科学院计算技术研究所	23	137	5.0	11.0
2	谭建龙	中国科学院信息工程研究所	43	444	11.0	19.0
3	姜腊林	长沙理工大学计算机与通信工程学院	22	115	5.0	10.0
4	戴琼	中国科学院信息工程研究所	7	65	3.0	7.0
5	杨嘉佳	长沙理工大学计算机与通信工程学院	2	3	1.0	1.0