AC 经典多模式匹配算法

ゝ一纸荒年。 2023-05-30 06:16 31阅读 0赞

今天说说多模式匹配AC算法（Aho and Corasick），感谢追风侠帮忙整理资料，while(1) \{Juliet.say("3Q");\}。前面学习了BM、Wu-Manber算法，WM由BM派生，不过AC与它们无染，是另外一种匹配思路。

<table style="color:rgb(51,51,51)"> 
 <tbody> 
 <tr> 
 <td> 1.&nbsp;初识AC算法 </td> 
 </tr> 
 </tbody> 
</table>

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

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

自动机的执行动作由三个部分组成：

（1）       一个goto function

（2）       一个failure function

（3）       一个output function

我们先通过一个具体实例来了解一下这三个部分，及该自动机的运作方式。先有个大概印象，后面会具体讲解。patterns集合\{he, she, his ,hers\}，我们要在”ushers”中查找并匹配。

![goto function][]

**(1) goto function**

i       1   2   3   4   5   6   7   8   9

f(i)     0   0   0   1   2   0   3   0   3 （发现没？貌似i和f(i)有相同前缀哦^\_^）

**(2) failure function**

i           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，记录下匹配位置。至此字符串ushers匹配完毕。

具体的匹配算法如下：

<table style="color:rgb(51,51,51)"> 
 <tbody> 
 <tr> 
 <td> 算法1. Pattern matching machine 输入：text和M。text是x=a1a2...an，M是模式匹配自动机（包含了goto函数g(),failure函数f()，output函数output()） 输出：text中出现的pat以及其位置。 &nbsp; state←0 for&nbsp;i←1 until n&nbsp;do&nbsp;//吞入text的ai &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;g(state, ai)=fail&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state←f(state)&nbsp;//直到能走下去，呵呵，至少0那个状态怎么着都能走下去 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state←g(state,ai)&nbsp;//得到下一个状态 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;output(state)≠empty&nbsp;//能输出就输出 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;print i; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;print output(state) </td> 
 </tr> 
 </tbody> 
</table>

AC算法的时间复杂度是O(n)，与patterns的个数及长度都没有关系。因为Text中的每个字符都必须输入自动机，所以最好最坏情况下都是O(n)，加上预处理时间，那就是O(M+n)，M是patterns长度总和。

OK，下面我们看看如何通过patterns集合构造上面的3个function

这三个function的构造分两个阶段：

（1）       我们决定状态和构造goto function

（2）       我们计算得出failure function

而output function的构造贯穿于这两个阶段中。

<table style="color:rgb(51,51,51)"> 
 <tbody> 
 <tr> 
 <td> 2.1 goto&nbsp;与&nbsp;ouput填表 </td> 
 </tr> 
 </tbody> 
</table>

我们仍然拿实例来一步步构造：patterns集合\{he,she,his,hers\}

首先我们构造patterns   he

![he构造][he]

然后接着构造she

![she构造][she]

再构造his，由于在构造his的时候状态0接收h已经能到状态1，所以就不用重新建一个状态了，有点像建trie树的过程，共用一段相同的前缀部分

![his构造][his]

最后构造hers

![hers构造][hers]

具体构造goto function算法如下：

<table style="color:rgb(51,51,51)"> 
 <tbody> 
 <tr> 
 <td> 算法2. Construction of the&nbsp;goto&nbsp;function 输入：patterns集合K={y1,y2,...,yk} 输出：goto function g&nbsp;和output function output的中间结果 &nbsp; /* We assume output(s) is empty when state s is first created, and g(s,a)=fail if a is undefined or if g(s,a) has not yet been defined. The procedure enter(y) inserts into the goto graph a path that spells out y. */ &nbsp; newstate←0 fori&nbsp;←&nbsp;1until k&nbsp;//对每个模式走一下enter(yi)，要插到自动机里来嘛 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;enter(yi) for&nbsp;all a such that g(0,a)=fail &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;g(0,a)←0 &nbsp; &nbsp; enter(a1a2...am) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state←0;j←;1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;g(state,aj)≠fail&nbsp;//能走下去，就尽量延用以前的老路子，走不下去，就走下面的for()拓展新路子 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state←g(state,aj) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j←j+1 &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;p←j until m&nbsp;//拓展新路子 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;newstate←newstate+1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;g(state,ap)←newstate &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state←newstate &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;output(state)←{a1a2...am}&nbsp;//此处state为每次构造完一个pat时遇到的那个状态 } </td> 
 </tr> 
 </tbody> 
</table>

<table style="color:rgb(51,51,51)"> 
 <tbody> 
 <tr> 
 <td> 2.2&nbsp;&nbsp;Failure&nbsp;与&nbsp;output填表 </td> 
 </tr> 
 </tbody> 
</table>

Failure function的构造：（这个比较抽象）

大家注意状态0不在failure function中，下面开始构造，首先对于所有depth为1的状态s，f(s)=0，然后归纳为所有depth为d的状态的failure值都由depth-1的状态得到。

具体讲，在计算depth为d的所有状态时候，我们会考虑到每一个depth为d-1的状态r

1.       如果对于所有的字符a，g(r,a)=fail，那么什么也不做，我认为这时候r已经是trie树的叶子结点了。

2.       否则的话，如果有g(r,a)=s，那么执行下面三步

（a）       设置state=f(r) //用state记录跟r共前缀的东东

（b）       执行state=f(state)零次或若干次，直到使得g(state,a)!=fail（这个状态一定会有的因为g(0,a)!=fail）//必须找条活路，能走下去的

（c）       设置f(s)=g(state,a)，即相当于找到f(s)也是由一个状态匹配a字符转到的状态。

