背景

之前项目里面的切词模块用到了AC自动机,一直没有好好总结一下,惭愧Orz…,今天总结一下。

问题场景一 : 空间换时间

有一堆人名,大约1000w个左右,我们现在需要知道,某个人名有没有出现在这堆人名里面。

问题场景二 : 状态转移-单模匹配

有一大段文本,大约1000w行,我们现在需要知道,某一个单词有没有在里面出现过,出现过几次?

问题场景三 : 状态转移-多模匹配

有一大段文本,大约1000w行,我们现在需要知道,我们手中的1000个单词,在里面一共出现过几次?

概述

我们就通过上面的三个问题,依次来总结空间换时间的Trie树,状态转移思想单模匹配的KMP算法,状态转移思想的多模匹配算法AC自动机。

问题一答案:Trie树

如果我们想知道某个人名有没有在这1000w个人名中出现,那么我们就需要把这1000w个人名都遍历一遍,如果我们每次为了知道这个人名有没有在这1000w个人名中出现过,都需要把这1000w个人名遍历一遍的话,是相当耗费时间的,单单遍历就需要1000w次,更不用说再加上字符串的匹配了。

上面的问题就是时间复杂度过高的问题,通常我们在解决时间复杂度过高问题的时候,往往很多问题可以通过空间换时间的方法来解决,正好这个问题就属于这个范畴。

时间浪费就浪费在我们需要把所有的人名拿过来就行匹配,这就好比这1000w个在排队等你匹配,很慢,但是如果我们把这1000w个人按姓名的字典序排好队,比如,姓陈的一队,姓王的一队,依此类推,那么我们再找姓陈的人的时候,就直接去姓陈的那一队去找,不就能大大加快时间了吗。

这就好比我们在新华字典里面查找某个单词,我们根据拼音的字母有目的的去找,这样就能在偌大的字典里面快速的找到某个单词。

Trie树正是上面的思想的产物,Trie树又称为前缀树、字典树,通过把我们需要查找的所有单词提前插入到Trie树中,然后当我们需要知道某个单词有没有出现时,可以直接定位那个单词所在的树分支,然后只进行O(n)复杂度的字符串本身的匹配就好。

比如,我们的人名都是英文小写字母的,那么,我们的树节点可以像下面这样定义。

struct Node{
	int cnt;
	Node* next[26];
};

我们的根节点不放字符,然后根节点有26个子节点,从a-z,这样,当我们查找某个人名的时候,就能直接定位到那个人名首字母所在的分支,依次类推,我们只需要进行O(n)复杂度的字符串本身匹配就能知道某个人名有没有出现在Trie树中。

细心的人已经发现了,我们上面的节点是存放的指针,而不是对象本身,如果存放对象本身,那么空间浪费未免太大,为了一个字母就要开辟26个Node空间,我们可以通过链表的思想来解决这个问题,我们存链表就好了。这样就能节省很大一部分空间。而且,我们还可以想到的是,如果我们两个人名的前缀是一样的,比如linukey,lisi,那么,前面的li两个字符就只用一套空间就可以了,这也是为什么Trie树也成为前缀树的原因。

如上,我们就通过Trie树,空间换时间的思想,完美的解决了问题一。Trie树的源码见我github,地址

用哈希怎么样?

哈希也可以解决上面的问题,但是感觉并不会比Trie树快,因为哈希的速度主要靠有效的hash函数来提升,单词量过大,冲突难以避免,而且hash函数本身计算就需要时间开销,所以感觉Trie树解决这个问题更好一些。

问题二答案:KMP

问题二我们是要在1000w行的文本中去查找某个单词有没有出现过。

这个经典的在文本中查找字符串的问题,通常,如果数据量小的话,最简单的方法就是朴素字符串匹配法,就是一个一个去比较,如果遇到不同的,就把单词整体后移一个继续比较,代码如下:

bool pusu(const string& text, const string& pattern){
    int len_text = text.length();
    int len_pat = pattern.length();
    for (unsigned i = 0; i < len_text - len_pat + 1; ++i){
        for (unsigned j = i; j < len_pat + i; ++j){
            if (text[j] != pattern[j-i]) break;
            if (j-i == len_pat-1) return true;
        }   
    }   
    return false;
}

上面的朴素字符串匹配时间复杂度很高,如果数据量比较小的话,还能用一下,数据量大的话,就不实用了,kmp算法可以理解为朴素字符串匹配法的一个改进版,下面,我们来分析一下朴素字符串匹配的缺点,以及看看kmp怎样进行改进的。

我们通过一个例子来看一下,我们在ababad中查找ababae,当然,这个是不可能找的到的,不过没关系,我们用这个例子来看一下朴素字符串匹配是怎样浪费时间,以及kmp是怎样进行改进的。
text就是ababad,pattern就是ababae,下面我们分别用text以及pattern称呼。

我们可以看到,第一次匹配的时候,到e不匹配了,这个时候朴素算法接下来做的是把pattern整体后移一位继续和text比较,这个时候,发现a是不一样的,然后继续整体后移,继续比较。

我们如果仔细想一下的话,我们的第二次匹配其实是浪费的,因为我们到e不匹配的时候,这个时候前面的ababa是匹配的,我们知道第一个字符a和第二个字符b不同,所以,如果我们后移一位的话,这次比较肯定是不成立的,就造成时间的浪费了,我们知道ababa的第一个a和第三个a是相同的字符,所以,我们如果后移两位的话,第一个a是肯定相同的,那么字符串匹配成功的几率就大一些。

我们按照上面的想法,我们如果知道第一个a和第三个a相同,可以直接后移两位,我们现在可以发现,不仅第一个a和第三个a相同,而且ababa的前缀aba和后缀aba是相同的,我们可以直接整体后移两位,因为我们知道后移后的aba是重叠的,肯定相同,这个时候,pattern中的ababae的前三位aba和text中的ababad的第三位起的aba是重叠的,我们直接比较text中的d,以及pattern中的b就好,如果他们两个相同的话,就有四个匹配的字符了。

我们整理一下上面的想法,我们现在第一次匹配到e发现不匹配了,这个时候,我们发现已经匹配好的ababa的前缀和后缀有一个相同的字符串,就是aba,这个时候,如果我们后移两位的话,text中的第三位起的aba和pattern中的第一位起的aba正好重叠,他们相同,我们直接从pattern中的第四位起,和text中的d进行比较,这样,我们就可以减少无谓的比较,减少时间浪费。如下图:

失配状态转移思想

我们上面介绍的优化后的步骤,就是kmp比较字符串的方式,总结为一句话,就是如果当前匹配到不匹配的字符了,下一步应该从哪里开始匹配。这个东西有一个名称,就是失配状态转移。
失配的意思就是不匹配了,状态转移就是下一步去哪里。

我们上面那个方法介绍,说的比较笼统,下面我们用“官方”的说法总结一下kmp。
kmp算法的核心就是失配数组,这个数组记录着一些值,这些值就是当我们匹配pattern和text的时候,匹配到pattern的某一个字符时如果发现不匹配了,下一步应该后移几位继续匹配。
这个失配数组是通过计算pattern来得到的。我们看个例子:

我们上面匹配到e不匹配的时候,这个时候,前面的ababa是匹配的。下一步应该后移几位,就是通过已经匹配好的ababa计算的。

我们把ababa的所有前缀{“a”, “ab”, “aba”, “abab”}以及所有后缀{“a”, “ba”, “aba”, “baba”}进行比较,找到相同的最大字符串,就是aba,这个时候,前缀aba和后缀aba相同,也就是我们可以后移pattern到pattern自身的前缀和后缀相同的位置,这个时候,我们可以肯定aba是相同的,我们就不用再比较aba,直接从text以及pattern中aba的下一位比较就好了。

