rambo

树(三) Trie树及扩展

字典树Trie

它是一种哈希树的变种。从字面意思即可理解,这种树的结构像英文字典一样,相邻的单词一般前缀相同。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高

基本性质:

  • 根节点不包含字符,除根节点外每一个节点都只包含一个字符;
  • 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串
  • 每个单词的公共前缀作为一个字符节点保存。
  • 每个节点的所有子节点包含的字符都不相同。
  • 其基本操作有:查找、插入和删除,当然删除操作比较少见。

和二叉搜索树不同,在trie树中,每个结点上并非存储一个元素。 trie树把要查找的关键词看作一个字符序列。并根据构成关键词字符的先后顺序构造用于检索的树结构。 在trie树上进行检索类似于查阅英语词典。

inn, int, at, age, adv, ant,这些关键词形成的trie树

  1. 每条边对应一个字母。
  2. 每个节点对应一项前缀叶节点对应最长前缀,即单词本身。
  3. 单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支,root->i->in。同理,ate, age, adv, 和ant共享前缀"a",所以他们共享从根节点到节点"a"的边。
搜索字典项目算法:
(1) 从根结点开始一次搜索;
(2) 取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索;
(3) 在相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
(4) 迭代过程……
(5) 在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。
从根开始按照单词的字母顺序向下遍历trie树,一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色,则表示该单词不存在,若最后的节点标记为红色,表示该单词存在。如下图中:trie树中存在的就是abc、d、da、dda四个单词。在实际的问题中可以将标记颜色的标志位改为数量count等其他符合题目要求的变量。

算法复杂度

对字符串的排序,若采用一些经典的排序算法,则时间复杂度一般为O(n*lgn),但若采用Trie树,则时间复杂度仅为O(n)。之所以时间复杂度低,是因为其采用了以空间换取时间的策略。

QQ截图20150819181908

应用

1、串的快速检索:

1) 给出N个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。(类似于词频统计)
词频统计简单可以用一个hash或者一个堆,但问题来了,如果内存有限呢
我们就可以用trie树来压缩下空间,因为公共前缀都是用一个节点保存的。先把熟词建一棵树,然后读入文章进行比较,这种方法效率是比较高的。

2)有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。

3) 给出一个词典,其中的单词为不良单词。单词均为小写字母。再给出一段文本,文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如,若rob是不良单词,那么文本problem含有不良单词。

4) 1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。(百度06面试题)

5)寻找热门查询:搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录,这些查询串的重复读比较高,虽然总数是1千万,但是如果去除重复和,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就越热门。请你统计最热门的10个查询串,要求使用的内存不能超过1G。

2、“串”排序
给定N个互不相同的仅由一个单词构成的英文名,将它们按字典序从小到大输出。
采用数组的方式创建字典树,这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。

3、前缀匹配(想到一道面试题,搜索关键词智能提示suggestion)

获取所有以"a"开头的字符串,从图中可以很明显的看到是:and,as,at,如果不用trie树,
很显然朴素的做法时间复杂度为O(N2) ,那么用Trie树就不一样了,它可以做到O(h),h为检索单词的长度。

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门),请你统计最热门的10个查询串,要求使用的内存不能超过1G。

解答:由上面第1题,我们知道,数据大则划为小的,如一亿个Ip求Top 10,可先%1000将ip分到1000个小文件中去,并保证一种ip只出现在一个文件中,再对每个小文件中的ip进行hashmap计数统计并按数量排序,最后归并或者最小堆依次处理每个小文件的top10以得到最后的结果。

但如果数据规模本身就比较小,能一次性装入内存呢?比如这第2题,虽然有一千万个Query,但是由于重复度比较高,因此事实上只有300万的Query,每个Query255Byte,因此我们可以考虑把他们都放进内存中去(300万个字符串假设没有重复,都是最大长度,那么最多占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理),而现在只是需要一个合适的数据结构,在这里,HashTable绝对是我们优先的选择。

所以我们放弃分而治之/hash映射的步骤,直接上hash统计,然后排序。So,针对此类典型的TOP K问题,采取的对策往往是:hashmap + 堆。如下所示:

  1. hashmap统计:先对这批海量数据预处理。具体方法是:维护一个Key为Query字串,Value为该Query出现次数的HashTable,即hash_map(Query,Value),每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计;
  2. 排序:第二步、借助堆这个数据结构,找出Top K,时间复杂度为N‘logK。即借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比。所以,我们最终的时间复杂度是:O(N) + N' * O(logK),(N为1000万,N’为300万)。

别忘了这篇文章中所述的堆排序思路:‘维护k个元素的最小堆,即用容量为k的最小堆存储最先遍历到的k个数,并假设它们即是最大的k个数,建堆费时O(k),并调整堆(费时O(logk))后,有k1>k2>...kmin(kmin设为小顶堆中最小元素)。继续遍历数列,每次遍历一个元素x,与堆顶元素比较,若x>kmin,则更新堆(x入堆,用时logk),否则不更新堆。这样下来,总费时O(k*logk+(n-k)*logk)=O(n*logk)。此方法得益于在堆中,查找等各项操作时间复杂度均为logk。
当然,你也可以采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

