Trie樹 php 實現敏感詞過濾

王笑朝發布于2019-07-01 12:46 / 3723人閱讀

摘要：在樹中，每個節點表示一個狀態，每條邊表示一個字符，從根節點到葉子節點經過的邊即表示一個詞條。查找一個詞條最多耗費的時間只受詞條長度影響，因此的查找性能是很高的，跟哈希算法的性能相當。

Last-Modified: 2019年5月10日15:25:35

參考文章

c++ 使用map實現Trie樹

關鍵詞過濾擴展，用于檢查一段文本中是否出現敏感詞，基于Double-Array Trie 樹實現

↑ 現成的php擴展, 同時支持 php5、php7

從Trie到Double Array Trie

↑ 深入淺出講解

前綴樹匹配 Double Array Trie

trie_filter擴展 + swoole 實現敏感詞過濾

↑ 簡單的php高性能實現方式

背景

項目中需要過濾用戶發送的聊天文本, 由于敏感詞有將近2W條, 如果用 str_replace 來處理會炸掉的.

網上了解了一下, 在性能要求不高的情況下, 可以自行構造 Trie樹(字典樹), 這就是本文的由來.

簡介

Trie樹是一種搜索樹, 也叫字典樹、單詞查找樹.

DFA可以理解為DFA(Deterministic Finite Automaton), 即

這里借用一張圖來解釋Trie樹的結構:

Trie可以理解為確定有限狀態自動機，即DFA。在Trie樹中，每個節點表示一個狀態，每條邊表示一個字符，從根節點到葉子節點經過的邊即表示一個詞條。查找一個詞條最多耗費的時間只受詞條長度影響，因此Trie的查找性能是很高的，跟哈希算法的性能相當。

上面實際保存了

abcd
abd
b
bcd
efg
hij

特點:

所有詞條的公共前綴只存儲一份

只需遍歷一次待檢測文本

查找消耗時間只跟待檢測文本長度有關, 跟字典大小無關

存儲結構 PHP

在PHP中, 可以很方便地使用數組來存儲樹形結構, 以以下敏感詞字典為例:

大傻子
大傻
傻子

↑ 內容純粹是為了舉例...游戲聊天日常屏蔽內容

則存儲結構為

{
    "大": {
        "傻": {
            "end": true
            "子": {
                "end": true
            }
        }
    },
    "傻": {
        "子": {
            "end": true
        },
    }
}

其他語言

簡單點的可以考慮使用 HashMap 之類的來實現

或者參考這篇文章 , 使用 Four-Array Trie，Triple-Array Trie和Double-Array Trie 結構來設計(名稱與內部使用的數組個數有關)

字符串分割

無論是在構造字典樹或過濾敏感文本時, 都需要將其分割, 需要考慮到unicode字符

有一個簡單的方法:

$str = "a笨蛋123";    // 待分割的文本
$arr = preg_split("http://u", $str, -1, PREG_SPLIT_NO_EMPTY);    // 分割后的文本
// 輸出
array(6) {
  [0]=>
  string(1) "a"
  [1]=>
  string(3) "笨"
  [2]=>
  string(3) "蛋"
  [3]=>
  string(1) "1"
  [4]=>
  string(1) "2"
  [5]=>
  string(1) "3"
}

匹配規則需加 u修飾符, /u表示按unicode(utf-8)匹配（主要針對多字節比如漢字）, 否則會無法正常工作, 如下示例 ↓
$str = "a笨蛋123";    // 待分割的文本
$arr = preg_split("http://", $str, -1, PREG_SPLIT_NO_EMPTY);    // 分割后的文本
// array(10) {
  [0]=>
  string(1) "a"
  [1]=>
  string(1) "?"
  [2]=>
  string(1) "?"
  [3]=>
  string(1) "?"
  [4]=>
  string(1) "?"
  [5]=>
  string(1) "?"
  [6]=>
  string(1) "?"
  [7]=>
  string(1) "1"
  [8]=>
  string(1) "2"
  [9]=>
  string(1) "3"
}

示例代碼 php

構建:

1. 分割敏感詞
    2. 逐個將分割后的次添加到樹中

使用:

分割待處理詞句