我们把pattern中每个字符匹配失败时应该后移的位置,提前计算记录到失配数组中,这样,当我们匹配时,遇到不匹配的字符,就只对当前应后移几位是最好的了。

失配数组计算

我们先来看算法导论中失配数组的计算方式,如下:

然后再来看一下我自己写的失配数组的计算方式,如下:
bool build_next(const string& pattern){
for (int i = 0; i < 500; ++i) next[i] = 0;

next[0] = 0;
for (unsigned i = 1; i < pattern.length(); ++i){
    if (pattern[i] == pattern[next[i-1]]){
        next[i] = next[i-1] + 1;
    } else if (pattern[i] == pattern[0]){
        next[i] = 1;
    } else next[i] = 0;
}

return true;

}

当时我自己推导了一遍kmp,然后自己实现了一下算法,发现这个失配数组的计算,和网上的以及算法导论上的计算方式有一点不同。

我们用next数组来称呼失配数组,我们认为,当前字符的next值,只和第一个字符以及他的前一个字符相关。共下面三种情况:
1.if (pattern[i] == pattern[next[i-1]]) next[i] = next[i-1] + 1
2.if (1不成立 && pattern[i] == pattern[0]) next[i] = 1
3.if (1和2不成立) next[i] = 0

第一种情况的话,我们好理解,比如aba中第三个a的next值是1,也就是当前最大后缀和最大前缀相同的字符a length是1,这个时候,我们来看abab最后一个b的next值,如果他和第二个b相同,那么顺其自然的ab就等于后一个ab,这个时候,最后一个b的next值就是next[a] + 1,算法导论上有正确性的推理,这里我们就通俗的说一下。

第二种情况就是最简单的情况,那就是如果最后一个字符和第一个字符相同的话,也就是前缀和后缀的一个字符相同,next值就是1

如果前面两种情况都不同,那么next值就是0

以上是我自己根据对kmp算法的理解得到的next数组的计算方式。
但是我发现和算法导论以及网页的绝大部分博客介绍的next数组计算方式有不同的地方,我估计网上的博客中next计算方式都是出于算法导论的计算方式。不同的地方就是算法导论给出的计算方式是用来一个递推的形式来计算当前next值,比如,ababad,求next[d]的时候,如果pattern[next[a]] == d,那么next[d] = next[a] + 1,不然的话,就继续比较pattern[next[next[a]]] == d,我自我感觉这样是浪费时间的,因为如果比较晚pattern[next[d]] == d不成立的话,pattern[next[next[a]]] == d是没有意义的,我没有想到这种情况下可以成立的例子。

然后,我用poj-3461这个题目分别验证了一下这两种计算next方式的程序,发现都ac了。

最后,在算法导论中找到了答案,算法导论后面有next数组正确性的推理,我们可以看到,计算当前字符next值一共就有两种情况,如下:

这个公式的意思就是,当前字符的next值,等于之前字符最大的一个next值+1,或者等于0。
也就是我上面提到的那三种形式,和这个其实是一样的。总结为一句话就是,当前字符的next值,要么等于他前一个字符next+1,要么等于1,要么等于0,计算方式就是我上面提到的那三种情况的计算方式。
然后算法导论给出的那种计算方式,原因是为了让我们可以方便的去通过递推的形式,找到合适的next值,代码可以更简便一些,但是个人感觉不太好理解。

上面是我对next数组计算方式的一些理解。

计算好next数组之后,我们就可以通过next数组,去快速的比较字符串了。

这样,第二个问题就解决了。

kmp全部代码地址

问题三答案:AC自动机

有一大段文本,大约1000w行,我们现在需要知道,我们手中的1000个单词,在里面一共出现过几次?

