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

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