多模式AC算法优化研究

多模式串匹配之AC自动机算法（Aho-Corasick算法）简介与C语言程序实现源码参考任侠发布于2011-03-22 22:27:53一、概述AC自动机算法全称Aho-Corasick算法，是一种字符串多模式匹配算法。

该算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。

AC算法用于在一段文本中查找多个模式字符串，即给你很多字符串，再给你一段文本，让你在文本中找这些串是否出现过，出现过多少次，分别在哪里出现。

该算法应用有限自动机巧妙地将字符比较转化为了状态转移。

此算法有两个特点，一个是扫描文本时完全不需要回溯，另一个是时间复杂度为O(n)，时间复杂度与关键字的数目和长度无关，但所需时间和文本长度以及所有关键字的总长度成正比。

AC算法有三个主要步骤，一个是字典树tire的构造，一个是搜索路径的确定（即构造失败指针），还有就是模式匹配过程。

学习AC自动机算法之前，最好先熟悉KMP算法，因为KMP算法与字典树tire的构造很是类似。

KMP算法是一种经典的单字符串匹配算法。

二、AC算法思想AC算法思想：用多模式串建立一个确定性的树形有限状态机，以主串作为该有限状态机的输入，使状态机进行状态的转换，当到达某些特定的状态时，说明发生模式匹配。

下图是多模式he/ she/ his /hers构成的一个确定性有限状态机，做几点说明：图2.11、该状态机优先按照实线标注的状态转换路径进行转换，当所有实线标注的状态转换路径条件不能满足时，按照虚线的状态转换路径进行状态转换。

如：状态0时，当输入h，则转换到状态1；输入s，则转换到状态3；否则转换到状态0。

2、匹配过程如下：从状态0开始进行状态转换，主串作为输入。

如主串为：ushers，状态转换的过程是这样的：图2.23、当状态转移到2，5，7，9等红色状态点时，说明发生了模式匹配。

如主串为：ushers，则在状态5、2、9等状态时发生模式匹配，匹配的模式串有she、he、hers。

AC经典多模式匹配算法多模式匹配AC算法（Aho and Corasick），BM、Wu-Manber算法，WM 由BM派生，不过AC与它们无染，是另外一种匹配思路。

1.Step1:将由patterns组成的集合（要同时匹配多个patterns嘛）构成一个有限状态自动机。

Step2:将要匹配的text作为自动机输入，输出含有哪些patterns及patterns在全文中位置。

自动机的执行动作由三个部分组成：（1）一个goto function（2）一个failure function（3）一个output function我们先通过一个具体实例来了解一下这三个部分，及该自动机的运作方式。

先有个大概印象，后面会具体讲解。

patterns集合{he,she,his,hers}，我们要在”ushers”中查找并匹配。

(1)goto functioni123456789f(i)000120303（发现没？貌似i和f(i)有相同前缀哦^_^）(2)failure functioni output(i)2{he}5{she,he}7{his}9{hers}(3)output function首先我们从状态0开始，接收匹配字符串的第一个字符u，在goto（简称goto function）中可以看到回到状态0，接着第二个字符s，发现转到状态3，在output中查找一下output(3)为空字符串，说明没有匹配到patterns。

继续匹配h，转到状态4，查找output发现仍然没有匹配，继续字符e，状态转到了5，查找output，发现output(5)匹配了两个字符串she和he，并输出在整个字符串中的位置。

然后接着匹配r，但发现g(5,r)=fail，这时候我们需要查找failure，发现f(5)=2，所以就转到状态2，并接着匹配r，状态转移到了8，接着匹配s，状态转移到了9，查看output，并输出output(9):hers，记录下匹配位置。

AC算法BM算法AC算法（Aho-Corasick Algorithm）AC算法是一种字符串算法，通常用于在一段文本中查询多个模式串的出现情况。

它是由Alfred V. Aho和Margaret J. Corasick于1975年提出的，并以他们的名字命名。

AC算法的原理是构建一个有限状态机（FSM），该状态机能够同时处理多个模式串的匹配。

