问题
在文本text中查找k个模式pattern出现的所有位置。其中text长度为n,patterni的长度为mi,其中最长的模式长度为mmax且n>mmax,所有模式长度之和为msum=∑i=1kmi,且所有模式两两互不重复。
简单字符串匹配算法
将简单字符串匹配SimpleMatch应用在本问题上,搜索所有模式需要重复k次,每次的时间复杂度为O(n⋅mi)。直接应用SimpleMatch算法的时间复杂度为O(n⋅msum)。
前缀树
能否在一次匹配text的过程中就同时找出所有模式呢?即并行算法(算法的并行,而非多线程/多进程的并行)。
首先用所有pattern构造一个前缀树pt,如图所示:
(1) 从text的首个字符text[i=0]开始,将其与前缀树中的节点依次向下匹配,可知text[0…1]=pt[2…5],但text[2]=pt[8]因此匹配失败;
(2) 匹配位置向右移动一位,从text[i=1]开始,可知text[1]=pt[1]但text[2]=pt[3],text[2]=pt[4];
(3) 匹配位置向右移动一位,从text[i=2]开始匹配,可知text[2…3]=pt[1…3],text[2…5]=pt[1…9]匹配成功;
构建前缀树的时间复杂度为O(msum)。利用前缀树,文本上的每个字符匹配前缀树即可,该算法的时间复杂度为O(msum)+O(n⋅mmax)。当n远大于mmax时显然构造第二种算法更优。
失败指针
下图中,当匹配到text[i=5]时有text[5…6]=pt[2…5],但text[7]=pt[8]匹配失败。我们不希望从text[i=6]处从前缀树的根节点重新开始匹配,显然text[i=6]在前缀树中已经存在。因为pt[1…1]是pt[2…5]的后缀字符串,这时将前缀树的匹配位置调整到pt[1],那么pt[1]和text[i=6]可以继续匹配,尝试找到一个成功的匹配。图中红色的连线称为失败链接/失败指针failurelink;
设字符串α的末尾字符为pt[i],尝试在前缀树中寻找α的最长后缀字符串β(设pt[j]是β的末尾字符)。若找到这样一个合适的β,建立从pt[i]到pt[j]的指针,否则建立从pt[i]到pt[root]的指针。显然前缀树中每个节点只有一个失败指针。失败指针的出发节点是前缀树中最后一个成功匹配的字符,其实质是后缀字符串,也称后缀链接/后缀指针suffixlink。
失败指针的核心思路在于匹配文本失败时,希望避免从前缀树的根部重新开始匹配。失败指针要么指向一个与当前位置上字符串相同的最长的后缀字符串(这样的指针就是后缀指针),要么指向前缀树的根节点。比如下图中pt[2…5]="sh"的最长后缀字符串是pt[1…1]="h",pt[2…8]="she"的最长后缀字符串是pt[1…3]="he"。pt[1…4]="hi"找不到最长后缀字符串(也可以认为最长后缀字符串为空),因此有失败指针pt[4]→pt[root]。
前缀树中的失败指针联系的两个节点可能在同一个字符串上,比如下图中有失败指针pt[11]→pt[5],pt[10]→pt[2],这两个失败指针在前缀树中构成了环形图。
输出指针
下图中,当匹配到text[10]=pt[8]时(即使在该位置没有text[8…10]=pt[2…8]匹配成功也同样适用),我们发现不管前缀树当前位置pt[8]匹配成功与否,一定存在成功的匹配pt[1…3]。利用这一特性避免了从text[i=9]和前缀树的根节点重新开始匹配。显然这也是失败指针,但并非在匹配失败时才跳转,这类跳转称为输出指针/输出链接outputlink,用红色虚线表示。
再给一个特别情况,当匹配到text[0…2]=pt[2…7]时,有失败指针pt[7]→pt[6],输出指针pt[6]→pt[1]。因此对于前缀树中的节点pt[7],需要递归的沿着所有失败指针,找出一次成功匹配text[2…2]=pt[1…1]。当匹配到text[0…3]=pt[2…9]时,有输出指针pt[9]→pt[8],pt[8]→pt[4]。如图所示:
仔细观察可以发现,输出指针pt[i]→pt[j]有几个特性:
(1) 两个节点不在同一个字符串分支上,pt[i]是前缀树中的任意节点;
(2) 输出指针是一种特殊的失败指针,pt[j]=pt[root]。显然每个节点上只有至多一个输出指针;
(3) pt[j]是前缀树中的叶子节点;
在匹配过程中,尝试递归的沿着前缀树上当前节点的失败指针,找出所有输出指针,这些输出指针都是(在其他分支的字符串上的)成功匹配。
最终得到AC自动机算法:对于文本text上的任意字符text[i],从前缀树pt的根部开始匹配:
(1) 沿着前缀树完成一次成功匹配,text[i]上的位置i向右移动一位,从前缀树pt的根节点重新开始匹配;
(2) 匹配失败时,若前缀树上的当前节点上有非pt[root](非前缀树根节点)的失败指针,则跳到失败指针处继续匹配;若没有这样的失败指针,则文本text的匹配位置向右移动一位,从前缀树pt的根节点重新开始匹配;
(3) 匹配途中若遇到输出指针,立刻找到一次输出指针所处的成功匹配,但不影响当前字符串分支上的匹配,当前的匹配仍然继续;
AC自动机的匹配时间复杂度为O(n+msum+z)。其中z是所有模式pattern在文本text上出现的次数。
构建AC自动机
构建AC自动机需要三步:构建前缀树;构建失败指针;构建输出指针。
构造前缀树的过程详见本书的DataStructure-PrefixTree。
构造失败指针的过程是一种类似BFS/层序遍历树的算法。初始时令根节点的失败指针指向自己,首先将前缀树的第一层节点加入空队列Queue中,所有的失败指针指向根节点。然后依次从Queue中取出头节点pt[i],对于头节点的某个孩子节点pt[child],寻找它的失败指针,并将pt[child]推入Queue中,直到Queue为空:
(1) 对于前缀树根节点pt[root],其失败指针指向自己;
(2) 对于前缀树第一层节点,其失败指针指向pt[root];
(3) 对于前缀树中其他的节点pt[i],设该节点的字符为x,其父节点为pt[father],且pt[fail]为pt[father]的失败指针。若pt[fail]有字符为x的孩子节点pt[child],则显然pt[child]所在的字符串为pt[i]所在字符串的最长后缀字符串。因此有失败指针pt[i]→pt[child]。若不存在这样的孩子节点,则递归的再考虑pt[j]的失败指针,直到失败指针本身是pt[root],则有失败指针pt[i]→pt[root],递归结束;如图所示:
在构造失败指针的同时构造输出指针,若pt[i]的失败指针pt[j]不是前缀树根节点pt[root],又是前缀树的叶子节点,则有输出指针pt[i]→pt[j]。显然pt[root]不存在输出指针,前缀树第一层节点也都不存在输出指针。
AC自动机的构造时间复杂度为O(msum),加上匹配的时间,AC自动机算法的时间复杂度为O(n+msum+z)。
Aho Corasick Automata
源码
AhoCorasickAutomata.h
AhoCorasickAutomata.cpp
测试
AhoCorasickAutomataTest.cpp