在做一些聊天网站,游戏等的时候,需要对大量的关键词进行过滤。如果仅仅通过正则表达式和for循环,会占用很高的CPU,严重影响性能。这个时候,就需要一个比较好的算法,来达到过滤的目的。这里有一篇,《利用树形结构过滤敏感词的文章》。按照文章中的算法,的确可以优化性能。
对于敏感词过滤,常用的有两个需求。第一是,将敏感词替换掉特定字符。比如“XXX”.第二是,仅仅判断字符串中包含该敏感词。然后,将和这个敏感词有关的消息发送的服务器。比如,谁发的,什么时候发的。这两种需求,该文章中都有讲述。
文章来源:http://bbs.9ria.com/thread-146078-1-1.html

http://bbs.9ria.com/thread-226068-1-1.html

先给出一个demo,可以输入常用的敏感词汇发送:

点击自由播放


对带敏感词的字符串进行过滤时,以字符为单位在树中匹配树节点,如果当前字符有匹配数节点,则下一个字符继续在当前节点的子节点继续匹配,直到全词匹配成功。在实际应用中,扩展了原文查找敏感词的功能。(建议看将军原文在树中储存敏感词)原文中查找敏感词功能的不足(他提供了思路,剩下没完善的可能是他没去做而已):
1. 注册敏感词树时,不支持注册词汇以及词汇的扩展词汇。
比如“大赖”和“大赖拉巴”。在实际应用中,有找出完整的“大赖拉巴”这个敏感词的需求,而不是在“大赖拉巴”只找出“大赖”替换成“**拉巴”。

2. 匹配敏感词成功的条件是匹配到树的根节点
不足2是不足1的引申问题,树的非叶子节点也可以是敏感词的词尾。比如,“大赖”和“大赖拉巴”都是两个敏感词,当敏感词树支持支持注册词汇以及词汇的扩展词汇时,“大赖”的“赖”字是树的非叶子节点,但它是一个敏感词的词尾。

扩展:
于是做相应的扩展,TreeNode添加isEnd属性,表示节点是敏感词词尾。数的叶子节点必然是敏感词词尾,数的非叶子节点可以是敏感词词尾。匹配敏感词成功的条件变为,遍历到敏感词数的节点,该节点是敏感词词尾。 实际应用中,我拿到手的敏感词有4800多个,我先做了去重。去重后,敏感词库的词量不一定是最优的。如果某一个词是敏感词库中其他几个词的拼接,这个时候这个拼接词是多余的。比如,“大赖”和“拉巴”构成“大赖拉巴”,那么“大赖拉巴”是多余的。“大赖拉巴”会增加对“大赖拉+”这类字符串的遍历,总的来说不影响整体的遍历效率,所以我没专门再对敏感词库进行优化,但在写匹配敏感词算法时考虑到了拼接词的存在。

下面用图示说明构建敏感词树。

图示说明扩展词的匹配过程。

源代码下载:http://pan.baidu.com/s/1c0GPeRA