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

计算机应用 ›› 2010, Vol. 30 ›› Issue (8): 2157-2160.

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

姚远¹,刘鹏²,王辉¹,笱程成¹

1.
2. 解放军信息工程大学信息工程学院

收稿日期:2010-03-01 修回日期:2010-04-04 发布日期:2010-07-30 出版日期:2010-08-01
通讯作者: 刘鹏
基金资助:
国家863计划基金资助项目;国家863计划基金资助项目

Compression algorithm of state transition table based on sparse matrix

Received:2010-03-01 Revised:2010-04-04 Online:2010-07-30 Published:2010-08-01

摘要/Abstract

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

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

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

姚远刘鹏王辉笱程成. 基于稀疏矩阵存储的状态表压缩算法[J]. 计算机应用, 2010, 30(8): 2157-2160.

[1]	李博, 黄建强, 黄东强, 王晓英. 基于异构平台的稀疏矩阵向量乘自适应计算优化[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3867-3875.
[2]	涂进兴, 李志雄, 黄建强. 基于GPU对角稀疏矩阵向量乘法的动态划分算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3521-3529.
[3]	孙梦迪, 孙忠贵, 孔旭, 韩红燕. 针对多模态图像的自适应引导形态学设计[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 560-566.
[4]	刘丽, 陈长波. 带状稀疏矩阵乘法及高效GPU实现[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3856-3867.
[5]	姜琨, 刘征, 朱磊, 李晓星. 基于有向无环图的倒排链等字长划分压缩算法[J]. 计算机应用, 2021, 41(3): 727-732.
[6]	沈亮, 王鑫, 陈曙晖. 面向移动应用识别的结构化特征提取方法[J]. 计算机应用, 2020, 40(4): 1109-1114.
[7]	徐光宪, 王栋. 基于混沌加密对抗窃听的安全网络编码方案[J]. 计算机应用, 2019, 39(5): 1374-1377.
[8]	邹腾宽, 汪钰颖, 吴承荣. 网络背景流量的分类与识别研究综述[J]. 计算机应用, 2019, 39(3): 802-811.
[9]	常征, 吕勇. 基于正则表达式的海量数据清洗系统[J]. 计算机应用, 2019, 39(10): 2942-2947.
[10]	麦涛涛, 潘晓中, 王亚奇, 苏阳. 基于预定义类的紧凑型正则表达式匹配算法[J]. 计算机应用, 2017, 37(2): 397-401.
[11]	俞艺涵, 付钰, 吴晓平. 基于改进正则表达式规则分组的内网行为审计方案[J]. 计算机应用, 2016, 36(8): 2241-2245.
[12]	卓艳男, 刘强, 姜磊, 戴琼. 基于FPGA改进电路的高性能正则表达式匹配算法[J]. 计算机应用, 2016, 36(4): 927-930.
[13]	江帆, 吴小天, 孙伟. 基于稀疏矩阵的Arnold数字图像加密算法[J]. 计算机应用, 2015, 35(3): 726-731.
[14]	仇杰, 梁久祯, 吴秦, 王培斌. 基于改进科学计算浮点数压缩算法的工业远程监控数据无损压缩方法[J]. 计算机应用, 2015, 35(11): 3232-3237.
[15]	万晓松, 王志海, 原继东. 基于稀疏矩阵面向论文索引排名的启发式算法[J]. 计算机应用, 2015, 35(10): 2733-2736.