asp.NET 脏字过滤算法 修改版

旧的算法是简单对每一个脏字调用一遍 string.replace，当然是用了StringBuilder。//www.gxlcms.com/article/20575.htm。在我这里测试的时候，RegEx要快一倍左右。但是还是不太满意，应为我们网站上脏字过滤用的相当多，经过一番思考后，自己做了一个算法。在自己的机器上测试了一下，使用原文中的脏字库，0x19c的字符串长度，1000次循环，文本查找耗时1933.47ms，RegEx用了1216.719ms，而我的算法只用了34.125ms.

算法的关键，还是使用空间来换时间，使用了2个全局的BitArray, 长度均为Char.MaxValue。其中一个BitArray用来判断是否有某个char开头的脏字，另一个BitArray用来判断所有脏字中是否包含某个char。经过这两个BitArray，可以做出快速判断，之后就使用Hash Code来判断完整的脏字，通过预先获取的最大脏字长度优化遍历过程。

需要的变量如下：
代码如下:

<br>private Dictionary<string, object> hash = new Dictionary<string, object>(); <br>private BitArray firstCharCheck = new BitArray(char.MaxValue); <br>private BitArray allCharCheck = new BitArray(char.MaxValue); <br>private int maxLength = 0; <br> <br>其中hash只使用到了key，value都置为null。也可以使用.NET 3.5中的HashSet，或者使用Dictionary<string, int>，记录脏字的出现次数。 <br><br>初始化这些数据的方法如下： <br><span><u></u></span> 代码如下:<pre class="brush:php;toolbar:false layui-box layui-code-view layui-code-notepad"><ol class="layui-code-ol"><li><br>foreach (string word in badwords) <br>{ <br>if (!hash.ContainsKey(word)) <br>{ <br>hash.Add(word, null); <br>maxlength = Math.Max(maxlength, word.Length); <br>firstCharCheck[word[0]] = true; <br><br>foreach (char c in word) <br>{ <br>allCharCheck[c] = true; <br>} <br>} <br>} <br> <br>判断脏字是否出现在一个字符串中的代码如下： <br><br><span><u></u></span> 代码如下:<pre class="brush:php;toolbar:false layui-box layui-code-view layui-code-notepad"><ol class="layui-code-ol"><li><br>int index = 0; <br>int offset = 0; <br>while (index < text.Length) <br>{ <br>if (!firstCharCheck[text[index]]) <br>{ <br>while (index < text.Length - 1 && !firstCharCheck[text[++index]]) ; <br>} <br><br>for (int j = 1; j <= Math.Min(maxlength, text.Length - index); j++) <br>{ <br>if (!allCharCheck[text[index + j - 1]]) <br>{ <br>break; <br>} <br><br>string sub = text.Substring(index, j); <br><br>if (hash.ContainsKey(sub)) <br>{ <br>return true; <br>} <br>} <br><br>index++; <br>} <br><br>return false; <br> <br>替换的代码就不贴了，跟判断包含类似，只不过不能发现一个脏字后就退出循环。如果出现脏字的可能不是很高，就没有必要创建一个临时的StringBuilder。 <br><br>进一步，可以通过借鉴.NET源码中string.GetHashCode()的实现，避免一次Substring的调用，提高性能。也可以设计递进的HashCode实现，比如"helloworld"可以用"helloworl"的hash进一步计算，优化效率。 <br><br>另外，也可以抛弃Hash，改用排序过的string[]，用BinarySearch来判断sub是否为脏字。BinarySearch的结果是可以递进的，即可以用查找"helloworl"的结果来加速判断"helloworld"。 （已测试，700个脏字，BinarySearch的效率有时会低很多。） <br>最后发一点牢骚，当初最早发的时候（//www.gxlcms.com/article/20576.htm），仅仅是为了说明下自己的算法，具体的代码甚至还有一点错误。两个事情让我觉得心里不很爽，一个是被乱七八糟的无数网站转载而不说明出处，导致我后来的改进和错误修正达不到效果，二是一些人都愿意看到最终的代码，而不是理解我想要表达的最核心的设计，然后自己去考虑实现。</li><li>            </li><li>                                </li></ol></pre></li></ol></pre>