大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > 算法技巧 > 经典算法之AC自动机

经典算法之AC自动机

关键词:经典算法AC自动机  阅读(935) 赞(40)

[摘要]本文谈一谈AC自动机算法,开讲!

上一篇我们说了单模式匹配算法KMP,现在我们有需求了,我要检查一篇文章中是否有某些敏感词,这其实就是多模式匹配的问题。

当然你也可以用KMP算法求出,那么它的时间复杂度为O(c*(m+n)),c:为模式串的个数。m:为模式串的长度,n:为正文的长度,那

么这个复杂度就不再是线性了,我们学算法就是希望能把要解决的问题优化到极致,这不,AC自动机就派上用场了。

   其实AC自动机就是Trie树的一个活用,活用点就是灌输了kmp的思想,从而再次把时间复杂度优化到线性的O(N),刚好我前面的文

章已经说过了Trie树和KMP,这里还是默认大家都懂。

一:构建AC自动机

  同样我也用网上的经典例子,现有say she shr he her 这样5个模式串,主串为yasherhs,我要做的就是哪些模式串在主串中出现过?

1: 构建trie树

    如果看过我前面的文章,构建trie树还是很容易的。

2:失败指针

    构建失败指针是AC自动机的核心所在,玩转了它也就玩转了AC自动机,失败指针非常类似于KMP中的next数组,也就是说,

 当我的主串在trie树中进行匹配的时候,如果当前节点不能再继续进行匹配,那么我们就会走到当前节点的failNode节点继续进行

匹配,构建failnode节点也是很流程化的。

①:root节点的子节点的failnode都是指向root。

②:当走到在“she”中的”h“节点时,我们给它的failnode设置什么呢?此时就要走该节点(h)的父节点(s)的失败指针,一直回溯直

     到找到某个节点的孩子节点也是当初节点同样的字符(h),没有找到的话,其失败指针就指向root。

     比如:h节点的父节点为s,s的failnode节点为root,走到root后继续寻找子节点为h的节点,恰好我们找到了,(假如还是没

             有找到,则继续走该节点的failnode,嘿嘿,是不是很像一种回溯查找),此时就将 ”she"中的“h”节点的fainode"指向

            "her"中的“h”节点,好,原理其实就是这样。(看看你的想法是不是跟图一样)

针对图中红线的”h,e“这两个节点,我们想起了什么呢?对”her“中的”e“来说,e到root距离的n个字符恰好与”she“中的e向上的n

个字符相等,我也非常类似于kmp中next函数,当字符失配时,next数组中记录着下一次匹配时模式串的起始位置。

#region Trie树节点
        /// <summary>
        /// Trie树节点
        /// </summary>
        public class TrieNode
        {
            /// <summary>
            /// 26个字符,也就是26叉树
            /// </summary>
            public TrieNode[] childNodes;

            /// <summary>
            /// 词频统计
            /// </summary>
            public int freq;

            /// <summary>
            /// 记录该节点的字符
            /// </summary>
            public char nodeChar;

            /// <summary>
            /// 失败指针
            /// </summary>
            public TrieNode faliNode;

            /// <summary>
            /// 插入记录时的编号id
            /// </summary>
            public HashSet<int> hashSet = new HashSet<int>();

            /// <summary>
            /// 初始化
            /// </summary>
            public TrieNode()
            {
                childNodes = new TrieNode[26];
                freq = 0;
            }
        }
        #endregion

刚才我也说到了parent和current两个节点,在给trie中的节点赋failnode的时候,如果采用深度优先的话还是很麻烦的,因为我要实时

记录当前节点的父节点,相信写过树的朋友都清楚,除了深搜,我们还有广搜。

/// <summary>
        /// 构建失败指针(这里我们采用BFS的做法)
        /// </summary>
        /// <param name="root"></param>
        public void BuildFailNodeBFS(ref TrieNode root)
        {
            //根节点入队
            queue.Enqueue(root);

            while (queue.Count != 0)
            {
                //出队
                var temp = queue.Dequeue();

                //失败节点
                TrieNode failNode = null;

                //26叉树
                for (int i = 0; i < 26; i++)
                {
                    //代码技巧:用BFS方式,从当前节点找其孩子节点,此时孩子节点
                    //         的父亲正是当前节点,(避免了parent节点的存在)
                    if (temp.childNodes[i] == null)
                        continue;

                    //如果当前是根节点,则根节点的失败指针指向root
                    if (temp == root)
                    {
                        temp.childNodes[i].faliNode = root;
                    }
                    else
                    {
                        //获取出队节点的失败指针
                        failNode = temp.faliNode;

                        //沿着它父节点的失败指针走,一直要找到一个节点,直到它的儿子也包含该节点。
                        while (failNode != null)
                        {
                            //如果不为空,则在父亲失败节点中往子节点中深入。
                            if (failNode.childNodes[i] != null)
                            {
                                temp.childNodes[i].faliNode = failNode.childNodes[i];
                                break;
                            }
                            //如果无法深入子节点,则退回到父亲失败节点并向root节点往根部延伸,直到null
                            //(一个回溯再深入的过程,非常有意思)
                            failNode = failNode.faliNode;
                        }

                        //等于null的话,指向root节点
                        if (failNode == null)
                            temp.childNodes[i].faliNode = root;
                    }
                    queue.Enqueue(temp.childNodes[i]);
                }
            }
        }

