DFA，全稱 Deterministic Finite Automaton 即確定有窮自動機：從一個狀態(tài)通過一系列的事件轉(zhuǎn)換到另一個狀態(tài)，即 state -> event -> state。

確定：狀態(tài)以及引起狀態(tài)轉(zhuǎn)換的事件都是可確定的，不存在“意外”。
有窮：狀態(tài)以及事件的數(shù)量都是可窮舉的。
計算機操作系統(tǒng)中的進程狀態(tài)與切換可以作為 DFA 算法的一種近似理解。如下圖所示，其中橢圓表示狀態(tài)，狀態(tài)之間的連線表示事件，進程的狀態(tài)以及事件都是可確定的，且都可以窮舉。

<?php
namespace Module\Vendor\File;

use Module\Vendor\BaseVendor;

/**
 * Created by PhpStorm.
 * Auth: aoshi
 * Date: 2021/04/28
 * Time: 13:01
 * 敏感詞過濾器
 * public 方法
 *      checkText：敏感詞匹配檢測
 *      addKeywords:添加敏感詞
 *      clearkeywors:清空敏感詞
 * 描述: 兼容單字符關(guān)鍵詞、重復(fù)關(guān)鍵詞、關(guān)鍵詞包含關(guān)系 例如: 青 青年 中國 中國青年 青年 國青 年  單字符:清 年 重復(fù)關(guān)鍵詞:青年  包含關(guān)系:中國青年  中國  青年
 * 支持無效字符剔除
 * 只要命中過濾詞 每一次命中都會被反饋，反饋格式: 關(guān)鍵詞 開始位置  結(jié)束位置
 */

/**
 *
 *
 *
 * */
class GreenFilterVender extends BaseVendor {

    protected $nodes;       //敏感詞節(jié)點列表
    protected $invalidChar = array(',',';','；','，','-','"','“','、');     //無效字符

    public function __construct()
    {
        parent::__construct();
        $this->_initialize();
    }

    /**
     * 對象關(guān)鍵屬性初始化
     * */
    protected function _initialize() {
        $this->nodes = $this->getKeywords();
    }

    /**
     * 敏感詞匹配檢測 兼容單個詞過濾
     * @param   string      要搜索的關(guān)鍵詞
     * @return  mixed       false:未命中 array:命中的關(guān)鍵詞
     * */
    public function checkText($keyWord) {
        if(!$keyWord) {
            return false;
        }

        //過濾無效字符
        if($this->invalidChar) {
            $keyWord = str_replace($this->invalidChar,'',$keyWord);   
        }
        $charList = $this->get_chars($keyWord);
        $nodes = $this->nodes;
        $charNum = count($charList);
        $nodeKey = 0;
        $nodeLevel = 0;
        $foundList = array();
        for($key = 0;$key < $charNum;$key++) {
            $val = $charList[$key];
            if($nodeKey == 0) {     //命中首個敏感關(guān)鍵詞
                if(in_array($val,array_keys($nodes[$nodeKey]))) {
                    $nodeKey = $nodes[$nodeKey][$val];
                }
            } else {
                if(in_array($val,array_keys($nodes[$nodeKey]))) {
                    if(in_array('',array_keys($nodes[$nodeKey]))) {     //單字符匹配  存在空字符key 就滿足
                        $matchkey = $nodes[$nodeKey][''];
                        $foundList[] = array($matchkey['keyword'],$key-1,$key);
                    }
                    $matchkey = $nodes[$nodeKey][$val];
                    $nodeLevel = $matchkey['level'];     //當前判斷深度 回滾需要
                    if(isset($matchkey['is_end']) && $matchkey['is_end'] == 1) {        //存在末尾結(jié)束符
                        $foundList[] = array($matchkey['keyword'],$key-count($matchkey['keyword']),$key+1);             //映射數(shù)據(jù)結(jié)構(gòu) array(命中次,開始位置,結(jié)束位置)
                        if(isset($matchkey['next_pointer']) && $matchkey['next_pointer']) {     //如果還有多余的字符
                            $nodeKey = $matchkey['next_pointer'];
                        } else {        //命中敏感詞結(jié)束 回退到關(guān)鍵詞開始的第二個位置
                            $key = $key - $nodeLevel;
                            $nodeLevel = 0;
                            $nodeKey = 0;
                        }
                    } else {
                        if(isset($matchkey['next_pointer']) && $matchkey['next_pointer']) {     //沒有結(jié)束符 繼續(xù)匹配
                            $nodeKey = $matchkey['next_pointer'];
                        }
                    }
                } else {
                    if(in_array('',array_keys($nodes[$nodeKey]))) {     //單字符匹配
                        $matchkey = $nodes[$nodeKey][''];
                        $foundList[] = array($matchkey['keyword'],$key-1,$key);
                    }
                    if($nodeLevel) {        //命中首字母 沒有命中全部 回退多減1 (多了一次無效循環(huán))
                        $key = $key - $nodeLevel - 1;
                    }
                    $nodeLevel = 0;
                    $nodeKey = 0;
                }
            }
        }

        return $foundList;
    }