问题三比较问题二的话,就是我们现在不是在超大文本里面找一个单词,而是找很多个单词,虽然kmp查找单词很效率,但是,抗不住若干次单词的查找,因为我们这个场景是多模匹配,有多个单词,也就是多个模式需要去匹配,而kmp是单模匹配算法,如果一次一次去匹配的话,也是十分浪费时间,所以,我们这里需要一种算法,来通过一次遍历,把所有需要匹配的模式都匹配一遍。我们下面来介绍多模匹配算法ac自动机。

如果使用

第一次接触多模匹配的同学,估计对ac自动机的使用方式比较疑惑,最起码我当时就是相当纳闷的,一次匹配多个模式,怎样搞。。。

步骤如下:
1. 把我们所有需要匹配的模式,都进行初始化到一个容器里面
2. 把我们的目标文本,放到容器里面过滤一下,这次过滤就能把所有的模式都匹配一遍

意思就是,和我们传统的单模匹配不一样的是,我们这里不是拿着pattern去text中找,而是需要先初始化所有的pattern字符串,然后再拿着text去初始化好的pattern里面找哪一个pattern出现过
这一段介绍主要是为了让大家初步明白ac自动机的使用方法,对ac自动机有一个初步认识

算法介绍

我们看题目,Trie + kmp = ac自动机,难道意思就是把Trie和kmp组合起来就是ac自动机?其实差不多可以这样理解,但是不是代码的简单组合,而是思想的组合。下面,我们来介绍ac自动机。

我们正式介绍一下ac自动机建立的步骤,然后按照这个步骤来进行:
1. 将所有的pattern串插入到一个Trie树中
2. 计算Trie树中所有节点的失配指针
3. 用Trie树过滤text进行多模匹配

节点设计

我们上面已经说了,要把pattern串插入到Trie树中,那么自然要设计一下树节点,和传统Trie树不同的是,ac自动机有失配状态转移,所以,我们要用一个和kmp算法里面失配数组一样功能的东西,来记录匹配到某个节点不匹配时需要状态转移到什么地方,kmp中用的数组来记录的这些状态,ac自动机用的是失配指针,每个节点有一个失配指针,当这个节点不匹配的时候,就通过这个指针进行状态转移,节点设计如下:

struct Node{
	Node* next[MAX];
	Node* fail = NULL; //失配指针
	int cnt = 0;
};

第一步 : 插入

插入的话,就是Trie树的插入过程,这个时候,失配指针我们暂时不管,赋值NULL,等第二步再去构建指针,代码如下:

bool insert(const string& word){
	Node* p = head;
	for (auto c : word){
		int index = int(c-'a');
		if (p->next[index] == NULL)
			p->next[index] = get_node(); //对象池
		p = p->next[index];
	}
	++p->cnt;
	return true;
}

我们这个程序里面使用对象池来管理内存,这样管理树节点内存比较方便,我们后面再对对象池补充一下说明。

第二步 : 构建失配指针

前面我们已经把所有的模式串都插入到Trie树了,这一步我们来构建所有节点的失配指针,我们先说一下构建步骤,然后再说明为什么需要这样构建,我们使用fail指针来称呼失配指针,步骤如下:

基本原则:
1.采用bfs对Trie树进行层次遍历
2.先初始化父亲节点的fail指针,再根据已初始化的父亲节点fail指针去初始化儿子节点的fail指针
3.在遍历到父亲节点的时候,进行所有儿子节点fail指针的构建

