分类: 2009 November 27

使用字典树–Using Tries

原文:Using Tries 作者:luison9999

翻译 Arthur1989@sysu

Introduction

在文本中索引和搜索一段字符有很多种算法和数据结构,某些被包含在标准库中,但有些并没有.数据结构trie就是这么一个未被包含在标准库中的很好的例子.

以word表示一个字符串,dictionary表示word的集合.在已经有了一个dictionary的情况下,当我们想知道一个特定的word是否在dictionary中时,trie数据结构可以帮上大忙.但是,也许你会问,”既然set和哈希表已经能够实现这一查询了,为什么还需要trie呢?”下面是两个主要的理由:

  • trie插入和查询字符串的时间复杂度是O(L)(L表示一个特定字符串的长度).这比起set可要快上不少,即便和哈希表比较,trie还是稍微更快的.
  • set和哈希表只支持在dictionary中查找到希望查询的字符串完全匹配的字符串;而trie允许我们容错查找,比如说,字符不一致,共同前缀,字符丢失等等.

trie不仅在TopCoder类型的比赛中很实用,它在软件项目中也有相当多的实际应用.举个例子,考虑一下网络浏览器.你知道浏览器是如何根据已输入的文字自动填充或者给出给出候选输入的吗?是的,通过trie你可以轻易地实现这个功能.你知道拼写检查器是怎么知道你所输入的每一个单词是否在词典中的吗?答案还是一样的,通过trie.你同样可以通过trie,判断输入的单词是否在词典中存在,如果不存在的话给出一个改正的建议单词.

What’s a Tree?

可能你早就知道trie的强大了,但是也许你并不清楚trie究竟是什么,它为什么被命名为trie呢?其实,trie的名字是”retrieval”的中缀,因为trie可以通过前缀在词典中搜索可能的字符串.trie数据结构主要基于以下的几点想法:

  • trie是一棵树,每一结点是一个字母或者是一个前缀.
  • 树根表示一个空的字符串(“”),根的直接后继结点表示长度为1的前缀,深度为2的结点表示长度为2的前缀,深度为3的结点表示长度为3的前缀,以此类推.换句话说,深度为k的结点表示长度为k的后缀.
  • 以v和w表示trie树的两个结点,v为w的直接前驱,那么v的前缀必须是w的前缀.

下图表示了一棵包含单词”tree”,”trie”,”algo”,”assoc”,”all”,和”also”的trie树.

alg_tries

注意,trie树的每一结点并不保存单词完整的前缀或者是单词本身,它仅仅保存一个字母,程序会记下它所有祖先存储的信息.

Coding a Trie

trie树可以通过不同的方法构造,有些方法可以用来在字典中查找与目的字符串略微有些不同的所有其他字符串,但是有些方法仅仅支持完全匹配的查询.本文介绍的是后者.trie的实现将以伪代码的形式给出,因为不同的人使用不同的语言.

我们将实现下面4个功能:

  • 插入.该功能允许向词典中插入单词.
  • 统计前缀.该功能统计所有以一特定字符串作前缀的单词的数目.
  • 统计单词.该功能统计词典中与一给定的字符串完全匹配的单词数目.
  • 这里的trie树仅仅支持英文字母表中的字符.

我们打算构造一个struct,用它的数据域来记录结点保存的信息.为了知道与一给定的字符串匹配的单词的数目,每一结点需要有一个变量来表示该结点代表一个完整的单词还是仅仅一个前缀(为简洁起见,给定的单词被认为是一个前缀),它还需要一个变量来统计以给定的单词作为前缀的单词的个数(词典中同一单词可以重复出现),这用一个整形变量就足够了.

正如前面所分析的,每个结点需要一个整形变量prefixes,它表示词典中以该结点代表的前缀为前缀的单词个数.同样,每个结点需要关联到它的所有可能儿子结点(26个关联).理清所有这些细节之后,我们可以知道,struct体需要包含下面的成员:

structure Trie

integer words;
integer prefixes;
reference edges[26];

而且,我们需要实现以下的函数:

initialize(vertex)
addWord(vertex, word);
integer countPrefixes(vertex, prefix);
integer countWords(vertex, word);

首先,以下的代码实现结点信息的初始化:

initialize(vertex)

vertex.words=0
vertex.prefixes=0
for i=0 to 26

edges[i]=NoEdge

addWord函数有两个参数,单词插入所在的结点,插入的单词.当一个字符串string被添加到结点vertex时,我们将根据word的首字母,将它加入相应的vertex的分支,然后将word的首字母去掉.当找不到相应的vertex分支时,我们需要对vertex结点新建一个分支.(Arthur989注:一直递归着这么做下去,直至word为空)所有TopCoder比赛支持的语言都能够在常数时间内删去一个字符串的首元素,而无需拷贝原字符串或者移动字符串的其他元素.

addWord(vertex, word)

if isEmpty(word)
vertex.words=vertex.words+1
else

vertex.prefixes=vertex.prefixes+1
k=firstCharacter(word)
if(notExists(edges[k]))

edges[k]=createEdge()
initialize(edges[k])

cutLeftmostCharacter(word)
addWord(edges[k], word)

函数countWords和countPrefixes是非常相似的.如果(在递归过程中)程序查询的字符串变为空,那么程序只要返回(此时递归所在的)结点所存储的统计变量prefixes就可以了.如果程序查询的字符串非空,我们需要递归查询字符串首字母对应的分支,当分支不存在时,程序将返回0.

