---

字典树（Trie），又称单词查找树，是一种树形结构，用于保存大量的字符串。它的优点是：利用字符串的公共前缀来节约存储空间。它有3个基本性质：

 

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

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

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

 

例子一：

如图，这是一个Trie结构的例子。在这个Trie结构中，保存了t、to、te、tea、ten、i、in、inn这8个字符串，仅占用8个字节（不包括指针占用的空间）。

在用户输入英文单词时，经常发生错误，需要对其进行纠错。假设已经有一个包

含了正确英文单词的词典，请你设计一个拼写纠错

的程序。

（1）请描述你解决这个问题的思路；

（2）请给出主要的处理流程，算法，以及算法的复杂度；

（3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。

 

                                                                                  图 Trie结构

A．思路：

字典以字母键树组织，在用户输入同时匹配

B．流程：

每输入一个字母：

沿字典树向下一层，

a）若可以顺利下行，则继续至结束，给出结果；

b)若该处不能匹配，纠错处理，给出拼写建议，继续至a）；

算法：

1．在字典中查找单词

字典采用27叉树组织，每个节点对应一个字母，查找就是一个字母一个字母匹配。算法时间就是单词的长度k。

2．纠错算法

情况：当输入的最后一个字母不能匹配时就提示出错，简化出错处理，动态提示

可能处理方法：

a)当前字母前缺少了一个字母：搜索树上两层到当前的匹配作为建议；

b)当前字母拼写错误：当前字母的键盘相邻作为提示；（只是简单的描述，可以有更多的）

根据分析字典特征和用户单词已输入部分选择(a),(b)处理

复杂性分析：影响算法的效率主要是字典的实现与纠错处理

 a）字典的实现已有成熟的算法，改进不大，也不会成为瓶颈；

b)纠错策略要简单有效，如前述情况，是线性复杂度；

C．改进

策略选择最是重要，可以采用统计学习的方法改进。

 

例子二：

题目：给你a、b两个文件，各存放50亿条url，每条url各占用64字节，内存限制是4G，让你找出a、b文件共同的url。

分析：

hash(string)-->int的话，50亿条记录4G内存不够使用。利用trie树：

 

typedef struct trienode

{

    int flag; //1:表示叶子结点,是一个字符串,0:表示不是一个字符串

    struct trienode *str[256];

}

 

首先读文件a，一行一个url，读的过程就是建立文件a的trie树的过程。每个url在trie树的叶子结点中的flag=1。

然后读文件b，每读一行url，从trie树的根结点开始往下查询，如果该url的最后一个字符能走到trie树的某条路径的叶子结点，说明该url在文件a中也是存在，则记录下该ur。

如果该url走到某条路径的叶子端点但不是url的最后一个字符,说明该url在文件a中是不存在的，则查询结束，没有必要把该url插入到trie树中。因为trie树公用了大量url的相同前缀，所以实际上用不了4G的内存。

时间复杂度：插入和查询url的时间复杂度都是O(n)。