short-video-back/web/PhalApi/public/TrieTree/TrieTree.php

<?php
/**
 *
 * Author: abel
 * Date: 17/4/10
 * Time: 17:26
 */

namespace AbelZhou\Tree;

/**
 * 这是一个支持中文的字典树
 * Class TrieTree
 * @package AbelZhou\Tree
 */
class TrieTree {
    protected $nodeTree = [];

    /**
     * 构造
     * TrieTree constructor.
     */
    public function __construct() {

    }

    /**
     * 从树种摘除一个文本
     * @param $index_str
     */
    public function delete($index_str, $deltree = false, $is_py = false, $chinese = "") {
        $str = trim($index_str);
        $chinese = trim($chinese);
        if ($is_py && empty($chinese)) {
            return false;
        }

        $delstr_arr = $this->convertStrToH($str);
        $len = count($delstr_arr);
        //提取树
        $childTree = &$this->nodeTree;
        $del_index = array();
        //提取树中的相关索引
        for ($i = 0; $i < $len; $i++) {
            $code = $delstr_arr[$i];
            //命中将其纳入索引范围
            if (isset($childTree[$code])) {
                //del tree
                $del_index[$i] = [
                    'code' => $code,
                    'index' => &$childTree[$code]
                ];
                //若检索到最后一个字，检查是否是一个关键词的末梢
                if ($i == ($len - 1) && !$childTree[$code]['end']) {
                    return false;
                }
                $childTree = &$childTree[$code]['child'];
            } else {
                //发现没有命中 删除失败
                return false;
            }
        }
        $idx = $len - 1;
        //删除整棵树
        if ($deltree) {
            //清空子集
            $del_index[$idx]['index']['child'] = array();
        }
        //只有一个字 直接删除
        if ($idx == 0) {
            //如果是拼音 只删除相应的拼音索引
            if ($is_py) {
                //清除单个拼音索引
                if (isset($this->nodeTree[$del_index[$idx]['code']]['chinese_list'])) {
                    $is_del = false;
                    foreach ($this->nodeTree[$del_index[$idx]['code']]['chinese_list'] as $key=>$node) {
                        if ($node['word'] == $chinese){
                            unset($this->nodeTree[$del_index[$idx]['code']]['chinese_list'][$key]);
                            $is_del = true;
                            break;
                        }
                    }
                    if($is_del && 0 != count($this->nodeTree[$del_index[$idx]['code']]['chinese_list'])){
                         return true;
                    }
                    if(!$is_del){
                        return false;
                    }
                    //如果依然存在中文数据 则继续向下跑删除节点
                }
            }else{
                if (count($del_index[$idx]['index']['child']) == 0) {
                    unset($this->nodeTree[$del_index[$idx]['code']]);
                    return true;
                }
            }

        }
        //末梢为关键词结尾，且存在子集 清除结尾标签
        if (count($del_index[$idx]['index']['child']) > 0) {
            $del_index[$idx]['index']['end'] = false;
            $del_index[$idx]['index']['data'] = array();
            unset($del_index[$idx]['index']['full']);
            return true;
        }
//        var_dump($this->nodeTree['e59bbd']);exit();
        //以下为末梢不存在子集的情况
        //倒序检索 子集大于2的 清除child
        for (; $idx >= 0; $idx--) {
            //检测子集 若发现联字情况 检测是否为其他关键词结尾
            if (count($del_index[$idx]['index']['child']) > 0) {
                //遇到结束标记或者count>1的未结束节点直接清空子集跳出
                if ($del_index[$idx]['index']['end'] == true || $del_index[$idx]['index']['child'] > 1) {
                    //清空子集
                    $child_code = $del_index[$idx + 1]['code'];
                    unset($del_index[$idx]['index']['child'][$child_code]);
                    return true;
                }

            }
        }
        return false;
    }

