PHP基于Trie实现敏感词替换

算法:
0、构建Trie树【疑问,插入树的时候使用指针】
1、遍历目标字符串中的每一个字符,如果字符不存在,继续下一个。
2、如果字符存在,从该字符下一个字符开始遍历,【这里可以记一个步长,设置跳过多少个字符】匹配成功则收集到数组中,否则回到第1步
3、重复1-2

/*
* 敏感词替换为*
*
* 例: 敏感词: [傻叉]
你丫就是傻叉 => 你丫就是**
你丫就是傻的叉 => 你丫就是*的*
*/
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'])) {
                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;
    }

    public function insertKey($keys)
    {
        foreach ($keys as $key) {
            $this->addWords($key);
        }
    }
}

// 敏感词存文件中
// $filter = new SensitiveWordFilter(PATH_APP . '/config/dirty_words.txt');
// $filter->loadData();
// $filter->filter("测试123文本",'*', 2);

// 敏感词不存文件中
$filter = new SensitiveWordFilter(null);
$sensitive_keys = ['大傻', '大傻逼', '傻叉', '白粉', '白粉人'];
$filter->insertKey($sensitive_keys);
$res = $filter->filter('你丫就是大傻叉, 还吸白粉, 是个白粉人', '*', 2);
var_dump($res);

参考: Trie树php实现敏感词过滤

发表评论

电子邮件地址不会被公开。 必填项已用*标注