当前位置： 移动技术网 > IT编程>开发语言>.net > asp.NET 脏字过滤算法 修改版

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

2017年12月12日  | 移动技术网IT编程  | 我要评论

666rtys,八路军女兵蒙难记,库迪奇尼

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

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

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

private dictionary<string, object> hash = new dictionary<string, object>();
private bitarray firstcharcheck = new bitarray(char.maxvalue);
private bitarray allcharcheck = new bitarray(char.maxvalue);
private int maxlength = 0;

其中hash只使用到了key，value都置为null。也可以使用.net 3.5中的hashset，或者使用dictionary<string, int>，记录脏字的出现次数。

初始化这些数据的方法如下：
复制代码 代码如下:

foreach (string word in badwords)
{
if (!hash.containskey(word))
{
hash.add(word, null);
maxlength = math.max(maxlength, word.length);
firstcharcheck[word[0]] = true;

foreach (char c in word)
{
allcharcheck[c] = true;
}
}
}

判断脏字是否出现在一个字符串中的代码如下：

复制代码 代码如下:

int index = 0;
int offset = 0;
while (index < text.length)
{
if (!firstcharcheck[text[index]])
{
while (index < text.length - 1 && !firstcharcheck[text[++index]]) ;
}

for (int j = 1; j <= math.min(maxlength, text.length - index); j++)
{
if (!allcharcheck[text[index + j - 1]])
{
break;
}

string sub = text.substring(index, j);

if (hash.containskey(sub))
{
return true;
}
}

index++;
}

return false;

替换的代码就不贴了，跟判断包含类似，只不过不能发现一个脏字后就退出循环。如果出现脏字的可能不是很高，就没有必要创建一个临时的stringbuilder。

进一步，可以通过借鉴.net源码中string.gethashcode()的实现，避免一次substring的调用，提高性能。也可以设计递进的hashcode实现，比如"helloworld"可以用"helloworl"的hash进一步计算，优化效率。

另外，也可以抛弃hash，改用排序过的string[]，用binarysearch来判断sub是否为脏字。binarysearch的结果是可以递进的，即可以用查找"helloworl"的结果来加速判断"helloworld"。 （已测试，700个脏字，binarysearch的效率有时会低很多。）
最后发一点牢骚，当初最早发的时候（//www.jb51.net/article/20576.htm），仅仅是为了说明下自己的算法，具体的代码甚至还有一点错误。两个事情让我觉得心里不很爽，一个是被乱七八糟的无数网站转载而不说明出处，导致我后来的改进和错误修正达不到效果，二是一些人都愿意看到最终的代码，而不是理解我想要表达的最核心的设计，然后自己去考虑实现。

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网