在实际当中，聊天过滤工作 最终可能会消耗掉可观的（有时是惊人的）资源总量--无论是从开发方面还是从原始计算能力方面来说。有些知名SNS类游戏仅在聊天过滤上就耗费了超过50%的计算资源。因此对于这部分的优化工作就显得特别重要。
最近做游戏服务器，需要用到聊天过滤，首先想到的是使用HashSet<string> 的方式。
基本的思路是把所有需要过滤的关键字保存在HashSet<string>中。
对于用户输入的消息进行暴力分割。
如：今天你好吗
单个字符分割为： 今/天/你/好/吗
2个字符分割为： 今天/天你/你好/好吗
3个字符分割为： 今天你/天你好/你好吗
..........以此类推
对于大的字符串。我们对分割把分割的长度限制为需过滤关键字的长度。
然后对分割的了字符串进行匹配。
View Code
{
int m_maxLen; // 关键字最大长度
HashSet < string > m_keys = new HashSet < string > ();
/// <summary>
/// 插入新的Key.
/// </summary>
/// <param name="name"></param>
public void AddKey( string key)
{
if (( ! string .IsNullOrEmpty(key)) && m_keys.Add(key) && key.Length > m_maxLen)
{
m_maxLen = key.Length;
}
}
/// <summary>
/// 检查是否包含非法字符
/// </summary>
/// <param name="text"> 输入文本 </param>
/// <returns> 找到的第1个非法字符.没有则返回string.Empty </returns>
public string FindOne( string text)
{
for ( int len = 1 ; len <= text.Length; len ++ )
{
int maxIndex = text.Length - len;
for ( int index = 0 ; index <= maxIndex; index ++ )
{
string key = text.Substring(index, len);
if (m_keys.Contains(key))
{
return key;
}
}
}
return string .Empty;
}
}
这个方式有个缺点.就是使用 String.Substring会创建大量临时对象.
即便是使用了最大长度进行分割字符串的控件.在需要过滤的字符串较长时,还是不见得高效.
Trie，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
我们先来看一个Trie结构的例子
在这个Trie结构中，保存了A、to、tea、ted、ten、i、in、inn这8个字符串
首先看我们如何实现这个结构：
{
private Char m_key;
private Dictionary < Char, TrieFilter > m_values;
//根节点，不包含字符，即m_key='\0';
public TrieFilter()
{
m_values = new Dictionary < Char, TrieFilter > ();
}
TrieFilter(Char key)
{
m_key = key;
m_values = new Dictionary < Char, TrieFilter > ();
}
/// <summary>
/// 添加关键字
/// </summary>
/// <param name="key"></param>
public void AddKey( string key)
{
if ( string .IsNullOrEmpty(key))
{
return ;
}
TrieFilter node = this ;
foreach (var c in key)
{
TrieFilter subnode;
if ( ! node.m_values.TryGetValue(c, out subnode))
{
subnode = new TrieFilter(c);
node.m_values.Add(c, subnode);
}
node = subnode;
}
node.m_values[ ' \0 ' ] = null ;
}
}
}
这样。一个C#的Trie结构就表示完成。。
下面我们来看看如何实现关键字查找
/// 检查是否包含非法字符
/// </summary>
/// <param name="text"> 输入文本 </param>
/// <returns> 找到的第1个非法字符.没有则返回string.Empty </returns>
public string FindOne( string text)
{
for ( int i = 0 ; i < text.Length; i ++ )
{
TrieFilter node;
if (m_values.TryGetValue(text[i], out node))
{
for ( int j = i + 1 ; j < text.Length; j ++ )
{
if (node.m_values.TryGetValue(text[j], out node))
{
if (node.m_values.ContainsKey( ' \0 ' ))
{
return text.Substring(i, (j + 1 - i));
}
}
else
{
break ;
}
}
}
}
return string .Empty;
}
是不是很简单呢？
把由蛮力匹配转变成基于Trie的匹配方案会极大的节省执行时间，这个比较对较长字符串进行匹配时更加明显。
对于长度在20左右的字符串。Tire的匹配速度比Hash的方式快了近10倍。
下面附上完整的代码下载
里面的BadWord.txt包括了7000多个敏感关键字。
完整的代码及性能对比测试下载：http://files.cnblogs.com/yeerh/FilterTest.rar
希望本文能对你有所帮助。欢迎拍砖。