单模式匹配

问题定义

在一个主文本字符串S内查找一个模式串W的出现位置.

在下述中,用下标i表示在主字符串S中的下标,S长度为n,下标j表示在模式串W中的下标,W长度为k.

解决算法

BF(Brute Force)算法

BF算法是最容易想到的解决单模式匹配问题的算法,是一种暴力搜索算法.算法时间复杂度O(n*k). 算法的基本思想是: 用i依次遍历S,在循环内,再遍历j来判断当前是否匹配上. 算法伪代码如下:

def bf_string_matcher(S,W):
    if (S or W) is None:
        return
    n = len(S)
    k = len(W)

    for i in range(0, n-k+1) :
        match = True
        for i in range(0, k) :
            if W[i] is not S[i+j]:
                match = False
                break
        if match:
            print "Pattern occurs with shift",i

KMP算法

KMP算法全称是Knuth-Morris-Pratt算法,是以3个发明人名字命名的,是解决单模式匹配问题的经典算法.时间复杂度为O(n+k),其中求next数组的时间复杂度为O(k),匹配时比较的时间复杂度为O(n).

KMP算法和BF算法比较起来, 最主要的改进是有效利用了已匹配的信息,使得算法可跳过一些没有必要再进行尝试的比较.在遇到匹配失效时,i无需迭代到i+1,而是可以直接跳过一些,迭代到i+m,j也无需回溯到0.

原理解释

下面假设S=BBC ABCDAB ABCDABCDABDE,W=ABCDABD.以一个具体例子说明KMP算法的原理: image.png   上面一个基本的事实是,当空格与D不匹配时,其实W前面的ABCDAB是与S当前空格前的6个字符是完全匹配的.这样,也就意味着接下来的5次(6-1)后移中,部分比较是可以提前计算出来的: image.png

可以看到当前已经匹配上的部分是ABCDAB,而后续的5次后移的比较中,分别会进行ABCDAB的等长的前缀与后缀的比较,如果这些前缀与后缀不等,实际上就意味着这次移位的比较最终是失败的(因为最终要匹配成功,必须完全匹配,只要部分有一个地方不匹配,就匹配失败),可以跳过这些移位.这个例子中,可以直接向后移动4位(i+4).而且此时已知AB=AB,故j也无需再回溯到0,而是可以回溯到j+2,这样接下来需要进行的比较是S[i+j]与W[j],即S[10]与W[2]. image.png 显然,遇到所有的部分匹配,都可以用这种方法加速.而对于一个确定的W来说,所有的部分匹配就是W的所有前缀.每种情况下的部分匹配, 关键是要计算出在这个部分匹配下,部分匹配部分的最大的公共前缀和后缀,这个公共的最大前缀和后缀的长度就作为部分匹配值,因此当W确定后,可以在一个O(k)的复杂度下,计算出W的一个表,这个表叫部分匹配表(或者其变形next表或失配函数表). 这这个例子中,此表值为:

搜索词 A B C D A B D
部分匹配值 0 0 0 0 1 2 0

因此,KMP算法匹配是的流程是,先根据当前的W,计算出其部分匹配表.(一个长度为k的数组即可表示.) 然后在S上,根据W和此表,进行比较搜索.

部分匹配值表与next表

假设部分匹配值表为数组T,失配时,W匹配到j,S中当前起始的匹配点为i(当前是在和S中的S[i+j]进行匹配).则失配时,按如下公式更新:

#模式串向右移动的位数：已匹配字符数 - 失配字符的上一位字符所对应的部分匹配表值
i_new = i+ (j(已匹配的字符数) - T[j-1] )
j_new = T[j-1]
#接下来比较S[i_new+j_new]=S[i+j]与W[j_new].