    /**
     * ADD word [UTF8]
     * 增加新特性，在质感末梢增加自定义数组
     * @param $index_str 添加的词
     * @param array $data 添加词的附加属性
     * @return $this
     */
    public function append($index_str, $data = array(), $is_py = false, $chinese = '') {
        $str = trim($index_str);
        $chinese = trim($chinese);
        if ($is_py && empty($chinese)) {
            return false;
        }

        $childTree = &$this->nodeTree;
        $len = strlen($str);
        for ($i = 0; $i < $len; $i++) {
            $ascii_code = ord($str[$i]);
            $code = NULL;
            $word = NULL;
            $is_end = false;

            if (($ascii_code >> 7) == 0) {
                $code = dechex(ord($str[$i]));
                $word = $str[$i];

            } else if (($ascii_code >> 4) == 15) {    //1111 xxxx, 四字节
                if ($i < $len - 3) {
                    $code = dechex(ord($str[$i])) . dechex(ord($str[$i + 1])) . dechex(ord($str[$i + 2])) . dechex(ord($str[$i + 3]));
                    $word = $str[$i] . $str[$i + 1] . $str[$i + 2] . $str[$i + 3];
                    $i += 3;
                }
            } else if (($ascii_code >> 5) == 7) {    //111x xxxx, 三字节
                if ($i < $len - 2) {
                    $code = dechex(ord($str[$i])) . dechex(ord($str[$i + 1])) . dechex(ord($str[$i + 2]));
                    $word = $str[$i] . $str[$i + 1] . $str[$i + 2];
                    $i += 2;
                }
            } else if (($ascii_code >> 6) == 3) {    //11xx xxxx, 2字节
                if ($i < $len - 1) {
                    $code = dechex(ord($str[$i])) . dechex(ord($str[$i + 1]));
                    $word = $str[$i] . $str[$i + 1];
                    $i++;
                }
            }
            if ($i == ($len - 1)) {
                $is_end = true;
                if ($is_py) {
                    $str = $chinese;
                }
            }
            $childTree = &$this->_appendWordToTree($childTree, $code, $word, $is_end, $data, $str, $is_py);
        }
        unset($childTree);
        return $this;
    }

    /**
     * 追加一个字[中英文]到树中
     * @param $tree
     * @param $code
     * @param $word
     * @param bool $end
     * @param array $data
     * @param string $full_str
     * @return mixed
     */
    private function &_appendWordToTree(&$tree, $code, $word, $end = false, $data = array(), $full_str = '', $is_py) {
        if (!isset($tree[$code])) {
            $tree[$code] = array(
                'end' => $end,
                'child' => array(),
                'value' => $word,
            );
        }
        if ($end) {
            $tree[$code]['end'] = true;
            $tree[$code]['is_py'] = $is_py;
            //拼音不需要full 拼音根据读音多样性对应多个词语 重复词语覆盖data
            if ($is_py) {
                $is_change = false;
                if(isset($tree[$code]["chinese_list"]) && count($tree[$code]["chinese_list"])>0) {
                    foreach ($tree[$code]["chinese_list"] as $key => &$node) {
                        if ($node['word'] == $full_str) {
                            $node['data'] = $data;
                            $is_change = true;
                            break;
                        }
                    }
                }
                if(!$is_change){
                    $tree[$code]['chinese_list'][] = ["word" => $full_str, "data" => $data];
                }
            } else {
                $tree[$code]['full'] = $full_str;
                $tree[$code]['data'] = $data;
            }
        }

        return $tree[$code]['child'];
    }

    /**
     * 获得整棵树
     * @return array
     */
    public function getTree() {
        return $this->nodeTree;
    }

    /**
     * 匹配下面的全部词语
     * @param $word
     * @param int $deep 检索深度 检索之后的词语数量可能会大于这个数字
     * @return array|bool
     */
    public function getTreeWord($word, $deep = 0) {
        $search = trim($word);
        if (empty($search)) {
            return false;
        }
        if ($deep === 0) {
            $deep = 999;
        }

        $word_keys = $this->convertStrToH($search);
        $tree = &$this->nodeTree;
        $key_count = count($word_keys);
        $words = [];
        foreach ($word_keys as $key => $val) {
            if (isset($tree[$val])) {
                //检测当前词语是否已命中
                if ($key == $key_count - 1 && $tree[$val]['end'] == true) {
                    if (isset($tree[$val]['chinese_list'])) {
                        $words = array_merge($words, $tree[$val]['chinese_list']);
                    } else {
                        $words[] = ["word" => $tree[$val]['full'], "data" => $tree[$val]['data']];
                    }
                }
                $tree = &$tree[$val]["child"];
            } else {
                //遇到没有命中的返回
//                if ($key == 0) {
                    return [];
//                }
            }
        }
        $this->_getTreeWord($tree, $deep, $words);
        return $words;
    }

