Trie树(字典树)

引出问题

以前面试的时候接触过一道题:如何统计全国有多少个人的名字是重复的?
本质上这是一道词频统计问题.当时我是用了很暴力的方法做的(掩面):直接将数据分块,输入hadoop集群,用map-reduce模型就可以输出结果了.
当然我的方法效率是非常低的,单机可以完成的东西,偏要用集群.事实上用字典树可以很优雅地解决这个问题.

什么是字典树

字典树也是一棵树,可以看图: trie 图示是一颗包含了b,abc,abd,bcd,abcd,efg,hii这6个单词的字典树. 由图可以看出字典树的一些性质:

按照我的理解,字典树中,字符的信息是包含在路径上的,而不是在节点中.网络上的很多图示把字符画在节点中,不是很严谨.

节点中存储的信息根据不同的问题而定.如果是词频统计,那么可以存储该节点表示的字符串的计数值.如果是单词搜索,那么节点中可以存储该节点表示的字符串是否是一个单词.

比如在图示的字典树中查找ab,那么找到b节点后,就可查看b节点的额外信息,了解到该节点表示的字符串ab不是树中的单词.从而判定查找失败:

#define MAX 26
typedef struct TrieNode               //Trie结点声明 
{
    bool isStr;                     //标记该结点处是否构成单词 
    struct TrieNode *next[MAX];      //儿子分支 
}Trie;

字典树的分析

假设单词的平均长度是m.

1.时间分析

字典树插入和查找,最多只需要对比m个字符,因此时间负责度为O(m).
一般来说很少单独删除某个节点(应用场景所限).

2.空间分析

字典树所消耗的空间的非常大的,一颗单词长度为m的树,节点数为:
26^0+26^1+26^2+...+26^m
而每个节点仅存储子分支的地址就需要26个地址,每个地址4字节.共104字节.如果再算上节点中额外的信息,26^m的节点消耗的空间非常大. 抛开应用场景就说"字典树因为不重复存储公共前缀,因此省空间",这是不负责任的.

和hash的对比

考虑到hash表也可以快速地完成字符串的计数,不免需要对比两者的优劣.
假设单词个数为n,单词平均长度为m.则:

字典树的实现

只朴素地进行了实现.

知识延伸

以下引用转载自结构之法 算法之道

参考资料

资料一
资料二