步骤:
1.根节点的fail指针为NULL
2.父亲节点为根节点的节点的fail指针指向根节点
3.除去以上两种节点,构建其他节点fail指针的时候,采用相同的方法,比如,当前节点是A节点,这个时候A->fail已经构建完成了,我们上面的基本原则已经说明了,是在A的父亲节点那里构建的A->fail,同理,我们要在这里构建所有A的儿子节点的fail指针。我们先给出一段代码,再通过代码来讲清楚这个构建过程。

    bool build(){
        queue<Node*> q;
        q.push(head);

        while(!q.empty()){
            Node* top = q.front();
            q.pop();
            for (int i = 0; i < MAX; ++i){
                if (top->next[i] == NULL) continue;
                if (top == head) {
                    //根节点儿子fail指向根节点
                    top->next[i]->fail = head; 
                    continue;
                }

                //如果当前节点不是根节点,初始化儿子节点的fail指针时
                //我们先看看当前节点的fail指针指向的节点的儿子里面有没有和当前儿子节点相同的字符
                //如果有,那么我们把当前儿子节点的fail指针指向当前节点fail指针节点指向的儿子节点
                //如果没有,那么我们就在去当前节点的fail指针的fail指针那里看看有没有和当前儿子节点相同的字符
                //如果有,那么我们把当前儿子节点的fail指针指向当前节点fail指针的fail指针节点指向的儿子节点
                //如果没有,我们继续再去更远的fail节点去查看
                //如果直到某个节点的fail指针是NULL了,说明这个节点是根节点了
                //这个时候我们就把当前儿子节点的fail指针指向根节点
                //构建结束
                Node* p = top->fail;
                while (p && p->next[i] == NULL) p = p->fail;
                if (p == NULL){
                    top->next[i]->fail = head;
                } else {
                    top->next[i]->fail = p->next[i];
                }

                q.push(top->next[i]);
            }
        }  
    }

上面注释中,我已经把整个构建步骤都讲清楚了,上面的代码是比较笨的一种写法,目的是让大家更容易理解这个逻辑。

其实上面的步骤是十分简单的,但是我们只看上面的步骤的话,还不能理解为什么要那样构建fail指针,我们暂时先不解释为什么那样构建,因为我们还有一个重要的步骤没有说,就是query,我们先讲完query,再来讲为什么需要那样构建。

第三步 : 查询

理解ac自动机是怎样进行查询的,对于理解ac自动机为什么那样构建起到至关重要的作用。我们还是先来看代码,通过代码进行说明查询步骤。代码如下:

    int query(const string& text) const{
        Node* p = head;
        int result = 0;
        // 我们像Trie树查询那样,通过一个字符一个字符的跟进来查询
        // 不同的是,Trie树是通过遍历pattern来查询,ac自动机是通过遍历text来多模查询
        for (auto c : text){
            int index = int(c - 'a');

            // 如果下一个字符不在当前节点的孩子中,我们就去当前节点的fail指针那里找
            // 如果当前节点的fail指针那里也没有,我们就去fail指针的fail指针那里找 (失配转移)
            while (p != NULL && p->next[index] == NULL) p = p->fail;
            // 如果找到最后发现是NULL,表示这个text匹配到目前为止已经找不到连续的串了,我们回到根节点
            if (p == NULL) {
                p = head;
                continue;
            }   

            // 如果找到了一个匹配的孩子节点,我们就看看这个孩子节点字符结尾代表的字符串,是不是一个模式串,特征就是cnt >= 1
            // 我们看完了当前孩子节点,继续去当前孩子节点的fail指针那里看看是不是一个模式串
            // 继续上面的过程,直到有一个节点的fail是NULL,说明到头了
            p = p->next[index];
            for (Node* tmp = p; tmp && tmp->cnt > 0; tmp = tmp->fail) ++result;
        }   
        return result;
    }  

通过上面的步骤,我们就能通过一次遍历text,来匹配出所有需要查询的模式串出现的次数,至于ac自动机为什么能这样查询,以及为什么能像上一个步骤那样构建失配指针,我们在下面进行说明。

为什么需要这样构建ac自动机

前面,我们说明了ac自动机的插入,构建失配指针,查询,已经过ac自动机的工作流程有了一个整体的了解,但是,我们还有最关键的一步没有说,就是ac自动机为什么能这样工作,也就是ac自动机算法的正确性。
我们这里做不到像数学证明那样严格证明ac自动机的正确性,但是,我们可以通过大白话的方式,来理解ac自动机的运作方式。

