Trie樹 php 實(shí)現(xiàn)敏感詞過濾

王笑朝發(fā)布于2019-07-01 12:46 / 3732人閱讀

摘要：在樹中，每個(gè)節(jié)點(diǎn)表示一個(gè)狀態(tài)，每條邊表示一個(gè)字符，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)經(jīng)過的邊即表示一個(gè)詞條。查找一個(gè)詞條最多耗費(fèi)的時(shí)間只受詞條長度影響，因此的查找性能是很高的，跟哈希算法的性能相當(dāng)。

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

參考文章

c++ 使用map實(shí)現(xiàn)Trie樹

關(guān)鍵詞過濾擴(kuò)展，用于檢查一段文本中是否出現(xiàn)敏感詞，基于Double-Array Trie 樹實(shí)現(xiàn)

↑ 現(xiàn)成的php擴(kuò)展, 同時(shí)支持 php5、php7

從Trie到Double Array Trie

↑ 深入淺出講解

前綴樹匹配 Double Array Trie

trie_filter擴(kuò)展 + swoole 實(shí)現(xiàn)敏感詞過濾

↑ 簡單的php高性能實(shí)現(xiàn)方式

背景

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

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

簡介

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

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

這里借用一張圖來解釋Trie樹的結(jié)構(gòu):

Trie可以理解為確定有限狀態(tài)自動(dòng)機(jī)，即DFA。在Trie樹中，每個(gè)節(jié)點(diǎn)表示一個(gè)狀態(tài)，每條邊表示一個(gè)字符，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)經(jīng)過的邊即表示一個(gè)詞條。查找一個(gè)詞條最多耗費(fèi)的時(shí)間只受詞條長度影響，因此Trie的查找性能是很高的，跟哈希算法的性能相當(dāng)。

上面實(shí)際保存了

abcd
abd
b
bcd
efg
hij

特點(diǎn):

所有詞條的公共前綴只存儲(chǔ)一份

只需遍歷一次待檢測(cè)文本

查找消耗時(shí)間只跟待檢測(cè)文本長度有關(guān), 跟字典大小無關(guān)

存儲(chǔ)結(jié)構(gòu) PHP

在PHP中, 可以很方便地使用數(shù)組來存儲(chǔ)樹形結(jié)構(gòu), 以以下敏感詞字典為例:

大傻子
大傻
傻子

↑ 內(nèi)容純粹是為了舉例...游戲聊天日常屏蔽內(nèi)容

則存儲(chǔ)結(jié)構(gòu)為

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

其他語言

簡單點(diǎn)的可以考慮使用 HashMap 之類的來實(shí)現(xiàn)

或者參考這篇文章 , 使用 Four-Array Trie，Triple-Array Trie和Double-Array Trie 結(jié)構(gòu)來設(shè)計(jì)(名稱與內(nèi)部使用的數(shù)組個(gè)數(shù)有關(guān))

字符串分割

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

有一個(gè)簡單的方法:

$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"
}

匹配規(guī)則需加 u修飾符, /u表示按unicode(utf-8)匹配（主要針對(duì)多字節(jié)比如漢字）, 否則會(huì)無法正常工作, 如下示例 ↓
$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

構(gòu)建:

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

使用:

分割待處理詞句

