-
题名基于簇聚类和游程编码的正则表达式压缩算法
被引量：1
- 1
-
-
作者
杨嘉佳
姜腊林
姜磊
戴琼
谭建龙
-
机构
长沙理工大学计算机与通信工程学院
中国科学院计算技术研究所
中国科学院信息工程研究所
-
出处
《计算机工程》
CAS
CSCD
2014年第8期282-287,292,共7页
-
基金
国家"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的压缩效率。
-
关键词
正则表达式
clusterfa算法
确定型有穷自动机
游程编码
压缩率
吞吐率
-
Keywords
regular expression
clusterfa algorithm
Deterministic Finite Automata DFA）
Run-length Encoding （RLE）
compression ratio
throughput
-
分类号
TN791
[电子电信—电路与系统]
-
