正则表达式的DFA压缩算法  

Effective algorithm of compressing regular expressions' DFA

作　　者：杨毅夫[1,2,3] 刘燕兵[1,2,3] 刘萍[1,3] 郭牧怡 郭莉[1,3] 

机构地区：[1]中国科学院计算技术研究所,北京100190 [2]中国科学院研究生院,北京100039 [3]信息内容安全技术国家工程实验室,北京100190

出　　处：《通信学报》2009年第S1期36-42,共7页Journal on Communications

基　　金：国家重点基础研究发展计划("973"计划)基金资助项目(2007CB311100)~~

摘　　要：基于确定有限自动机(DFA)的正则表达式匹配技术通常用于网络流量实时处理、病毒检测等系统中。随着正则表达式的数量不断增加,DFA的存储空间急剧膨胀。为此,提出了一种有效的DFA压缩算法——簇分割算法,首先总结了DFA的一个结构特征;然后依据此特征把DFA分割为3个部分分别存入3个矩阵中,由此构造出2个特征明显的矩阵和1个典型的稀疏矩阵;最后分别对3个矩阵进行压缩。实验表明,簇分割算法在各组数据中均达到了很好的压缩效果,空间压缩率比较稳定。Regular expression matching technology based on DFA is often used in network real-time processing and virus detection systems.With the number of regular expressions growing, the storage of DFA expands rapidly.An effective algorithm of compressing regular expressions' DFA was presented, which was called cluster-split algorithm.Firstly, a structural characteristic of DFA was summarized.Secondly, the DFA was divided into three parts based the characteristic.Finally, the three parts was compressed respectively.Experiments show that cluster-split algorithm achieves good effects in all test data, and its space compression rate is relatively stable.

关 键 词：字符串匹配 自动机压缩 正则表达式 入侵检测 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]