算法:AC 自动机实现多模式匹配

一、引入

如果我们想要在字符串“hello”中查找“he”,可以用暴力匹配、KMP、BM 算法等,但是如果想要同时查找“he”和“el“,又该如何实现?

最简单的方式就是先查找一遍”he“,然后再查找一遍”el“,如下图所示:

但这种方式的效率显然很低。为了更高效地完成多个模式串的匹配,贝尔实验室于 1975 年诞生了 Aho-Corasick Automaton 算法,即 AC 自动机。

二、AC 自动机特点

AC 自动机算法利用了有限自动机的状态转移,只需要扫描一遍字符串,就能找出匹配的多个模式串。

与 KMP 算法相似,AC 自动机是在匹配前,先对多个模式串进行预处理,得到一个有限自动机。构建自动机的过程会消耗一些资源,但只需要在最开始构建一次,就可以重复用它来高效地匹配文本,因此这点消耗可以忽略不计。

三、AC 自动机示例

AC 自动机的构建主要包含了三个部分:转移函数(goto 函数)、输出函数(output 函数)、失配函数(fail 指针)。

  • 转移函数:给出在某个状态下,成功匹配某个字符之后,应该转移到哪一个状态。
  • 输出函数:在当前状态下,如果已经匹配到了某些模式串,那么就输出对应的模式串。
  • 失配函数:AC 自动机最核心的部分,与 KMP 中的 next 表有异曲同工之妙。当文本在匹配过程中失配时(即不匹配),我们可以通过失配函数转移到某个状态继续匹配,待匹配文本不需要回溯。

注意

上述的三个函数表达的是一种映射关系,便于描述原理,在真正实现时未必使用函数,也可用数组或图的形式来描述状态的转移关系、以及其对应的失配指针等。

例子

接下来,我们结合例子来理解 AC 自动机的构建过程。

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

先来看该模式串构建得到的自动机:

图中的“正常转移”表示读入一个字符时,能成功匹配,通过 goto 函数转移到下一个状态。“失配转移”表示读入字符时,根据当前字符无法到达下一个状态,匹配失败,因此根据 fail 函数转移到合适的状态继续匹配。

可以看到,读入一个字符时,无论匹配成功或者失败,AC 自动机都是做同一件事情:状态转移。只不过成功时是根据 goto 函数转移,而失败时是根据 fail 函数转移。

要点分析

我们先看图中的状态 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 对应状态的创建。

2. 建立输出函数

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

3. 建立失配函数

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

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

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

举个例子,我们看下图 3->5->6 失配指针的建立过程:

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

假设我们现在要给状态 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。

(完)

相关文章

Loading Likes...

发表评论

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