    /**
     * 添加敏感詞 可以考慮儲存到redis
     * @param   array|string    關(guān)鍵詞
     * @return  bool    false:失敗  true:成功
     * */
    public function addKeywords($keyWords) {
        if(!is_array($keyWords)) {
            $keyWords = array($keyWords);
        }
        $nodes = $this->nodes;
//        is_end:終止符號 keyword:關(guān)鍵詞  next_pointer:下一個指針  level:層次
        foreach($keyWords as $keyWord) {
            $charList = $this->get_chars($keyWord);
            $lastKey = count($charList) - 1;
            foreach($charList as $key => $val) {
                if($key == 0) {        //過濾詞的第一個元素 添加一個元素
                    if(!in_array($val,array_keys($nodes[0]))) {
                        $nodeKey = count($nodes);
                        $nodes[$nodeKey] = array();
                        $nodes[0][$val] = $nodeKey;
                        if($key == $lastKey) {      //首字符不存在  單字符過濾
                            if(!isset($nodes[$nodeKey][''])) {      //創(chuàng)建單字符終結(jié)
                                $nodes[$nodeKey]['']['is_end'] = 1;
                                $nodes[$nodeKey]['']['level'] = $key;
                                $nodes[$nodeKey]['']['keyword'] = $keyWord;
                            }
                        }
                    } else {
                        $nodeKey = $nodes[0][$val];
                        if($key == $lastKey) {      //首字符存在 單字符過濾
                            if(!isset($nodes[$nodeKey][''])) {      //創(chuàng)建單字符終結(jié)
                                $nodes[$nodeKey]['']['is_end'] = 1;
                                $nodes[$nodeKey]['']['level'] = $key;
                                $nodes[$nodeKey]['']['keyword'] = $keyWord;
                            }
                        }
                    }
                } else {
                    if(!in_array($val,array_keys($nodes[$nodeKey]))) {      //新增字符
                        if($key == $lastKey) {      //此處為結(jié)束字符 創(chuàng)建結(jié)束標識&關(guān)鍵詞結(jié)束  兼容字符截斷  例如: 積分少了 積分
                            $nodes[$nodeKey][$val]['is_end'] = 1;
                            $nodes[$nodeKey][$val]['level'] = $key;
                            $nodes[$nodeKey][$val]['keyword'] = $keyWord;
                        } else {        //創(chuàng)建下一個節(jié)點 回寫下個節(jié)點的指針標識
                            $newKey = count($nodes);        //下一個字段指針
                            $nodes[$newKey] = array();
                            $nodes[$nodeKey][$val]['next_pointer'] = $newKey;
                            $nodes[$nodeKey][$val]['level'] = $key;
                            $nodeKey = $newKey;         //指針后移
                        }
                    } else {        //字符存在
                        $nodeInfo = $nodes[$nodeKey][$val];
                        if($key == $lastKey) {      //字符被終結(jié)  創(chuàng)建結(jié)束標識&關(guān)鍵詞結(jié)束
                            $nodes[$nodeKey][$val]['is_end'] = 1;
                            $nodes[$nodeKey][$val]['keyword'] = $keyWord;
                        } else {    //字符未被終結(jié)
                            if($nodeInfo['next_pointer']) { //指針后移
                                $nodeKey = $nodeInfo['next_pointer'];
                            } else {        //創(chuàng)建后續(xù)指針
                                $newKey = count($nodes);
                                $nodes[$newKey] = array();
                                $nodes[$nodeKey][$val]['next_pointer'] = $newKey;
                                $nodeKey = $newKey;
                            }
                        }
                    }

                }
            }
        }
        //todo 節(jié)點列表寫入存儲  redis mysql都可以
        $this->nodes = $nodes;

//        $this->_initialize();
    }

    /**
     * 清空敏感詞
     * */
    public function clearkeywors() {
        $nodes = array(array());
        //todo 節(jié)點列表寫入存儲  redis mysql都可以
        $this->nodes = $nodes;
    }

    /**
     * 獲取敏感詞
     * @return  array       關(guān)鍵詞節(jié)點
     * */
    protected function getKeywords() {
        //todo 節(jié)點列表獲取  redis mysql都可以
        $nodes = array();
        if(!$nodes) {
            $nodes = array(array());
        }
        return $nodes;
    }


    /**
     * 將字符串轉(zhuǎn)換成字符數(shù)組
     * @param   string      字符串
     * @return  array
    * */
    protected function get_chars($utf8_str){
        $s = $utf8_str;
        $len = strlen($s);
        if($len == 0) return array();
        $chars = array();
        for($i = 0;$i < $len;$i++){
            $c = $s[$i];
            $n = ord($c);
            if(($n >> 7) == 0){       //0xxx xxxx, asci, single
                $chars[] = $c;
            }
            else if(($n >> 4) == 15){     //1111 xxxx, first in four char
                if($i < $len - 3){
                    $chars[] = $c.$s[$i + 1].$s[$i + 2].$s[$i + 3];
                    $i += 3;
                }
            }
            else if(($n >> 5) == 7){  //111x xxxx, first in three char
                if($i < $len - 2){
                    $chars[] = $c.$s[$i + 1].$s[$i + 2];
                    $i += 2;
                }
            }
            else if(($n >> 6) == 3){  //11xx xxxx, first in two char
                if($i < $len - 1){
                    $chars[] = $c.$s[$i + 1];
                    $i++;
                }
            }
        }
        return $chars;
    }
}