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

A Novel Deterministic Finite Automata State Representation and Compression

针对传统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.