终于也写了关于AC自动机的博客

ACAho-Corasick automaton,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。比如,给出一组单词,再给出一组字符串,找出有多少个单词在这个字符串中出现了。

先行知识:
* 字典树(Trie树) 不赘述了,当年数据结构的大作业词频统计接受过洗礼了
* KMP算法(主要的思想就是:当不匹配的时候,不要无脑地直接挪动到起始位置(即又从模式串(待匹配串)开始的位置开始匹配),而是将模式串往后移动,移动位数 = 已匹配的字符数 – 对应的部分匹配值。例如模式串ABCDABF已经匹配到了最后一位F了,然后不匹配,此时我们知道待匹配串的这几位肯定也是ABCDAB,只是后面的这个不是F.然后我们就把模式串往后移动4位,即AB与待匹配串的AB对齐,如果此时正好是C那么就省了很多次。时间复杂度O(n+m), 因为next数组是O(m), 而后面的扫描是O(n)。

next 负责把模式串向前移动,且当第j位不匹配的时候,用第 next[j] 位和主串匹配,就像打了张“表”。此外,next 也可以看作有限状态自动机的状态,在已经读了多少字符的情况下,失配后,前面读的若干个字符是有用的。

《终于也写了关于AC自动机的博客》

贴上KMP代码:

AC自动机就是在一棵字典树上增加了失配指针的数据结构。比如我们有如下的一个AC自动机。《终于也写了关于AC自动机的博客》

那么这里有2个指针。

  • p 指向当前匹配的字符。
  • p->fail p的失败指针,当p->next[i]为空的时候,可以跳转到p->fail继续匹配,如果没有,则指向root
    对于Trie树的一个节点,对应一个序列s[1…m]。即p指向s[m],那么接下来的下一个字符s[m+1]有2种情况。

1.p->next[s[m+1]] 不为空,那么就继续匹配。

2.p->next[s[m+1]] 如果为空,则跳转到失败指针p=p->fail 然后再重复1或2。如果失败指针为空,那么就匹配结束。

这里有个p指针转移的过程,如果是一般的Trie树匹配,那么在2的情况下p->next[s[m+1]]==NULL,匹配直接结束了,就说找不到单词s[1…m+1]。

那么这里p指针转移的目的是: 虽然单词s[1…m+1]不存在,也许单词s[i…m+1]存在,所以我们可以让p跳到某个节点,并且这个节点对应的字符串是s[i…m],然后以s[i…m]为前缀继续匹配s[i…m+1]。这里的s[i…m]是s[1…m]的后缀,i具体是多少这里暂时先不管。

这里用失败指针跳转就有KMP的next数组的味道了。

还是举刚刚的AC自动机为例子:

我们先看图中的状态 3,当我们处于状态 3 时,无论再读入什么字符,都没有可到达的下一个状态,因此必定匹配失败。那么失配时有什么可以利用的信息?可以确定的是,在状态 3 时已经读入了“she”这三个字符,包含了“he”这两个字符,因此我们可以认为是在读入了“he”的基础上继续匹配,那么就可以转移到状态 7 接着匹配。
例如,当我们在状态 3 中读入字符 r 时,由于匹配失败会转移到状态 7,然后在状态 7 重新匹配 r,发现匹配成功,于是转移到状态 8。
再看状态 6,当我们处于状态 6 时,说明已经读入了“his”,此时如果失配,则可以在读入“s“的基础上继续匹配,即转移到状态 1 继续匹配。
例如,在状态 6 中读入字符 h,由于匹配失败先转移到状态 1,再次匹配 h,成功转移到状态 2。


关于AC自动机的构建过程:

我们接着上面的例子,看看该自动机如何建立转移函数、输出函数和失配函数。

  1. 建立转移函数
    实际上这里并不是建立真正的函数,而是通过有向图(树)建立了转移关系。

模式串中的每个字符相当于自动机中的一条有向边,由状态 A 指向状态 B,表示在状态 A 时,如果读入该字符,则转移至状态 B。

模式串:{she, his, he, her}

初始时只有一个 root 结点(状态 0),同时也是当前状态。

首先为模式串 she 创建对应的状态和边:从状态 0 开始,读入字符 s,发现不存在这条边(或转移关系),于是创建状态 1,并为状态 0 添加一条指向状态 1 的边 s,同时转移到状态 1。接着读入字符 h,发现不存在该边,于是创建状态 2,并为状态 1 添加一条指向状态 2 的边 h,同时转移到状态 2。接着读入字符 e,发现不存在该边,于是创建状态 3,并为状态 2 添加一条指向状态 3 的边 e,结束。

同理,我们依然从状态 0 开始,为模式串 his 创建对应状态 4、5、6,并添加相应的边。

然后是模式串 he,从状态 0 开始,读入字符 h,发现已经存在该边,于是转移到其指向的状态 4。接着读入字符 e,发现不存在该边,于是创建状态 7,并为状态 4 添加一条指向状态 7 的边 e。

同理可完成模式串 her 对应状态的创建。

  1. 建立输出函数
    该步骤实际上是在建立转移函数的时候同时进行的。在上述过程中,当我们为某个模式串创建了最后一个状态时,就在该状态上绑定这个模式串。这样一来,当我们在匹配过程中转移到了绑定有某个模式串的状态时,就可以将该模式串输出,表示已经匹配到了该模式串。

  2. 建立失配函数
    虽然说是创建失配函数,但实际上就是建立失配指针。失配指针的建立是通过迭代来完成的,以广度优先的方式从根节点开始遍历所有状态,首先设置第一层状态的 fail 指针,然后第二层,以此类推。

假设状态 u 下读入字符 x 可成功转移到状态 v,即 goto(u, x) = v,那么 v 的失配指针可表述为:

fail(v) = goto(fail(u), x)

举个例子,我们看下图 3->5->6 失配指针的建立过程:
《终于也写了关于AC自动机的博客》

图中橙色的虚线表示广度优先搜索的层次。

假设我们现在要给状态 3 建立失配指针,此时前两层状态的失配指针都已经设置好了,其中 goto(2, e) = 3,相当于 u = 2,v = 3,而 fail(2) = 4,于是可以计算状态 3 的失配指针 fail(3) = goto(fail(2), e) = goto(4, e) = 5。

下图是一个建立完所有状态的失配指针后的示例,红色和粉色分别表示指向 root 和非 root 状态的失配指针。

假设现在给状态 2 建立失配指针,goto(1, h) = 2,相当于 u = 1,v = 2,而 fail(1) = 0,于是 fail(2) = goto(fail(1), h) = goto(0, h) = 4。

《终于也写了关于AC自动机的博客》

总结

可以说,AC自动机就是KMP算法以Trie为基础的实现。其中失配指针的作用也和KMP算法中的一样,写法也类似。唯一有些不同的是,在单模式匹配中,由于只有一个模板串,成功匹配也就是一个串;但是多模式匹配时,有可能在成功匹配一个模板串时,也同时成功匹配了另一个模板串。这个问题可以用后缀链接进行处理。

参考博客1,,例子非常清晰。
博客2

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注