Aho-Corasick算法实现C#（简单关键字过滤）代码片段

CodeSnippet.Cn
代码片段

Algorithm 小笨蛋发布于：2023年06月29日更新于：2023年06月29日 69

> 关于AC算法网上一大堆，下面内容为摘抄

### 背景
Aho–Corasick 算法（也称 AC 算法，AC 自动机）是由 Alfred V. Aho 和 Margaret J.Corasick 发明的字符串搜索算法，该算法在 1975 年产生于贝尔实验室，是著名的多模匹配算法之一。

一个典型应用就是：给出 k 个单词，再给出一段文章（长度是 n），让你找出有多少个单词在文章里出现过。

与其它模式串匹配不同，KMP 算法是单模式串的匹配算法，AC 算法是多模式串的匹配算法，匹配所需的时间复杂度是 O(n)。

AC 算法建立在字典树基础上，如果您还不了解字典树，可以参考字典树入门。

### 算法过程分析
以上述所说的典型应用为例，现给定 3 个单词 {“china”, “hit”, “use”}，再给定一段文本 “chitchat”，求有多少个单词出现在文本中。

![图片alt](/uploads/images/20230629/114857-41de98f80c274591aab352ec3ac10f33.png '代码片段：Www.CodeSnippet.Cn')

根据单词 {“china”, “hit”, “use”} 建立字典树。

![图片alt](/uploads/images/20230629/114925-9f2bc77cdfc343bda6fde2086b2c1b9f.png '代码片段：Www.CodeSnippet.Cn')

根据所给文本 “chitchat” 依次匹配，图中所示 “chi” 为匹配成功的字符串。

![图片alt](/uploads/images/20230629/114944-364e0907fa744493b87fa59832ce4223.png '代码片段：Www.CodeSnippet.Cn')

当匹配到第四个字符时，“t”和 “n” 匹配失败。

![图片alt](/uploads/images/20230629/115002-f5efa5bfe8bc478e96db5fc6229dd3bd.png '代码片段：Www.CodeSnippet.Cn')

我们此时是知道已匹配成功的字符串的，即 “chi”。

AC 算法的核心就是在所有给定的单词中，找到这样的一个单词，使其与已匹配成功字符串的相同前后缀最长，利用这个最长的相同前后缀实现搜索跳转。

如上图，单词 “hit” 与已匹配成功字符串 “chi” 的最长相同前后缀为 “hi”，因此下一步从单词“hit” 的“t”开始搜索。

![图片alt](/uploads/images/20230629/115027-936cb3129e2d4edcadbcac97f87bf670.png '代码片段：Www.CodeSnippet.Cn')

此时 “t” 是匹配的，在文本 “chitchat” 中找到一个单词“hit”。

其实到这里，AC 算法的思想已经基本呈现在大家面前了。剩下的问题就是如何解决第（3）步所述的 “核心”。

### AC 算法核心
在每个结点里设置一个指针（我们称之为 fail 指针），指向跳转的位置。

![图片alt](/uploads/images/20230629/115105-97b18c28ec154292a6c88c8d7b6ae4b2.png '代码片段：Www.CodeSnippet.Cn')

对于跳转位置的选择，基于以下两点：

对于根结点的所有儿子结点，它们的 fail 指针指向根结点；

而对于其它结点，不妨设该结点上的字符为ch，沿着它的父亲结点的 fail 指针走，直到走到一个结点，它的儿子中也有字符为ch的结点，然后把该结点的 fail 指针指向那个字符为ch的结点。如果一直走到了根结点都没找到，那就把 fail 指针指向根结点。

对于第 2 点，初学者可能有点不理解，我这里稍微解释下。请仔细阅读上面的第（3）步过程，利用父亲结点的最长相同前后缀来找到儿子的最长相同前后缀。

### C#代码

