我們公司一直都有的一個敏感詞檢測服務，前一段時間遇到了瓶頸，因為詞庫太多了導致會有一些速度過慢，而且一個正則表達式已經放不下了，需要進行拆分正則才可以。
正好我以前看過有關 dfa 的介紹，但是并沒有深入的進行研究，所以就趁著周末好好的了解一下這個東西。跟 php 的正則進行一下對比，看看速度如何，如果表現較好，說不定還能用得上。
什么是 dfa
通過百度可以知道 dfa 是 確定有窮自動機 的縮寫。 應該還會見到類似下面圖的說明
原諒我實在一些，我這人數學不好不說，貌似看圖能力也不行，這個圖恕我直言我沒看懂。所以關于精準的解釋，請大家去百度或者 google 自行查閱了。
我的理解
說明之前，我們先看看做檢測需要準備的東西
- 一個組織好的關鍵詞樹
- 待檢測的字符串
什么是組織好的關鍵詞樹
我們一批需要檢測詞庫，比如下面這些
日本人，日本鬼子，日本人傻，破解*版
先做個解釋，前三個大家都能看懂，那么 * 是什么，這個是我定義的通配符，代表著 * 可以是 0 - n 個占位符用來替代在關鍵詞中間插入混淆字符。至于可以替換幾個我們可以在代碼中進行定義，需要注意 n 越大，速度就會越慢。
說明完了，來看看構造好的樹是什么一樣的，應該是跟下圖差不多的。
為什么要手動畫一個，因為需要對比，我的理解跟程序是否一致，如果不一致，就要找出程序是不是寫的不對了。那么我們來看看程序生成的是啥樣的。
程序生成的跟圖片一致，到這里還都是正確的。
待檢測的字符串
這個就很容易理解了，就是我們需要檢測的字符串。
為什么要組織好那樣的一棵樹（算法思路）
這塊需要先說一個概念
它是是通過event和當前的state得到下一個state，即event+state=nextstate
這句話，或者類似的話你會在絕大多數的解釋文章里面看到。而我的理解就是，一個字符一個字符的檢測，如果檢測的字符在我們的樹種，就進入命中的樹，看下一個字在不在樹里面，如果持續的命中就持續進入，最后完全命中了，也就是那個字的子樹只有一個元素，并且元素的鍵是 end （這里是在我們的這個例子中，看圖就明白了）。就是完全命中了關鍵詞，就可以記錄命中，或者準備替換了。
這里說一個可以優化的點，看我們的例子有兩個詞 日本人，日本鬼子 這兩個，如果為了快，完全可以去掉第二個詞，質保流一個就行了，這樣當檢測到 end 就可以直接屏蔽或者記錄了，而在我們的例子中，還需要判斷元素數量，不是 1 的情況下還得繼續深入，看看是不是命中了長尾。
這樣的長尾檢測會引發一個問題，那就是 回滾 ，當我們命中了前置的詞，后續的沒有命中的時候就得記錄并且回滾，這個回滾的長度是是多少呢？其實不僅僅是沒有命中長尾的回滾，還有一個 回滾 操作，就是檢測率幾個字之后就沒命中率額，就得回顧，這個回滾的長度是， 已檢測字符長度 - 1 的長度 。那么沒有命中長尾的長度我們就知道了， 已檢測字符長度 - 上次命中的長度 就可以了。
下面我們來看看代碼實現。
// 通配符的數量
$maskMin = 0;
$maskMax = 3;
// 關鍵詞詞典字符串，這個部分的處理自己可以替換
$dict = "傻瓜";
$checkDfaTree = [];
$dictArr = explode(',', $dict);
// 重組一下帶有 * 通配符的數組
$fullDictArr = [];
foreach ($dictArr as $word) {
if (mb_strpos($word, '*') !== false) {
// 帶有通配符就把通配符去掉
for ($maskIndex = $maskMin; $maskIndex <= $maskMax; $maskIndex++) {
$maskString = str_pad('', $maskIndex, '*');
$inputWord = str_replace('*', $maskString, $word);
$fullDictArr[] = $inputWord;
}
} else {
$fullDictArr[] = $word;
}
}
foreach ($fullDictArr as $word) {
// 每次開始新詞都要回到樹的根部
$treeStart = &$checkDfaTree;
$wordLen = mb_strlen($word);
for ($i = 0; $i < $wordLen; $i++) {
$char = mb_substr($word, $i, 1);
$treeStart[$char] = isset($treeStart[$char]) ? $treeStart[$char] : [];
if ($i + 1 == $wordLen) {
// 如果已經是次的結尾了就設置null
$treeStart[$char]['end'] = true;
}
// 移動指針到下一個
$treeStart = &$treeStart[$char];
}
}
// 遍歷str
$start = microtime(true);
$checkMessageLen = mb_strlen($checkMessage);
$wordArr = [];
$checkTreeStart = &$checkDfaTree;
$hasPrefixLength = 0;
$targetWord = '';
for ($i = 0; $i < $checkMessageLen; $i++) {
// 獲取一個字符
$char = mb_substr($checkMessage, $i, 1);
if (isset($checkTreeStart[$char])) {
// 如果有這個字就進入子樹里面
if (isset($checkTreeStart[$char]['end']) && $checkTreeStart[$char]['end'] === true) {
// 如果包含這個標識，就記錄標識
$hasPrefixLength = mb_strlen($targetWord);
}
$checkTreeStart = &$checkTreeStart[$char];
$targetWord .= $char;
} else if (isset($checkTreeStart['*'])) {
// 如果有通配符就進入子樹
$checkTreeStart = &$checkTreeStart['*'];
$targetWord .= $char;
} else {
if ($hasPrefixLength) {
$wordArr[] = mb_substr($targetWord, 0, $hasPrefixLength + 1);
// 回滾
$i -= mb_strlen($targetWord) - $hasPrefixLength;
} else {
// 回滾
$i -= mb_strlen($targetWord);
}
// 回到頭部
$checkTreeStart = &$checkDfaTree;
$targetWord = '';
$hasPrefixLength = 0;
}
if (count($checkTreeStart) == 1 && isset($checkTreeStart['end']) && $checkTreeStart['end'] === true) {
// 子樹只有一個并且是end 就說明是命中了
// 賦值
$wordArr[] = $targetWord;
// 清空
$targetWord = '';
// 回到頭部
$checkTreeStart = &$checkDfaTree;
$hasPrefixLength = 0;
}
}
var_dump($wordArr);
echo "<br /> useTime:" . (microtime(true) - $start) * 1000;
下面這個就是匹配加測試了，目前我能想到的都測試通過了，如果有問題，可以回復我。
結論
目前來看，效率是比正則要好一些，命中的情況下速度差不多，沒命中的情況下表現要優于正則
