基于稀疏矩阵存储的状态表压缩算法  

Compression algorithm of state transition table based on sparse matrix

作　　者：姚远[1] 刘鹏[1] 王辉[1] 笱程成[1] 

机构地区：[1]信息工程大学信息工程学院,郑州450002

出　　处：《计算机应用》2010年第8期2157-2160,2217,共5页journal of Computer Applications

基　　金：国家863计划项目(2006AA01Z408;2009AA01Z201)

摘　　要：正则表达式匹配对于网络安全应用至关重要。将稀疏矩阵和索引表引入确定的有限自动机的状态转换表,提出了一种稀疏矩阵索引的状态压缩表算法,并给出了稀疏矩阵和索引表的构造方法。而后同字母压缩表算法结合,给出了该算法的优化策略。最后在实际规则集上进行评估,实验结果证明了算法的压缩效果,并进一步得出了算法的适用范围。Regular expression matching is essential for network security applications.In this paper a smi-SCT State transition Compressed Table of sparse matrix index algorithm was proposed.Firstly a sparse matrix and index table were introduced into Deterministic Finite Automaton DFA with a general create method of them.Then combined with the smi-SCT with alphabet compression table algorithm an optimization strategy of the algorithm was given.At last proved the compression effect of smi-SCT and gave the applicable scope of smi-SCT according to the experimental results on compression effects.

关 键 词：确定的有限自动机 深度包检测 正则表达式 稀疏矩阵 压缩算法 

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