Aho-Corasick 多模式匹配算法(AC自动机) 的算法详解及具体实现

蔚落 2022-05-25 02:55 190阅读 0赞

# 多模式匹配 #

多模式匹配就是有多个模式串P1,P2,P3…，Pm，求出所有这些模式串在连续文本T1….n中的所有可能出现的位置。  
　　例如：求出模式集合\{“nihao”,”hao”,”hs”,”hsr”\}在给定文本”sdmfhsgnshejfgnihaofhsrnihao”中所有可能出现的位置。

# AC 自动机算法 #

在计算机科学中，Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasick 发明的字符串搜索算法，\[1\]用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数，如果每个子串互相匹配（如字典为a，aa，aaa，aaaa，输入的字符串为aaaa），算法的时间复杂度会近似于匹配的二次函数。

该算法主要依靠构造一个有限状态机（类似于在一个trie树中添加失配指针）来实现。这些额外的失配指针允许在查找字符串失败时进行回退（例如设Trie树的单词cat匹配失败，但是在Trie树中存在另一个单词cart，失配指针就会指向前缀ca），转向某前缀的其他分支，免于重复匹配前缀，提高算法效率。  
当一个字典串集合是已知的(例如一个计算机病毒库), 就可以以离线方式先将自动机求出并储存以供日后使用，在这种情况下，算法的时间复杂度为输入字符串长度和匹配数量之和。  
UNIX系统中的一个命令fgrep就是以AC自动机算法作为基础实现的。

# 具体实现 #

在ac自动机算法中，以下3步尤为重要：

1.  构造前缀树
2.  设置每个节点的失配跳转并收集每个节点的所有匹配模式串
3.  对目标字符串进行搜索匹配

**这里我们考虑模式集合P=\{“he”,”she”,”his”,”hers”\}**

## 步骤1：构造前缀数组 ##

![这里写图片描述][trie4.gif]  
其中的数字和字母分别表示状态和条件。

## 步骤2：设置每个节点的失配跳转 ##

h,s这个条件的失败转移值为0，也就是fail(1)=0, fail(3)=0也就是如果查找一个字符串从最开始查，即不是s,h就直接跳转到0节点  
在深度为2的情况下，有2，6，4三个节点:  
计算fail（2），也就是求he的失败转移状态，由于父节点1的失败转移状态0,0下面也没有e的条件可以跳转，所以fail(2)=0  
计算fail（6），也就是求hi的失败转移状态，由于父节点1的失败转移状态0,0下面也没有i的条件可以跳转，所以fail(6)=0  
计算fail（4），也就是求sh的失败转移状态，由于父节点3的失败转移状态0,0下面有h的条件可以跳转到状态1，所以fail(3)=1

在深度为3的情况下，有8,7,5三个节点:  
计算fail（8），也就是求her的失败转移状态，由于父节点2的失败转移状态0,0下面也没有r的条件可以跳转，所以fail(8)=0  
计算fail（7），也就是求his的失败转移状态，由于父节点6的失败转移状态0,0下面有s的条件可以跳转到状态3，所以fail(7)=3  
计算fail（5），也就是求she的失败转移状态，由于父节点4的失败转移状态1,1下面有e的条件可以跳转到状态2，所以fail(5)=2

在深度为4的情况下，有节点9  
计算fail（9），也就是求hers的失败转移状态，由于父节点8的失败转移状态0,1下面有s的条件可以跳转到状态3，所以fail(5)=3  
这样一来我们构造的fail表如下：  
![这里写图片描述][70]

## 步骤3：对目标字符串进行搜索匹配 ##

上面两个步骤都完成了之后就可以开始对目标串进行搜索了，只需对目标串从头到尾线性扫描，且没有回溯。搜索之前先记录树的当前节点node，初始时，树的当前节点node为根节点Root。从目标串的第一个字符开始，和Root的孩子节点进行匹配，如果不匹配，则目标字符串往后挪一个字符，继续在Root的孩子节点中查找匹配。如果找到匹配的孩子，则目标字符串往后挪一个字符，node变为匹配上的孩子节点。在接下来的匹配过程中，如果失配将跳转到node节点的fail值处继续进行匹配。在树上每次往孩子节点方向走一步都要检查该孩子节点的匹配模式串信息，如果有匹配的模式串信息，则应记录找到了哪些能够匹配的模式串。

# 未完待续 #

## 参考文档 ##

[https://tech.meituan.com/ac.html][https_tech.meituan.com_ac.html]  
[https://my.oschina.net/u/3132973/blog/812141][https_my.oschina.net_u_3132973_blog_812141]

[trie4.gif]: /images/20220525/2eaedcf0b2e949cd911fc050508b040b.png
[70]: /images/20220525/79d458b238dd4a2a9d29e96448de581b.png
[https_tech.meituan.com_ac.html]: https://tech.meituan.com/ac.html
[https_my.oschina.net_u_3132973_blog_812141]: https://my.oschina.net/u/3132973/blog/812141