3:模式匹配

   所有字符在匹配完后都必须要走failnode节点来结束自己的旅途,相当于一个回旋,这样做的目的防止包含节点被忽略掉。

    比如:我匹配到了"she",必然会匹配到该字符串的后缀”he",要想在程序中匹配到,则必须节点要走失败指针来结束自己的旅途。

从上图中我们可以清楚的看到“she”的匹配到字符"e"后,从failnode指针撤退,在撤退途中将其后缀字符“e”收入囊肿,这也就是

为什么像kmp中的next函数。

/// <summary>
        /// 根据指定的主串,检索是否存在模式串
        /// </summary>
        /// <param name="root"></param>
        /// <param name="s"></param>
        /// <returns></returns>
        public void SearchAC(ref TrieNode root, string s, ref HashSet<int> hashSet)
        {
            int freq = 0;

            TrieNode head = root;

            foreach (var c in s)
            {
                //计算位置
                int index = c - 'a';

                //如果当前匹配的字符在trie树中无子节点并且不是root,则要走失败指针
                //回溯的去找它的当前节点的子节点
                while ((head.childNodes[index] == null) && (head != root))
                    head = head.faliNode;

                //获取该叉树
                head = head.childNodes[index];

                //如果为空,直接给root,表示该字符已经走完毕了
                if (head == null)
                    head = root;

                var temp = head;

                //在trie树中匹配到了字符,标记当前节点为已访问,并继续寻找该节点的失败节点。
                //直到root结束,相当于走了一个回旋。(注意:最后我们会出现一个freq=-1的失败指针链)
                while (temp != root && temp.freq != -1)
                {
                    freq += temp.freq;

                    //将找到的id追加到集合中
                    foreach (var item in temp.hashSet)
                        hashSet.Add(item);

                    temp.freq = -1;

                    temp = temp.faliNode;
                }
            }
        }
好了,到现在为止,我想大家也比较清楚了,最后上一个总的运行代码:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.IO;

namespace ConsoleApplication2
{
    public class Program
    {
        public static void Main()
        {
            Trie trie = new Trie();

            trie.AddTrieNode("say", 1);
            trie.AddTrieNode("she", 2);
            trie.AddTrieNode("shr", 3);
            trie.AddTrieNode("her", 4);
            trie.AddTrieNode("he", 5);

            trie.BuildFailNodeBFS();

            string s = "yasherhs";

            var hashSet = trie.SearchAC(s);

            Console.WriteLine("在主串{0}中存在模式串的编号为:{1}", s, string.Join(",", hashSet));

            Console.Read();
        }
    }

    public class Trie
    {
        public TrieNode trieNode = new TrieNode();

        /// <summary>
        /// 用光搜的方法来构建失败指针
        /// </summary>
        public Queue<TrieNode> queue = new Queue<TrieNode>();

        #region Trie树节点
        /// <summary>
        /// Trie树节点
        /// </summary>
        public class TrieNode
        {
            /// <summary>
            /// 26个字符,也就是26叉树
            /// </summary>
            public TrieNode[] childNodes;

            /// <summary>
            /// 词频统计
            /// </summary>
            public int freq;

            /// <summary>
            /// 记录该节点的字符
            /// </summary>
            public char nodeChar;

            /// <summary>
            /// 失败指针
            /// </summary>
            public TrieNode faliNode;

            /// <summary>
            /// 插入记录时的编号id
            /// </summary>
            public HashSet<int> hashSet = new HashSet<int>();

            /// <summary>
            /// 初始化
            /// </summary>
            public TrieNode()
            {
                childNodes = new TrieNode[26];
                freq = 0;
            }
        }
        #endregion

        #region 插入操作
        /// <summary>
        /// 插入操作
        /// </summary>
        /// <param name="word"></param>
        /// <param name="id"></param>
        public void AddTrieNode(string word, int id)
        {
            AddTrieNode(ref trieNode, word, id);
        }