实例分析：

首先我们将depth为1的状态f(1)=f(3)=0，然后考虑depth为2的结点2，6，4

计算f(2)时候，我们设置state=f(1)=0，因为g(0,e)=0,所以f(2)=0;

计算f(6)时候，我们设置state=f(1)=0，因为g(0,i)=0,所以f(6)=0;

计算f(4)时候，我们设置state=f(3)=0，因为g(0,h)=1,所以f(4)=1;

然后考虑depth为3的结点8，7，5

计算f(8)时候，我们设置state=f(2)=0，因为g(0,r)=0,所以f(8)=0;

计算f(7)时候，我们设置state=f(6)=0，因为g(0,s)=3,所以f(7)=3;

计算f(5)时候，我们设置state=f(4)=1，因为g(1,e)=2,所以f(5)=2;

最后考虑depth为4的结点9

计算f(9)时候，我们设置state=f(8)=0，因为g(0,s)=3,所以f(9)=3;

具体算法：

<table style="color:rgb(51,51,51)"> 
 <tbody> 
 <tr> 
 <td> 算法3. Construction of the failure function 输入：goto function g and output function output from&nbsp;算法2 输出：failure function f and output function output &nbsp; queue←empty for&nbsp;each&nbsp;a such that g(0,a)=s≠0//其实这是广搜BFS的过程 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;queue←queue∪{s} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f(s)←0 &nbsp; while&nbsp;queue≠empty &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pop(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;each&nbsp;a such that g(r,a)=s≠fail&nbsp;//r是队列头状态，如果r遇到a能走下去 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;queue←queue∪{s}&nbsp;//那就走 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state←f(r)&nbsp;//与r同前缀的state &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;g(state,a)=fail&nbsp;//其实一定能找着不fail的，因为至少g(0,a)不会fail &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state←f(state) &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f(s)←g(state,a)&nbsp;//OK，这一步相当于找到了s的同前缀状态，即f(s) &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;output(s)←output(s)∪output(f(s))&nbsp;//建议走一下例子中g(4,e)=5的例子，然后ouput(5)∪output(2)={she,he} </td> 
 </tr> 
 </tbody> 
</table>

<table style="color:rgb(51,51,51)"> 
 <tbody> 
 <tr> 
 <td> 2.3&nbsp;&nbsp;output </td> 
 </tr> 
 </tbody> 
</table>

Output function的构造参见算法2，3

**改进1：**观察一下算法3中的failure function还不够优化

![改进1][1]

我们可以看到g(4,e)=5，如果现在状态到了4并且当前的字符为t！=e，因为g(4,t)=fail，

所以就根据f(4)=1,跳转到状态1，而之前已经知道t！=e，所以就没必要跳到1，而直接跳到状态f(1)=0。

为了避免不必要的状态迁移，和KMP算法有异曲同工之处。重新定义了一个failure function：f1

<table style="color:rgb(51,51,51)"> 
 <tbody> 
 <tr> 
 <td> f1(1)=0， 对于i&gt;1,如果能使状态f(i)转移的所有字符也能使i状态转移，那么f1(i)=f1(f(i))， 否则f1(i)=f(i)。 </td> 
 </tr> 
 </tbody> 
</table>

**改进2：**由于goto function中并不是每个状态对应任何一个字符都有状态迁移的，当迁移为fail的时候，我们就要查failure function，然后换个状态迁移。现在我们根据goto function和failure function来构造一个确定的有限自动机next move function，该自动机的每个状态遇到每个字符都可以进行状态迁移，这样就省略了failure function。

构造next move function的算法如下：

<table style="color:rgb(51,51,51)"> 
 <tbody> 
 <tr> 
 <td> 算法4：Construction of a deterministic finite automaton 输入：goto functioni g and failure function f 输出：next move function delta &nbsp; queue←empty for&nbsp;each&nbsp;symbol a &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;delta(0,a)←g(0,a) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;g(0,a)≠0 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;queue←queue∪g(0,a) &nbsp; while&nbsp;queue≠empty &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pop() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;each&nbsp;symbol a &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;g(r,a)=s≠fail &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;queue←queue∪{s} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;delta(r,a)←s else&nbsp;delta(r,a)←delta(f(r),a) </td> 
 </tr> 
 </tbody> 
</table>

Next function delta的计算如下：

![改进2][2]

其中’.’表示除了该状态能识别字符的其他字符。

改进2有利有弊：好处是能减少状态转移的次数；坏处是由于状态与状态之间的迁移多了，导致存储的空间比较大。

[goto function]: https://p-blog.csdn.net/images/p_blog_csdn_net/ijuliet/EntryImages/20090821/goto%20function.jpg
[he]: https://p-blog.csdn.net/images/p_blog_csdn_net/ijuliet/EntryImages/20090821/he%E6%9E%84%E9%80%A0.jpg
[she]: https://p-blog.csdn.net/images/p_blog_csdn_net/ijuliet/EntryImages/20090821/she%E6%9E%84%E9%80%A0.jpg
[his]: https://p-blog.csdn.net/images/p_blog_csdn_net/ijuliet/EntryImages/20090821/his%E6%9E%84%E9%80%A0.jpg
[hers]: https://p-blog.csdn.net/images/p_blog_csdn_net/ijuliet/EntryImages/20090821/hers%E6%9E%84%E9%80%A0.jpg
[1]: https://p-blog.csdn.net/images/p_blog_csdn_net/ijuliet/EntryImages/20090821/%E6%94%B9%E8%BF%9B1.jpg
[2]: https://p-blog.csdn.net/images/p_blog_csdn_net/ijuliet/EntryImages/20090821/%E6%94%B9%E8%BF%9B2.jpg