從Trie樹根節點開始逐個匹配

class SensitiveWordFilter
{
    protected $dict;
    protected $dictFile;

    /**
     * @param string $dictFile 字典文件路徑, 每行一句
     */
    public function __construct($dictFile)
    {
        $this->dictFile = $dictFile;
        $this->dict = [];
    }

    public function loadData($cache = true)
    {
        $memcache = new Memcache();
        $memcache->pconnect("127.0.0.1", 11212);
        $cacheKey = __CLASS__ . "_" . md5($this->dictFile);
        if ($cache && false !== ($this->dict = $memcache->get($cacheKey))) {
             return;
        }

        $this->loadDataFromFile();

        if ($cache) {
            $memcache->set($cacheKey, $this->dict, null, 3600);
        }
    }

    /**
     * 從文件加載字典數據, 并構建 trie 樹
     */
    public function loadDataFromFile()
    {
        $file = $this->dictFile;
        if (!file_exists($file)) {
            throw new InvalidArgumentException("字典文件不存在");
        }

        $handle = @fopen($file, "r");
        if (!is_resource($handle)) {
            throw new RuntimeException("字典文件無法打開");
        }

        while (!feof($handle)) {
            $line = fgets($handle);
            if (empty($line)) {
                continue;
            }

            $this->addWords(trim($line));
        }

        fclose($handle);
    }

    /**
     * 分割文本(注意ascii占1個字節, unicode...)
     *
     * @param string $str
     *
     * @return string[]
     */
    protected function splitStr($str)
    {
        return preg_split("http://u", $str, -1, PREG_SPLIT_NO_EMPTY);
    }

    /**
     * 往dict樹中添加語句
     *
     * @param $wordArr
     */
    protected function addWords($words)
    {
        $wordArr = $this->splitStr($words);
        $curNode = &$this->dict;
        foreach ($wordArr as $char) {
            if (!isset($curNode)) {
                $curNode[$char] = [];
            }

            $curNode = &$curNode[$char];
        }
        // 標記到達當前節點完整路徑為"敏感詞"
        $curNode["end"]++;
    }

    /**
     * 過濾文本
     * 
     * @param string $str 原始文本
     * @param string $replace 敏感字替換字符
     * @param int    $skipDistance 嚴格程度: 檢測時允許跳過的間隔
     *
     * @return string 返回過濾后的文本
     */
    public function filter($str, $replace = "*", $skipDistance = 0)
    {
        $maxDistance = max($skipDistance, 0) + 1;
        $strArr = $this->splitStr($str);
        $length = count($strArr);
        for ($i = 0; $i < $length; $i++) {
            $char = $strArr[$i];

            if (!isset($this->dict[$char])) {
                continue;
            }

            $curNode = &$this->dict[$char];
            $dist = 0;
            $matchIndex = [$i];
            for ($j = $i + 1; $j < $length && $dist < $maxDistance; $j++) {
                if (!isset($curNode[$strArr[$j]])) {
                    $dist ++;
                    continue;
                }

                $matchIndex[] = $j;
                $curNode = &$curNode[$strArr[$j]];
            }

            // 匹配
            if (isset($curNode["end"])) {
//                Log::Write("match ");
                foreach ($matchIndex as $index) {
                    $strArr[$index] = $replace;
                }
                $i = max($matchIndex);
            }
        }
        return implode("", $strArr);
    }

    /**
     * 確認所給語句是否為敏感詞
     *
     * @param $strArr
     *
     * @return bool|mixed
     */
    public function isMatch($strArr)
    {
        $strArr = is_array($strArr) ? $strArr : $this->splitStr($strArr);
        $curNode = &$this->dict;
        foreach ($strArr as $char) {
            if (!isset($curNode[$char])) {
                return false;
            }
        }
//        return $curNode["end"] ?? false;  // php 7
        return isset($curNode["end"]) ? $curNode["end"] : false;
    }
}

字典文件示例:

敏感詞1
敏感詞2
敏感詞3
...

使用示例:

$filter = new SensitiveWordFilter(PATH_APP . "/config/dirty_words.txt");
$filter->loadData()
$filter->filter("測試123文本","*", 2)

優化 緩存字典樹

