PARA-AC:一种基于AC自动机的高性能匹配算法

摘要

原始AC自动机由于匹配性能低,无法满足当前大数据环境下大规模特征串实时匹配的应用需求.针对这一问题,提出一种基于多线程的多模式串匹配加速算法,称之为PARA-AC(Parallel Aho-Corasick automaton).该算法将待匹配字符串切割成若干字符子串以及若干切割点边界字符集,并将字符子串、切割点边界字符集输入至线程池中进行匹配,从而实现字符串的并行化加速处理.实验结果表明,与原始AC自动机匹配算法相比,PARA-AC算法显著提高了匹配速度,约为原始AC的13.91倍.