Trieツリーphp敏感語フィルタリングを実現

Last-modified:2019年5月10日15:25:35
参考記事

c++mapを用いてTrieツリー

を実現

キーワードフィルタ拡張は、テキストに敏感語が表示されているかどうかを確認するために使用され、Double-Array Trieツリーに基づいて↑既成のphp拡張を実現し、php 5、php 7

をサポートする.

TrieからDouble Array Trie↑深入浅出解説

接頭辞ツリー一致Double Array Trie

trie_filter拡張+swoole敏感語フィルタリングを実現↑簡単なphp高性能実現方式

背景
プロジェクトではユーザが送信チャットテキストをフィルタリングする必要があるが、敏感語は2 W近くあるため、str_replaceで処理すると爆発する.
インターネットで調べたところ、性能の要求が高くない場合、Trieツリー(辞書ツリー)を自分で構築することができるのが本論文の由来である.
概要
Trieツリーは検索ツリーであり、辞書ツリー、単語検索ツリーとも呼ばれる.
DFA(D e terministic Finite Automaton)は、DFA(D e terministic Finite Automaton)、すなわち
ここではTrieツリーの構造を説明するために図を借ります.
Trieは、有限状態オートマトン、すなわちDFAを決定することと理解される.Trieツリーでは、各ノードはステータスを表し、各エッジは文字を表し、ルートノードからリーフノードまでのエッジは単語を表します.1つの単語を検索するのに最もかかる時間は単語の長さにのみ影響されるため、Trieの検索性能はハッシュアルゴリズムの性能に匹敵するほど高い.
実際に保存されています

abcd
abd
b
bcd
efg
hij

特徴:

すべての語句の共通接頭辞は

のみを格納する.

検出対象テキスト

を1回巡回するだけでよい.

検索の消費時間は、辞書サイズに関係なく、検出されるテキストの長さにのみ関係する

.
きおくこうぞう
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("//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("//", $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("//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)

最適化
辞書ツリーのキャッシュ
原始敏感語ファイルサイズ:194 KB(約20647行)
ディクショナリツリーの生成後のメモリ使用量(約):7 MB
ディクショナリツリーの構築にかかる時間:140 ms+!!!
phpのメモリ消費量は...先に置く
ディクショナリツリーの構築に時間がかかる点は最適化できます:キャッシュ!
phpスクリプトは常駐メモリタイプではないため、新しいリクエストが来るたびに辞書ツリーを構築する必要がある.
生成するディクショナリツリー配列をキャッシュ(memcachedまたはredis)することで、後続のリクエストで毎回キャッシュから読み出すことで、パフォーマンスを大幅に向上させることができる.
テストの結果、辞書ツリーを構築する時間は140 ms+から6 ms未満に減少しました.
注意:

memcachedデフォルトではキャッシュの配列が自動的にシーケンス化され、取り出し時に自動的に逆シーケンス化されます

redisの場合は手動でjsonアクセス

を選択することができる.
上記で生成したTrie配列をシーケンス化した文字の長さ:

serialize: 426KB

json: 241KB

ヒント:したがって、辞書全体が大きすぎると、memcachedに格納ときに単一valueサイズの制限を超えた場合(デフォルトは1 M)、手動jsonシーケンス化配列を考慮して保存することができる.
↑ ...memcacheがvalueに格納されていることを発見したばかりで圧縮機能を提供し、使用を考慮することができます.
常駐サービス
フィルタ敏感ワード機能を1つの常駐メモリのサービスとして独立すると、辞書ツリーを構築するプロセスは1回しか必要とせず、後続の値はフィルタテキストの要求を処理する必要がある.
PHPであればSwooleの利用も考えられます
項目の現在の敏感語の辞書は2 W程度であり、アクセスのボトルネックはここではないため、上記のスキームを一時的に使用する.
abテスト時単一
辞書が百万個に達したら、常駐メモリにするサービスを考えなければならないだろう.
ここではSwoole(swoole_http_server)+trie-filter拡張を用いた辞書レベル200 Wをテストした文章がある.