AC自动机增量更新算法

AC自动机算法概述

Aho-Corasick算法[1]是多模式匹配中的经典算法，目前在实际应用中较多。Aho-Corasick算法通过将模式串预处理为确定有限状态自动机，这个数据结构是Aho-Corasick自动机，简称AC自动机。模式匹配的时候，只需要扫描文本一遍就能得到所有匹配该文本的模式串，其时间复杂度为O(n)，即只跟输入文本长度线性相关，与模式串的数量和长度无关。

在Aho-Corasick算法的原始论文中，描述了自动机构建的过程，包含两个步骤：(1)、首先扫描所有的模式串，构建goto状态转换函数，在实际的程序实现中goto函数实际上是一颗Trie树结构；(2)、利用上一步构建的Trie树，构建failure函数。在模式匹配的过程中，一个个字符的方式扫描待匹配的输入文本，在Trie树中从根节点进行搜索，一旦遇到字符匹配失败的节点，就跳转到failure函数指向的下一个节点继续匹配，直到输入文本扫描完毕，得到匹配的所有模式串。因为failure函数的构建使得匹配失败时可以利用之前匹配的结果，无需从头开始匹配，因此匹配的性能比较好。在实际的应用中，模式串数据库可能量非常巨大，而且会频繁的变化，例如对于网络爬虫的URL黑白名单会频繁更新，在匹配的同时，需要不断重构自动机。显然，一种可行的方案是依照作者在论文中介绍的那样，每次模式串更新，就对自动机从0开始重建，这种方案对于模式库比较小的场景下是可行的，但是模式库数量比较大的时候就不可能，每次重建的性能消耗会比较大。如果能有一种算法能增量式地进行构建，而不是每次推倒重来，将会极大减少模式库更新的性能消耗，也更加符合实际应用场景。

针对AC自动机的动态更新模式库的需求，这里介绍一种增量更新的算法，不需要每次重建自动机索引树，而只是在一个局部范围内微调这颗树，使得自动机的正确性保持不变。

接下来描述算法详细过程。

基于AC自动机原始算法，我们增加两个增量添加模式和增量删除模式的算法。

模式添加算法

模式串添加算法见Algorithm-1，整个算法分为两个步骤：首先利用Trie树找到需要添加的模式串在Trie树中匹配最长前缀串的节点位置，然后根据需要对Trie树进行节点扩展，以及failure函数的局部调整。1-6行是对输入模式k1,k2,…,km一个匹配的过程，找出最长前缀匹配。这里存在两种情况，第一种情况，这个模式串能被Trie树完整匹配，此时Trie树的结构不需要扩展，也就是不需要创建新节点，算法可以提前完成（也就是对应j>m，7-25行的代码直接被跳过）；第二种情况，模式串被部分匹配，这时需要插入新的树节点，对应7-25行的过程。

Algorithm 1. add pattern incrementally
Input: pattern K=k1,k2,...,km, goto function G, output O, failure function F, 
reverse failure function RF, maximun state number maxstate
Output: adjusted goto function G, adjusted output O, adjusted failure function F, 
adjusted reverse failure function RF, adjusted maximun state number maxstate
Method.begin1	state<--0; j<--1;
2	while G(state, kj) != fail  and j <= m do
3	begin4		 state <--G(state, kj);
5		 j <-- j + 1;
6	end
7	for p<-- j until m do
8	begin9		  newstate <-- maxstate + 1; 
10		maxstate <-- maxstate + 1;
11		failure <-- findFailure(state, kp, G, F);
12		G(state, kp) <-- newstate;
13		F(newstate) <-- failure;
14		RF(failure) <-- RF(failure) + {newstate}
15		for all s in RF(state) do
16		begin17			if G(s, kp) != fail  then do
18			begin19				RF(F(s)) <-- RF(F(s)) - {s};
20				F(s) <-- newstate;
21				RF(newstate) <-- RF(newstate) + {s};
22			end
23		end24	       state <-- newstate;
25	 end
26	 O(state)<--K;
end

7-25行遍历剩下的后缀串的每一个字符kp，对每一个字符都需要创建一个新的Trie树节点（状态），然后需要调整failure函数。调整failure函数也可以分解成两个步骤：1. 调整newstate的failure指针；2. 调整其他节点的应该指向newstate的failure指针。

