VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > temp > 简明python教程 >
  • 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     }    
复制代码


相关教程