DFA算法C#实现

当前位置:

首页 > c#编程 >

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     }

栏目列表