美文网首页
敏感词检测 评论敏感词过滤 DFA算法 AC自动机

敏感词检测 评论敏感词过滤 DFA算法 AC自动机

作者: aoshi | 来源:发表于2021-04-28 14:24 被阅读0次

DFA,全称 Deterministic Finite Automaton 即确定有穷自动机:从一个状态通过一系列的事件转换到另一个状态,即 state -> event -> state。

确定:状态以及引起状态转换的事件都是可确定的,不存在“意外”。
有穷:状态以及事件的数量都是可穷举的。
计算机操作系统中的进程状态与切换可以作为 DFA 算法的一种近似理解。如下图所示,其中椭圆表示状态,状态之间的连线表示事件,进程的状态以及事件都是可确定的,且都可以穷举。

<?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:清空敏感词
 * 描述: 兼容单字符关键词、重复关键词、关键词包含关系 例如: 青 青年 中国 中国青年 青年 国青 年  单字符:清 年 重复关键词:青年  包含关系:中国青年  中国  青年
 * 支持无效字符剔除
 * 只要命中过滤词 每一次命中都会被反馈,反馈格式: 关键词 开始位置  结束位置
 */

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

    protected $nodes;       //敏感词节点列表
    protected $invalidChar = array(',',';',';',',','-','"','“','、');     //无效字符

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

    /**
     * 对象关键属性初始化
     * */
    protected function _initialize() {
        $this->nodes = $this->getKeywords();
    }

    /**
     * 敏感词匹配检测 兼容单个词过滤
     * @param   string      要搜索的关键词
     * @return  mixed       false:未命中 array:命中的关键词
     * */
    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) {     //命中首个敏感关键词
                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) {        //存在末尾结束符
                        $foundList[] = array($matchkey['keyword'],$key-count($matchkey['keyword']),$key+1);             //映射数据结构 array(命中次,开始位置,结束位置)
                        if(isset($matchkey['next_pointer']) && $matchkey['next_pointer']) {     //如果还有多余的字符
                            $nodeKey = $matchkey['next_pointer'];
                        } else {        //命中敏感词结束 回退到关键词开始的第二个位置
                            $key = $key - $nodeLevel;
                            $nodeLevel = 0;
                            $nodeKey = 0;
                        }
                    } else {
                        if(isset($matchkey['next_pointer']) && $matchkey['next_pointer']) {     //没有结束符 继续匹配
                            $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 (多了一次无效循环)
                        $key = $key - $nodeLevel - 1;
                    }
                    $nodeLevel = 0;
                    $nodeKey = 0;
                }
            }
        }

        return $foundList;
    }

    /**
     * 添加敏感词 可以考虑储存到redis
     * @param   array|string    关键词
     * @return  bool    false:失败  true:成功
     * */
    public function addKeywords($keyWords) {
        if(!is_array($keyWords)) {
            $keyWords = array($keyWords);
        }
        $nodes = $this->nodes;
//        is_end:终止符号 keyword:关键词  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][''])) {      //创建单字符终结
                                $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][''])) {      //创建单字符终结
                                $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) {      //此处为结束字符 创建结束标识&关键词结束  兼容字符截断  例如: 积分少了 积分
                            $nodes[$nodeKey][$val]['is_end'] = 1;
                            $nodes[$nodeKey][$val]['level'] = $key;
                            $nodes[$nodeKey][$val]['keyword'] = $keyWord;
                        } else {        //创建下一个节点 回写下个节点的指针标识
                            $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) {      //字符被终结  创建结束标识&关键词结束
                            $nodes[$nodeKey][$val]['is_end'] = 1;
                            $nodes[$nodeKey][$val]['keyword'] = $keyWord;
                        } else {    //字符未被终结
                            if($nodeInfo['next_pointer']) { //指针后移
                                $nodeKey = $nodeInfo['next_pointer'];
                            } else {        //创建后续指针
                                $newKey = count($nodes);
                                $nodes[$newKey] = array();
                                $nodes[$nodeKey][$val]['next_pointer'] = $newKey;
                                $nodeKey = $newKey;
                            }
                        }
                    }

                }
            }
        }
        //todo 节点列表写入存储  redis mysql都可以
        $this->nodes = $nodes;

//        $this->_initialize();
    }

    /**
     * 清空敏感词
     * */
    public function clearkeywors() {
        $nodes = array(array());
        //todo 节点列表写入存储  redis mysql都可以
        $this->nodes = $nodes;
    }

    /**
     * 获取敏感词
     * @return  array       关键词节点
     * */
    protected function getKeywords() {
        //todo 节点列表获取  redis mysql都可以
        $nodes = array();
        if(!$nodes) {
            $nodes = array(array());
        }
        return $nodes;
    }


    /**
     * 将字符串转换成字符数组
     * @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;
    }
}

相关文章

网友评论

      本文标题:敏感词检测 评论敏感词过滤 DFA算法 AC自动机

      本文链接:https://www.haomeiwen.com/subject/byevrltx.html