asp.NET 臟字過濾算法 修改版
更新時間:2009年10月25日 10:18:46 作者:
我們網(wǎng)站的臟字字典中大概有600多個詞,而且會發(fā)生變化,因此簡單的在數(shù)據(jù)新增/修改的時候做一次臟字過濾是不夠的。在網(wǎng)站從.NET 1.1到2.0改版的時候,對新版的測試發(fā)現(xiàn)舊的臟字過濾算法耗費的時間過長,需要做一些優(yōu)化。
舊的算法是簡單對每一個臟字調(diào)用一遍 string.replace,當(dāng)然是用了StringBuilder。http://chabaoo.cn/article/20575.htm。在我這里測試的時候,RegEx要快一倍左右。但是還是不太滿意,應(yīng)為我們網(wǎng)站上臟字過濾用的相當(dāng)多,經(jīng)過一番思考后,自己做了一個算法。在自己的機器上測試了一下,使用原文中的臟字庫,0x19c的字符串長度,1000次循環(huán),文本查找耗時1933.47ms,RegEx用了1216.719ms,而我的算法只用了34.125ms.
算法的關(guān)鍵,還是使用空間來換時間,使用了2個全局的BitArray, 長度均為Char.MaxValue。其中一個BitArray用來判斷是否有某個char開頭的臟字,另一個BitArray用來判斷所有臟字中是否包含某個char。經(jīng)過這兩個BitArray,可以做出快速判斷,之后就使用Hash Code來判斷完整的臟字,通過預(yù)先獲取的最大臟字長度優(yōu)化遍歷過程。
需要的變量如下:
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ù)的方法如下:
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)在一個字符串中的代碼如下:
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)一個臟字后就退出循環(huán)。如果出現(xiàn)臟字的可能不是很高,就沒有必要創(chuàng)建一個臨時的StringBuilder。
進一步,可以通過借鑒.NET源碼中string.GetHashCode()的實現(xiàn),避免一次Substring的調(diào)用,提高性能。也可以設(shè)計遞進的HashCode實現(xiàn),比如"helloworld"可以用"helloworl"的hash進一步計算,優(yōu)化效率。
另外,也可以拋棄Hash,改用排序過的string[],用BinarySearch來判斷sub是否為臟字。BinarySearch的結(jié)果是可以遞進的,即可以用查找"helloworl"的結(jié)果來加速判斷"helloworld"。 (已測試,700個臟字,BinarySearch的效率有時會低很多。)
最后發(fā)一點牢騷,當(dāng)初最早發(fā)的時候(http://chabaoo.cn/article/20576.htm),僅僅是為了說明下自己的算法,具體的代碼甚至還有一點錯誤。兩個事情讓我覺得心里不很爽,一個是被亂七八糟的無數(shù)網(wǎng)站轉(zhuǎn)載而不說明出處,導(dǎo)致我后來的改進和錯誤修正達不到效果,二是一些人都愿意看到最終的代碼,而不是理解我想要表達的最核心的設(shè)計,然后自己去考慮實現(xiàn)。
算法的關(guān)鍵,還是使用空間來換時間,使用了2個全局的BitArray, 長度均為Char.MaxValue。其中一個BitArray用來判斷是否有某個char開頭的臟字,另一個BitArray用來判斷所有臟字中是否包含某個char。經(jīng)過這兩個BitArray,可以做出快速判斷,之后就使用Hash Code來判斷完整的臟字,通過預(yù)先獲取的最大臟字長度優(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)在一個字符串中的代碼如下:
復(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)一個臟字后就退出循環(huán)。如果出現(xiàn)臟字的可能不是很高,就沒有必要創(chuàng)建一個臨時的StringBuilder。
進一步,可以通過借鑒.NET源碼中string.GetHashCode()的實現(xiàn),避免一次Substring的調(diào)用,提高性能。也可以設(shè)計遞進的HashCode實現(xiàn),比如"helloworld"可以用"helloworl"的hash進一步計算,優(yōu)化效率。
另外,也可以拋棄Hash,改用排序過的string[],用BinarySearch來判斷sub是否為臟字。BinarySearch的結(jié)果是可以遞進的,即可以用查找"helloworl"的結(jié)果來加速判斷"helloworld"。 (已測試,700個臟字,BinarySearch的效率有時會低很多。)
最后發(fā)一點牢騷,當(dāng)初最早發(fā)的時候(http://chabaoo.cn/article/20576.htm),僅僅是為了說明下自己的算法,具體的代碼甚至還有一點錯誤。兩個事情讓我覺得心里不很爽,一個是被亂七八糟的無數(shù)網(wǎng)站轉(zhuǎn)載而不說明出處,導(dǎo)致我后來的改進和錯誤修正達不到效果,二是一些人都愿意看到最終的代碼,而不是理解我想要表達的最核心的設(shè)計,然后自己去考慮實現(xiàn)。
相關(guān)文章
asp.net URL中包含中文參數(shù)造成亂碼的解決方法
中文亂碼一直以來是WEB開發(fā)中比較常見的問題之一,對于初學(xué)者來說,各種各樣的編碼方式可能會有點不適應(yīng),本篇文章并不講述這些編碼,而是把自己遇到的一個小問題以及該問題的解決之法說明一下,希望對大家有用。2010-03-03Asp.net MVC實現(xiàn)生成Excel并下載功能
這篇文章主要為大家詳細介紹了Asp.net MVC實現(xiàn)生成Excel并下載功能,具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-12-12在 .NET Core 中使用 Diagnostics (Diagnostic Source) 記錄跟蹤信息
今天給大家講一下在 .NET Core 2 中引入的全新 DiagnosticSource 事件機制,為什么說是全新呢? 在以前的 .NET Framework 有心的同學(xué)應(yīng)該知道也有 Diagnostics,那么新的 .NET Core 中有什么變化呢?跟隨小編一起看看吧2021-06-06asp.net下UTF-7轉(zhuǎn)GB2312編碼的代碼(中文)
UTF-7轉(zhuǎn)換GB2312編碼的方法2010-07-07