高效的关键字过滤及查找算法

最近做游戏服务器需要使用到关键字查找和过滤的功能

首先想到的是使用HashSet<string> 的方式.

实现如下:

View Code

 public class FilterWord
    {
        int m_maxLen=8; //关键字最大长度

        HashSet<string> m_keys = new HashSet<string>();
        public FilterWord(string path)
        {
            init(path);
        }
        FilterWord()
        {
            string path = System.AppDomain.CurrentDomain.BaseDirectory;
            path = Path.Combine(path, "Config", "FilterWord.txt");
            init(path);
        }

        void init(string path)
        {
            using (StreamReader sw = new StreamReader(File.OpenRead(path)))
            {
                string key = sw.ReadLine();
                while (key != null)
                {
                    if (key != string.Empty && m_keys.Add(key) && key.Length > m_maxLen)
                    {
                        m_maxLen = key.Length;
                    }
                    key = sw.ReadLine();
                }
            }
        }

        /// <summary>
        /// 插入新的Key.
        /// </summary>
        /// <param name="name"></param>
        public void InsertKey(string key)
        {
            if ((!string.IsNullOrEmpty(key)) && m_keys.Add(key) && key.Length > m_maxLen)
            {
                m_maxLen = key.Length;
            }
        }


        /// <summary>
        /// 检查是否包含非法字符
        /// </summary>
        /// <param name="name"></param>
        /// <returns>找到的第1个非法字符.没有则返回string.Empty</returns>
        public string GetBadWord(string name)
        {
            for (int len = 1; len <= name.Length; len++)
            {
                int maxIndex = name.Length - len;
                for (int index = 0; index <= maxIndex; index++)
                {
                    string key = name.Substring(index, len);
                    if (m_keys.Contains(key))
                    {
                        return key;
                    }
                }
            }
            return string.Empty;
        }

        /// <summary>
        /// 替换非法字符
        /// </summary>
        /// <param name="name"></param>
        /// <returns></returns>
        public string ReplacetBadWord(string name)
        {
            int maxLen = Math.Min(m_maxLen, name.Length);
            for (int len = 1; len <= maxLen; len++)
            {
                int maxIndex = name.Length - len;
                for (int index = 0; index <= maxIndex; index++)
                {
                    string key = name.Substring(index, len);
                    if (m_keys.Contains(key))
                    {
                        int l = key.Length;
                        name = name.Replace(key, new string('*', l));
                        index += (l - 1);
                    }
                }
            }
            return name;
        }
    }

这个方式有个缺点.就是使用 String.Substring会创建大量临时对象.即便是使用了最大长度进行分割字符串的控件.在需要过滤的字符串较长时,还是不见得高效.

有没有一种方法如避免创建大量字符串呢?有,就是下面要给大家推荐的Trie树..

Trie，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

更多介绍见维基百科: http://zh.wikipedia.org/wiki/Trie

维基百科上有一个C++的实现..

在这里我给出一个C#的实现.

 在游戏或聊天系统中,消息过滤的开销经常占到了系统总开销的一半.

使用这种方式基本上杜绝了新对象的创建,有效的减少了垃圾回收的负担,节约了资源.

测试代码:

    //添加关键字

TrieFilter filter = new TrieFilter();

filter.AddKey("SB");

filter.AddKey("fuck");

filter.AddKey("日本");

 //过滤

string x = filter.FindOne("名字加fuck日本人妖成"); 

var xs= filter.FindAll("名字加fuck日本人妖成"); 

{

 Console.WriteLine(v);

}

//替换

string y= filter.Replace("名字加fuck日本人妖成",'*');foreach(var v in xs)

作者: 边城浪 发表于 2011-08-24 22:27 原文链接

评论: 0　查看评论　发表评论

最新新闻：
· 15个基于jQuery开发的网站，非常有创意！(2011-08-24 22:25)
· 移动社交游戏平台木瓜移动用户数突破2500万(2011-08-24 22:24)
· 分析称Groupon中国业务是一场灾难(2011-08-24 22:21)
· Facebook手机HTC Status销量不佳 AT&T或停售(2011-08-24 21:49)
· 三星诺基亚将效仿苹果推廉价智能手机(2011-08-24 21:46)

编辑推荐：Hack, Everything!

网站导航：博客园首页  我的园子  新闻  闪存  小组  博问  知识库