该算法具有高效的时间和空间复杂度，并且能够在一次扫描内找到所有模式串的匹配位置。

下面将介绍AC算法的详细步骤：1. 构建Trie树（前缀树）：根据给定的模式串集合，构建一个Trie树。

Trie树是一种特殊的字典树，它能够实现快速的字符串匹配。

Trie树的根节点为一个空节点，每个节点都有多个子节点，每个子节点都代表一个字符。

从根节点到叶子节点的路径上的所有字符组成一个模式串。

2. 构建失败指针（Fail Pointer）：在Trie树中，每个节点的失败指针指向它的最长后缀节点，该后缀节点也是Trie树的节点。

如果一个节点的当前字符在其最长后缀节点的子节点中不存在，则将失败指针指向最长后缀节点的失败指针指向的节点。

如果没有最长后缀节点，则将失败指针指向根节点。

3. 在文本中匹配模式串：从文本的第一个字符开始，按照Trie树的路径进行匹配。

如果在一些节点匹配失败，则通过失败指针转移到下一个节点进行匹配，直到匹配成功或到达文本的末尾。

当匹配成功时，可以通过沿着失败指针回溯，找到其他可能的匹配位置。

4.输出匹配结果：对于每个文本字符，记录匹配的模式串。

使用一个结果链表，其中每个节点包括一个指向匹配的模式串的指针和该模式串在文本中的位置。

AC算法的时间复杂度为O(n+m)，其中n是文本的长度，m是模式串的总长度。

空间复杂度为O(m)，即模式串的长度。

BM算法（Boyer-Moore Algorithm）BM算法是一种字符串和匹配算法，通过对模式串的后缀进行预处理，实现在文本中的快速。

基于AC_QS多模式匹配算法的优化研究作者：董志鑫方滨兴来源：《智能计算机与应用》2017年第05期摘要：随着互联网的日益强大，互联网上数据急剧增多，如何在海量的数据中快速准确地找到所需信息，就显得尤为重要，这就需要多模式串匹配算法。

多模式串匹配算法在越来越多的领域里都有应用，比如：信息安全领域中，入侵检测系统、防火墙等，在医学领域、数据挖掘、信息检索等等领域中均有广泛的应用。

AC算法在多模式串匹配算法中是一个能达到线性时间的算法，其算法效率较高，AC_QS算法是在AC算法基础上增加坏字符规则，进一步增加了AC算法的匹配效率，但其空间复杂度较高。

本文在AC_QS算法的基础上，对算法预处理和匹配过程中继续优化，并对字典树存储时进行了优化，使算法在空间和时间复杂度上得到进一步优化，提高了算法性能。

实验结果也验证了该算法的高效性。

关键词：多模式；模式匹配； AC算法； QS算法中图分类号： TP301文献标志码： A文章编号： 2095-2163（2017）05-0100-04Abstract： With the Internet becoming more and more powerful and the data increasing dramatically on the internet， it is very important to find the needed information quickly and accurately in the mass of data， so it is determined to require multipatterns string matching algorithm. Multi-patterns string matching algorithm has been used in more and more fields such as information security， intrusion detection system and firewall， data mining and medicine， and also has a wide range of applications in the field of information retrieval and so on. AC algorithm in multipatterns string matching algorithm is a linear time algorithm， which can achieve high efficiency. AC_QS algorithm is to increase the bad character in the AC algorithm and then improve the matching efficiency of AC algorithm， but its space complexity is high. In this paper， based on the AC_QS algorithm， the algorithm will continue to optimize the preprocessing and matching process， and in the dictionary tree storage are optimized. After that， the algorithm in space/time complexity is further optimized， therefore the algorithm performance is improved. The experimental results also verify the efficiency of the algorithm.Keywords： multiple patterns； pattern matching； AC algorithm； QS algorithm0引言模式串匹配算法，适用于从某个序列中，找到具有某种属性的模式段或者位置等信息。

AC算法BM算法AC算法（Aho-Corasick Algorithm）和BM算法（Boyer-Moore Algorithm）都是一种用于在一个大文本中查找多个关键词的字符串匹配算法。

