首页 > 代码库 > Trie树-脏词过滤应用

Trie树-脏词过滤应用

2024-07-15 16:17:02   220人阅读

Trie树，又称字符查找树、前缀树，主要用于字符匹配（详见http://en.wikipedia.org/wiki/Trie）。适合做关键词查找，比如查找文章中的关键字然后给他们加链接。 当然对脏词的过滤应用也是样，只是把替换连接的工作换成了替换字符。

当前的代码还只是进行简单的替换，并没有做一些字符的处理，比如“昨天见到你妈，逼我要买房”，这本身不是脏词，因为有逗号，所以程序里要增加字符的范围判断。

程序中的skip就是用来过滤脏词的简单变体，比如“找*小*姐”，默认是最多跳过3个字符，这个可以随便调整了。总之是一个Trie的锻炼吧。

 

  1. public class TrieTree  
  2. {  
  3.     private readonly Dictionary<char, TrieTree> Children;  
  4.   
  5.     public bool End { get; set; }  
  6.   
  7.     public TrieTree()  
  8.     {  
  9.         Children = new Dictionary<char, TrieTree>();  
  10.     }  
  11.   
  12.     public void AddKey(string keyword)  
  13.     {  
  14.         if (String.IsNullOrEmpty(keyword))  
  15.         {  
  16.             return;  
  17.         }  
  18.   
  19.         var cNode = this;  
  20.   
  21.         foreach (var key in keyword)  
  22.         {  
  23.             if (cNode.Children.ContainsKey(key))  
  24.             {  
  25.                 cNode = cNode.Children[key];  
  26.             }  
  27.             else  
  28.             {  
  29.                 var node = new TrieTree();  
  30.                 cNode.Children.Add(key, node);  
  31.                 cNode = node;  
  32.             }  
  33.         }  
  34.         cNode.End = true;  
  35.     }  
  36.   
  37.   
  38.     public void Replace(ref string text)  
  39.     {  
  40.         for (var i = 0; i < text.Length; i++)  
  41.         {  
  42.             var cNode = this;  
  43.             var key = text[i];  
  44.             //碰到脏词的第一个词  
  45.             if (cNode.Children.ContainsKey(key))  
  46.             {  
  47.                 cNode = cNode.Children[key];  
  48.                 //查找是否包含脏词后面的词  
  49.                 var skip = 0;  
  50.                 for (var j = i + 1; j < text.Length; j++)  
  51.                 {  
  52.                     if (cNode.Children.ContainsKey(text[j]))  
  53.                     {  
  54.                         cNode = cNode.Children[text[j]];  
  55.                         skip = 0;  
  56.                     }  
  57.                     else  
  58.                     {  
  59.                         //允许略过过几个字符  
  60.                         skip++;  
  61.                         if (skip > 3)  
  62.                         {  
  63.                             break;  
  64.                         }  
  65.                     }  
  66.                     if (cNode.End)  
  67.                     {  
  68.                         var len = j + 1 - i;  
  69.                         text = text.Replace(text.Substring(i, len), string.Empty.PadLeft(len, ‘*‘));  
  70.                         i += len;  
  71.                         break;  
  72.                     }  
  73.                 }  
  74.             }  
  75.         }  
  76.     }  
  77.   
  78. }  

使用方法如下：

 

  1. class Program  
  2. {  
  3.     static void Main(string[] args)  
  4.     {  
  5.         var trie = new TrieTree();  
  6.         var keywords = "我操,妓女,fuck".Split(‘,‘);  
  7.         foreach (var key in keywords)  
  8.         {  
  9.             trie.AddKey(key);  
  10.         }  
  11.   
  12.         var text = @"我擦啊，尼玛，，fuck you，你这个妓女，贱人。";  
  13.         trie.Replace(ref text);  
  14.         Console.WriteLine(text);  
  15.         Console.Read();  
  16.     }  
  17. }  


执行的结果：

 

转自http://blog.csdn.net/maddemon/article/details/7011699


联系
我们