从这里也可以解释部分匹配值,为什么是要选取公共的最大前缀和后缀的长度. 这是因为最大的匹配长度,带来的是跳过的最小的移动位数.这样不会漏掉任何一个可能的匹配. 但当j=0时,就失配,并没有上一个字符,此时应该是让i_new=i+1;另外j的最大值也是len(W)-1(下标从0开始),这时查表也只是会用到T[len(W)-2],最后一个T[len(W)-1]没有用到,所以在实际中,经常对此表做一个变换,变成next表,记为数组N. 从部分匹配值表可按如下方法得到next表:

next表 = 部分匹配值表数字中值整体向右移动一位，然后初始值赋为-1

用next表的话:

#模式串向右移动的位数为：失配字符在W中所在位置(j) - 失配字符对应的next值
i_new = i+ (j(已匹配的字符数) - N[j] )
j_new = max(0,N[j])
#接下来比较S[i_new+j_new]与W[j_new]
#当N[j]>=0时,实际上说明前面已经有了部分匹配.当前S中要比较的字符下标认为i+j,此时j回退到N[j] (注意N[j]<j必定成立)
#当N[j]<0时,说明一开始的匹配就失败,i_new=i+1, i_new+j_new=i+1,j_new=0. i加1,W向右移一位.

next表用起来更方便,但两个表本质上一样的.

next表的求解

最直观的求解方法是按照定义,暴力求解. 但实际上可以用递归的方法求解,比较更少的次数. next数组的计算过程利用了递归原则，如下：

假设对于值k，已有p0 p1, …, pk-1 = pj-k pj-k+1, …, pj-1，也即串p[0,j-1]的最长相同前后缀的长度为k,这样按next[j] 的规则（为 前面的串的value值）,next[j] = k。下面从next[j]求next[j+1],分情况讨论： （1）pk = pj, 那么就有p0 p1, …, pk = pj-k pj-k+1, …, pj，这样同理得到next[j+1] = k + 1 = next[j] + 1; （2）pk ≠ pj, 那么就不能简单的由next[j]得到next[j+1]了，next[j+1]的计算过程就需要以其它方法了，不过由于存在next[j]=k,也即p0 p1, …, pk-1 = pj-k pj-k+1, …, pj-1,那么对于i,i>=0且i<k-1, 则必定会有 pi pi+1, …, pk-1 = pj-k+i, pj-k-i+1, …, pj-1。这样对于p0 p1, …, pk-1,我们假设next[k] = k-i, 则存在 p0 p1, …, pk-i-1 = pi pi+1, …, pk-1, 则p0 p1, …, pk-i-1 = pj-k+i, pj-k-i+1, …, pj-1，则时如果 pk-i = pj了，则如情况下，next[j+1] 就可以等于k-i+1,即next[j+1] = next[k] + 1, 若不存在，则可以继续递归下去。 直到找到这样一个i,或者停止。 实现如下:

/**
 * 求next数组
 * @param char* p 匹配串
 * @param int   l 匹配串的长度
 * @param array n next数组
 * 
 * @return void
 */
void getnext(char* p, int l, int n[])  
{  
    int k = -1, j = 0;  
    n[0] = -1;  
    while (j < l - 1) {  
        //p[k]表示前缀，p[j]表示后缀  
        if (k == -1 || p[j] == p[k]) {  
            ++j, ++k;  
            n[j] = k;  
        } else {  
            k = n[k];  
        }  
    }  
}

代码实现(python)

def getPartialTable(pattern):
    if not pattern:
        return None
    lp = len(pattern)
    res = [-1, 0]
    if lp > 1:
        for curr in xrange(1, lp):
            ptr = curr
            while ptr > 0 and pattern[curr] != pattern[res[ptr]]:
                ptr = res[ptr]
            else:
                res.append(res[ptr] + 1)
    return res

def matchPatternKMP(string, pattern):
    if not string or not pattern:
        return None
    p_table = getPartialTable(pattern)
    start, matched = 0, 0
    ls, lp  = len(string), len(pattern)
    stop    = ls - lp + 1
    res     = list()
    while True:
        while matched == lp or string[start + matched] != pattern[matched]:
            if matched == lp:
                res.append(start)
            start   += matched - p_table[matched]
            matched  = max(0, p_table[matched])
            if not start < stop:
                return res
        else:
            matched += 1

