23 Oct 2012

元芳,我是这么理解Trie树的

如图,该trie树有abc、d、da、dda四个字符串,如果是字符串会在节点的尾部进行标记,没有后续字符的分支指向NULL。

Trie

介绍

Trie,读作 /’trai’/,又称前缀树和字典树,是一种用于快速检索的多叉树结构,所以在字符串查找、前缀匹配等中应用很广泛。
Trie可以理解为确定有限状态自动机,即DFA。在Trie树中,每个节点表示一个状态,每条边表示一个字符,从根节点到叶子节点经过的边即表示一个词条。查找一个词条最多耗费的时间只受词条长度影响,因此Trie的查找性能是很高的,跟哈希算法的性能相当。

Trie原理

Trie的核心思想是空间换时间。利用串构成的字典树的公共前缀信息来降低查询时间的开销已达到提高效率的目的。

Trie复杂度

1. 插入、查找的复杂度均为 O(len),len为字符串长度。
2. 空间复杂度是 26^n级别级的,非常庞大(DAT能改善)。

Trie的简单实现(插入、查询、删除)

<?PHP
class Trie {
    /**
     * 词典的存储
     */
    private $_tree = array();

    /**
     * 把关键词加入词典
     * @attr array 关键词的属性
     */
    public function set($word, $attr = array())
    {
        $cur = & $this->_tree;
        for ($i=0, $len=strlen($word); $i<$len; $i++) {
            $ascValue = ord($word[$i]);
            if ( ! isset($cur[$ascValue])) {
                $cur[$ascValue] = array();
            }
            if ($i === $len-1) {
                $data = array();
                array_walk($attr, function ($a) use (& $data) {$data[$a] = 1;});
                $data['text'] = $word;
                $cur[$ascValue]['$'] = $data;
            } else {
                $cur = & $cur[$ascValue];
            }
        }
    }

    /**
     * 从词典中查找关键词
     */
    public function search($word)
    {
        $cur = & $this->_tree;
        $terms = array();
        for ($i=0, $len=strlen($word); $i<$len; $i++) {
            $ascValue = ord($word[$i]);
            if (isset($cur[$ascValue])) {
                if ($i === $len-1) {
                    $terms = $this->_traversal($cur[$ascValue]);
                } else {
                    $cur = & $cur[$ascValue];
                }
            } else break;
        }
        return $terms;
    }

    /**
     * 遍历词典
     */
    private function _traversal( & $tree)
    {
        $terms = array();
        foreach ($tree as $key => $val) {
            if ('$' === $key) {
                $terms[] = $val;
            } else {
                $terms = array_merge($terms, $this->_traversal($val));
            }
        }
        return $terms;
    }

    /**
     * 从词典中删除关键词
     */
    public function del($word)
    {
        $cur = & $this->_tree;
        for ($i=0, $depth=strlen($word); $i<$depth+1; $i++) {
            if (isset($cur['$']) && $word === $cur['$']['text']) {
                unset($cur['$']);
                return true;
            } else {
                if ($i < $depth) {
                    $ascValue = ord($word[$i]);
                    if (isset($cur[$ascValue])) {
                        $cur = & $cur[$ascValue];
                        continue;
                    }
                }
                return false;
            }
        }
    }

    /**
     * 打印字典树
     */
    public function getTree()
    {
        return $this->_tree;
    }
}
$trie = new Trie();
$trie->set('good', array('a'));
$trie->set('goal', array('n'));
$trie->set('go', array('v'));
$trie->set('gloria');
print_r($trie->search('go'));
$trie->del('go');
print_r($trie->search('go'));

总结

Trie的查询效率很高,但由于稀疏的现象严重,空间利用效率很低,但Double-Array Trie会有明显改善。
它一种非常重要的数据结构,在信息检索、字符串匹配等领域有广泛的应用,同时它也是很多算法和复杂数据结构的基础,如后缀树,AC自动机等,因此,掌握Trie树这种数据结构,对于像我这样一名PHPer,显得非常基础且必要。。

#trie