一种基于分类存储的空间高效Aho-Corasick算法

摘要

针对经典Aho-Corasick算法存在空间开销大,存储效率低的问题,提出一种改进的空间高效Aho-Corasick算法.新算法在预处理阶段根据状态转移函数、输出函数的不同特性,灵活选择不同的方式存储状态结点,实现对Aho-Corasick算法状态机的压缩.实验表明,新算法与经典Aho-Corasick算法、Bitmapped AC算法相比,以匹配阶段较小的时间性能为代价,极大幅度地压缩状态机的存储空间.%Aiming at the problem that the classical Aho-Corasick algorithm has large space overhead and low storage efficiency, an improved space-efficient Aho-Corasick algorithm is proposed.In the preprocessing stage, the new algorithm chooses different storage state nodes flexibly according to the different characteristics of the state transfer function and the output function, and achieves the compression of the Aho-Corasick algorithm state machine.Experiments show that compared with the classical Aho-Corasick algorithm and Bitmapped AC algorithm, the new algorithm can greatly reduce the storage space of the state machine at the cost of matching small time performance.