if __name__ == '__main__':
    string  = 'abababaababacbababacb'
    pattern = 'aaa'
    print 'string:\t\t%s\npattern:\t%s' % (string, pattern)
    print matchPatternKMP(string, pattern)

参考

多模式匹配

问题定义

:::info 在一个主文本字符串S内查找多个模式串(这里模式集合定义为Pset)的出现位置. :::

这里假设S的长度为n,用下标i表示在主字符串S中的起始匹配下标,模式集合PSet的元素个数为m.

解决算法

尝试一:遍历模式集合,用m次KMP算法

这个是最容易想到的思路,即把多模式问题转换为单模式匹配的问题. 但是实际中,len(PSet)一般是很大的,通常有几万/几十万的量级.太过低效.

尝试二:把PSet构建到Trie(前缀树)中,遍历S

这个思路是把所有的模式构建到一个Trie的数据结构中,这样中S中一个指定的起始比较位置,利用Trie可以很快的找到所有前缀的特性,就可以很快找出中这个其实比较位置上,所有匹配到的模式串.然后起始比较位置下移一位,继续找符合的前缀模式. 这个方法利用Trie,解决了上述len(PSet)很大时,效率太慢的问题,但其实比较位置总是向前移动一步,当len(S)很长时,也不高效,也是一种暴力的匹配方式.(我在京东实现的分词模块中的多模式匹配实现,其实就是这种方式,汗!)

AC自动机

AC自动机(Aho–Corasick算法)是贝尔实验室1975年提出的著名的多模式匹配算法.AC自动机在实现上要依托于Trie树并借鉴了KMP模式匹配算法的核心思想。实际上可以把KMP算法看成每个节点都仅有一个孩子节点(只有一条路径的树)的AC自动机。(当需要匹配的模式词表缩减到只有一个word,也可以按AC自动机的方式建trie树和fail指针,此时即退化为KMP算法)

原理解释

AC自动机的基础是Trie树,模式集合Pset存储在Trie树上.但AC自动机和上述的尝试二的方法比起来,是给树中的所有节点加了一个fail指针,它表示输入的字符与当前结点的所有孩子结点都不匹配时(注意，不是和该结点本身不匹配)，自动机的状态应转移到的状态（或者说应该转移到的结点）。fail指针的功能可以类比于KMP算法中next数组的功能。这样就可以实现失配时,可有效利用了已匹配的信息,使得算法可跳过一些没有必要再进行尝试的比较.在遇到匹配失效时,i无需迭代到i+1.

Trie树 Trie树也就是前缀树.构建出Trie树,可以很方便的实现如下操作:

  1. 输入一个S,判断S是否出现在PSet中(并可获取到对应的value) 这时,只需要在树上遍历一次(甚至可以提前返回),就可以判断出. 实际上,这相当于实现了dict的功能,不过常规的dict一般用hash实现.因为Trie还是比较消耗内存的一种结构.
  2. 支持common-prefix-search 输入一个S,查询出PSet中所有的属于S前缀的模式. 同样,也只需按S的字母序在树上遍历一次即可(半路匹配失败,也可以提前返回).效率很高. 而这个hash的方法就不支持这种查询了.
  3. 支持predictive-search 输入一个S,查询出PSet中所有以S为前缀的模式.利用这个特性,很容易实现一个基本的搜索suggestion.hash的方法同样不支持这种查询了.
一个具体的例子

假设PSet={abd,abdk, abchijn, chnit, ijabdf, ijaij}.则构造出的AC自动机如下图: image.png 其中根结点不存储任何字符，根结点的fail指针为null。虚线表示该结点的fail指针的指向，所有表示字符串的最后一个字符的结点外部都用红圈表示，我们称该结点为这个字符串的终结结点。每个结点实际上都有fail指针，但为了表示方便**，本文约定一个原则，即所有指向根结点的 fail虚线都未画出**。

