快捷導(dǎo)航

asp.NET 臟字過濾算法修改版

更新時(shí)間：2009年10月25日 10:18:46 作者：

我們網(wǎng)站的臟字字典中大概有600多個(gè)詞，而且會(huì)發(fā)生變化，因此簡(jiǎn)單的在數(shù)據(jù)新增/修改的時(shí)候做一次臟字過濾是不夠的。在網(wǎng)站從.NET 1.1到2.0改版的時(shí)候，對(duì)新版的測(cè)試發(fā)現(xiàn)舊的臟字過濾算法耗費(fèi)的時(shí)間過長(zhǎng)，需要做一些優(yōu)化。

舊的算法是簡(jiǎn)單對(duì)每一個(gè)臟字調(diào)用一遍 string.replace，當(dāng)然是用了StringBuilder。http://www.dbjr.com.cn/article/20575.htm。在我這里測(cè)試的時(shí)候，RegEx要快一倍左右。但是還是不太滿意，應(yīng)為我們網(wǎng)站上臟字過濾用的相當(dāng)多，經(jīng)過一番思考后，自己做了一個(gè)算法。在自己的機(jī)器上測(cè)試了一下，使用原文中的臟字庫，0x19c的字符串長(zhǎng)度，1000次循環(huán)，文本查找耗時(shí)1933.47ms，RegEx用了1216.719ms，而我的算法只用了34.125ms.

算法的關(guān)鍵，還是使用空間來換時(shí)間，使用了2個(gè)全局的BitArray, 長(zhǎng)度均為Char.MaxValue。其中一個(gè)BitArray用來判斷是否有某個(gè)char開頭的臟字，另一個(gè)BitArray用來判斷所有臟字中是否包含某個(gè)char。經(jīng)過這兩個(gè)BitArray，可以做出快速判斷，之后就使用Hash Code來判斷完整的臟字，通過預(yù)先獲取的最大臟字長(zhǎng)度優(yōu)化遍歷過程。

需要的變量如下：

復(fù)制代碼代碼如下:

 
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>，記錄臟字的出現(xiàn)次數(shù)。

初始化這些數(shù)據(jù)的方法如下：

復(fù)制代碼代碼如下:

 
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; 
} 
} 
} 

判斷臟字是否出現(xiàn)在一個(gè)字符串中的代碼如下：

復(fù)制代碼代碼如下:

 
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; 

替換的代碼就不貼了，跟判斷包含類似，只不過不能發(fā)現(xiàn)一個(gè)臟字后就退出循環(huán)。如果出現(xiàn)臟字的可能不是很高，就沒有必要?jiǎng)?chuàng)建一個(gè)臨時(shí)的StringBuilder。

進(jìn)一步，可以通過借鑒.NET源碼中string.GetHashCode()的實(shí)現(xiàn)，避免一次Substring的調(diào)用，提高性能。也可以設(shè)計(jì)遞進(jìn)的HashCode實(shí)現(xiàn)，比如"helloworld"可以用"helloworl"的hash進(jìn)一步計(jì)算，優(yōu)化效率。

另外，也可以拋棄Hash，改用排序過的string[]，用BinarySearch來判斷sub是否為臟字。BinarySearch的結(jié)果是可以遞進(jìn)的，即可以用查找"helloworl"的結(jié)果來加速判斷"helloworld"。（已測(cè)試，700個(gè)臟字，BinarySearch的效率有時(shí)會(huì)低很多。）
最后發(fā)一點(diǎn)牢騷，當(dāng)初最早發(fā)的時(shí)候（http://www.dbjr.com.cn/article/20576.htm），僅僅是為了說明下自己的算法，具體的代碼甚至還有一點(diǎn)錯(cuò)誤。兩個(gè)事情讓我覺得心里不很爽，一個(gè)是被亂七八糟的無數(shù)網(wǎng)站轉(zhuǎn)載而不說明出處，導(dǎo)致我后來的改進(jìn)和錯(cuò)誤修正達(dá)不到效果，二是一些人都愿意看到最終的代碼，而不是理解我想要表達(dá)的最核心的設(shè)計(jì)，然后自己去考慮實(shí)現(xiàn)。

您可能感興趣的文章: