多模式AC算法优化研究

多模式AC算法优化研究1概述模式匹配问题是计算机科学中的一个基本问题，其研究内容在信息检索、模式识别、入侵检测、生物信息等方面有重要广泛的应用。模式匹配是实质是字符串匹配。字符串匹配是指在文本𝑇=𝑡1𝑡2⋯𝑡𝑛中是匹配是否有模式串𝑃=𝑝1𝑝2⋯𝑝𝑖出现。字符串匹配分为单模式匹配和多模式匹配。单模式匹配就是一次只匹配一个模式串，经典的单模式匹配算法有KMP(Knuth-Morris-Pratt)算法和BM(Boyer-Moore)算法。KMP算法实现了无回溯匹配，字符串中的每个字符只匹配一次，时间复杂度为O(n+m)[1]；BM算法采用跳跃方式，匹配时跳过不需匹配的字符，最优情况下的时间复杂度为O(n/m)，平均情况下也大大优于KMP算法[2]；文献[3]取掉BM算法的好后缀试探(GoodSuffixHeuristic)，形成BMH(Boyer-Moore-Horspool)算法，实验证明BMH算法性能在自然语言环境下比原始BM算法还要好。字符串集合匹配是从文本Text中一次查找多个字符串的所有出现，最经典的是AC(AhoandCorasick)算法。该算法将待匹配的多个字符串转换为树状有限状态自动机，然后进行扫描匹配，最优情况和平均情况的时间复杂度都为O(n)[4]；针对AC算法的改进算法有很多，文献[]提出了一种AC算法与BMH算法结合算法，改进后的算法匹配效率明显提升。AC自动机存在着内存占用量大的缺点，尤其是进行正则表达式匹配，会出现内存爆炸的情况，针对这个问题，文献[]根据统计发现AC自动机在匹配过程中，访问深度为5的概率为7.75%，访问深度为6的概率为2.33%，从第六个字符开始访问频率更少。为此提出了只建立前5个字符的半AC自动机而第6个字符以后的字符，即以字符串的形式存储在自动机叶结点的尾部。匹配时，用前5个字符的半自动机进行过滤，前5个字符全部命中，而后再用尾部的剩余字符串进行验证。本文基于半AC自动机，使用Hash函数，提出了AC-Hash算法，算法不仅减小了自动机的存储容量，而且匹配精度更高，半自动机可以实现**%模式串的精确匹配。2Aho-Corasick算法2.1基本的Aho-Corasick算法Aho-Corasick自动机算法（简称AC自动机）1975年产生于贝尔实验室。该算法应用有限自动机巧妙地将字符比较转化为了状态转移。此算法有两个特点，一个是扫描文本时完全不需要回溯，另一个是时间复杂度为O(n)，时间复杂度与关键字的数目和长度无关。AC算法思想是用多模式串建立一个确定性的树形有限状态机，以主串作为该有限状态机的输入，使状态机进行状态的转换，当到达某些特定的状态时，说明发生模式匹配在预处理阶段，AC自动机算法建立了三个函数，即转向函数goto，失效函数failure和输出函数output，由此构造了一个树型有限自动机。goto函数，指的是一种状态之间的转向关系。g(pre,x)=next：状态pre在输入一个字符x后转换为状态next。如果在模式串中不存在这样的转换，则next=failstate，goto函数通过一个二维数组来存储数据。failure函数，是在比较失配的情况下使用的转换关系。在构造转向函数时，某状态遇到匹配失败时，从该状态开始回退查找，查找其父节点的孩子节点中是否有该状态，如果存在将失配状态的失败指针指向该加点，否则失败指针指向初始状态。Output函数，是由来标记在某个状态是否已经发生了匹配，发生匹配则将匹配的模式串输出。2.2去掉failstate函数的Aho-Corasick算法算法使用确定性有限状态机构造一个next函数。确定性有限状态机由一系列确定状态S和next函数δ构成，对于任意状态s和输入符a，S中有唯一的一个确定的状态δ(s,a)=s′与之对用，δ函数构造过程就是将goto函数和failure函数构造过程合并。构造确定性有限状态机比2.3算法性能分析