从上图中的AC自动机，我们可以看出一个重要的性质：每个结点的fail指针表示由根结点到该结点所组成的字符序列的所有后缀　和　整个目标字符串集合（也就是整个Trie树）中的所有前缀 两者中最长公共的部分的最后一个字符节点。 比如图中，由根结点到目标字符串“ijabdf”中的 ‘d’组成的字符序列“ijabd”的所有后缀在整个目标字符串集{abd,abdk, abchijn, chnit, ijabdf, ijaij}的所有前缀中最长公共的部分就是abd，而图中d结点（字符串“ijabdf”中的这个d）的fail正是指向了字符序列abd的最后一个字符。

原理直观的解释 假设S串与模式的起始匹配位置在i,按Trie树匹配到了D,然后D的子节点只有F,而S串中为K,出现了失配.(在匹配的过程中,只要遇到一个节点上模式终点,就可以输出一个模式了,这其实就是Trie的common-prefix-search).失配,也就意味着,在当前的起始匹配位置i上,所有模式中已经没有可以再匹配出的模式了.此时按前述的尝试二是起始匹配位置下移1位(i++). 但同样,类似于KMP算法,这里是可以优化的. 首先,我们知道从根节点到当前的D的路径IJABD是和S中对应部分匹配的.所以,接下来的起始匹配点i的几次后移,都是需要和IJABD的几个后缀比较(JABD、ABD、BD、D),如果一个后缀和所有模式的前缀都没有匹配上,这个此移动式没有意义的,可以跳过.同样和KMP类似,最大的匹配,意味着最小的跳跃,不会错过任何一个可能的匹配. image.png

AC自动机的运行过程

1）表示当前结点的指针指向AC自动机的根结点，即curr = root
2）从文本串中读取（下）一个字符
3）从当前结点的所有孩子结点中寻找与该字符匹配的结点，
若成功：判断当前结点以及当前结点fail指向的结点是否表示一个字符串的结束，若是，则将文本串中索引起点记录在对应字符串保存结果集合中（索引起点= 当前索引-字符串长度+1）。curr指向该孩子结点，继续执行第2步
若失败：执行第4步。
4）若fail == null（说明目标字符串中没有任何字符串是输入字符串的前缀，相当于重启状态机）curr = root, 执行步骤2，
否则，将当前结点的指针指向fail结点，执行步骤3)

现在，我们来一个具体的例子加深理解，初始时当前结点为root结点，我们现在假设文本串text = “abchnijabdfk”。 image.png 图中的实曲线表示了整个搜索过程中的当前结点指针的转移过程，结点旁的文字表示了当前结点下读取的文本串字符。比如初始时，当前指针指向根结点时，输入字符‘a’,则当前指针指向结点a，此时再输入字符‘b’,自动机状态转移到结点b,……，以此类推。图中AC自动机的最后状态只是恰好回到根结点。

需要说明的是，当指针位于结点b（图中曲线经过了两次b,这里指第二次的b，即目标字符串“ijabdf”中的b）,这时读取文本串字符下标为9的字符（即‘d’）时，由于b的所有孩子结点（这里恰好只有一个孩子结点）中存在能够匹配输入字符d的结点,那么当前结点指针就指向了结点d，而此时该结点d的fail指针指向的结点又恰好表示了字符串“abc”的终结结点（用红圈表示），所以我们找到了目标字符串“abc”一次。这个过程我们在图中用虚线表示，但状态没有转移到“abd”中的d结点。

在输入完所有文本串字符后，我们在文本串中找到了目标字符串集合中的abd一次，位于文本串中下标为7的位置；目标字符串ijabdf一次，位于文本串中下标为5的位置。

AC自动机的构造方法与原理

构造的基本方法

首先我们将所有的目标字符串插入到Trie树中，然后通过广度优先遍历为每个结点的所有孩子节点的fail指针找到正确的指向。 确定fail指针指向的问题和KMP算法中构造next数组的方式如出一辙。具体方法如下

