下载文档原格式
多模式串匹配之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，记录下匹配位置。
多模式串匹配算法详解随着计算机技术的不断发展，我们的生活已经离不开计算机了。
计算机技术也在不断完善和发展，其中算法是计算机科学的基础之一。
在计算机科学中，字符串匹配是一个非常重要的问题，而多模式串匹配算法就是解决字符串匹配问题的一种方法。
一、什么是多模式串匹配算法多模式串匹配算法是指在一个文本串中查找多个模式串的匹配位置。
举个例子，如果我们想在一段英文文章中查找“apple”、“banana”和“pear”这三个单词的位置，那么就可以使用多模式串匹配算法。
在这个例子中，文本串就是整篇文章，而“apple”、“banana”和“pear”就是模式串。
二、常见的多模式串匹配算法1.基于Trie树的多模式串匹配Trie树是一种树形数据结构，它是一种有序树，用于保存关联数组，其中键通常是字符串。
Trie树的基本思想是将字符串拆分成单个字符，然后构建一棵树，使得每个节点代表一个字符，从根节点到叶子节点组成的字符串就是一个完整单词。
构建出Trie 树之后，就可以使用类似深度优先搜索的方法，在Trie树上查找所有匹配的字符串。
2.基于AC自动机的多模式串匹配AC自动机是一种自动机算法，它是基于Trie树的改进。
AC自动机可以在O(n)的时间复杂度内找出文本串中所有出现在模式串集合中的模式串出现的位置。
就算是在模式串集合非常大的情况下，AC自动机依然可以保持良好的时间复杂度。
所以AC自动机是一种非常高效的多模式串匹配算法。
三、多模式串匹配算法的应用多模式串匹配算法的应用非常广泛，下面列举一些常见的应用场景。
1.搜索引擎搜索引擎需要快速地查找网页中的关键词，并列出所有相关的网页。
多模式串匹配算法可以帮助搜索引擎实现这个功能。
2.文本编辑器文本编辑器需要在用户输入时提示相关的自动补全单词和拼写纠错。
多模式串匹配算法可以根据用户输入的前缀，返回与之最相似的单词。
3.网络安全网络安全中常常需要检测恶意代码和病毒。
多模式串匹配算法可以帮助检测这些恶意代码和病毒。
基于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引言模式串匹配算法，适用于从某个序列中，找到具有某种属性的模式段或者位置等信息。
基于字频特征的自动机多模匹配增效算法
李超;张宏莉;楚国锋
【期刊名称】《微计算机信息》
【年(卷),期】2009(025)003
【摘要】针对自动机类多模匹配算法内存占用过多的缺点,分析了DFA存储的列特征,并结合模式串所属字符集的编码范围,提出了按字符频率特征压缩自动机状态空间的多模匹配增效算法.本算法采用了榆入字符阅值映射技术,在保存高频率字符对应列的同时,用位图信息提高对压缩列的检索速度.实验结果表明,在万条配置规则级的环境下,能够同时有效降低内存和CPU利用率.
【总页数】3页(P206-208)
【作者】李超;张宏莉;楚国锋
【作者单位】150001,哈尔滨,哈尔滨工业大学国家计算机信息内容安全重点实验室;150001,哈尔滨,哈尔滨工业大学国家计算机信息内容安全重点实验室;710106,西安,西安通信学院基础部计算中心
【正文语种】中文
【中图分类】TP393.08
【相关文献】
1.基于AC自动机的多模式匹配算法FACA [J], 陈新驰;韩建民;贾泂
2.一种基于反向有限自动机的多模式匹配算法 [J], 关超;蒋建中;郭军利
3.基于确定有限状态自动机的改进多模式匹配算法研究 [J], 陆琳琳;田野
4.一种基于特征提取和多模板匹配的心律失常检测算法 [J], 崔永华;梁正友
5.一种基于汉字编码特征的中文多模式匹配算法 [J], 黄宇;侯整风;余虎;刘春晖因版权原因，仅展示原文概要，查看原文内容请购买。
基于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 概述模式匹配算法是信息领域中的重要内容，广泛应用于文本搜索、网络入侵检测系统、病毒检测、信息检索、计算生物学等领域。
关键字:AC自动机自动机有限状态自动机 Trie 字母树字符串匹配多串匹配算法Note:阅读本文需要有KMP算法基础，如果你不知道什么是KMP，请看这里：/blog/article.asp?id=146(Matrix67大牛写的) AC自动机是用来处理多串匹配问题的，即给你很多串，再给你一篇文章，让你在文章中找这些串是否出现过，在哪出现。
也许你考虑过AC自动机名字的含义，我也有过同样的想法。
你现在已经知道KMP了，他之所以叫做KMP，是因为这个算法是由Knuth、Morris、Pratt三个提出来的，取了这三个人的名字的头一个字母。
那么AC自动机也是同样的，他是Aho-Corasick。
所以不要再YY 地认为AC自动机是AC(cept)自动机，虽然他确实能帮你AC一点题目。
扯远了。
要学会AC自动机，我们必须知道什么是Trie，即字母树。
如果你会了，请跳过这一段Trie是由字母组成的。
先看张图：这就是一棵Trie树。
用绿色标出的点表示一个单词的末尾（为什么这样表示？看下去就知道了）。
树上一条从root到绿色节点的路径上的字母，组成了一个“单词”。
/* 也许你看了这一段，就知道如何构建Trie了，那请跳过以下几段。
*/那么如何来构建一棵Trie呢？就让我从一棵空树开始，一步步来构建他。
一开始，我们有一个root：现在，插入第一个单词，she。
这就相当于在树中插入一条链。
过程很简单。
插完以后，我们在最后一个字母’e’上加一个绿色标记，结果如图：再来一个单词，shr(什么词？…..右位移啊)。
由于root下已经有’s’了，我们就不重复插入了，同理，由于’s’下有’h’了，我们也略过他，直接在’h’下插入’r’，并把’r’标为绿色。
结果如图：按同样的方法，我们继续把余下的元素插进树中。
最后结果:也就是这样:好了，现在我们已经有一棵Trie了，但这还不够，我们还要在Trie上引入一个很强大的东西：失败指针或者说shift数组或者说Next函数…..你爱怎么叫怎么叫吧，反正就是KMP的精华所在，这也是我为什么叫你看KMP的原因。
