我要评论搬运自：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 }
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论