4 、作为其他数据结构和算法的辅助结构
如后缀树,AC自动机等。

 

基数树(Radix Tree)

字典树 (Trie) 的一种特殊情况。

给定两个串a = a_{0}a_{1}...a_{p}b = b_{0}b_{1}...b_{q},其中每一个a_{i}和每一个b_{j}都属于某个有序字符集,如果下面两条规则之一成立(只要一条成立即可),则说串a按字典序小于串b:

1)存在一个整数j,0<=j<=min(p,q),使得a_{i}=b_{i},i=0,1,...,j-1,且a_{j}<b_{j}
2)p<q,且a_{i}=b_{i},对所有的i=0,1,...,p成立

例如,如果a和b是位串,则根据规则1)(设j=3),有10100 < 10110;根据规则2),有10100 < 101000。这与英语字典中的排序很相似。

图12-5中示出的是基数树(radix tree)数据结构,其中存储了位串1011、10、011、100和0。当查找某个关键a = a_{0}a_{1}...a_{p}时,在深度为i的一个结点处,若a_{i} = 0则向左转;若a_{i} = 1则向右转。设S为一组不同的二进制串构成的集合,各串的长度之和为n。说明如何利用基数树,O(n)时间内对S按字典序排序。例如,对图12-5中每个结点的关键字,排序的输出应该是序列0、011、10、100、1011。

QQ截图20150819142925

 

如果一些结点的关键字不在树中,它们就标为深阴影。

相关题目:

1、设计一个最优算法来查找一n个元素数组中的最大值和最小值。已知一种需要比较2n次的方法,请给一个更优的算法。情特别注意优化时间复杂度的常数。(这道题目显然可以采用RadixTree,将数组中的元素采用二进制表示)。

 

Linux基数树(转载)

Linux基数树(radix tree)是将指针与long整数键值相关联的机制,它存储有效率,并且可快速查询,用于指针与整数值的映射(如:IDR机制)、内存管理等。
IDR(ID Radix)机制是将对象的身份鉴别号整数值ID与对象指针建立关联表,完成从ID与指针之间的相互转换。IDR机制使用radix树状结构作为由id进行索引获取指针的稀疏数组,通过使用位图可以快速分配新的ID,IDR机制避免了使用固定尺寸的数组存放指针。IDR机制的API函数在lib/idr.c中实现,这里不加分析。
Linux radix树最广泛的用途是用于内存管理,结构address_space通过radix树跟踪绑定到地址映射上的核心页,该radix树允许内存管理代码快速查找标识为dirty或writeback的页(脏页)。Linux radix树的API函数在lib/radix-tree.c中实现。

Linux radix树最广泛的用途是用于内存管理,结构address_space通过radix树跟踪绑定到地址映射上的核心页,该radix树允许内存管理代码快速查找标识为dirty或writeback的页。Linux radix树的API函数在lib/radix-tree.c中实现。

(1)radix树概述

radix树是通用的字典类型数据结构,radix树又称为PAT位树(Patricia Trie or crit bit tree)。Linux内核使用了数据类型unsigned long的固定长度输入的版本。每级代表了输入空间固定位数。
radix tree是一种多叉搜索树,树的叶子结点是实际的数据条目。每个结点有一个固定的、2^n指针指向子结点(每个指针称为槽slot),并有一个指针指向父结点。

Linux内核利用radix树在文件内偏移快速定位文件缓存页,图4是一个radix树样例,该radix树的分叉为4(22),树高为4,树的每个叶子结点用来快速定位8位文件内偏移,可以定位4x4x4x4=256页,如:图中虚线对应的两个叶子结点的路径组成值0x00000010和0x11111010,指向文件内相应偏移所对应的缓存页。


图4 一个四叉radix树

(2)radix树slot数

Linux内核根用户配置将树的slot数定义为4或6,即每个结点有16或64个slot,如图2所示,当树高为1时,64个slot对应64个页,当树高为2时,对应64*64个页。


图2 高为1和2、slot数为64的radix树

 

 

总结:

Trie树一般用于字符串到对象的映射,Radix树一般用于长整数到对象的映射。
trie树主要问题是树的层高,如果要索引的字的拼音很长很变态,我们也要建一个很高很变态的树么?
radix树能固定层高(对于较长的字符串,可以用数学公式计算出其特征值,再用radix树存储这些特征值

参考资料:

1)http://blog.csdn.net/hguisu/article/details/8131559

2)http://blog.csdn.net/mishifangxiangdefeng/article/details/7581579

3)http://blog.csdn.net/mishifangxiangdefeng/article/details/7719324

4) http://blog.csdn.net/joker0910/article/details/8250085  Linux Radix

2)http://machinelearningmastery.com/tactics-to-combat-imbalanced-classes-in-your-machine-learning-dataset/

2)http://machinelearningmastery.com/classification-accuracy-is-not-enough-more-performance-measures-you-can-use/