        /// <summary>
        /// 插入操作
        /// </summary>
        /// <param name="root"></param>
        /// <param name="s"></param>
        public void AddTrieNode(ref TrieNode root, string word, int id)
        {
            if (word.Length == 0)
                return;

            //求字符地址,方便将该字符放入到26叉树中的哪一叉中
            int k = word[0] - 'a';

            //如果该叉树为空,则初始化
            if (root.childNodes[k] == null)
            {
                root.childNodes[k] = new TrieNode();

                //记录下字符
                root.childNodes[k].nodeChar = word[0];
            }

            var nextWord = word.Substring(1);

            //说明是最后一个字符,统计该词出现的次数
            if (nextWord.Length == 0)
            {
                root.childNodes[k].freq++;
                root.childNodes[k].hashSet.Add(id);
            }

            AddTrieNode(ref root.childNodes[k], nextWord, id);
        }
        #endregion

        #region 构建失败指针
        /// <summary>
        /// 构建失败指针(这里我们采用BFS的做法)
        /// </summary>
        public void BuildFailNodeBFS()
        {
            BuildFailNodeBFS(ref trieNode);
        }

        /// <summary>
        /// 构建失败指针(这里我们采用BFS的做法)
        /// </summary>
        /// <param name="root"></param>
        public void BuildFailNodeBFS(ref TrieNode root)
        {
            //根节点入队
            queue.Enqueue(root);

            while (queue.Count != 0)
            {
                //出队
                var temp = queue.Dequeue();

                //失败节点
                TrieNode failNode = null;

                //26叉树
                for (int i = 0; i < 26; i++)
                {
                    //代码技巧:用BFS方式,从当前节点找其孩子节点,此时孩子节点
                    //         的父亲正是当前节点,(避免了parent节点的存在)
                    if (temp.childNodes[i] == null)
                        continue;

                    //如果当前是根节点,则根节点的失败指针指向root
                    if (temp == root)
                    {
                        temp.childNodes[i].faliNode = root;
                    }
                    else
                    {
                        //获取出队节点的失败指针
                        failNode = temp.faliNode;

                        //沿着它父节点的失败指针走,一直要找到一个节点,直到它的儿子也包含该节点。
                        while (failNode != null)
                        {
                            //如果不为空,则在父亲失败节点中往子节点中深入。
                            if (failNode.childNodes[i] != null)
                            {
                                temp.childNodes[i].faliNode = failNode.childNodes[i];
                                break;
                            }
                            //如果无法深入子节点,则退回到父亲失败节点并向root节点往根部延伸,直到null
                            //(一个回溯再深入的过程,非常有意思)
                            failNode = failNode.faliNode;
                        }

                        //等于null的话,指向root节点
                        if (failNode == null)
                            temp.childNodes[i].faliNode = root;
                    }
                    queue.Enqueue(temp.childNodes[i]);
                }
            }
        }
        #endregion

        #region 检索操作
        /// <summary>
        /// 根据指定的主串,检索是否存在模式串
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public HashSet<int> SearchAC(string s)
        {
            HashSet<int> hash = new HashSet<int>();

            SearchAC(ref trieNode, s, ref hash);

            return hash;
        }

        /// <summary>
        /// 根据指定的主串,检索是否存在模式串
        /// </summary>
        /// <param name="root"></param>
        /// <param name="s"></param>
        /// <returns></returns>
        public void SearchAC(ref TrieNode root, string s, ref HashSet<int> hashSet)
        {
            int freq = 0;

            TrieNode head = root;

            foreach (var c in s)
            {
                //计算位置
                int index = c - 'a';

                //如果当前匹配的字符在trie树中无子节点并且不是root,则要走失败指针
                //回溯的去找它的当前节点的子节点
                while ((head.childNodes[index] == null) && (head != root))
                    head = head.faliNode;

                //获取该叉树
                head = head.childNodes[index];

                //如果为空,直接给root,表示该字符已经走完毕了
                if (head == null)
                    head = root;

                var temp = head;

                //在trie树中匹配到了字符,标记当前节点为已访问,并继续寻找该节点的失败节点。
                //直到root结束,相当于走了一个回旋。(注意:最后我们会出现一个freq=-1的失败指针链)
                while (temp != root && temp.freq != -1)
                {
                    freq += temp.freq;

                    //将找到的id追加到集合中
                    foreach (var item in temp.hashSet)
                        hashSet.Add(item);

                    temp.freq = -1;

                    temp = temp.faliNode;
                }
            }
        }
        #endregion
    }
}



相关评论