标题:字典树


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

 

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

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

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

 

例子一:

如图,这是一个Trie结构的例子。在这个Trie结构中,保存了ttoteteateniininn8个字符串,仅占用8个字节(不包括指针占用的空间)。

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

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

的程序。

1)请描述你解决这个问题的思路;

2)请给出主要的处理流程,算法,以及算法的复杂度;

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

 

                                                                                  图 Trie结构

A.思路:

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

B.流程:

每输入一个字母:

沿字典树向下一层,

a)若可以顺利下行,则继续至结束,给出结果;

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

算法:

1.在字典中查找单词

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

2.纠错算法

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

可能处理方法:

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

b)当前字母拼写错误:当前字母的键盘相邻作为提示;(只是简单的描述,可以有更多的)

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

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

 a)字典的实现已有成熟的算法,改进不大,也不会成为瓶颈;

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

C.改进

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

 

例子二:

题目:给你ab两个文件,各存放50亿条url,每条url各占用64字节,内存限制是4G,让你找出ab文件共同的url

分析:

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

 

typedef struct trienode

{

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

    struct trienode *str[256];

}

 

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

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

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

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


看文字不过瘾?点击我,进入腾讯课堂视频教学
麦洛科菲长期致力于IT安全技术的推广与普及,我们更专业!我们的学员已经广泛就职于BAT360等各大IT互联网公司。详情请参考我们的 业界反馈 《周哥教IT.C语言深学活用》视频

我们的微信公众号,敬请关注