在本人昨晚发的　文章中，只是介绍过虑的功能和性能，这个文章主要讲一下实现的思路，另外给大家看一下Aho–Corasick算法的C#实现。

 

既然是要过虑，那就要先查找，如果是直接的一个字符一个字符的匹配，那是很耗时的，因为时间花在不需要匹配的工作，有不少人会用正则去解决过虑，我09年的时候也这样，但后来发现大量关键词下性能确实极低下，所以才会另想它法。上一文中的过虑主要思想是这样的，开始会先用一个字典保存保存所有关键词，同一个字母开头的会另放在一个子字典里，这样一来，扫描的范围就大大的缩小了，然后再考虑到脏字一般是2个字的占了很大的比例，所以再在第二个字母做判断，如果不存在就不需要再扫描下去了，至于可跳字符，就是在直接需要扫描的时候一一判断的，没技巧可讲，另外一点值得注意的是，大小写敏感的情况下，在判断时需要转换大小写，大量关键词影响不小，所以就初始化时再保存了一分小写的，所以在扫描的时候就不需要转换了，所以是否大小写的两个情况性能上不会有什么变化，基本的思路就这样了。如果说，你想要很准确的过虑，那就要用到分词了（判断可以人性化），我的方法只能处理比较简单匹配与过虑。实现过程并没有使用Aho–Corasick算法。

 

在查找资料的时候还了解到算法，它可以帮助我们快速的找出多个子字符串。可以到这里了解算法：

 

５点有约会，先直接上实现代码了（从一老外的例子里小改的），本人测试过我上面的方法和使用过虑用的时候差不了多少：

 

/// 
    /// 表示一个查找结果    /// 
    public struct KeywordSearchResult    {        private int index;        private string keyword;        public static readonly KeywordSearchResult Empty = new KeywordSearchResult(-1, string.Empty);        public KeywordSearchResult(int index, string keyword)        {            this.index = index;             this.keyword = keyword;        }        /// 
        /// 位置        /// 
        public int Index        {            get { return index; }        }        /// 
        /// 关键词        /// 
        public string Keyword        {            get { return keyword; }        }    }    /// 
    /// Aho-Corasick算法实现    /// 
    public class KeywordSearch    {        /// 
        /// 构造节点        /// 
        private class Node        {            private Dictionary
     
       transDict;            public Node(char c, Node parent)            {                this.Char = c;                this.Parent = parent;                this.Transitions = new List
      
       ();                this.Results = new List
       
        ();                this.transDict = new Dictionary
        
         ();            }            public char Char            {                get;                private set;            }            public Node Parent            {                get;                private set;            }            public Node Failure            {                get;                set;            }            public List
         
           Transitions            {                get;                private set;            }            public List
          
            Results { get; private set; } public void AddResult(string result) { if (!Results.Contains(result)) { Results.Add(result); } } public void AddTransition(Node node) { this.transDict.Add(node.Char, node); this.Transitions = this.transDict.Values.ToList(); } public Node GetTransition(char c) { Node node; if (this.transDict.TryGetValue(c, out node)) { return node; } return null; } public bool ContainsTransition(char c) { return GetTransition(c) != null; } } private Node root; // 根节点 private string[] keywords; // 所有关键词 public KeywordSearch(IEnumerable
           
             keywords) { this.keywords = keywords.ToArray(); this.Initialize(); } /// 
            
 /// 根据关键词来初始化所有节点 /// 
 private void Initialize() { this.root = new Node(' ', null); // 添加模式 foreach (string k in this.keywords) { Node n = this.root; foreach (char c in k) { Node temp = null; foreach (Node 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); } // 第一层失败指向根节点 List
            
              nodes = new List
             
              (); foreach (Node node in this.root.Transitions) { // 失败指向root node.Failure = this.root; foreach (Node trans in node.Transitions) { nodes.Add(trans); } } // 其它节点 BFS while (nodes.Count != 0) { List
              
                newNodes = new List
               
                (); foreach (Node nd in nodes) { Node r = nd.Parent.Failure; char c = nd.Char; while (r != null && !r.ContainsTransition(c)) { r = r.Failure; } if (r == null) { // 失败指向root nd.Failure = this.root; } else { nd.Failure = r.GetTransition(c); foreach (string result in nd.Failure.Results) { nd.AddResult(result); } } foreach (Node child in nd.Transitions) { newNodes.Add(child); } } nodes = newNodes; } // 根节点的失败指向自己 this.root.Failure = this.root; } /// 
                
 /// 找出所有出现过的关键词 /// 
 /// 
                 /// 
                 public List
                
                  FindAllKeywords(string text) { List
                 
                   list = new List
                  
                   (); Node current = this.root; for (int index = 0; index < text.Length; ++index) { Node trans; do { trans = current.GetTransition(text[index]); if (current == this.root) break; if (trans == null) { current = current.Failure; } } while (trans == null); if (trans != null) { current = trans; } foreach (string s in current.Results) { list.Add(new KeywordSearchResult(index - s.Length + 1, s)); } } return list; } /// 
                   
 /// 简单地过虑关键词 /// 
 /// 
                    /// 
                    public string FilterKeywords(string text) { StringBuilder sb = new StringBuilder(); Node current = this.root; for (int index = 0; index < text.Length; index++) { Node trans; do { trans = current.GetTransition(text[index]); if (current == this.root) break; if (trans == null) { current = current.Failure; } } while (trans == null); if (trans != null) { current = trans; } // 处理字符 if (current.Results.Count > 0) { string 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(); } }
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

 

 

测试结果：

 

 下载源码：