1. 前言

前几天因为项目需要对用户回复内容进行敏感词过滤，所以我就去找了一下解决方案，在此记录下

博客地址

2. 关于解决方案的选择

   刚想到这个，先想到的就是把敏感词放到数组里面，循环遍历，判断文本中是否存在，存在则替换成*号。但是这个方案一进入大脑，转念间就被pass掉，众多的关键词需要去做全文匹配，这样效率低下。
   有此想法的还有正则表达式，这个和上面的方法类似，其效率也有待商榷，所以也直接pass掉。
   我当时想到的比较靠谱的方案是前缀树,把所有词放到前缀树里面进行匹配，这样能有效利用前缀树的特性去做匹配，避免无谓的查找开销，而且可以复用前缀树的相同节点。

3. 最终的解决方案

   我在上述三个方案中决定了之后，又去网上找了一下，大致都是用的dfa算法写的一个树形结构，和前缀树差不多等效.
   dfa算法链接

   大致结构如下(图是别人那拿过来的，借花献佛)
   

每个尾节点和其经过的节点，构成一个完整的关键词。通过字段来标识当前节点是否是尾节点。

{"日" : {"isEnd" : 0,"本" : {"isEnd" : 0,"人" : {"isEnd" : 1},"鬼"  : {"isEnd" : 0,"子" : {"isEnd" : 1}},"男" 	: {"isEnd" : 0,"人" : {"isEnd" : 1}}}},"毛" : {"isEnd" : 0,"泽" : {"isEnd" : 0,"东" : {"isEnd" : 1}}}	  }

上图的关键词存储结构大致如上。

规则如下，敏感词是否存在map中，存在则在该敏感词的map下继续匹配，匹配不上，则跳过，匹配上之后，且isEnd字段为1，则说明敏感词匹配成功。

代码地址
敏感词库我就不放了，自己按需找一个就好了。