Trie

May 16th, 2020

介绍

Trie树,又称单词查找树、字典树，是一种树形结构，是一种哈希树的变种，是一种用于快速检索的多叉树结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。Trie 的强大之处就在于它的时间复杂度，插入和查询的效率很高，都为O(N)，其中 N 是待插入/查询的字符串的长度，而与 Trie 中保存了多少个元素无关。 Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 Trie树也有它的缺点,Trie树的内存消耗非常大。

三个基本特性

1）根节点不包含字符，除根节点外每一个节点都只包含一个字符。　　

2）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。　

3）每个节点的所有子节点包含的字符都不相同。

用PHP实现一版。


<?php

class TrieNode
{
    // <char, TrieNode>
    public $children = [];
    public $isEnfOfWord = false;
}

class Trie
{
    public $root;

    public function __construct()
    {
        $this->root = new TrieNode;
    }

    public function insert(string $word)
    {
        $current = $this->root;

        $l = strlen($word);
        for ($i = 0; $i < $l; $i++) {
            $c = $word[$i];
            if (empty($current->children[$c])) {
                $current->children[$c] = new TrieNode;
            }
            $current = $current->children[$c];
        }
        $current->isEnfOfWord = true;
    }

    public function search(string $word)
    {
        $current = $this->root;

        $l = strlen($word);
        for ($i = 0; $i < $l; $i++) {
            $c = $word[$i];
            if (empty($current->children[$c])) {
                return false;
            }
            $current = $current->children[$c];
        }

        return ($current && $current->isEnfOfWord);
    }

    private function _remove($root, string $word, int $depth)
    {
        if (!$root) {
            return null;
        }

        // If last character of key is being processed
        if ($depth == strlen($word)) {
            // This node is no more end of word after removal of given key
            if ($root->isEnfOfWord) {
                $root->isEnfOfWord = false;
            }

            // If given is not prefix of any other word
            if ($this->isEmpty($root)) {
                $root = null;
            }
            return $root;
        }

        // If not last character, recur for the child
        // obtained using ASCII value
        $root->children[$word[$depth]] = $this->_remove(
            $root->children[$word[$depth]],
            $word,
            $depth + 1
        );

        // If root does not have any child (its only child got
        // deleted), and it is not end of another word.
        if ($this->isEmpty($root) && $root->isEnfOfWord == false) {
            $root = null;
        }

        return $root;
    }

    public function remove($word)
    {
        return $this->_remove($this->root, $word, 0);
    }

    public function isEmpty($root)
    {
        foreach ($root->children as $child) {
            if (!empty($child)) {
                return false;
            }
        }
        return true;
    }

    public function display()
    {
        $words = [];
        $this->_display($this->root, '', $words);
        foreach ($words as $word) {
            echo $word, PHP_EOL;
        }
    }

    private function _display($root, $prefix, &$words)
    {
        if (empty($root->children)) {
            return;
        }
        $old = $prefix;
        foreach ($root->children as $char => $child) {
            if (empty($child)) {
                continue;
            }
            $prefix = $old . $char;
            if ($child->isEnfOfWord) {
                $words[] = $prefix;
            }
            $this->_display($child, $prefix, $words);
        }
    }

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

    private function _wordCount($root)
    {
        $result = 0;
        if ($root->isEnfOfWord) {
            $result++;
        }
        foreach ($root->children as $char => $child) {
            $result += $this->_wordCount($child);
        }

        return $result;
    }

    public static function main()
    {
        // Input keys (use only 'a' through 'z' and lower case)
        $keys = ["the", "a", "there", "answer", "any", "by", "bye", "their"];
        $output = ["Not present in trie", "Present in trie"];

        $trie = new Trie;
        foreach ($keys as $key) {
            $trie->insert($key);
        }
        $trie->remove('by');

        $trie->display();
        echo $trie->wordCount(), PHP_EOL;

    }
}

Trie::main();

延伸

  • 使用Trie实现一个字典 
    class TrieNode
{
  // <char, TrieNode>
  public $children = [];
  public $isEnfOfWord = false;
  public $meaning = ''; // 字典的释义
}
  • 词频统计 
    class TrieNode
{
  // <char, TrieNode>
  public $children = [];
  public $isEnfOfWord = false;
  public $wordFreq = 0; // 词频统计
}
  • 字典序排序
  • 前缀匹配
  • 最长公共前缀

问题实例

1、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析

提示：用trie树统计每个词出现的次数，时间复杂度是O(nle)（le表示单词的平均长度），然后是找出出现最频繁的前10个词。当然，也可以用堆来实现，时间复杂度是O(nlg10)。所以总的时间复杂度，是O(nle)与O(nlg10)中较大的哪一个。

2、寻找热门查询

原题：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

提示：利用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

参考

  • https://blog.csdn.net/hguisu/article/details/8131559
  • https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/06.09.md

JY