DFA演算法C#實現

搬運自：https://www.cnblogs.com/AlanLee/p/5329555.html

原理搜關鍵字：DFA演算法

基本照抄了原文的JAVA代碼，其中應該可以用Dictionary<string,int>來代替Hashtable，但搜到的資料都說Hashtable快得要命，雖然知道他們說的是JAVA環境，但也懶得改了，這東西實現出來不卡線程就行。

試了一下，初始化一個一萬九千多行的文本大概需要40毫秒，然後在一個大約二萬字的文本內搜索100多個關鍵詞（隨機插入測試的，話說處理這個測試文本還花了一些功夫，第一版的隨機插入，時不時就會插入到前面插入的關鍵詞中間去，導致匹配出來的數量老是不對），只需要7毫秒。

  1     /// <summary>
  2     /// 過濾詞DFA演算法實現
  3     /// </summary>
  4     public class ForbiddentWordLibrary
  5     {
  6         /// <summary>
  7         /// 用分行過濾詞文件來初始化過濾詞庫
  8         /// </summary>
  9         /// <param name="path">文件路徑</param>
 10         public ForbiddentWordLibrary( string path )
 11         {
 12             try
 13             {
 14                 words = new HashSet<string>();
 15                 using( var stream = new StreamReader( path, Encoding.UTF8 ) )
 16                 {
 17                     while( !stream.EndOfStream )
 18                     {
 19                         words.Add( stream.ReadLine().Trim() );
 20                     }
 21                 }
 22                 InitLibrary();
 23             }
 24             catch( Exception ex )
 25             {
 26                 throw ex;
 27             }
 28         }
 29 
 30         /// <summary>
 31         /// 找到輸入字元串內所有敏感詞
 32         /// </summary>
 33         /// <param name="input"></param>
 34         /// <returns></returns>
 35         public List<string> GetAllForbiddenWords( string input )
 36         {
 37             List<string> result = new List<string>();
 38             for( int i = 0; i < input.Length; i++ )
 39             {
 40                 int length = SearchFW( input, i );
 41                 if( length > 0 )
 42                 {
 43                     result.Add( input.Substring( i, length ) );
 44                     i = i + length - 1;
 45                 }
 46             }
 47 
 48             return result;
 49         }
 50 
 51         /// <summary>
 52         /// 搜索輸入的字元串，查找所有敏感詞，找到則返回敏感詞長度
 53         /// </summary>
 54         /// <param name="input">輸入字元串</param>
 55         /// <param name="beginIndex">查找的起始位置</param>
 56         /// <returns></returns>
 57         private int SearchFW( string input, int beginIndex )
 58         {
 59             bool flag = false;
 60             int len = 0;
 61             Hashtable ht = lib;
 62             for( int i = beginIndex; i < input.Length; i++ )
 63             {
 64                 var c = input[ i ];
 65                 var obj = ht[ c.ToString() ];
 66                 if( obj == null )
 67                     break;
 68                 else
 69                 {
 70                     len++;
 71                     ht = (Hashtable)obj;
 72                     if( (int)ht[ "IsEnd" ] == 1 )
 73                         flag = true;
 74                 }
 75             }
 76 
 77             if( !flag )
 78                 len = 0;
 79 
 80             return len;
 81         }
 82 
 83         /// <summary>
 84         /// 初始化詞庫結構
 85         /// </summary>
 86         private void InitLibrary()
 87         {
 88             lib = new Hashtable( words.Count );
 89             var tmp = lib;
 90             foreach( string k in words )
 91             {
 92                 for( int i = 0; i < k.Length; i++ )
 93                 {
 94                     var c = k[ i ].ToString();
 95                     if( tmp.ContainsKey( c ) )
 96                     {
 97                         tmp = (Hashtable)tmp[ c ];
 98                     }
 99                     else
100                     {
101                         var nht = new Hashtable();
102                         nht.Add( "IsEnd", 0 );
103                         tmp.Add( c, nht );
104                         tmp = nht;
105                     }
106 
107                     if( i == k.Length - 1 )
108                     {
109                         if( tmp.ContainsKey( "IsEnd" ) )
110                             tmp[ "IsEnd" ] = 1;
111                         else
112                             tmp.Add( "IsEnd", 1 );
113                     }
114                 }
115                 tmp = lib;
116             }
117         }
118 
119         /// <summary>
120         /// 原始過濾詞數據集
121         /// </summary>
122         private HashSet<string> words;
123         /// <summary>
124         /// 過濾詞庫
125         /// </summary>
126         private Hashtable lib;
127     }