背景
之前做的聊天项目中涉及敏感词过滤,当时只是采用了简单的字符串匹配,敏感词量还不大,性能还能接受。
最近刚好有时间,于是就研究了trie tree来实现敏感词过滤。
资料
trie tree的原理网上很多。
找到了darts的c/c++版
使用
主要涉及几个接口的使用:
build : 传入敏感词数组,构建trie tree
exactMatchSearch : 查找完全匹配的敏感词
commonPrefixSearch : 前缀匹配。找到已字符串开头开始匹配的敏感词,并返回匹配的数组
性能比较
主要是和之前普通的字符串匹配进行性能比较,已10000个敏感词做测试,差距在10000倍以上。理论上性能差距量级 = 敏感词数量。
测试代码
1 | // redistest.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 |