札记之PHP实现字典树(Trie)

我们每天百度搜索的时候，输入一个字符，搜索框下会展示前缀相似的搜索提示，这个是怎么做到的呢？？？

定义

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计，它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

基本性质

根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。

应用场景

典型应用是用于统计、排序和保存大量的字符串（不仅限于字符串），经常常用于统计、查找搜索引擎中用于分词，词频统计（TF/IDF）,自动补全机制等。

图示

Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起，比如我们有[‘GO’,’PHP’,’PER’,’JAVA’,’JS’,’VUE’];这个字符串集合，可以将其构建成下面这棵Trie树：

札记之PHP实现字典树(Trie)

注：每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（红色节点表示是某个单词的结束字符，但不一定都是叶子节点）。

PHP代码实现

将字符串集合构造成Trie树, 用数组存储每个结点的所有子节点

class TrieNode
{
    public $data;
    // 存储子串
    public $children = [];
    // 是否为某个单词的结束节点
    public $isWord = false;

    public function __construct($data) 
    {
        $this->data = $data;
    }
}

class Trie
{
    public $root = NULL;
    public function __construct() 
    {
        $this->root = new TrieNode('ROOT');
    }

    public function getRoot() 
    {
        return $this->root;
    }

    public function createTrieTree($str) 
    {
        $headNode = $this->getRoot();
        $strLen = strlen($str);

        for ($i = 0; $i < $strLen; $i++) {
            //统一小写处理
            //索引采用ASCII码
            $index = strtolower(ord($str[$i])); 
            $data = strtolower($str[$i]);

            if (empty($headNode->children[$index])) {
                $newNode = new TrieNode($data);
                $headNode->children[$index] = $newNode;
            }
            $headNode = $headNode->children[$index];
        }
        $headNode->isWord = true;
    }

    public function search($str)
    {
        $headNode = $this->getRoot();
        $strLen = strlen($str);

        for ($i = 0; $i < $strLen; $i++) { 
            $index = strtolower(ord($str[$i]));
            $data = strtolower($str[$i]);

            if (empty($headNode->children[$index])) {
                return false;
            }
            $headNode = $headNode->children[$index];
        }

        if ($headNode->isWord == false) {
            return false;
        }
        return true;
    }

    //根据前缀进行搜索
    public function searchStrPrefix($str)
    {
        $headNode = $this->getRoot();
        $strLen = strlen($str);

        for ($i = 0; $i < $strLen; $i++) {
            $index = strtolower(ord($str[$i]));
            $data = strtolower($str[$i]);
            $headNode = $headNode->children[$index];
        }

        return $this->getChildStr($headNode);
    }

    //获取孩子节点
    public function getChildStr($node, $strArr = array(), $str='')
    {
        //单词结尾处
        if ($node->isWord == true) {
            $strArr[] = $str;
        }

        if (empty($node->children)) {
            return $strArr;
        }
        foreach ($node->children as $v) {
            $strArr = $this->getChildStr($v, $strArr, $str. $v->data);
        }

        return $strArr;
    }
}

$trie = new Trie();
$strList = ['GO', 'PHP', 'PER', 'JAVA', 'JS', 'VUE'];

foreach ($strList as $str) {
    $trie->createTrieTree($str);
}

echo "所有节点：\n";
print_r($trie->getRoot());

echo "查询PHP是否存在:\n";
var_dump($trie->search('PHP'));

echo "查询前缀以P开头的串:\n";
print_r($trie->searchStrPrefix('P'));

运行结果