Abstract: 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.

Key words: Deterministic Finite Automaton (DFA), Deep Packet Inspection (DPI), regular expression, sparse matrix, compression algorithm

摘要： 正则表达式匹配对于网络安全应用至关重要。将稀疏矩阵和索引表引入确定的有限自动机的状态转换表，提出了一种稀疏矩阵索引的状态压缩表算法，并给出了稀疏矩阵和索引表的构造方法。而后同字母压缩表算法结合，给出了该算法的优化策略。最后在实际规则集上进行评估，实验结果证明了算法的压缩效果，并进一步得出了算法的适用范围。

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