    private function _getTreeWord(&$child, $deep, &$words = array()) {
        foreach ($child as $node) {
            if ($node['end'] == true) {
                if (isset($node['chinese_list'])) {
                    $words = array_merge($words, $node['chinese_list']);
                } else {
                    $words[] = ["word" => $node['full'], "data" => $node['data']];
                }
            }
            if (!empty($node['child']) && $deep >= count($words)) {
                $this->_getTreeWord($node['child'], $deep, $words);
            }
        }
    }

    /**
     * overwrite tostring.
     * @return string
     */
    public function __toString() {
        // TODO: Implement __toString() method.
        return json_encode($this->nodeTree);
    }


    /**
     * 检索
     * @param $search
     * @return array|bool
     */
    public function search($search) {
        $search = trim($search);
        if (empty($search)) {
            return false;
        }
        $search_keys = $this->convertStrToH($search);
        //命中集合
        $hit_arr = array();
        $tree = &$this->nodeTree;
        $arr_len = count($search_keys);
        $current_index = 0;
        for ($i = 0; $i < $arr_len; $i++) {
            //若命中了一个索引 则继续向下寻找
            if (isset($tree[$search_keys[$i]])) {
                $node = $tree[$search_keys[$i]];
                if ($node['end']) {
                    //发现结尾 将原词以及自定义属性纳入返回结果集中 3.1 增加词频统计
                    $key = md5($node['full']);
                    if (isset($hit_arr[$key])) {
                        $hit_arr[$key]['count'] += 1;
                    } else {
                        $hit_arr[$key] = array(
                            'word' => $node['full'],
                            'data' => $node['data'],
                            'count' => 1
                        );
                    }
                    if (empty($node['child'])) {
                        //若不存在子集，检索游标还原
                        $i = $current_index;
                        //还原检索集合
                        $tree = &$this->nodeTree;
                        //字码游标下移
                        $current_index++;
                    } else {
                        //存在子集重定义检索tree
                        $tree = &$tree[$search_keys[$i]]['child'];
                    }
                    continue;
                } else {
                    //没发现结尾继续向下检索
                    $tree = &$tree[$search_keys[$i]]['child'];
                    continue;
                }
            } else {
                //还原检索起点
                $i = $current_index;
                //还原tree
                $tree = &$this->nodeTree;
                //字码位移
                $current_index++;
                continue;
            }
        }

        unset($tree, $search_keys);
        return $hit_arr;
    }

    /**
     * 将字符转为16进制标示
     * @param $str
     * @return array
     */
    public function convertStrToH($str) {
        $len = strlen($str);
        $chars = [];
        for ($i = 0; $i < $len; $i++) {
            $ascii_code = ord($str[$i]);
            if (($ascii_code >> 7) == 0) {
                $chars[] = dechex(ord($str[$i]));
            } else if (($ascii_code >> 4) == 15) {    //1111 xxxx, 四字节
                if ($i < $len - 3) {
                    $chars[] = dechex(ord($str[$i])) . dechex(ord($str[$i + 1])) . dechex(ord($str[$i + 2])) . dechex(ord($str[$i + 3]));
                    $i += 3;
                }
            } else if (($ascii_code >> 5) == 7) {    //111x xxxx, 三字节
                if ($i < $len - 2) {
                    $chars[] = dechex(ord($str[$i])) . dechex(ord($str[$i + 1])) . dechex(ord($str[$i + 2]));
                    $i += 2;
                }
            } else if (($ascii_code >> 6) == 3) {    //11xx xxxx, 2字节
                if ($i < $len - 1) {
                    $chars[] = dechex(ord($str[$i])) . dechex(ord($str[$i + 1]));
                    $i++;
                }
            }
        }
        return $chars;
    }
}