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

A SPACE-EFFICIENT AHO-CORASICK ALGORITHM BASED ON CLASSIFICATION STORAGE

作　　者：汪泓才 李训根[1] 

机构地区：[1]杭州电子科技大学电子信息学院,浙江杭州310018

出　　处：《计算机应用与软件》2017年第5期279-282,316,共5页Computer Applications and Software

摘　　要：针对经典Aho-Corasick算法存在空间开销大,存储效率低的问题,提出一种改进的空间高效Aho-Corasick算法。新算法在预处理阶段根据状态转移函数、输出函数的不同特性,灵活选择不同的方式存储状态结点,实现对Aho-Corasick算法状态机的压缩。实验表明,新算法与经典Aho-Corasick算法、Bitmapped AC算法相比,以匹配阶段较小的时间性能为代价,极大幅度地压缩状态机的存储空间。Aiming at the problem that the clas sical Aho-C^orasick algorithm has large space overhead and low^ storageefficiency, an improved space-efficient Aho-Corasick algorithm is proposed. In the preprocessing stage, the newalgorithm chooses different storage state nodes flexibly according to the different characteristics of the state transferfunction 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 newalgorithm can greatly reduce the storage space of the state machine at the cost of matching small time performance.

关 键 词：AC算法 模式匹配 空间高效 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]