README

场景介绍

敏感词过滤是每个有发帖、留言等用户输入的系统都需要构建的一个功能，当用户提交了一句话或是一条留言或是一篇帖子，都需要在后端进行敏感词过滤。当检测到敏感词后，要么提示用户输入包含敏感词要求重新输入，要么把敏感词替换为 “*” 这种特殊字符后再存入存储系统。

关于敏感词库

构建敏感词过滤系统的第一步是需要有一个敏感词库。一般企业都会构建自己的敏感词库，可以在管理后台增删改查这些敏感词。这里只是为了介绍和对比敏感词过滤的几种不同实现，所以敏感词库只是从网上简单 copy 了一份词典，放在了 data 目录下。

几种方案的比较

敏感词过滤主要是定位到输入内容中的包含在敏感词库中的敏感词。所以如何查找敏感词，是关键步骤。

我能想到的大体方案分为以下几种：

方案一

遍历敏感词库，通过正则匹配或字符串匹配，看每个敏感词是否在输入内容中；

优点：原理易懂，无复杂算法，实现简单

缺点：运算量大，效率低，尤其当敏感词库量较大时，这种方案的响应时间会较长

方案二

索引

首先，构建一个字典 dict，以敏感词的首字符为 key ，以相同首字符的敏感词组成的数组（相同长度的敏感词放到同一个子数组中）为value。

比如有这几个敏感词：大坏蛋、大笨蛋、大兵、小老鼠，那么 dict 就是 {"大" :{3: ["大坏蛋'", "大笨蛋"],2:["大兵"]} , "小" :{3:["小老鼠"]}}

接下来逐个字符遍历输入内容，如果在 dict 中能找到这个字符key，取出对应的敏感词数组，按长度倒序逐个匹配输入内容中这个字符后面对应长度的内容，如果匹配到则命中敏感词，跳过对应长度，再去看下一个字符，直到输入内容结尾。

这种方式和查词典很像。

优点：能够缩小待匹配敏感词的范围

缺点：不会命中的敏感词也会进行匹配运算

方案三

分词

分词也分为两种方式：

先基于字典词库分词，把一句话拆分为多个字词，比如：我爱祖国天安门 拆为 我/爱/祖国/天安门 然后逐个字词去匹配看是否在敏感词库中，命中则为敏感词。

这种方式并不好，本身基于词库的分词就慢，而且还需要额外的存储空间存储词库，而且分出来的词还可能错拆，把原本的敏感词给拆开或是把单字敏感词错误组合，导致敏感词的过滤效果差，所以暂时跳过
基于敏感词库分词，如果根据敏感词库分词成功，则命中敏感词。分词算法有：基于字符串匹配的分词法、基于统计的分词法、基于理解的分词法，具体可参考：中文分词的基本原理。

这里采用简单的方式：基于字符串匹配的 正向最大匹配 法。

简单介绍下这种方法：
1. 把敏感词库放入集合中记为 set 并统计敏感词的不同长度，放入有序数组或集合中记为 sort_set
2. 从输入内容开头开始，倒序取 sort_set 中的不同长度，按该长度取输入内容的子字符串，检查子字符串是否在集合 set 中，如果在，则命中敏感词
3. 跳过命中敏感词的长度，再从下一个位置开始，循环执行步骤2，直到输入内容的结尾
优点：多数敏感词都是至少2个字符以上，如果敏感词长度范围集中不分散，比如在1-3个字之间，则就能有效减少运算量，提高过滤速度

缺点：如果敏感词长度分散，会显著增加运算量，降低过滤速度

方案四

DFA算法

这个算法是目前比较流行的一个搜索算法，看了它的实现原理后感觉受益很多。

基本原理是构建一种树形的数据结构，以敏感词首字符为根节点，以与首字符相连的下一个字符为下一级节点，直到最后一个字符为叶子节点，叶子节点上同时标记一个结束状态，这样具有相同首字符的敏感词会存在于同一个树上，数据结构如图：

当逐字符遍历输入内容时，如果匹配到根节点，则接下来去看下个字符是否匹配下个节点，依次进行，如果一直匹配到叶子节点，则命中敏感词。

接下来从下一个位置再重复前面的步骤，直到输入内容的结尾。

优点：通过构造树形数据结构，能够减少存储占用。算法匹配效率高，过滤速度快

缺点：算法实现相对复杂

实测结果

环境：Mac PHP + 虚拟机 Redis

词库：16838 lines

输入：476 字

各个方案耗费的内存和时间：

方案一：811672 bytes 77ms

方案二：810648 bytes 245ms

方案三：820056 bytes 8.36s

方案四：812216 bytes 27ms

总结：考虑到读取redis的影响，结果有一定的偏差，但总体来看，方案四还是优于其他几个方案的

安装和使用

composer require poettian/sensitive-words-filter

require './vendor/autoload.php';

// 第一个参数数组为 Predis 的连接参数，第二个参数对应上面各个不同的方案[simple|index|participle|dfa]
$filter = new Poettian\Filter\Filter([
    'host' => '192.168.10.10',
    'port' => 6379,
    'password' => 'secret',
], 'dfa');

/*
读取词库文件，写入redis，不传则使用data目录下的词库。当词库较大时，此方法存在性能问题，下面会讲述
此方法只需执行一次
*/
$filter->build('/tmp/sensitive_dict');

// 增加敏感词
$filter->add('敏感词一');
$filter->add('敏感词二');
$filter->add('敏感词三');
//...

// 过滤输入内容
echo $filter->run($content);

待优化内容

目前数据的存取都是通过redis。

@tudo 使用redis的pipeline

在构建词库时，现在实现方式是从词库文件一行行读取数据写入redis的，如果词库较大，这一步存在比较严重的性能问题，应该改为批量写入。

在执行过滤动作时，每一步的数据也是从redis读取而来，但是这有个问题就是一次过滤操作可能会多次读取数据，如果考虑并发量，可能会因达到读取速度上限而影响响应时间。看了下，30w的词库占用存储空间貌似是可以接受的，可以考虑一次性读入所有数据，这还有待实验确认。

此外，如果输入内容中在敏感词之间插入了特殊字符，比如 坏&蛋，可能就会跳过过滤，这种情况下，是否考虑先把这些特殊字符筛掉，然后再进行过滤。

poettian / sensitive-words-filter

Maintainers

Details