countWords(vertex, word)

k=firstCharacter(word)
if isEmpty(word)

return vertex.words

else if notExists(edges[k])

return 0

else

cutLeftmostCharacter(word)
return countWords(edges[k], word);

countPrefixes(vertex, prefix)

k=firstCharacter(prefix)
if isEmpty(word)

return vertex.prefixes

else if notExists(edges[k])

return 0

else

cutLeftmostCharacter(prefix)
return countWords(edges[k], prefix)

Complexity Analysis

通过上文的介绍,你已经感性地知道在trie树中查询和插入一个字符串的复杂度是线性的,但我们却还没着手于具体的分析.在查询和插入的过程中,根据字符串找到下一层对应的儿子是可以在常数时间内实现的,每次程序递归到下一分支时,字符串首字母将被删除;如果字符串长度为L,查询和插入将做L次的递归,因此,这两个操作的时间复杂度为O(L).tire树耗费的内存取决于存储分支的具体方法,以及trie树中有多少单词共享相同的前缀.

Other Kinds of Tries

在我们的介绍中,trie树结点局限于存储小写的英文字母,事实上,它还可以存储其他的信息.我们可以用结点来存储比特或者是字节,此时trie树可以表示任意的数据类型,而不再只是字符串了.发挥你的想像来使用trie树吧!比如说,假设你想在字典中查找一个单词,但是该单词缺失了一个特定的字母,你可以这么修改代码:

countWords(vertex, word, missingLetters)

k=firstCharacter(word)
if isEmpty(word)

return vertex.word

else if notExists(edges[k]) and missingLetters=0

return 0

else if notExists(edges[k])

cutLeftmostCharacter(word)
return countWords(vertex, word, missingLetters-1)
这里我们删去字符串首字母,但不递归查找下一分支.

else

这里我们考虑了两种可能:字符串首字母已被删除和未被删除
r=countWords(vertex, word, missingLetters-1)
cutLeftmostCharacter(word)
r=r+countWords(edges[k], word, missingLetters)
return r

比起原来的程序,修改后的代码的时间复杂度会更高,但是它比检查某一单词的所有子集来得更快.

Problems to Practice

WordFind SRM 232
SearchBox SRM 361
CyclicWords SRM 358
TagalogDictionary SRM 342
JoinedString SRM 302
CmpdWords SRM 268
Scruffle 2007 TCCC Marathon Online Round 1

无聊(1)

荒废了一个多星期..突然想要写点什么.

首先仍旧是感情.先谈谈老丘的.老丘最近在泡妞,这没什么不好的.地球上那么多善男信女,多一对也不打紧.可是,杀千刀的是,老丘一直在向我输出泡妞的好处,这是很不厚道的.老丘说,为了能在女生面前有个更好的形象,所以会自觉不自觉地注意到自己的缺陷.比如说,太过偏僻,又比如说,太过冲动.这话一点不假,放我身上恐怕也这么想.可是当老丘谈到要多读读汪国真同学的诗歌,看看discovery频道的人文时,我想,真t的,泡个妞还得这么麻烦,莫名其妙地成了个恶心的文学男…老丘看来,这可真是好事一桩,不但能读书还能送个女生,一点不亏的买卖.既然老丘都这么想了,我也不好说什么,奉上一句话,理论上,实际是接近于理论的;实际上,理论是接近于实际的.

然后是我遇到的感情事了.前几天,师傅很神奇地给我发了封邮件.我和师傅初一就认识了,数数到现在也有8年了.可惜从初三到上个月之前,6年的时间里从没再见面过.我和师傅关系一直很好,记忆中除了初二吵过一架之外.初中和高中的日子里,我们一直都是在写信.很无奈的是,上高中时,我把初中的信扔了.高考前几天,我又在东中后山亲手种的树下烧了好几封,剩下的也全无踪迹了.我不无天真的想,如果从没丢过信的话,摞起来该是厚厚的一叠了吧.信丢了自然是有愧歉的,而这一愧歉就是几年..收到师傅的邮件,我才知道,师傅去年搬家时也把信扔了.看来是两不相欠了.师傅初三送的一套邮票如今也早不见了,唯一还在的就是去年生日时师傅送的一件上衣和三张我非常非常喜欢的班得瑞CD了.师傅是我少有的几个聊得来的异形朋友了.多亏常和师傅写信,不然我的本来就单调苍白的初中高中生活怕是更会减色不少.上次见面时,发现师傅成熟了好多,最不错的一点是坚持着自己喜欢的.世界观很不错,价值观也很健康,不再像以前那个有那么一点霸道的大姐大了.

再然后,最近在烦着该不该读研呢.师傅是”举双脚赞成的”,老丘说应该慎重考虑.爷爷是要我读研的,因此,我应该是不读研了.我没打算用一个3年去再一次证明爷爷错了,中大的4年已经很浪费青春了.其实,读不读研有那么要紧吗,也许是我从没决定好,所以才这么纠结.也许,follow my heart就行了.

最后,什么时候我才能不懒呢.

_________________

代码:
sudo apt-get install girlfriend
正在读取软件包列表… 完成
正在分析软件包的依赖关系树… 完成
有一些软件包无法被安装。
下列的信息可能会对解决问题有所帮助:
下列的软件包有不能满足的依赖关系:
girlfriend: 依赖: house但是它将不会被安装
girlfriend: 依赖: car但是它将不会被安装
house,car: 依赖: money但是它将不会被安装
E: 无法安装的软件包