0 引言
模式串匹配的作用是给定一组特定的字符串集合 S={s1，s2，…，sm}，对于任意一个字符串T=t1t2…tn，找出S中所有字符串在T中出现的位置[1]。基于Aho-Corasick(AC)自动机的模式串匹配算法在当前的串匹配算法中占据着重要地位，它以Trie树为基础，通过fail指针来实现状态匹配失效的过程跳转，保持了较为稳定的匹配性能。因此，基于AC自动机的串匹配算法在字符串搜索、生物特征识别、网络安全等领域有着广泛的应用。
截至目前，已经提出了各式各样的AC自动机优化算法，包括基于前缀识别的自动机算法AC[2]、基于状态转移表加速的算法[3]、利用字符跳跃的加速匹配算法[4]。但是，这些算法的处理过程本质上为串行匹配，因而匹配性能较低，无法满足大数据环境下的高性能数据实时处理要求。此外，直接对AC自动机进行简单并行化易出现假阴性错误。
因此，针对原始AC自动机匹配速度较慢的问题，本文提出了一种基于多线程并行化的多模式串加速匹配算法。通过将文本分割成若干文本段进行多线程加速匹配，同时为保证算法功能的正确性，提取出切割点附近的边界字符形成切割点边界字符集进行处理。理论分析与实验结果表明，此算法与原始AC自动机的性能加速比达到8.38，性能提高接近1个数量级，非常适合于大规模数据的实时处理。
本文详细内容请下载：http://www.chinaaet.com/resource/share/2000003063
作者信息：
熊仁都1，杨嘉佳1，朱广宇1，唐 球1，隋 然2
(1.华北计算机系统工程研究所，北京100083；2.中央军委后勤保障部 信息中心，北京100842)
此内容为AET网站原创，未经授权禁止转载。
