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