一种新的确定型有限自动机状态表示及压缩

• 作者: 于凯 张蕾 王思秀 陆光
• 来源期刊: 火力与指挥控制
• 学科: 工学
• 关键词: 深度包检测 有限自动机 内存压缩 正则表达式 状态指针
• 年，卷（期）: 2020,（1）
• 所属期刊栏目: 理论研究
• 页码范围: 12-17
• 页数: 6页
• 分类号: TP393
• 字数: 4972字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-0640.2020.01.003

摘要

针对传统DFA存在时间复杂度和空间复杂度高的问题,提出了一种新的DFA状态表示和字符-状态压缩方案.通过对传统DFA状态转换的观察发现,对于一个给定的输入来说,可以仅存储相邻状态之间的差异,从而得到一种新的DFA状态表示N-DFA;对每个大小不固定的状态设置一个状态指针来有效地减少每个指针所需要的比特数,从而得到一种基于输入字符的字符-状态压缩算法C-S;把N-DFA和C-S有效地集成在一起,进一步减少内存.实验结果表明,提出的N-DFA和C-S集成方案相比于传统的DFA和其他改进DFA方案,可以获得更好的内存压缩和加速性能.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张蕾	新疆财经大学计算机科学与工程学院	19	15	2.0	3.0
2	于凯	新疆财经大学计算机科学与工程学院	16	59	4.0	7.0
3	王思秀	新疆财经大学计算机科学与工程学院	30	37	3.0	4.0
4	陆光	北京科技大学计算机与通信工程学院	1	0	0.0	0.0