本人是一枚PHPer，工作期间学习过一些东西，也看过一些书，发现要把知识吸收为自己的能力，还是要多应用、总结。所以，下定决心，要把自己“毕生”所学、所实践写下来。一方面是为了自己提升能力；另一方面也是为做个记录，日后回顾。
本人写的所有东西都将与PHP服务端开发相关，也都将是工作过程中遇到的实际问题，并且在实际项目中所有应用。鉴于能力有限，若有写错之处，请多多包涵，恳请斧正，以免误人。
最近接触到一个用户留言数据处理的接口，其中一部分逻辑是对留言进行敏感词过滤。我看了下之前同事的代码，用的是正则匹配，将目标字符串放入循环对与敏感词依次匹配。好在目前数据量不大，这个任务暂时不存在太大问题，但始终不是长久之计。但是为了产品的长远发展，我想搞点新花样，决定用 DFA 算法重新做一下这个匹配逻辑。
“DFA（Deterministic Finite Automaton）就是确定有穷自动机，它是是通过...” 这种定义我就不写（chao）了，我看着都晕，下面我来讲讲我理解的DFA算法的计算过程（也不知道对不对）。
首先按照一般人的思维逻辑，看一下这个例子。假设给你一个词语 A（“中国”），让你判断是否在字符串 C（“我是中国人”）出现了。一般人的做法是，用眼睛瞄一下 C 里是否有 A 这个字串，然后得出结论 “C中出现了A”。这里的瞄一眼的逻辑过程应该是，先从C的第一个字往后看，直到看到A字符串。具体过程如下：
1、先将 C 的第一个字符 “我” 与 A 的第一个字符 “中” 进行对比，很明显 “我” 和 “中” 不相同
2、再对比 C 的第二个字符 “是” 与 A 的第一个字符，遗憾的是 “是” 和 “中” 也不相同
3、然后对比 C 的第三个字符 “中” 与 A 的第一个字符，可以看到这两个字符匹配上了
4、接着对比 C 的第四个字符 “国” 和 A 的第二个字符 “国”，很幸运又匹配成功
5、这个时候可以看到， A 已经到了最后一个字符了，也就是说在字符串 C 中找到了词语 A
上面的案例中的词语 A 可以看作是敏感词，字符串 C 就是用户输入的待过滤字符串。整个过程可以想象为，有一个指针(pa)指向待过滤字符串，然后依次往字符串尾部移动。同时将指针(pa)指向的字符，与敏感词的第一个字符进行对比。如果成功匹配，那就尝试对比指针(pa)后面（字符串尾部方向）的连续几个字符与敏感词对应的后续几个字符，直到敏感词的最后一个字符。
现实中，敏感词肯定不是一个词语，而是很多个词语。那怎样快速将指针(pa)指向的字符与多个敏感词的第一个字符进行对比呢？在 PHP 里可以将敏感词的第一个字符串放在一个数组里，然后用 isset等函数即可判断出指针指向的字符是否匹配上了其中一个敏感词的某个字符。具体的数据结构，可以看下图，比较好理解。
可以看到，数据结构里，还有一个 'end' 字段，这就是用于判断当前这个字符，是否是某个敏感词的结束位置。
数据结构的构建代码如下
/**
* 添加一个词到 hashmap 里
* @param string $_word 单个敏感词
*/
protected function addToTree($_word) {
$hashMap = &$this->__hashMap;
$wordLen = mb_strlen($_word, 'UTF-8');
for ($i = 0; $i < $wordLen; $i++) {
$char = mb_substr($_word, $i, 1, 'UTF-8');
if (array_key_exists($char, $hashMap)) {
// hashmap 中已经存在
if ($i == ($wordLen - 1)) {
$hashMap[$char]['end'] = 1;
}
} else {
// 不存在于 hashmap 中
if ($i == ($wordLen - 1)) {
// 当前已经到了 敏感词 的最后一个字符了
$hashMap[$char] = [];
$hashMap[$char]['end'] = 1;
} else {
$hashMap[$char] = [];
}
}
$hashMap = &$hashMap[$char];
}
}
数据结构构建好了之后，就可以进行匹配逻辑了。匹配逻辑也比较简单，还是按照上面的例子来推导一下：
1、在 $tree 数组里查询，是否存在键为 C 的第一个字符 “我” .很明显，不存在的。
2、然后查询是否存在 C 的第二个字符 “是” 的键。假装很遗憾，也没有。
3、接着再查询一下 C 的第三个字符 “中” ，array_key_exists('中', $tree)，那么可以看到结果喜人
4、这个时候因为要对比下一个字符了，我们弄两个中间变量 $tmpTree = $tree['中']; $curChar = '国'
5、重复上面的步骤，查询一下 $tmpTree 数组里是否有 '国' 这个键。答案是肯定的，而且 $tmpTree['国']['end'] == 1，说明已经到了敏感词的一个结束位置了
6、至此，成功匹配到一个敏感词，更多的敏感词匹配过程和上面一样
秉着能用就行的态度，我的代码是这样的：
/**
* 不间断（全）匹配
* @param type $_dfaTree DFA敏感词数据
* @param type $_dstStr 目标字符串
* @param type $_matchAll 是否全匹配（false 时匹配成功一个敏感词就会返回结果）
*/
public function unbreakSearch($_dfaTree, $_dstStr, $_matchAll = true) {
// 匹配到的位置集合，[1,3] 表示从下标为 1-3 的匹配到了敏感词
$matchSet = [];
$dstStrLen = mb_strlen($_dstStr, 'UTF-8');
for ($header = 0; $header < $dstStrLen; $header++) {
$firstChar = mb_substr($_dstStr, $header, 1, 'UTF-8');
if (!array_key_exists($firstChar, $_dfaTree)) {
continue;
}
$matchTree = $_dfaTree[$firstChar];
for ($matchPos = $header + 1; true; $matchPos++) {
$curChar = mb_substr($_dstStr, $matchPos, 1, 'UTF-8');
if (!array_key_exists($curChar, $matchTree)) {
// 当前字符没有匹配上，直接结束本轮匹配即可
break;
}
// 当前字符已经匹配了，且这个字符还不是敏感词的结束位置
$matchTree = $matchTree[$curChar];
if (array_key_exists('end', $matchTree)) {
// 已经到达结束位置
$matchSet[] = [$header, $matchPos];
// 一次匹配
if (false === $_matchAll) {
return $matchSet;
}
break;
}
}
}
return $matchSet;
}
至此，核心的东西已经编完了。
里面其实还有很多细节，需要根据具体的业务需求去做权衡。比如要不要把目标字符串里的所有敏感词都筛选出来，还是匹配到一个就完事？要不要处理标点符号？是否要做不连续的匹配，也就是“我是中国的人”能否判定为匹配到敏感词“中国”？
文中的源码，可以在下面的仓库里找到，里面还有一个 demo 和更多注释、说明信息。
源码 git 地址：https://gitee.com/tangqiangjun/mopen/tree/master/dfa