1）将根结点的所有孩子结点的fail指向根结点，然后将根结点的所有孩子结点依次入列。
2）若队列不为空：
   2.1）出列，我们将出列的结点记为curr, failTo表示curr的fail指向的结点，即failTo = curr.fail
   2.2) a.判断curr.child[i] == failTo.child[i]是否成立，
           成立：curr.child[i].fail = failTo.child[i]，
           不成立：判断 failTo == null是否成立
                  成立： curr.child[i].fail == root
                  不成立：执行failTo = failTo.fail，继续执行2.2）
       b.curr.child[i]入列，再次执行再次执行步骤2)
   若队列为空:结束
通过一个例子来理解构造AC自动机的原理

每个结点fail指向的解决顺序是按照广度优先遍历的顺序完成的，或者说层序遍历的顺序进行的，也就是说我们是在解决当前结点的孩子结点fail的指向时，当前结点的fail指针一定已指向了正确的位置。 image.png 为了说明问题，我们再次强调“每个结点的fail指针表示：由根结点到该结点所组成的字符序列的所有后缀 和 整个目标字符串集合（也就是整个Trie树）中的所有前缀 两者中最长公共的部分”。

以上图所示为例，我们要解决结点x1的某个孩子结点y的fail的指向问题。已知x1.fail指向x2，依据x1结点的fail指针的含义，我们可知红色实线椭圆框内的字符序列必然相等，且表示了最长公共部分。依据y.fail的含义，如果x2的某个孩子结点和结点y表示的字符相等，那么y.fail就该指向它。

如果x2的孩子结点中不存在结点y表示的字符，这个时候该怎么办？由于x2.fail指向x3，根据x2.fail的含义，我们可知绿色方框内的字符序列必然相等。显然，如果x3的某个孩子结点和结点y表示的字符相等，那么y.fail就该指向它。

如果x3的孩子结点中不存在结点y表示的字符，我们可以依次重复这个步骤，直到x结点的fail指向null，这时说明我们已经到了最顶层的根结点，这时，我们只需要让ｙ.fail = root即可。

构造的过程的核心本质就是，已知当前结点的最长公共前缀的前提下，去确定孩子结点的最长公共前缀。这完全可以类比于KMP算法的next数组的求解过程。

确定图中h结点fail指向的过程 现在我们假设我们要确定图中结点c的孩子结点h的fail指向。图中每个结点都应该有表示fail的虚线，但为了表示方便,按照本文约定的原则，所有指向根结点的 fail虚线均未画出。 image.png

左图中，蓝色实线框住的结点的fail都已确定。现在我们应该怎样找到h.fail的正确指向？由于且结点c的fail已知（c结点为h结点的父结点），且指向了Trie树中所有前缀与字符序列‘a’‘b’‘c’的所有后缀（“bc”和“c”）的最长公共部分。现在我们要解决的问题是目标字符串集合的所有前缀中与字符序列‘a’‘b’‘c’ ‘h’的所有后缀的最长公共部分。显然c.fail指向的结点的孩子结点中存在结点h，那么h.fail就应该指向c.fail的孩子结点h，所以右图表示了h.fail确定后的情况。

确定图中i.fail指向的过程 image.png 确定i.fail的指向时，显然h.fail(h指图中i的父结点的那个h)已指向了正确的位置。也就是说我们现在知道了目标字符串集合所有前缀中与字符序列‘a’‘b’‘c’ ‘h’的所有后缀在Trie树中的最长前缀是‘c’‘h’。显然从图中可知h.fail的孩子结点是没有i结点（这里h.fail只有一个孩子结点n）。字符序列‘c’‘h’的所有后缀在Trie树中的最长前缀可由h.fail的fail得到，而h.fail的fail指向root（依据本博客中画图的原则，这条fail虚线并未画出）,root的孩子结点中存在表示字符i的结点,所以结果如右图所示。

在知道i.fail的情况下，大家可以尝试在纸上画出j.fail的指向，以加深AC自动机构造过程的理解。

参考