我們網站的臟字字典中大概有600多個詞，而且會發生變化，因此簡單的在數據新增/修改的時候做一次臟字過濾是不夠的。在網站從.NET 1.1到2.0改版的時候，對新版的測試發現舊的臟字過濾算法耗費的時間過長，需要做一些優化。
舊的算法是簡單對每一個臟字調用一遍 string.replace，當然是用了StringBuilder。在cnblogs里發現了一篇討論臟字過濾的blog http://www.rzrgm.cn/goody9807/archive/2006/09/12/502094.html。在我這里測試的時候，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>，記錄臟字的出現次數。
初始化這些數據的方法如下：
替換的代碼就不貼了，跟判斷包含類似，只不過不能發現一個臟字后就退出循環。如果出現臟字的可能不是很高，就沒有必要創建一個臨時的StringBuilder。
進一步，可以通過借鑒.NET源碼中string.GetHashCode()的實現，避免一次Substring的調用，提高性能。也可以設計遞進的HashCode實現，比如"helloworld"可以用"helloworl"的hash進一步計算，優化效率。
另外，也可以拋棄Hash，改用排序過的string[]，用BinarySearch來判斷sub是否為臟字。BinarySearch的結果是可以遞進的，即可以用查找"helloworl"的結果來加速判斷"helloworld"。 （已測試，700個臟字，BinarySearch的效率有時會低很多。）
最后發一點牢騷，當初最早發的時候（http://www.rzrgm.cn/xingd/archive/2007/09/26/906013.html），僅僅是為了說明下自己的算法，具體的代碼甚至還有一點錯誤。兩個事情讓我覺得心里不很爽，一個是被亂七八糟的無數網站轉載而不說明出處，導致我后來的改進和錯誤修正達不到效果，二是一些人都愿意看到最終的代碼，而不是理解我想要表達的最核心的設計，然后自己去考慮實現。
舊的算法是簡單對每一個臟字調用一遍 string.replace，當然是用了StringBuilder。在cnblogs里發現了一篇討論臟字過濾的blog http://www.rzrgm.cn/goody9807/archive/2006/09/12/502094.html。在我這里測試的時候，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;
}
}
}
{
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;
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進一步計算，優化效率。
最后發一點牢騷，當初最早發的時候（http://www.rzrgm.cn/xingd/archive/2007/09/26/906013.html），僅僅是為了說明下自己的算法，具體的代碼甚至還有一點錯誤。兩個事情讓我覺得心里不很爽，一個是被亂七八糟的無數網站轉載而不說明出處，導致我后來的改進和錯誤修正達不到效果，二是一些人都愿意看到最終的代碼，而不是理解我想要表達的最核心的設計，然后自己去考慮實現。
浙公網安備 33010602011771號