它们都具有高效的时间复杂度和较低的内存消耗，适用于很多实际应用场景。

AC算法是由Alfred V. Aho和Margaret J. Corasick于1975年提出的一种多模式匹配算法。

该算法主要用于匹配一个文本中的多个关键词，比如在引擎中匹配用户输入的多个关键词。

AC算法的核心思想是构建一个状态机来匹配关键词，通过一种类似于字典树的数据结构来高效地存储关键词，并利用自动机的转移函数进行匹配操作。

AC算法的具体实现过程如下：1.构建一个关键词集合，将所有关键词插入到一个类似于字典树的数据结构（通常称为AC自动机）中，其中节点表示状态，边表示状态之间的转移。

2.根据插入的关键词构建AC自动机的转移函数，即每个状态的状态转移表。

这个过程主要是通过BFS（广度优先）算法来实现的。

3.根据AC自动机进行文本匹配，也就是遍历待匹配文本的字符，并根据状态转移表进行状态转移，如果遇到一个匹配状态，则找到了一个关键词的匹配。

相比于传统的字符串匹配算法，AC算法的时间复杂度是O(N+M)，其中N是文本长度，M是总的关键词个数。

AC算法的优势主要体现在其高效的多模式匹配能力以及较小的内存消耗。

BM算法是由Robert S. Boyer和J Strother Moore于1977年提出的一种字符串匹配算法。

该算法采用了从左到右的匹配策略，结合了好后缀规则和坏字符规则两种启发式方法进行匹配操作，能够快速定位匹配失败的位置，并进行有效的后移操作。

BM算法的具体实现过程如下：1.从待匹配文本的末尾开始，与关键词的末尾进行匹配。

2.如果遇到不匹配的字符，根据坏字符规则计算出错位数，即将关键词后移一定的距离。

3.如果遇到好后缀，则根据好后缀规则计算正确的后移位数，即将关键词后移一定的距离。

基于AC自动机的多模式匹配算法FACA陈新驰;韩建民;贾泂【摘要】Aho-Corasick automata algorithm has to backtrack for multiple times to shift to the effective subsequence state when it fails in one pattern matching. In order to solve this problem, this paper proposes a fast multiple patterns matching algorithm based on Aho-Corasick automata. The improved algorithm builds the subsequence pointers for each state. On failing matching, it can shift to the effective subsequence state through the subsequence pointers efficiently, which can reduce backtracking times in Aho-Corasick automata. Furthermore, the proposed algorithm achieves information such as matching length, matching times etc for each state during building automata by dynamic programming methods. Based on this information, the algorithm can calculate the repeated times of pattern strings, earliest position of pattern strings. Experimental results show that the algorithm has advantages of matching accuracy, efficiency, and supporting on-line operation.%Aho-Corasick自动机算法在模式匹配失配时,需要多次回溯才转移到有效的后继状态.为此,提出一种快速多模式匹配算法.该算法为每个状态建立失配时的后继指针,在模式匹配失配时,可以通过失配后继指针快速找到有效后继状态,从而避免Aho-Corasick自动机失配时的过多回溯,提高匹配效率.算法在自动机建立时采用动态规划的方法,为每个状态建立匹配长度和匹配量等信息,在模式匹配过程中,基于这些信息统计模式串在主串中的重复次数、最早出现模式串位置等信息.实验结果表明,该算法匹配精确、效率高,且支持在线操作.【期刊名称】《计算机工程》【年(卷),期】2012(038)011【总页数】4页(P173-176)【关键词】模式匹配;自动机;动态规划;Trie树【作者】陈新驰;韩建民;贾泂【作者单位】浙江师范大学计算机系,浙江金华321004;浙江师范大学计算机系,浙江金华321004;浙江师范大学计算机系,浙江金华321004【正文语种】中文【中图分类】TP3121 概述模式匹配算法是信息领域中的重要内容，广泛应用于文本搜索、网络入侵检测系统、病毒检测、信息检索、计算生物学等领域。