原始敏感詞文件大小: 194KB(約20647行)

生成字典樹后占用內存(約): 7MB

構建字典樹消耗時間: 140ms+ !!!

php 的內存占用這點...先放著

構建字典樹消耗時間這點是可以優化的: 緩存!

由于php腳本不是常駐內存類型, 每次新的請求到來時都需要構建字典樹.

我們通過將生成好的字典樹數組緩存(memcached 或 redis), 在后續請求中每次都從緩存中讀取, 可以大大提高性能.

經過測試, 構建字典樹的時間從 140ms+ 降低到 6ms 不到,

注意:

memcached 默認會自動序列化緩存的數組(serialize), 取出時自動反序列化(unserialize)

若是redis, 則需要手動, 可選擇 json 存取

序列化上述生成的Trie數組后的字符長度:

serialize: 426KB

json: 241KB

提示: 因此若整個字典過大, 導致存入memcached時超出單個value大小限制時(默認是1M), 可以考慮手動 json 序列化數組再保存.

↑  ...剛發現memcache存入value時提供壓縮功能, 可以考慮使用

常駐服務

若是將過濾敏感字功能獨立為一個常駐內存的服務, 則構建字典樹這個過程只需要1次, 后續值需要處理過濾文本的請求即可.

如果是PHP, 可以考慮使用 Swoole

由于項目當前敏感詞詞庫僅2W條左右, 而且訪問瓶頸并不在此, 因此暫時使用上述方案.

ab測試時單個

若是詞庫達上百萬條, 那估計得考慮一下弄成常駐內存的服務了

這里有一篇文章測試了使用 Swoole(swoole_http_server) + trie-filter 擴展, 詞庫量級200W

云服務器 GPU云服務器敏感詞過濾 asp 敏感詞過濾敏感詞 trie樹

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/31442.html

敏感詞檢測算法小結

摘要：序本文簡單介紹下敏感詞或者臟詞檢測算法。經典算法經典的算法由三部分構成，表，表和表，共包含四種具體的算法，分別是計算三張查找表的算法以及算法本身。表是由模式集合中的所有模式構成的狀態轉移自動機。序本文簡單介紹下敏感詞或者臟詞檢測算法。經典AC算法經典的AC算法由三部分構成，goto表，fail表和output表，共包含四種具體的算法，分別是計算三張查找表的算法以及AC算法本身。...

劉厚水 2019-08-16 10:41 評論0 收藏0
如何快速實現高并發短文檢索

摘要：問龍哥，還有什么更好，更輕量級的方案么龍哥用樹，數據會膨脹文檔數標題長度這么多，標題越長，文檔數越多，內存占用越大。一、需求緣起某并發量很大，數據量適中的業務線需要實現一個標題檢索的功能：（1）并發量較大，每秒20w次（2）數據量適中，大概200w數據（3）是否需要分詞：是（4）數據是否實時更新：否二、常見潛在解決方案及優劣（1）數據庫搜索法具體方法：將標題數據存放在數據庫中，使用...

URLOS 2019-06-28 13:51 評論0 收藏0
[Leetcode] Word Search 單詞搜索

摘要：我們可以先用待查單詞建立一個字典樹，這樣我們在從矩陣中某個點開始深度優先搜索時，可以直接用字典樹判斷當前組成的字符串是否是某個單詞的前綴。字典樹同樣也提供接口，所以同樣可以用于判斷是否已經搜索到這個詞了。 Word Search I 更新的思路與解法請訪問：https://yanjia.me/zh/2018/11/... Given a 2D board and a word, f...

objc94 2019-08-14 12:25 評論0 收藏0
Spring Boot項目實踐之問答社區

摘要：異步事件處理本項目涉及到多種異步事件的處理。即是的粉絲，是的關注對象。模式定義優缺點推事件觸發后廣播給所有粉絲。具體來說，推模式就是事件觸發后產生，觸發事件的用戶下所有粉絲的實現中都存入該的。項目源代碼已托管在 Github，歡迎 Star、Fork。 Q & A 問答社區 QA 是一個基于 B/S 架構而設計開發的社區網站。 showImg(https://segmentfault...

binaryTree 2019-08-16 12:31 評論0 收藏0