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     }