下面,我们通过一个例子,来通过我自己的理解,简单的解释一下为什么要那样构建fail指针。

我们现在来看一个用目标字符串集合{abd,abdk, abchijn, chnit, ijabdf, ijaij}构造出来的AC自动机图示:

这张图里面,所有指向根节点的fail指针都没有画出。红色圈表示当前字符截止的字符串为一个模式串。虚线代表fail指针指向。

我们下面通过两个例子,来依次说明两个问题:
1.ac自动机是怎样进行失配状态转移的
2.ac自动机为什么能够进行多模匹配

ac自动机实现失配转移

我们来看ac自动机匹配text为ijabdk的时候,是怎样进行匹配的,这个时候,我们查询的模式串就是abdk。

首先,按照我们程序的逻辑,我们依次遍历,i -> j -> a -> b -> d,到了d之后,我们发现,d的下一个没有k,这个时候,如果没有失配指针的话,就查询截止了,因为下面没法走了,但是,按照我们程序的逻辑,如果下面没路可以走了,我们就去当前节点的fail指针指向的节点那里看看有没有路可以走。果然,d的fail指针指向的左边的d节点的孩子节点那里,有一个k,这样,我们就成功查到了abdk这个模式串。

但是大家肯定还有疑惑,就是为什么这样能行的通,我们明明是查找的ijabdk,为什么能把abdk这个模式串匹配出来,因为按照我们以前Trie树查询逻辑,这样很神奇。因为ac自动机是多模匹配模式,要想明白刚刚是怎样失配转移成功匹配到模式串的,我们必须清楚ac自动机是怎样多模匹配的,看下面。

ac自动机实现多模匹配

我们看到ijabdf那个分支,我们看到abd三个节点的fail指针,分别指向左边根节点开始的abd三个节点。

按照我们程序的逻辑,我们在这颗已经构建好失配指针的Trie树里面,通过ijabd这个text来匹配模式串,我们会发现,当我们遍历到d这个字符的时候,我们首先看看d这个节点字符为结尾代表的字符串是不是一个模式串,我们发现并不是,然后,我们就去d的fail指针指向的节点那里,看看d的fail指针指向的节点字符为结尾代表的字符串是不是一个模式串,我们发现,左边的abd正好是一个模式串,然后,我们就查询到了abd这个模式串。

感觉是不是比较神奇,按照Trie树的逻辑,我们需要直接从头开始查询abd,才能够查询到abd是否为一个模式串,但是,我们现在用ac自动机,我们查询ijabd,就能够直接查询出里面的模式串abd,这是怎样做到的?

我们失配指针的第一个作用,就是失配状态转移。上面我们将的那个例子。
我们的失配指针的第二个作用,就是当前模式串的子串中,如果有一个子串等于其他模式串,我们就让这个子串的相应节点的fail指针,指向那个模式串相应的几点,这样,当我们有文本匹配当前模式串的时候,就能顺便匹配出另外一个模式串。这也就是为什么上面失配转移能成立的原因。

但是还有一个新问题,就是,为什么我们在构建ac自动机的时候,能让当前模式串子串指向和他相同的其他模式串。

还记得我们前面讲构建失配指针时提到的基本原则和步骤吗,根节点的fail指针是NULL,然后根节点的孩子指向根节点,然后加上我们下面说的构建步骤后,我们仔细想想的话,就能够理解,我们在构建失配指针的时候,确实能够把当前模式串的子串指向和他相同的其他模式串。

这个过程是我自己理解的,没有设计到严格的数学推理,但是我感觉还比较好理解。

本文全部代码地址

总结

说到这里,ac自动机相关的知识点就总结完了,肯定还有很多不足的地方,欢迎看到这篇笔记的同学指出来,后面如果有了新的认识,也会补充进来。


原创文章,转载请注明地址: 文章地址