精华内容
下载资源
问答
  • AC自动机详细讲解
    千次阅读
    2021-03-13 08:46:27

    AC自动机简介:

    首先简要介绍一下AC自动机:Aho-Corasickautomation,该算法在1975年产生于贝尔实验室,
    是著名的多模匹配算法之一。一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,
    让你找出有多少个单词在文章里出现过。要搞懂AC自动机,先得有字典树Trie和KMP模式匹配算法的
    基础知识。KMP算法是单模式串的字符匹配算法,AC自动机是多模式串的字符匹配算法。
    此AC和平时刷题的AC可不一样,AC自动机不自动AC编程题。
    个人觉得AC自动机根字典树的联系比较大,但是和KMP的联系并不大。

    字典树Trie:
    字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,
    排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的
    优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
    简而言之:字典树就是像平时使用的字典一样的,我们把所有的单词编排入一个字典里面,当我们
    查找单词的时候,我们首先看单词首字母,进入首字母所再的树枝,然后看第二个字母,再进入相应的树枝,
    假如该单词再字典树中存在,那么我们只用花费单词长度的时间查询到这个单词。

    字典树的构建过程:
    当前给出n个字符串,我们用这n个字符串来构建字典树,构建的过程是这样的,按顺序将n个字符串插入
    到字典树,插入某个单词的时候,我们遍历这个字符串,如果发现当前要插入的字符其节点在先前已经建成,
    我们直接取考虑下一个字符即可。当我们发现当前要插入的字符对应的节点还没有创建,我们就创建一个新的
    节点。往下处理其他字符,重复上述过程。

    例如一个例子she,he,say,her,shr构建字典树的形态如下动图所示。

    其中绿色节点代表从根节点到当前节点所组成的字符串是一个完整的单词。我们对其标记一下。

    字典树的构建代码:非完全版
    /*动态链表写法*/
    const int maxn = 26;  
    typedef struct TrieNode          ///字典树节点定义  
    {  
        bool isWord;                 ///标记是否是完整的单词
        struct TrieNode *son[maxn];  ///26个儿子。  
    }Trie;  
    void insertWord(Trie *root,char word[])  ///将单词word插入到字典树  
    {  
        Trie *p = root;  
        int i = 0;  
        char ch = word[i];  
        while(ch != '\0')  
        {  
            if(p->son[ch-'a'] == NULL)       ///节点不存在创造节点
            {  
                Trie *node = (Trie*)malloc(sizeof(Trie));  
                for(int i = 0; i < maxn; i++)  
                {  
                    node->son[i] = NULL;  
                }  
                node->isWord = false;  
                p->son[ch-'a'] = node;  
                p = p->son[ch-'a'];  
            }  
            else                          ///节点已经存在,直接到下一个节点
            {  
                p = p->son[ch-'a'];  
            }  
            ch = word[++i];  
        }  
        p->isWord = true;                 ///单词插入完毕后,进行标记

     
     
     /**静态链表做法**/
    const int maxn = 26;       
    struct TrieNode  
    {  
        bool isWord; 
        struct TrieNode *son[maxn];  
    }node[100000];  
    int num;  
    TrieNode* createNode()  
    {  
       TrieNode *p = &node[num++];  
       for(int i = 0; i < maxn; i++)  
       {  
           p->son[i] = NULL;  
       }  
       return p;  
    }  
    void insertTel(TrieNode *root,char word[])  
    {  
        TrieNode *p;  
        p = root;  
        int i = 0;  
        char ch = word[i];  
        while(ch != '\0')  
        {  
            if(p->son[ch-'a'] == NULL)  
            {  
      
                p->son[ch-'a'] = createNode();  
                p = p->son[ch-'a'];  
                p->isWord = false;
            }  
            else  
            {  
                p = p->son[ch-'a'];  
            }  
            ch = tel[++i];  
        }  
        p->isWord = true;
    }  

    以上两个代码是构建字典树的代码:
    一个是动态链表一个是静态链表写的,动态链表写的时候就是动态分配内存,有点就是用多少节点创建
    多少节点,缺点,分配内存时比较耗时,有时候会超时,静态链表写法优点就是比较快,但是会消耗大量的
    内存,用不用反正我都开了那么多。

    AC自动机第一关键点创建字典树:

    AC自动机作为多模式匹配,假如有n个模式串,一个长为m的文本串,让找有多少个模式串在文本串中
    出现过,我们首先要做的第一步就是用n个模式串建立字典树,上面我们已经讲解了如何创建字典树,因此
    我们对n个模式串she,he,say,her,shr已经可以创建出上图的字典树。

    AC自动机第二关键点找节点的Fail指针构建AC自动机:

    在KMP算法中,当我们比较到一个字符发现失配的时候,我们会通过next数组找到下一个开始匹配的位置,
    然后进行字符串的匹配操作,当然我们知道KMP算法适用于单模式匹配,所谓单模式匹配就是给出一个模式串,
    给出一个文本串,然后看模式串在文本串中第一次出现的位置。
    在AC自动机中,我们也有类似next数组的东西就是fail指针,当发现失配的时候,跳转到fail指针指向的位置,
    然后再次进行匹配操作,AC自动机之所以能够实现多模式串与文本串的匹配,就归功于fail指针的建立,也就是fail
    指针的建立,我们这颗树才变成了AC自动机,否则其就是一颗单纯的字典树。
    fail指针的建立是通过广搜(BFS)来实现的,其节点搜索的顺序与树的层次遍历是完全相同。对于直接与
    根相连的节点来说,这些节点的fail指针直接指向root(根节点).其他节点的fail指针求法如下。假设当前节点为
    father,它已经求过fail指针了,如果father出队,我们现在就要求father节点孩子们的失败指针。对于那些非空
    的孩子节点,由于他们存在,所以我们要求他们的fail指针,对于father下面为空的孩子节点,我们不予理睬就
    可以了。对于father节点的非空孩子t,t必然代表了一个字母,此时我们首先找到father->fail。然后看看
    father->fail->child  有没有等于和t表示的字符是一样的,如果有的话t->fail = father->fail->child。如果发现
    没有的话,我们继续往前翻找,father->fail->fail->child有没有和t表示的字符一样的孩子,有的话
    t->fail = father->fail->fail->child。否则的话继续往前翻找,翻找到什么程度,如果都翻到根了,还没找到
    对应的节点的话,则我们只能让t->fail指向根节点了。
    下图是各个节点的fail指针的指向:

    图中最后一个yasherhs是文本串。
    我们按照广搜的思路来走一下。最开始的时候根节点root进队。
    1.root出队,我们为root的儿子们找fail指针,通过检测我们发现当前是要给root的儿子们h,s找fail,指针,
    股h,s直接指向root,如图中红色虚线所示。并且h,s依次进队。当前队列中有h,s
    2.接下来h出队,我们现在要给h的儿子e找fail指针,因此首先我们temp = h->fail,我们知道temp现在肯定
    是root,然后会看root的孩子有没有字符是e的,发现是没有的,这时候已经到根了,没有办法往前再翻找了,所以
    节点e的fail指针就指向了root。同时e进队。当前队列有s,e
    3.接下来出队的是s,我们现在要给s的儿子a,h找fail指针,按照顺序先给a找,同样temp = s->fail,则temp现在
    指向根节点root,我们发现根节点的孩子是没有字符是a的,所以a的fail只能指向root.同时a进队,此时队列有e,a。然后找h的fail指针,同样temp = s->fail,则temp依然是根,我们发现根节点的孩子有字符是h的,则这个时候h的
    fail指针就会指向第二层的h节点。然后h进队,当前队列e a h.第三层的节点的fail指针就都找完了,如图中蓝色虚线
    所示。
    4.接下来出队的e,然后该给e的孩子r找fail指针,同样temp = e->fail。则temp是根root当前,我们看根节点
    下面没有字符是r的节点,所以r的fail会指向root,r进队,当前队里面有 a , h , r.
    5.接下来出队的a,然后找a的孩子y的fail指针,可以发现情况和4这一条是相同的,所以y的fail指针也是指向
    root的。同时y进队。当前队里面有h,r,y
    6.接下来h出队,我们给h的孩子e,r找fail指针,按顺序先给e找,temp = h->fail。则当前temp就是第二层的
    h,然后我们看temp的孩子有没有是字符e的,发现第二层的h其孩子有字符值是e的.则e的fail指针就指向图中第
    三层的e,同时e进队,然后我们找r的fail,会发现r其情况与4,5是相同的,则r的fail指针指向root.并且r进队。
    当前队中节点有:r,y,e,r。 第四层的所有点的fail指针已经找到,其指向如图中绿色虚线线条所示。
    7.r出队,找r的孩子的fail指针,发现r没有孩子,那就不管了,后面的y,e,r都是没孩子的,依次出队就可以
    了。
    此时我们已经给字典树上各个节点求了fail指针,所以AC自动机已构建完毕。

    求Fail指针的代码片段:
    ///求fail指针。构造AC自动机。  
    void build_AC_automaton()  
    {  
        TrieNode *p;  
        p = root;  
        queue<TrieNode*>qu;  
        qu.push(p);  
        while(!qu.empty())  
        {  
            p = qu.front();  
            qu.pop();  
            for(int i = 0; i < allSon; i++)  
            {  
                if(p->son[i] != NULL) ///第i个孩子存在  
                {  
                    if(p == root)  ///p是根,根节点的孩子的失败指针都指向自己  
                    {  
                        p->son[i]->fail = root;  
                    }  
                    else  
                    {  
                        TrieNode *node = p->fail;   
                        while(node != NULL)  
                        {  
                            if(node->son[i]!=NULL)  
                            {  
                                p->son[i]->fail = node->son[i];  
                                break;  
                            }  
                            node = node->fail;  
                        }  
                        if(node == NULL)  
                            p->son[i]->fail = root;  
                    }  
                    qu.push(p->son[i]);  
                }  
            }  
        }  
    }  

    AC自动机第三关键点文本串的匹配:

    最后一步就是让文本串上AC自动机上跑一遍。匹配的过程分了两种情况。
     (1)当前节点node与文本串上字符成功匹配,我们要做的是检测当前节点是否有标记表示它是模式串
    中一个单词的结尾,如果是结尾的话,就说明当前节点到根这条路上字母组成的单词是一个完整的单词,
    我们统计的单词数就要加1.不管它是不是结尾我们都要执行下面的操作,此时我们可以利用当前节点的fail指针,
    找到另一个节点temp=node->fail。如果发现它也有标记表明它是一个完整的单词,则我们就可以让统计的单词
    数加1.That's why。因为temp=node->fail。从temp这个节点到root所组成的字符串是从node到root所组成字符
    串的后缀,你肯定又到问That's why。然而这点还是要从fail指针的求解过程中找答案。首先我们知道一点,node
     和 node->fail这两个节点代表的字符是相同的。(除非节点的fail指针是root)现在有节点father我们给其孩子
    child找fail指针,首先找到father的fail指针记为fail_father,然后看fail_father的孩子有没有和child所代表的字符
    相同的。有的话我们记这个节点为fail_child。则child->fail = fail_child。father和fail_father所代表字符相同,
    child和fail_child所代表的字符相同。则他们的关系如图所示:

    同样的道理,father节点和它的父亲也是按上面的方法给father找fail指针的。所以当前node节点匹配上了
    文本串的一个字符,记root到node的字符串用[root,node]来表示,则我们可以通过temp= node->fail.则根据上面的讲解,[root,temp] 是 [root,node]的后缀,如果发现当前节点temp有标记,则说明[root,temp]也是一个完整的单词,要统计上,temp = temp->fail.[root,temp]又是上一个[root,temp]的后缀,如果它也是一个完整单词,则也要统计。直到翻找到根节点我们就不用找了。这就是AC自动机,不会露掉一个串。
    (2)如果当前节点node匹配上了文本串的一个字符,然后发现匹配下一个字符的时候是失配的,那么我们
    就到node->fail处,因为【root,node->fail】是【root,node】的后缀,我们知道【root,node->fail】这一段还是
    根文本串中的一段是匹配着的,我们看node->fail它的孩子有没有给我失配的字符匹配得上得,匹配不上得话,
    就要往前翻找node->fail->fail。如果配上了的话,我们执行(1),否则就往前找。一直进行这个过程。


    还是这个图,我们用文本串yasherhs在AC自动机上跑一次,我们直接用眼观察得话,就可以知道her,he,she
    这些模式串在yasherhs中出现过,则答案就就是3,现在我们跑依次来看看对不对。
    首先现在匹配y,看root的孩子有没有y,发现没有,则root就会找自己的fail指针,发现是空的,也就是说匹配
    下一次匹配要从root开始开始进入,然后遍历到a,发现root的孩子也没有a,那么root找自己的fail指针,是空,下次
    配的时候还要从root开始,然后遍历到s,我们发现root的孩子有s,则此时字符s得到匹配,然后通过temp指针一直
    翻找s对应的fail,因为那些后缀可能是完整的单词,统计过后是0. 执行完操作(1)直接往下匹配,遍历到字符h,
    发现s的孩子有h,则此时字符sh都得到匹配,同时temp翻找h的fail,统计出来也是0.然后往下匹配,遍历到字符e,发现h的孩子有e,则此时字符she都得到匹配,检测到e是一个完整单词的结尾,统计单词数+1.同时找e->fail,找到了第二层的e,当前这个节点代表的单词是she的后缀he ,而且发现第二层的e是个完整单词的结尾,则统计单词数加+1,然后第二层的e还会去找fail,发现到root了.则翻找过程结束,当前匹配到的单词数是2.然后我们继续遍历文本串,该遍历r,原来是匹配了she,现在第四层e的孩子没有r,则r当前失配,找e的失败指针,找到了第三层的e,代表后缀he,我们发现e后面有r,则r也匹配上了,则现在匹配到的是her,发现r是一个完整的单词,统计+1,然后temp来翻找那
    些后缀是不是完整的单词。发现没有。接下来遍历到文本串的h发现第四层r下面没有h,发现h失配,那么就找h->fail
    发现是根,根下面有是h的孩子,则就从第二层的h开始匹配上了,然后我们遍历到文本串的最后一个字符,s发现第二
    层h后面没有s这个节点,则s失配了,就找h->fail,是根,发现根下面有s这个字符,则s和第一层的s配上了,然而
    这个s不是任何单词的结尾,此时匹配结束。我们统计到5个模式串有3个在文本串中出现过。

    PS:在此讲解中,我一直说节点代表字母,这样是不准确的,确切说一个节点有两层含义,第一层:代表根
    root到当前节点node的字符串,第二层,代表该字符串的最后一个字符。

    AC自动机完整的模板代码如下:
    #include <iostream>  
    #include <stdio.h>  
    #include <stdlib.h>  
    #include <queue>  
      
    using namespace std;  
      
    const int allSon=26;  
    char patten[60];      ///模式串  
    char text[1000010];   ///文本串  
    int ans;  
    struct TrieNode  
    {  
        struct TrieNode *son[allSon];  ///儿子们  
        struct TrieNode *fail;         ///匹配失败时候的指针指向  
        int num;                       ///以该节点所代表字符串为结尾的单词数  
    }*root;  
    ///创建节点  
    TrieNode* createNode()  
    {  
        TrieNode *p;  
        p = (TrieNode*)malloc(sizeof(TrieNode));  
        for(int i = 0; i < allSon; i++) p->son[i] = NULL;  
        p->num = 0;  
        p->fail = NULL;  
        return p;  
    }  
    ///插入模式串,构建字典树  
    void insertPatten()  
    {  
        TrieNode *p;  
        p = root;  
        int index = 0;  
        while(patten[index] != '\0')  
        {  
            int lowercase = patten[index]-'a';  
            if(p->son[lowercase]==NULL)    
            {  
                p->son[lowercase] = createNode();  
            }  
            p = p->son[lowercase];  
            index++;  
        }  
        p->num++;  
    }  
    ///求fail指针。构造AC自动机。  
    void build_AC_automaton()  
    {  
        TrieNode *p;  
        p = root;  
        queue<TrieNode*>qu;  
        qu.push(p);  
        while(!qu.empty())  
        {  
            p = qu.front();  
            qu.pop();  
            for(int i = 0; i < allSon; i++)  
            {  
                if(p->son[i] != NULL) ///第i个孩子存在  
                {  
                    if(p == root)  ///p是根,根节点的孩子的失败指针都指向自己  
                    {  
                        p->son[i]->fail = root;  
                    }  
                    else  
                    {  
                        TrieNode *node = p->fail;   
                        while(node != NULL)  
                        {  
                            if(node->son[i]!=NULL)  
                            {  
                                p->son[i]->fail = node->son[i];  
                                break;  
                            }  
                            node = node->fail;  
                        }  
                        if(node == NULL)  
                            p->son[i]->fail = root;  
                    }  
                    qu.push(p->son[i]);  
                }  
            }  
        }  
    }  
    void find_in_AC_automaton()  
    {  
        TrieNode *p;  
        p = root;  
        int index = 0;  
        while(text[index] != '\0')  
        {  
            int lowercase = text[index]-'a';  
            while(p->son[lowercase]==NULL && p!=root)  
                p = p->fail;   ///失配,转到能配的地方再尝试匹配  
            p = p->son[lowercase];  
            if(p == NULL) p = root;   
            TrieNode *temp = p; ///把那些以当前节点的后缀作为后缀的字符串统计了。  
            while(temp!=NULL && temp->num!=-1)  
            {  
                ans += temp->num;  
                temp->num = -1;  
                temp = temp->fail;  
            }  
            index++;  
        }  
    }  
    ///记得释放接内存,用完及时归还系统,不然会爆的。  
    void freeNode(TrieNode *node)  
    {  
        if(node != NULL)  
        {  
            for(int i = 0; i < allSon; i++)  
                freeNode(node->son[i]);  
        }  
        free(node);  
    }  
    int main()  
    {  
        int t,n;  
        scanf("%d",&t);  
        while(t--)  
        {  
            scanf("%d",&n);  
            root = createNode();  
            for(int i = 0; i < n; i++)  
            {  
                scanf("%s",patten);  
                insertPatten();   ///用模式串构建字典树  
            }  
            scanf("%s",text);  
            build_AC_automaton(); ///构建AC自动机   
            ans = 0;  
            find_in_AC_automaton(); ///多模式匹配  
            printf("%d\n",ans);  
            freeNode(root);        ///释放内存  
        }  
        return 0;  
    }  

    如有错误请及时告知,必将改正,以免误认子弟。
    如要转载请留言告知,转载博客必附原文链接。
    ————————————————
    版权声明:本文为CSDN博主「温姑娘」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/wyxeainn/article/details/77430218

    更多相关内容
  • ac自动机python的实现,可用于python2 python3等主流python发行版,对标准的ac自动机算法进行了完善 优化(主要是改进了结果的准确性)。 注意:为了保证结果的准确性,请安装使用最新版(0.0.9)。 1.如何安装 pip 安装...
  • 本篇文章主要介绍了Java实现AC自动机全文检索示例,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • AC自动机

    2019-03-06 10:05:43
    基于字典树的ac自动机,自己前期的实现,具有源码参考,用于查找可屏蔽应用
  • ac自动机.pptx

    2020-07-14 13:32:51
    要学AC自动机需要自备两个前置技能:KMP和trie树(其实个人感觉不会kmp也行,失配指针的概念并不难) 其中,KMP是用于一对一的字符串匹配,而trie虽然能用于多模式匹配,但是每次匹配失败都需要进行回溯,如果模式串很长的话...
  • 主要介绍了java编程之AC自动机的有关内容,涉及其应用场景,运行原理,运行过程,构造方法及Java中的实现代码,具有一定参考价值,需要的朋友可以了解下。
  • 经典AC自动机.cpp

    2020-08-19 16:16:49
    ac自动机,就是在tire树的基础上,增加一个fail指针,如果当前点匹配失败,则将指针转移到fail指针指向的地方,这样就不用回溯,而可以路匹配下去了
  • ac自动机

    2021-03-24 20:09:09
    AC自动机,是Aho-Corasick automaton的简称,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法。AC自动机是对字典树算法的一种延伸,是字符串中运用非常广泛的一种算法; AC自动机比字典树Trie多维护一个数组...

     AC自动机,是Aho-Corasick automaton的简称,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法。AC自动机是对字典树算法的一种延伸,是字符串中运用非常广泛的一种算法;

    AC自动机比字典树Trie多维护一个数组——fail数组。fail数组的作用是指向当前节点表示的字符串的后缀可以和模式串匹配上的最大长度的节点。是不是和KMP的next数组有点相似?

    KMP的next数组是自己和自己的匹配,而AC自动机的fail数组是自己和模式串(当然也包括自己)的匹配。

    比如:我们有字典集合{acd、aceb、bef、cef},则可以生产如下的AC自动机

    当查找acefcab时,首先会按aceb的支路一直匹配到e,在e的位置发现找不到f,然后跳转到e的失败节点(即cef支路的e节点),查到f。并以此完成了第一次匹配。 

    实现方法

    1.ahocorasick

    安装方法:pip install pyahocorasick

    使用说明

    import ahocorasick
    import time
    
    
    class AhocorasickNer:
        def __init__(self):
            # self.user_dict_path = user_dict_path
            self.actree = ahocorasick.Automaton()
            self.flage=0
        def add_keywords(self,key):
            self.actree.add_word(key,(self.flage,key))
            self.flage+=1
        def make_automaton(self):
            self.actree.make_automaton()
    
        def get_ner_results(self, sentence):
            # print(list(self.actree.keys()))
            # for key in list(self.actree.keys()):
            #     print(key,list(self.actree.values(key)))
            # print(self.actree.get(sentence,''))
            ner_results = []
            # i的形式为(index1,(index2,word))
            # index1: 提取后的结果在sentence中的末尾索引
            # index2: 提取后的结果在self.actree中的索引
            # print(self.actree.get(word))
            # print(self.actree.find_all(word))
            # for i in self.actree.items(word):
            #     print(i)
            # for i in self.actree.iter(sentence):
            for i in self.actree.iter_long(sentence):
                print("iter_long",i)
            for i in self.actree.iter(sentence):
                print("iter",i)
            #     ner_results.append((i[1], i[0] + 1 - len(i[1][1]), i[0] + 1))
            return ner_results
    
    
    if __name__ == "__main__":
        def sub_seq(string):
            sub_string=[]
            sub=""
            for s in string:
                sub+=s
                sub_string.append(sub)
            return sub_string
        ahocorasick_ner = AhocorasickNer()
        # words=['abcdefg', 'abcdef', 'abcde','abcd','abc','ab','a','abdcef','cde']
        words=["外卖公司","百度","百度集团","百度外卖","阿里巴巴","腾讯"]
        # words = [ "百度","百度集团","百度外卖"]
        for index,word in enumerate(words):
            print(sub_seq(word))
            for key in sub_seq(word):
                ahocorasick_ner.add_keywords(key)
                ahocorasick_ner.make_automaton()
    
        while True:
            sentence = input("\nINPUT : ")
            ss = time.time()
            res = ahocorasick_ner.get_ner_results(sentence)
            print("TIME  : {0}ms!".format(round(1000 * (time.time() - ss), 3)))
            print("OUTPUT:{0}".format(res))
    
    
    
    

    2. esmre

    安装方法:pip install esmre

    使用说明:http://xiaorui.cc/archives/1649

    import esmre
    index=esmre.Index()
    words = [ "百度","百度集团","百度外卖","阿里巴巴","腾讯"]
    for i,word in enumerate(words):
        index.enter(word,word)
    result=index.query("百度大战阿里巴巴")
    print(result)

    3.flashtext

    安装方法:pip install flashtext

    使用说明

    from flashtext import KeywordProcessor
    keyword_processor=KeywordProcessor()
    def sub_seq(string):
        sub_string = []
        sub = ""
        for s in string:
            sub += s
            sub_string.append(sub)
        return sub_string
    words = [ "百度","百度集团","百度外卖"]
    for word in words:
        print(sub_seq(word))
        for sub_word in sub_seq(word):
            keyword_processor.add_keyword(sub_word,word)
    print(keyword_processor.get_all_keywords())
    
    

    4.python代码实现

    使用说明:http://ddrv.cn/a/653542

    https://blog.csdn.net/Big_Head_/article/details/80144495?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-6.baidujs&dist_request_id=1328690.11672.16165895136911425&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-6.baidujs

     

     

    展开全文
  • 原始AC自动机由于匹配性能低,无法满足当前大数据环境下大规模特征串实时匹配的应用需求。针对这一问题,提出一种基于多线程的多模式串匹配加速算法,称之为PARA-AC(Parallel Aho-Corasick automaton)。该算法将待...
  • AC自动机实现多模式串匹配,支持中文系统,同时可以支持多个模式串,测试使用Linux和Windows系统,使用20条模式串,中英文混合,测试通过
  • ac自动机java版

    2014-07-24 09:13:29
    从别的共享资源下载的java版ac自动机,已验证使用非常好。
  • AC自动机算法(Aho-Corasick 多模式匹配算法)C#实现
  • hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
  • AC自动机算法

    2021-08-12 22:12:28
    ac自动机,双数组

    前言

    有时我们在想《字典树》是不是也能引入快速失败《字符串模式匹配算法KMP》的方式,从而加快词语匹配。它就是AC自动机算法。

    AC自动机算法

    首先我们使用she , he , hers, his 等单词,使用AC自动机算法构建一棵字典树。
    在这里插入图片描述
    与普通的字典树的区别是多了一些虚线指针,为“Fail指针”。

    验证fail指针

    我们通过单词“ushers” 对其验证。

    1. 输入‘u’, 0节点下面没找到,失败,根据fail指针指向0结点, 因是0结点终止搜索
    2. 输入’s’, 前进至3结点
    3. 输入‘h’,前进至4结点
    4. 输入‘e’,前进至5结点, 5节点是终结点收获{”he“,”she“}
    5. 输入‘r’,5节点下面没找到,失败,根据fail指针指向2结点,搜索2结点下面‘r’前进至8结点
    6. 输入‘s’,前进至9结点, 9节点是终结点收获{”hers“}
    7. 因此得到单词 {”he“,”she“, ”hers“}

    经过上面查询规则发现,所谓的失败指针,就是匹配不上时,查找最长公共后缀转过去

    构建fail指针

    再以上述词典树为例

    1. 创建一队列Q,把结点0(root)进行

    2. 结点0出队,发现是root,把结点0的孩子的失败指针都指向root,结点1,3的失败指针都结点0。再把结点1,3入队列Q

    3. 结点1出队,根据路径e,把结点2入队列Q. 然后假装“路径e”失败,查询当前fail指针下结点0的“路径e”. 没找到且发现是root,结点2的失败指针都结点0

    4. 结点3出队,根据路径h,把结点4入队列Q. 然后假装“路径h”失败,查询当前fail指针下结点0的“路径h”. 找到结点1,结点4的失败指针都结点1

    5. 结点2出队,根据路径r,把结点8入队列Q. 然后假装“路径r”失败,查询当前fail指针下结点0的“路径r”. 没找到且发现是root,结点8的失败指针都结点0

    6. 结点4出队,根据路径e,把结点5入队列Q. 然后假装“路径e”失败,查询当前fail指针下结点1的“路径e”. 找到结点2,结点5的失败指针都结点2, 发现2结点是终节节点,并把他的词加入自己结点中

    7. 以至类推,重复上述步骤,就构造出示图中的fail指针

    class StreamChecker {
        ACNode root;
        ACNode p;
    
        public StreamChecker(String[] words) {
            // 构造字典树
            this.root = new ACNode(' ');
            this.p = root;
            for (String word : words) {
                ACNode temp = root;
                for (char c : word.toCharArray()) {
                    int idx = c - 'a';
                    if (temp.children[idx] == null) temp.children[idx] = new ACNode(c);
                    temp = temp.children[idx];
                }
                temp.isEnding = true;
                temp.length = word.length();
            }
            // 维护失败指针
            buildFailPointer();
        }
    
        private void buildFailPointer() {
            Queue<ACNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                ACNode p = queue.poll();
                for (int i = 0; i < 26; i++) {
                    ACNode pc = p.children[i];
                    if (pc == null) continue;
    
                    if (p == root) pc.fail = root;
                    else {
                        ACNode q = p.fail;
                        while (q != null && q.children[i] == null) {
                            q = q.fail;
                        }
    
                        if (q == null) pc.fail = root;
                        else pc.fail = q.children[i];
                    }
                    queue.add(pc);
                }
            }
        }
        
        public boolean query(char letter) {
            int idx = letter - 'a';
            while (this.p != root && p.children[idx] == null) {
                p = p.fail;
            }
            p = p.children[idx];
            if (p == null) p = root;
    
            ACNode temp = p;
            while (temp != root) {
                if (temp.isEnding) return true;
                temp = temp.fail;
            }
    
            return false;
        }
    }
    
    class ACNode {
        char c;
        boolean isEnding;
        int length = -1;
    
        ACNode[] children = new ACNode[26];
        ACNode fail;
    
        ACNode(char c) {
            this.c = c;
        }
    }
    

    双数组AC自动机算法

    当然在《双数组字典树DoubleArrayTrie》也研究了"双数组ac自动机".

    1. 引出fail数组表示失败指针
    2. 引入output 表示ac的字符集

    对she , he , hers, his的数组表为

    字符值: [e-1,h-2,i-3,r-4,s-5]

    字符--ehihsrses
    pos012345678910
    base10-313835-3-8-5
    check-1-1303602457
    output--he-----hisshe
    he
    hers
    fail-1-1000300626
    public class AcDoubleArrayTrie {
     
        String[] keys;// 字符集
        int[] base;// 转移数组
        int[] check;// 较验数组
        int fail[]; //fail表
        String[][] output;//输出表
     
        private static class Node {
     
            private int code;// 字符编码
     
            private int s;// 父字符位置
    
            @Override
            public boolean equals(Object o) {
                if (this == o)
                    return true;
                if (o == null || getClass() != o.getClass())
                    return false;
    
                Node node = (Node) o;
    
                if (code != node.code)
                    return false;
                return s == node.s;
            }
    
            @Override
            public int hashCode() {
                int result = code;
                result = 31 * result + s;
                return result;
            }
        }
     
        public void build(List<String> list) {
     
            // 给所有字符定编码
            this.keys = list.stream().map(word -> word.split("")).flatMap(Arrays::stream).distinct().sorted()
                    .collect(Collectors.toList()).toArray(new String[0]);
     
            base = new int[3 * keys.length];
            check = new int[3 * keys.length];
            fail = new int[3* keys.length];
            output = new String[3 * keys.length][];
    
            String[] dir = list.toArray(new String[0]);
     
            // 设置root
            base[0] = 1;
            for (int i = 0; i < check.length ; i++) {
                check[i] = -1;
            }
            for (int i = 0; i < fail.length ; i++) {
                fail[i] = -1;
            }
     
            // 词的深度
            int depth = 1;
     
            while (!list.isEmpty()) {
     
                // 根据相同前缀分组
                Map<Integer, List<Node>> map = new HashMap<>();
                for (int i = 0; i < list.size();) {
                    String word = list.get(i);
    
                    String pre = word.substring(0, depth - 1);
                    String k = word.substring(depth - 1, depth);
    
                    Node n = new Node();
                    n.code = findIndex(k);
                    n.s = depth == 1 ? 0 : indexOf(pre);
                    if (depth == word.length()) {
                        list.remove(i);
                    } else {
                        i++;
                    }
    
                    List<Node> siblings = map.getOrDefault(n.s, new ArrayList<>());
    
                    if(siblings.contains(n)){
                        continue;
                    }
                    siblings.add(n);
                    map.put(n.s, siblings);
                }
     
                map.forEach((s, siblings) -> {
                    int offset = 0;
    
                    for (int i = 0; i < siblings.size(); i++) {
                        Node node = siblings.get(i);
                        int c = node.code;
                        int t = base[s] + offset + c;
    
                        // 发现在节点已有值则偏移+1
                        if (check[t] != -1) {
                            offset++;
                            i = -1;
                        }
                    }
    
                    base[s] = base[s] + offset;
    
                    for (Node node : siblings) {
                        int c = node.code;
                        int t = base[s] + c;
                        // 给上父结点
                        check[t] = s;
                        // 给拿上一个节点偏移量
                        base[t] = base[s];
                    }
                });
                depth++;
            }
     
            // 发现字节点,置为负数
            for (String aDir : dir) {
                int s = indexOf(aDir);
                base[s] = -1 * base[s];
                output[s] = new String[]{aDir};
            }
            constructFail();
        }
    
        private void constructFail() {
    
            Queue<Integer> queue = new LinkedBlockingDeque<>();
    
            // 第一步,将深度为1的节点的failure设为根节点
            for (int i = 0; i < check.length; i++) {
                if (check[i] != 0) {
                    continue;
                }
                fail[i] = 0;
                queue.add(i);
            }
    
            // 第二步,为深度 > 1 的节点建立failure表,这是一个bfs
            while (!queue.isEmpty()) {
                int currentIndex = queue.remove();
                int current = base[currentIndex];
    
                for (int target = 0; target < check.length; target++) {
                    if (check[target] != currentIndex) {
                        continue;
                    }
                    queue.add(target);
                    int code = target - (current < 0 ? -1 * current : current);
    
                    int currentFailIndex = fail[currentIndex];
    
                    while (true) {
                        if (check[base[currentFailIndex] + code] == currentFailIndex) {
                            fail[target] = base[currentFailIndex] + code;
                            constructOutput(target, base[currentFailIndex] + code);
                            break;
                        } else if (currentFailIndex == 0) {
                            fail[target] = 0;
                            break;
                        }
                        currentFailIndex = fail[currentFailIndex];
                    }
    
                }
            }
        }
    
        private void constructOutput(int target, int failTarget) {
            if (output[target] == null || output[failTarget] == null) {
                return;
            }
            List<String> result = Stream.of(output[target]).collect(Collectors.toList());
            result.addAll(Stream.of(output[failTarget]).collect(Collectors.toList()));
            output[target] = result.toArray(new String[0]);
        }
     
        // 找询字符编码
        private int findIndex(String key) {
            for (int i = 0; i < keys.length; i++) {
                if (keys[i].equals(key))
                    return i + 1;
            }
            throw new RuntimeException("找不到[" + key + "]");
        }
     
        // 定位前缀结点position
        private int indexOf(String pre) {
            int s = 0;
            String[] ss = pre.split("");
            for (String word : ss) {
                int c = findIndex(word);
                s = (base[s] < 0 ? -1 * base[s] : base[s]) + c;
            }
            return s;
        }
    
        public List<String> parseText(String text){
            List<String> result = new ArrayList<>();
            int s = 0;
            String[] ss = text.split("");
    
            for (int i = 0; i < ss.length; i++) {
                String word = ss[i];
                int c;
                try{
                    c= findIndex(word);
                }catch (Exception e){
                    s = 0;
                    continue;
                }
    
                int t = (base[s] < 0 ? -1 * base[s] : base[s]) + c;
    
                if (check[t] == s) {
                    if(output[t] !=null){
                        result.addAll(Stream.of(output[t]).collect(Collectors.toList()));
                    }
                    s = t;
                } else {
                    if(fail[s] == -1){
                        continue;
                    }
                    s = fail[s];
                    i--;
                }
    
            }
            return result;
        }
    
        public static void main(String[] args) {
            AcDoubleArrayTrie adt = new AcDoubleArrayTrie();
            List<String> list = Stream.of(new String[]{"hers", "his", "she", "he"}).collect(Collectors.toList());
     
            // 构建DoubleArrayTrie
            adt.build(list);
    
            List<String> result = adt.parseText("ushers");
    
            result.forEach(System.out::println);
        }
    }
    

    主要参考

    AC自动机 - 关于Fail指针

    展开全文
  • 供信息学奥林匹克竞赛选手使用 AC自动机模板
  • AC自动机-详解AC自动机以及模板AC自动机算法简介AC自动机算法大致流程AC自动机详细图解AC自动机模板题与模板题目内容代码详解完整代码 AC自动机算法简介 首先简要介绍一下AC自动机,英文名:Aho-Corasick automation...

    AC自动机算法简介

    首先简要介绍一下AC自动机,英文名:Aho-Corasick automation,该算法在1975年产生于贝尔实验室,是著名的多模板匹配算法之一。一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过
    要搞懂AC自动机,先要有字典树Trie和KMP模式匹配算法的基础知识。其中,KMP是用于一对一的字符串匹配,而trie虽然能用于多模式匹配,但是每次匹配失败都需要进行回溯,如果模式串很长的话会很浪费时间,所以AC自动机应运而生,如同Manacher一样,AC自动机利用某些操作阻止了模式串匹配阶段的回溯,将时间复杂度优化到了O ( n ) - n 为文本长度

    AC自动机算法大致流程

    1.构造一棵Trie,作为AC自动机的搜索数据结构。

    2.构造fail指针,使当前字符失配时跳转到具有最长公共前后缀的字符继续匹配。如同 KMP算法一样, AC自动机在匹配时如果当前字符匹配失败,那么利用fail指针进行跳转。由此可知如果跳转,跳转后的串的前缀,必为跳转前的模式串的后缀并且跳转的新位置的深度(匹配字符个数)一定小于跳之前的节点。所以我们可以利用 bfs在 Trie上面进行 fail指针的求解。

    3.扫描主串进行匹配。

    AC自动机详细图解

    对于AC自动机算法,要是只通过语言来描述,真的十分不容易理解,小编在这里就用图来详细解释一下这个算法啦。

    1、首先给定模式串 “ash” , “shex” , “bcd” , “sha” ,然后我们根据模式串建立如下 Trie 树:
    Trie
    2、然后我们再了解下一步:,AC自动机就是在Trie树的基础上,增加一个fail指针,如果当前点匹配失败,则将指针转移到fail指针指向的地方,这样就不用回溯,而可以继续匹配下去了.(当前模式串后缀和fail指针指向的模式串部分前缀相同,如 abce bcd,我们找到 c 发现下一个要找的不是 e,就跳到 bcd 中的 c 处,看看此处的下一个字符 d 是不是应该找的那一个)。一般,fail 指针的构建都是用 bfs 实现的。
    (1)首先每个模式串的首字母肯定是指向根节点的:
    在这里插入图片描述
    (2)现在第一层 bfs 遍历完了,开始第二层(根节点为第0层)第二层节点 s 是第一层节点 a 的子节点,但是我们还是要从 a - z 遍历,如果不存在这个子节点我们就让他指向根节点(如下图中的红色 a ):
    在这里插入图片描述
    (3)当我们遍历到 s 的时候,由于存在 s 这个节点,我们就让它的fail指针指向他父亲节点 a 的 fail 指针指向的那个节点(根)的具有相同字母的子节点(第一层的 s),也就是这样:
    在这里插入图片描述
    (4)按照相同规律构建第二层后,到了第三层的 h 点,还是按照上面的规则,我们找到 h 的父亲节点 s 的 fail 指针指向的那个位置(第一层的 s),然后指向它所指向的相同字母 根 -> s -> h 的这个链的 h 节点,如下图:
    在这里插入图片描述
    (5)按照如上的规律,完全构造好后的树如下所示:
    在这里插入图片描述
    3、然后匹配就很简单了,这里以 ashw 为例:
    我们先用 ash 匹配,到 h 了发现,ash 是一个完整的模式串,则ans++,然后找下一个 w,可是 ash 后面没字母了呀,我们就跳到 h 的 fail 指针指向的那个 h 继续找,还是没有?再跳,结果当前的 h 指向的是根节点,又从根节点找,然而还是没有找到 w,匹配结束。流程图如下:
    在这里插入图片描述

    AC自动机模板题与模板

    在这里选取洛谷上面的一个AC自动机的模板题,题目链接

    题目内容

    给定 n 个模式串 si 和一个文本串 t,求有多少个不同的模式串在文本串里出现过。
    两个模式串不同当且仅当他们编号不同。

    输入格式
    第一行是一个整数,表示模式串的个数 n。
    第 2 到第 (n + 1) 行,每行一个字符串,第 (i + 1) 行的字符串表示编号为 i 的模式串 si。
    最后一行是一个字符串,表示文本串 t。

    输出格式
    输出一行一个整数表示答案。

    输入输出样例
    输入 #1
    3
    a
    aa
    aa
    aaa
    输出 #1
    3
    输入 #2
    4
    a
    ab
    ac
    abc
    abcd
    输出 #2
    3
    输入 #3
    2
    a
    aa
    aa
    输出 #3
    2

    代码详解

    1、输入输出(主函数)
    小编将AC自动机的函数都封装在类型为Aho_Corasick_Automaton,名为AC打的结构体中了,因此主函数只需要对输入、输出以及调用结构体里面的功能函数即可。代码如下:

    int main()
    {
    	freopen("in.in", "r", stdin);
    	freopen("out.out", "w", stdout);
    	int i, j;
    	scanf("%d", &n);
    	//AC.initial();
    	for (i = 1; i <= n; i++)
    	{
    		scanf("%s", p);
    		AC.insert(p);        //插入模板单词
    	}
    	AC.build();              //建立fail指针
    	scanf("%s", p);
    	int ans = AC.solve(p);   //开始匹配
    	cout << ans;             //输出结果
    	return 0;
    }
    

    2、插入模板单词
    这一部分按照如上图解中的搜索树的结构一个字母一个字母的依次建立节点即可,代码如下:

    void insert(char *s)   //添加模板单词
    	{
    		int i;
    		int len = strlen(s);
    		int now = 0;       //当前节点
    		for (i = 0; i < len; i++)
    		{
    			int v = s[i] - 'a';
    			if (trie[now][v] == 0) 
    			{
    				cnt++;
    				trie[now][v] = cnt;
    			}
    			now = trie[now][v];
    		}
    		mark[now]++;
    	}
    

    3、建立fail指针
    这一部分按照如上图解中的情况,用bfs的思想进行fail数组的建立即可,代码如下:

    void build()
    	{
    		int i;
    		for (i = 0; i < 26; i++)
    		{
    			if (trie[0][i] != 0)
    			{
    				fail[trie[0][i]] = 0;
    				q.push(trie[0][i]);
    			}
    		}
    		while (!q.empty())
    		{
    			int u = q.front();
    			q.pop();
    			for (i = 0; i < 26; i++)
    			{
    				if (trie[u][i] != 0)
    				{
    					fail[trie[u][i]] = trie[fail[u]][i];
    					q.push(trie[u][i]);
    				}
    				else
    				{
    					trie[u][i] = trie[fail[u]][i];
    				}
    			}
    		}
    	}
    

    4、模板匹配
    代码如下:

    int solve(char *s)
    	{
    		int i, j;
    		int len = strlen(s);
    		int now = 0;
    		int ans = 0;
    		for (i = 0; i < len; i++)
    		{
    			now = trie[now][s[i] - 'a'];
    			for (j = now; j && ~mark[j]; j = fail[j])
    			{
    				ans = ans + mark[j];
    				mark[j] = -1;
    			}
    		}
    		return ans;
    	}
    

    完整代码

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    int n;
    char p[1000005];
    struct Aho_Corasick_Automaton
    {
    	int trie[500010][26];  //AC自动机需要的搜索树结构
    	int fail[500010];      //fail指针
    	int mark[500010];      //词典结束标志
    	int cnt;               //节点序号
    	queue<int>q;		   //建立fail指针时需要的队列
    	void initial()         //初始化
    	{
    		cnt = 0;
    		memset(trie, 0, sizeof(trie));
    		memset(fail, 0, sizeof(fail));
    		memset(mark, 0, sizeof(mark));
    		while (!q.empty()) q.pop();
    	}
    	void insert(char *s)   //添加模板单词
    	{
    		int i;
    		int len = strlen(s);
    		int now = 0;       //当前节点
    		for (i = 0; i < len; i++)
    		{
    			int v = s[i] - 'a';
    			if (trie[now][v] == 0) 
    			{
    				cnt++;
    				trie[now][v] = cnt;
    			}
    			now = trie[now][v];
    		}
    		mark[now]++;
    	}
    	void build()
    	{
    		int i;
    		for (i = 0; i < 26; i++)
    		{
    			if (trie[0][i] != 0)
    			{
    				fail[trie[0][i]] = 0;
    				q.push(trie[0][i]);
    			}
    		}
    		while (!q.empty())
    		{
    			int u = q.front();
    			q.pop();
    			for (i = 0; i < 26; i++)
    			{
    				if (trie[u][i] != 0)
    				{
    					fail[trie[u][i]] = trie[fail[u]][i];
    					q.push(trie[u][i]);
    				}
    				else
    				{
    					trie[u][i] = trie[fail[u]][i];
    				}
    			}
    		}
    	}
    	int solve(char *s)
    	{
    		int i, j;
    		int len = strlen(s);
    		int now = 0;
    		int ans = 0;
    		for (i = 0; i < len; i++)
    		{
    			now = trie[now][s[i] - 'a'];
    			for (j = now; j && ~mark[j]; j = fail[j])
    			{
    				ans = ans + mark[j];
    				mark[j] = -1;
    			}
    		}
    		return ans;
    	}
    }AC;
    int main()
    {
    	int i, j;
    	scanf("%d", &n);
    	//AC.initial();
    	for (i = 1; i <= n; i++)
    	{
    		scanf("%s", p);
    		AC.insert(p);
    	}
    	AC.build();
    	scanf("%s", p);
    	int ans = AC.solve(p);
    	cout << ans;
    	return 0;
    }
    
    
    展开全文
  • 解耦了的AC自动机模板,可工程使用。内包含头文件与源文件与使用方法,参照使用方法即可直接调用。 纯C代码,不依赖任何外部库。
  • AC自动机最全数据,大家可以看一下,欢迎下载,谢谢支持!!!!!!!!!!!!!!!!!!!!!!!!
  • AC自动机是KMP算法和Trie(字典树)的巧妙结合这篇文章主要讲针对几个例题给出解答模版(主要是知识点自己讲不清楚)。 至于针对的知识点,给上几个我认为说的比较好的传送门,读者可以自行选择阅读。(我就是看这...
  • 经典的多模式串匹配算法:AC 自动机。如何用多模式串匹配实现敏感词过滤功能
  • C++ AC自动机算法

    2021-08-12 18:05:53
    AC自动机简介 如何构造 AC自动机 算法实现 1、建树 2、预处理失配指针 nex: 3、匹配 AC自动机例题推荐 AC自动机简介: 正所谓 AC自动机,就是能自动 AC 的算法。 AC自动机全称:Aho-Corasick automaton...
  • 正题 ybtoj AC自动机-4 题目大意 有一个字符串和若干要删除的串(不存在包含关系),每次从前往后搜,搜到第一个要删除的串然后删掉,再从0开始搜 问你最后得到的字符串 解题思路 先把所有删除串丢进AC自动机中,每...
  • AC自动机(详解)

    千次阅读 2021-08-15 19:31:22
    AC自动机是KMP和字典树的结合体, 如果说KMP用于单模式匹配,那么AC自动机是用于多模式匹配的。 举个例子,KMP适用于在一篇文章中找一句话, AC自动机适合在一篇文章中寻找多句话(并不是简单的多用几次KMP)。 KMP...
  • AC 自动机和字典树

    2022-01-26 20:11:19
    AC 自动机三,AC 自动机1,二次认识 KMP2,二次认识失配数组3,二次认识匹配过程4,多模匹配的典例step 1,建立失配边DAG,并对主串匹配step 2 深搜,进行食物链计数累计获得匹配数目的奥秘 ...故AC自动机是在 K

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 20,803
精华内容 8,321
关键字:

ac自动机