爭取能讓大家都能看懂的 DFA 算法

我們公司一直都有的一個敏感詞檢測服務,前一段時間遇到了瓶頸,因為詞庫太多了導致會有一些速度過慢,而且一個正則表達式已經放不下了,需要進行拆分正則才可以。

正好我以前看過有關 dfa 的介紹,但是並沒有深入的進行研究,所以就趁著週末好好的瞭解一下這個東西。跟 php 的正則進行一下對比,看看速度如何,如果表現較好,說不定還能用得上。

什麼是 dfa

通過百度可以知道 dfa 是 確定有窮自動機 的縮寫。 應該還會見到類似下面圖的說明

爭取能讓大家都能看懂的 DFA 算法

原諒我實在一些,我這人數學不好不說,貌似看圖能力也不行,這個圖恕我直言我沒看懂。所以關於精準的解釋,請大家去百度或者 google 自行查閱了。

我的理解

說明之前,我們先看看做檢測需要準備的東西

  • 一個組織好的關鍵詞樹
  • 待檢測的字符串

什麼是組織好的關鍵詞樹

我們一批需要檢測詞庫,比如下面這些

日本人,日本鬼子,日本人傻,破解*版

先做個解釋,前三個大家都能看懂,那麼 * 是什麼,這個是我定義的通配符,代表著 * 可以是 0 - n 個佔位符用來替代在關鍵詞中間插入混淆字符。至於可以替換幾個我們可以在代碼中進行定義,需要注意 n 越大,速度就會越慢。

說明完了,來看看構造好的樹是什麼一樣的,應該是跟下圖差不多的。

爭取能讓大家都能看懂的 DFA 算法

為什麼要手動畫一個,因為需要對比,我的理解跟程序是否一致,如果不一致,就要找出程序是不是寫的不對了。那麼我們來看看程序生成的是啥樣的。

爭取能讓大家都能看懂的 DFA 算法

程序生成的跟圖片一致,到這裡還都是正確的。

待檢測的字符串

這個就很容易理解了,就是我們需要檢測的字符串。

為什麼要組織好那樣的一棵樹(算法思路)

這塊需要先說一個概念

它是是通過event和當前的state得到下一個state,即event+state=nextstate

這句話,或者類似的話你會在絕大多數的解釋文章裡面看到。而我的理解就是,一個字符一個字符的檢測,如果檢測的字符在我們的樹種,就進入命中的樹,看下一個字在不在樹裡面,如果持續的命中就持續進入,最後完全命中了,也就是那個字的子樹只有一個元素,並且元素的鍵是 end (這裡是在我們的這個例子中,看圖就明白了)。就是完全命中了關鍵詞,就可以記錄命中,或者準備替換了。

這裡說一個可以優化的點,看我們的例子有兩個詞 日本人,日本鬼子 這兩個,如果為了快,完全可以去掉第二個詞,質保流一個就行了,這樣當檢測到 end 就可以直接屏蔽或者記錄了,而在我們的例子中,還需要判斷元素數量,不是 1 的情況下還得繼續深入,看看是不是命中了長尾。

這樣的長尾檢測會引發一個問題,那就是 回滾 ,當我們命中了前置的詞,後續的沒有命中的時候就得記錄並且回滾,這個回滾的長度是是多少呢?其實不僅僅是沒有命中長尾的回滾,還有一個 回滾 操作,就是檢測率幾個字之後就沒命中率額,就得回顧,這個回滾的長度是, 已檢測字符長度 - 1 的長度 。那麼沒有命中長尾的長度我們就知道了, 已檢測字符長度 - 上次命中的長度 就可以了。

下面我們來看看代碼實現。

<code>// 通配符的數量
$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];
}
}/<code>
<code>// 遍歷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 "
useTime:" . (microtime(true) - $start) * 1000;/<code>

下面這個就是匹配加測試了,目前我能想到的都測試通過了,如果有問題,可以回覆我。

結論

目前來看,效率是比正則要好一些,命中的情況下速度差不多,沒命中的情況下表現要優於正則。


分享到:


相關文章: