正则表达式的DFA压缩算法

• 作 者: 杨毅夫[1]刘燕兵[1]刘萍[2]郭牧怡[1]郭莉[2]
• 机 构: 中国科学院 计算技术研究所,北京 100190 中国科学院 研究生院,北京 100039 信息内容安全技术国家工程实验室,北京 100190
• 出 处: 第二届中国计算机网络与信息安全学术会议
• 发表日期: 2009年期

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