從Trie樹根節(jié)點(diǎn)開始逐個(gè)匹配

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);
        }
    }

    /**
     * 從文件加載字典數(shù)據(jù), 并構(gòu)建 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個(gè)字節(jié), 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];
        }
        // 標(biāo)記到達(dá)當(dāng)前節(jié)點(diǎn)完整路徑為"敏感詞"
        $curNode["end"]++;
    }

    /**
     * 過濾文本
     * 
     * @param string $str 原始文本
     * @param string $replace 敏感字替換字符
     * @param int    $skipDistance 嚴(yán)格程度: 檢測(cè)時(shí)允許跳過的間隔
     *
     * @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);
    }

    /**
     * 確認(rèn)所給語句是否為敏感詞
     *
     * @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("測(cè)試123文本","*", 2)

優(yōu)化 緩存字典樹

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

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

構(gòu)建字典樹消耗時(shí)間: 140ms+ !!!

php 的內(nèi)存占用這點(diǎn)...先放著

構(gòu)建字典樹消耗時(shí)間這點(diǎn)是可以優(yōu)化的: 緩存!

由于php腳本不是常駐內(nèi)存類型, 每次新的請(qǐng)求到來時(shí)都需要構(gòu)建字典樹.

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

經(jīng)過測(cè)試, 構(gòu)建字典樹的時(shí)間從 140ms+ 降低到 6ms 不到,

注意:

memcached 默認(rèn)會(huì)自動(dòng)序列化緩存的數(shù)組(serialize), 取出時(shí)自動(dòng)反序列化(unserialize)

若是redis, 則需要手動(dòng), 可選擇 json 存取

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

serialize: 426KB

json: 241KB

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

↑  ...剛發(fā)現(xiàn)memcache存入value時(shí)提供壓縮功能, 可以考慮使用

常駐服務(wù)

若是將過濾敏感字功能獨(dú)立為一個(gè)常駐內(nèi)存的服務(wù), 則構(gòu)建字典樹這個(gè)過程只需要1次, 后續(xù)值需要處理過濾文本的請(qǐng)求即可.

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

由于項(xiàng)目當(dāng)前敏感詞詞庫僅2W條左右,  而且訪問瓶頸并不在此, 因此暫時(shí)使用上述方案.ab測(cè)試時(shí)單個(gè)
若是詞庫達(dá)上百萬條, 那估計(jì)得考慮一下弄成常駐內(nèi)存的服務(wù)了
這里有一篇 文章 測(cè)試了使用 Swoole(swoole_http_server) + trie-filter 擴(kuò)展, 詞庫量級(jí)200W

GPU云服務(wù)器云服務(wù)器敏感詞過濾 asp 敏感詞過濾敏感詞 trie樹

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/31442.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

王笑朝

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

#yyds干貨盤點(diǎn)# Python - 第一個(gè)爬蟲

閱讀 3523·2021-11-25 09:43
新的惡意軟件家族使用CLFS日志文件逃避檢測(cè)

閱讀 1281·2021-09-08 09:45
2021-09-06_address_list（通訊錄）

閱讀 2654·2021-09-07 09:59
#八月優(yōu)惠#極光KVM：VPS價(jià)格全部下調(diào)，洛杉磯、香港CN2直連全部5折優(yōu)惠

閱讀 1516·2021-08-09 13:45
使用inline-flex讓容器自適應(yīng)寬度

閱讀 3370·2019-08-30 15:54
CSS 居中

閱讀 706·2019-08-29 18:35
原生js造輪子之模仿JQ的slideDown()與slideUp()

閱讀 523·2019-08-29 17:18
iOS Safari 中點(diǎn)擊事件失效的解決方法

閱讀 1008·2019-08-29 14:10

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

Trie樹 php 實(shí)現(xiàn)敏感詞過濾

相關(guān)文章

敏感詞檢測(cè)算法小結(jié)

**如何快速實(shí)現(xiàn)高并發(fā)短文檢索**

[Leetcode] Word Search 單詞搜索

Spring Boot項(xiàng)目實(shí)踐之問答社區(qū)

發(fā)表評(píng)論

0條評(píng)論

王笑朝

男|高級(jí)講師

TA的文章

#yyds干貨盤點(diǎn)# Python - 第一個(gè)爬蟲

新的惡意軟件家族使用CLFS日志文件逃避檢測(cè)

2021-09-06_address_list（通訊錄）

#八月優(yōu)惠#極光KVM：VPS價(jià)格全部下調(diào)，洛杉磯、香港CN2直連全部5折優(yōu)惠

使用inline-flex讓容器自適應(yīng)寬度

CSS 居中

原生js造輪子之模仿JQ的slideDown()與slideUp()

iOS Safari 中點(diǎn)擊事件失效的解決方法

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

Trie樹 php 實(shí)現(xiàn)敏感詞過濾

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！