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

A Novel Deterministic Finite Automata State Representation and Compression

作　　者：张蕾[1] 于凯[1] 王思秀[1] 陆光 ZHANG Lei;YU Kai;WANG Si-xiu;LU Guang(College of Computer Science and Engineering,Xinjiang University of Finance and Economics,Urumqi 830012,China;School of Computer and Information Technology,University of Science and Technology Beijing,Beijing 100083,China)

机构地区：[1]新疆财经大学计算机科学与工程学院,乌鲁木齐830012 [2]北京科技大学计算机与通信工程学院,北京100083

出　　处：《火力与指挥控制》2020年第1期12-17,共6页Fire Control & Command Control

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

摘　　要：针对传统DFA存在时间复杂度和空间复杂度高的问题,提出了一种新的DFA状态表示和字符-状态压缩方案。通过对传统DFA状态转换的观察发现,对于一个给定的输入来说,可以仅存储相邻状态之间的差异,从而得到一种新的DFA状态表示N-DFA;对每个大小不固定的状态设置一个状态指针来有效地减少每个指针所需要的比特数,从而得到一种基于输入字符的字符-状态压缩算法C-S;把N-DFA和C-S有效地集成在一起,进一步减少内存。实验结果表明,提出的N-DFA和C-S集成方案相比于传统的DFA和其他改进DFA方案,可以获得更好的内存压缩和加速性能。In view of the high time complexity and space complexity existing in traditional DFA,a new DFA state representation and character-state compression scheme is proposed.Firstly,through observing the state transitions of the traditional DFA,it is found that,for a given input,only the differences between adjacent states can be stored and a new DFA state representation,namely NDFAs,can be obtained.Secondly,a state pointer for each size unfixed state is required to reduce effectively the number of bits required for each pointer so as to obtain a character-state compression algorithm based on the input characters,referred simply to as C-S.Finally,the C-S can be integrated effectively within the N-DFA to reduce memory further.Experimental results show that the proposed NDFA and C-S integration schemes can achieve better memory compression and speedup performance compared with traditional DFA and other improved DFA schemes.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]