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

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

扫码查看
原文链接
  • 国家科技期刊平台
  • NETL
  • NSTL
  • 万方数据
  • 维普
针对传统DFA存在时间复杂度和空间复杂度高的问题,提出了一种新的DFA状态表示和字符-状态压缩方案.通过对传统DFA状态转换的观察发现,对于一个给定的输入来说,可以仅存储相邻状态之间的差异,从而得到一种新的DFA状态表示N-DFA;对每个大小不固定的状态设置一个状态指针来有效地减少每个指针所需要的比特数,从而得到一种基于输入字符的字符-状态压缩算法C-S;把N-DFA和C-S有效地集成在一起,进一步减少内存.实验结果表明,提出的N-DFA和C-S集成方案相比于传统的DFA和其他改进DFA方案,可以获得更好的内存压缩和加速性能.
A Novel Deterministic Finite Automata State Representation and Compression

张蕾、于凯、王思秀、陆光

展开 >

新疆财经大学计算机科学与工程学院,乌鲁木齐 830012

北京科技大学计算机与通信工程学院,北京 100083

深度包检测 有限自动机 内存压缩 正则表达式 状态指针

国家自然科学地区基金新疆维吾尔自治区高校科研计划青年基金资助项目

71561025XJEDU2017S036

2020

火力与指挥控制
火力与指挥控制研究会,火力与指挥控制专业情报网

火力与指挥控制

CSTPCDCSCD北大核心
影响因子：0.312
ISSN：1002-0640
年,卷(期)：2020.45(1)
  • 1