正则表达式的DFA压缩算法

摘要：

基于确定有限自动机(DFA)的正则表达式匹配技术通常用于网络流量实时处理、病毒检测等系统中。随着正则表达式的数量不断增加,DFA的存储空间急剧膨胀。为此,提出了一种有效的DFA压缩算法-簇分割算法,首先总结了DFA的一个结构特征;然后依据此特征把DFA分割为3个部分分别存入3个矩阵中,由此构造出2个特征明显的矩阵和1个典型的稀疏矩阵;最后分别对3个矩阵进行压缩。实验表明,簇分割算法在各组数据中均达到了很好的压缩效果,空间压缩率比较稳定。

关键词： 正则表达式 DFA压缩算法 病毒检测 匹配技术

作者: 杨毅夫 刘燕兵 刘萍 郭牧怡 郭莉

作者单位: 中国科学院 计算技术研究所,北京 100190 中国科学院 研究生院,北京 100039 信息内容安全技术国家工程实验室,北京 100190 中国科学院 计算技术研究所,北京 100190 信息内容安全技术国家工程实验室,北京 100190

会议类型: 国内会议

会议名称: 第二届中国计算机网络与信息安全学术会议

会议地点: 天津

会议语种:中文

页码: 36-42

在线出版日期: 2009-10-01（万方平台首次上网日期，不代表论文的发表时间）