9-14行首先创建一个新的节点newstate插入树中。然后设置newstate的failure指针。寻找failure指针指向节点的算法参见Algorithm-2，原则是沿着newstate的父亲节点state的failure指针链搜索，一直搜索到具有G(s, kp)为非空的节点为止，该节点就是newstate的failure指向节点。最坏情况，state的failure指针链一直会到达根节点会结束，因为根节点的G(s, kp)肯定非空。

Algorithm 2. findFailure
Input: state s, character k, goto function G, failure function F
Output: failure state f
Methodbegin1  do2	 begin3		  state <-- F(s);
4		  next <-- G(state, k);
5	 end
6	 while next == fail 
7	   f <-- next;
end

设置完newstate的failure指针之后，还需要考虑现存的Trie树中，哪些节点的failure指针需要指向这个新建的newstate。如何寻找这些候选节点呢，实际上，这些需要调整failure指针的候选节点，其父节点的failure指针必然指向newstate的父节点state。我们只需要遍历failure指向state的节点，记为RF(state)，判断它们是否存在以字符kp为跳转的子节点G(s,kp)，如果G(s,kp)存在，则把该子节点G(s,kp)的failure指针指向newstate。注意，此时，newstate所代表的字符串是是候选节点G(s,kp)所代表的字符串的最长后缀。

最终，调整完failure函数之后，设置最后一个叶子节点state的output，算法结束。

为了便于理解，这里给出一个案例，刚开始的时候，自动机结构如图1的初始状态，假设我们添加模式”ers”，因为”ers”没有任何一个前缀能匹配到的Trie树中，因此算法进入7-23行，创建紫色的新节点10，并设置它的failure指针，指向root，当执行完后就变成“第一步”所示状态。然后设置failure应该指向节点10的failure指针。我们知道10的父节点是0, 根据算法，failure指向0的节点是1、2、3、6、8，但是具有字符e的儿子节点的只有节点1，因此1的e边指向孩子节点2的failure指针需要调整成指向10，见图示的“第二步”，以此类推，当e、r、s三个字符循环构建完成之后，最终自动机达到图示的“最终状态”。

图1-添加模式”ers”的过程示例图

介绍完了模式添加算法，接下来我们介绍模式删除算法

模式删除算法

删除算法基本上是添加算法的逆过程，同样，先找到模式串的完全匹配节点在Trie树种的节点位置，如果模式串不能被Trie树完全匹配，也就是匹配失败，则说明模式串本身不存在，删除提前结束。同时，如果删除模式串之后，不改变树的结构，则提前终止操作，见Algorithm-3中的第10行以及25行。

Algorithm 3. remove pattern incrementally
Input: pattern K=k[1],k[2],...,k[m], goto function G, output O, failure function F, reverse failure function RF
Output: adjusted goto function G, adjusted output O, adjusted failure function F, adjusted reverse failure function RF
Method.begin1	state<--0; j<--1; list <-- empty;
2	while G(state, kj) != fail  and j <= m do
3	begin4		list <-- list + {state};
5		state <--G(state, kj);
6		j <-- j + 1;
7	end
8	if j > m then return;
9	O(state)<--null;
10	if for any character c that G(state, c)=fail then return; 
11	list <-- list + {state};
12	for p<--m+1 until 1 do
13	begin14		current <-- list[p];15		prev <-- list[p-1];
16		for all s in RF(current) do
17		begin18			if G(s, kp) != fail  then do
19				F(s) <-- F(current);
20				RF(F(current)) <-- RF(F(current)) + {s};
21			endif
22		end23	      RF(F(current)) <-- RF(F(current)) - {current};
24	      G(prev, k[p-1]) <-- fail;
25		if there exists a character c that G(prev, c) != fail then return;
26	end
end

至此，AC自动机增量添加和删除模式介绍完了，这里给出一个完整的实现代码：

https://github.com/jayzhang/aho-corasick-enhance

 

---

[1] Aho, Alfred V.; Corasick, Margaret J. (June 1975). "Efficient string matching: An aid to bibliographic search". Communications of the ACM. 18 (6): 333-340. doi:10.1145/360825.360855. MR 0371172.