```csharp
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleTest
{ 
    internal class Program
    { 
        /// <summary>
        /// 简单关键字过滤
        /// </summary>
        /// <param name="args"></param>
        private static void Main(string[] args)
        { 
            var originstr = "sswo1lfsss殺殺殺尼玛币阿三勾特朗普大蘇打阿薩伊万卡";
            var ss = CheckDirtyWords(originstr);
            if (ss != null && ss.Count > 0)
                for (var i = 0; i < ss.Count; i++)
                    originstr = originstr.Replace(ss[i].Keyword, "****");
            Console.WriteLine(originstr);
            Console.ReadLine();
        }
		
        /// <summary>
        /// 检查指定的内容是否包含非法关键字
        /// </summary>
        /// <param name="text"></param>
        /// <returns></returns>
        private static List<KeywordSearchResult> CheckDirtyWords(string text)
        { 
            var dirtyStr = "wolf|jason|特朗普|尼玛币";
            if (string.IsNullOrEmpty(dirtyStr)) return null;
            var keywords = dirtyStr.Split('|').ToList();
            var ks = new KeywordFilter(keywords);
            return ks.FindAllKeywords(text);
        }
        //protected static bool CheckDirtyWords(string text)
        //{ 
        // var dirtyStr = "wolf|jason|hoho|barry|喫屎";
        // if (string.IsNullOrEmpty(dirtyStr))
        // { 
        // return false;
        // }
        // List<string> keywords = dirtyStr.Split('|').ToList();
        // KeywordFilter ks = new KeywordFilter(keywords);
        // return ks.FindAllKeywords(text).Count > 0;
        //}
    }
	
    /// <summary>
    /// Aho-Corasick算法实现
    /// </summary>
    public class KeywordFilter
    { 
        /// <summary>
        /// 构造节点
        /// </summary>
        private class Node
        { 
            private readonly Dictionary<char, Node> transDict;
            public Node(char c, Node parent)
            { 
                Char = c;
                Parent = parent;
                Transitions = new List<Node>();
                Results = new List<string>();
                transDict = new Dictionary<char, Node>();
            }
            public char Char {  get; }
            public Node Parent {  get; }
            public Node Failure {  get; set; }
            public List<Node> Transitions {  get; private set; }
            public List<string> Results {  get; }
            public void AddResult(string result)
            { 
                if (!Results.Contains(result)) Results.Add(result);
            }
            public void AddTransition(Node node)
            { 
                transDict.Add(node.Char, node);
                Transitions = transDict.Values.ToList();
            }
            public Node GetTransition(char c)
            { 
                Node node;
                if (transDict.TryGetValue(c, out node)) return node;
                return null;
            }
            public bool ContainsTransition(char c)
            { 
                return GetTransition(c) != null;
            }
        }
        private Node root; // 根节点
        private readonly string[] keywords; // 所有关键词
        public KeywordFilter(IEnumerable<string> keywords)
        { 
            this.keywords = keywords.ToArray();
            Initialize();
        }
        /// <summary>
        /// 根据关键词来初始化所有节点
        /// </summary>
        private void Initialize()
        { 
            root = new Node(' ', null);
            // 添加模式
            foreach (var k in keywords)
            { 
                var n = root;
                foreach (var c in k)
                { 
                    Node temp = null;
                    foreach (var tnode in n.Transitions)
                        if (tnode.Char == c)
                        { 
                            temp = tnode;
                            break;
                        }
                    if (temp == null)
                    { 
                        temp = new Node(c, n);
                        n.AddTransition(temp);
                    }
                    n = temp;
                }
                n.AddResult(k);
            }
            // 第一层失败指向根节点
            var nodes = new List<Node>();
            foreach (var node in root.Transitions)
            { 
                // 失败指向root
                node.Failure = root;
                foreach (var trans in node.Transitions) nodes.Add(trans);
            }
            // 其它节点 BFS
            while (nodes.Count != 0)
            { 
                var newNodes = new List<Node>();
                foreach (var nd in nodes)
                { 
                    var r = nd.Parent.Failure;
                    var c = nd.Char;
                    while (r != null && !r.ContainsTransition(c)) r = r.Failure;
                    if (r == null)
                    { 
                        // 失败指向root
                        nd.Failure = root;
                    }
                    else
                    { 
                        nd.Failure = r.GetTransition(c);
                        foreach (var result in nd.Failure.Results) nd.AddResult(result);
                    }
                    foreach (var child in nd.Transitions) newNodes.Add(child);
                }
                nodes = newNodes;
            }
            // 根节点的失败指向自己
            root.Failure = root;
        }
		
        /// <summary>
        /// 找出所有出现过的关键词
        /// </summary>
        /// <param name="text"></param>
        /// <returns></returns>
        public List<KeywordSearchResult> FindAllKeywords(string text)
        { 
            var list = new List<KeywordSearchResult>();
            var current = root;
            for (var index = 0; index < text.Length; ++index)
            { 
                Node trans;
                do
                { 
                    trans = current.GetTransition(text[index]);
                    if (current == root)
                        break;
                    if (trans == null) current = current.Failure;
                } while (trans == null);
                if (trans != null) current = trans;
                foreach (var s in current.Results) list.Add(new KeywordSearchResult(index - s.Length + 1, s));
            }
            return list;
        }
		
        /// <summary>
        /// 简单地过虑关键词
        /// </summary>
        /// <param name="text"></param>
        /// <returns></returns>
        public string FilterKeywords(string text)
        { 
            var sb = new StringBuilder();
            var current = root;
            for (var index = 0; index < text.Length; index++)
            { 
                Node trans;
                do
                { 
                    trans = current.GetTransition(text[index]);
                    if (current == root)
                        break;
                    if (trans == null) current = current.Failure;
                } while (trans == null);
                if (trans != null) current = trans;
                // 处理字符
                if (current.Results.Count > 0)
                { 
                    var first = current.Results[0];
                    sb.Remove(sb.Length - first.Length + 1, first.Length - 1); // 把匹配到的替换为**
                    sb.Append(new string('*', current.Results[0].Length));
                }
                else
                { 
                    sb.Append(text[index]);
                }
            }
            return sb.ToString();
        }
    }
	
    /// <summary>
    /// 表示一个查找结果
    /// </summary>
    public struct KeywordSearchResult
    { 
        public static readonly KeywordSearchResult Empty = new KeywordSearchResult(-1, string.Empty);
        public KeywordSearchResult(int index, string keyword)
        { 
            Index = index;
            Keyword = keyword;
        }
        /// <summary>
        /// 位置
        /// </summary>
        public int Index {  get; }
        /// <summary>
        /// 关键词
        /// </summary>
        public string Keyword {  get; }
    }
}
```

结果如下图
![图片alt](/uploads/images/20230629/114455-7b788c7bc2064d129bd9496178ac8b94.png '代码片段：Www.CodeSnippet.Cn')

这里⇓感觉得写点什么，要不显得有点空，但还没想好写什么... 返回顶部