今天我们学习一种多模式匹配算法：AC自动机。（这个名字可能不太严谨，自动机知识这个算法的一个部分）
多模式匹配算法：在主串中查找多个模式串。
为了让匹配的过程更加形象，我们设置这样一个需求：请你实现一个类似于网站屏蔽敏感词的功能。
多模式匹配-AC自动机
首先，我们需要用一个数据结构存储所有的敏感词，然后使用这个数据结构过滤字符串中的敏感信息。在这个过程中，你可以将所有的敏感词看作模式串，将需要审核的字符串看作主串。
当然，你可以使用前面学过的单模式匹配算法，对一段内容做多次匹配，但是这样的效率比较低，所以我们使用多模式匹配算法进行匹配，这也是我们今天要学习的主要内容。
经典的多模式匹配算法：AC自动机
AC自动机实际上是在 Trie树 的基础上添加了一些功能，让它可以快速的进行匹配。相比于一般的 Trie树，它的节点有更多的信息需要存储：
public class AcNode {
public char data;
public AcNode[] children = new AcNode[26]; // 字符集只包含a~z这26个字符
public boolean isEndingChar = false; // 结尾字符为true
public int length = -1; // 当isEndingChar=true时，记录模式串长度
public AcNode fail; // 失败指针
public AcNode(char data) {
this.data = data;
}
}
AC自动机的构建，包含两个操作：
- 将多个模式串构建成 Trei树。
- 在 Trie树 上构建失败指针。
第一点我们已经在之前的学习中学过了，所以我们需要重点看一下：如何在构建好的 Trie树 上构建失败指针。
失败指针的构建
要想编写出合适的代码，我们首先要了解代码需要执行的操作，下面我们就看一下，在一个已经构建完成的 Trie树 上，我们需要AC自动机做些什么。
我这样解释失败指针：当在某个节点中进行下一次匹配失败的时候，我们可以通过 fail指针 移动到另一个可能匹配成功的节点上。
首先，我们假设 abcd , bcd, c 是敏感词，我们将其构建为 Trie树：
AC自动机-Trie树.jpg
当我们匹配 abce 的时候，会在如下图的紫色节点匹配失败，根据 fail指针，它将会进入下一个模式串进行匹配：
AC自动机-构建fail指针.jpg
我们可以发现 fail指针 的构建规律：如果一个模式串的前缀子串的后缀子串可以作为另一个模式串的前缀子串，则他们可以构建 fali指针。例如，上图中 bc 为 abc 的后缀子串，他们就可以构建一个 fail指针。 我们将 root 节点的 fail指针 定义为 NULL。并且，当我们已经求得某个节点的 p 的 fail指针 后，可以寻找它的子节点的 fail指针 ：（我知道你可能听不明白，但是你要记住，我们需要通过 p 节点构建 它的的孩子节点的 fail指针。你多看几遍图，你就会明白的）
AC自动机-构建孩子的fail指针.jpg
如果节点 q 中没有子节点等于 pc 节点，则另 q=q->fail，继续查找，直到 q 为 root 为止（如下图中的虚线）：
AC自动机-构建孩子的fail指针2.jpg
如果 pc 没有找到相同的子节点，则 pc->fail 指向 root。
最终，一个构建完成的自动机如下图：
AC自动机-自动机.jpg
你可以参考代码：
public void buildFailurePointer() {
Queue<AcNode> queue = new LinkedList<>();
root.fail = null;
queue.add(root);
while (!queue.isEmpty()) {
AcNode p = queue.remove();
for (int i = 0; i < 26; ++i) {
AcNode pc = p.children[i];
if (pc == null) continue;
if (p == root) {
pc.fail = root;
} else {
AcNode q = p.fail;
while (q != null) {
AcNode qc = q.children[pc.data - 'a'];
if (qc != null) {
pc.fail = qc;
break;
}
q = q.fail;
}
if (q == null) {
pc.fail = root;
}
}
queue.add(pc);
}
}
}
自动机的匹配过程
匹配主要有两个过程：
- 如果匹配成功，则进行下一个字符的匹配。
-
如果匹配不成功，则使用 fail指针 进行模式串切换，再继续匹配。
你可以看一下原文的解释：
image.png
代码如下：
public void match(char[] text) { // text是主串
int n = text.length;
AcNode p = root;
for (int i = 0; i < n; ++i) {
int idx = text[i] - 'a';
while (p.children[idx] == null && p != root) {
p = p.fail; // 失败指针发挥作用的地方
}
p = p.children[idx];
if (p == null) p = root; // 如果没有匹配的，从root开始重新匹配
AcNode tmp = p;
while (tmp != root) { // 打印出可以匹配的模式串
if (tmp.isEndingChar == true) {
int pos = i-tmp.length+1;
System.out.println("匹配起始下标" + pos + "; 长度" + tmp.length);
}
tmp = tmp.fail;
}
}
}
我自己使用python代码完整地实现了这个数据结构，你可以参考一下：
class AcNonde():
def __init__(self, data):
self.data = data
self.children = [None for i in range(26)]
self.isEndingChar = False
self.length = 0
self.fail = None
class Trie:
def __init__(self):
self.root = AcNonde('root')
def addChar(self, s):
'''
在 Trie树中创建一个字符串
:param s: 要创建的字符串
:return:
'''
cur = self.root
l = 0
for i in s:
l += 1
if cur.children[ord(i) - ord('a')]:
cur = cur.children[ord(i) - ord('a')]
else:
temp = AcNonde(i)
temp.length = l
cur.children[ord(i) - ord('a')] = temp
cur = temp
cur.isEndingChar = True
def prin(self):
cur = self.root
for i in cur.children:
if i:
self.dg(i, mark=[])
@staticmethod
def dg(root, mark=[]):
if mark:
mark[0] += root.data
else:
mark.append(root.data)
if root.isEndingChar:
print(mark[0] + ' length:', root.length)
for i in root.children:
if i:
Trie.dg(i, mark=mark.copy())
else:
continue
def buildFailurePointer(self):
'''
在这里，我们将 Trie 树的所有节点构建出 fail 指针
:return: None
'''
self.root.fail = None # 初始化操作
que = []
que.append(self.root)
while que:
p = que.pop(0)
# 在队列中取出一个数据作为 p ，在接下来的过程中，我们会为 p 的孩子节点 pc 构造 fail 指针，指针指向 qc（如果存在的话）
for pc in p.children:
if pc == None: # 如果没有当前字符的子节点，跳过
continue
if p is self.root: # 如果 p 是root，pc 的fail 指向 root，注意，在这里已经通过 pc 构建了 root 外第一层的 fail 指针。
# 我们要保证每个节点都有fail指针，这个操作是必需的。
pc.fail = self.root
else: # 如果 p 不是根节点，那么 p 已经有了 fail 指针。
# 注意，因为上面的那个判断，第一层树节点已经有了 fail，之后的逻辑就比较简单了。
q = p.fail # q 是 p->fail 指向的另一个节点。
while q != None:
qc = q.children[ord(pc.data) - ord('a')] # 如果 qc 拥有和 pc 相同的 data，则可以构建 pc->fail 指向 qc
if qc:
pc.fail = qc
break # pc 的 fail 构建成功以后就没有必要继续查找了
q = q.fail # q->fail 也指向 data 为 p.data 的结点，可能这个结点也会有符合条件的子节点
if q == None: # 如果 q 为 None，证明最终 pc 没有匹配到 fail 节点。
# 它只能指向 root （所有没有fail的结点的fail都指向root）
pc.fail = self.root
que.append(pc)
def match(self, s):
'''
在这里完成匹配敏感词的操作，如果你要替换敏感词，可以很简单地实现替换
:param s: 要匹配的字符串，它是主串
:return: None
'''
p = self.root
for i, v in enumerate(s):
index = ord(v) - ord('a')
while p.children[index] == None and p is not self.root: # 寻找下一个节点值为当前字符的结点，如果没有，就最终传递到root
p = p.fail
p = p.children[index] # 如果匹配到了，p更新为下一个节点，如果没有匹配到，p为root，它对应的孩子会是 None
if p == None: # 处理匹配失败的情况
p = self.root
temp = p
while not (temp is self.root): # 如果 p 匹配成功，需要看当前的节点是否为最终节点，如果是最终节点，代表匹配成功，输出信息
if temp.isEndingChar:
print('匹配到敏感词汇：起始位置{}，长度{}'.format(i - temp.length + 1, temp.length))
temp = temp.fail
if __name__ == '__main__':
x = Trie()
x.addChar('sb')
x.addChar('shabi')
x.addChar('cao')
x.buildFailurePointer()
x.match('nishigesbcao')
# x.prin()
----------------------------------------
执行结果：
匹配到敏感词汇：起始位置7，长度2
匹配到敏感词汇：起始位置9，长度3
性能分析
AC自动机的空间复杂度类似 Trie树 的空间复杂度，在这里就不多说了，下面主要分析时间复杂度：
1.构建 AC 自动机：
1.1构建 Trie树 的时间复杂度为 O(m*len)，其中 m 为敏感词的个数，len 为敏感词的平均长度。
1.2构建 自动机：构建自动机要遍历每个节点，假设节点个数为 k 。构建每个节点都要构建它的 fail 指针，构建指针的过程中数据规模会递减，所以构建一个节点的 fail指针 最多 len 次。综上，构建自动机的时间复杂度为 O(k*len)。
由于 AC自动机 一般是静态配置好的，所以在匹配中我们基本不用考虑这方面的时间消耗。
2.匹配中的时间复杂度：
假设一个字符串的长度为 n ，在匹配的过程中我们要遍历 n 次，每次遍历最多使用自动机 len 次。所以匹配的时间复杂度为 O(n*len)。由于 len 是一个并不太长的常数，所以我们可以将复杂度看成 O(n)。
AC自动机-性能退化.jpg
总结
要理解AC自动机的匹配过程，最重要的是理解 fail指针的作用，以及如何构建 fail指针。
以上就是 AC自动机的全部内容。到这里，数据结构的内容差不多就结束了，之后将是算法的主场。有没有...一点期待呢？哈哈哈哈。
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间
网友评论