Trie树和其它数据结构的比较

Trie树和其它数据结构的比较

Trie树,又叫做前缀树或者是字典树,是一种有序的树。从空字符串的根开始,往下遍历到某个节点,确定了对应的字符串,也就是说,任意一个节点的所有子孙都具备相同的前缀。每一棵Trie树都可以被看做是一个简单版的确定有限状态的自动机(DFA,deterministic finite automaton),也就是说,对于一个任意给定的属于该自动机的状态(①)和一个属于该自动机字母表的字符(②),都可以根据给定的转移函数(③)转到下一个状态去。其中:

  • ① 对于Trie树中的每一个节点都确定了一个自动机的状态;
  • ② 给定一个属于该自动机字母表的字符,在图中可以看到根据不同的字符形成的分支;
  • ③ 从当前节点进入下一层次节点的过程经过状态转移函数得出。

一个非常常见的应用就是搜索提示,在搜索框中输入搜索信息的前缀,如“乌鲁”,提示“乌鲁木齐”;再有就是输入法的联想功能,也是一样的道理。

和二叉搜索树(binary search tree)相比

二叉搜索树又叫做二叉排序树,它满足:

  • 任意节点如果左子树不为空,左子树所有节点的值都小于根节点的值;
  • 任意节点如果右子树不为空,右子树所有节点的值都大于根节点的值;
  • 左右子树也都是二叉搜索树;
  • 所有节点的值都不相同。

其实二叉搜索树的优势已经在与查找、插入的时间复杂度上了,通常只有O(log n),很多集合都是通过它来实现的。在进行插入的时候,实质上是给树添加新的叶子节点,避免了节点移动,搜索、插入和删除的复杂度等于树的高度,属于O(log n),最坏情况下整棵树所有的节点都只有一个子节点,完全变成一个线性表,复杂度是O(n)。

Trie树在最坏情况下查找要快过二叉搜索树,如果搜索字符串长度用m来表示的话,它只有O(m),通常情况(树的节点个数要远大于搜索字符串的长度)下要远小于O(n)。

我们给Trie树举例子都是拿字符串举例的,其实它本身对key的适宜性是有严格要求的,如果key是浮点数的话,就可能导致整个Trie树巨长无比,节点可读性也非常差,这种情况下是不适宜用Trie树来保存数据的;而二叉搜索树就不存在这个问题。

和Hash表相比

考虑一下Hash表键冲突的问题。Hash表通常我们说它的复杂度是O(1),其实严格说起来这是接近完美的Hash表的复杂度,另外还需要考虑到hash函数本身需要遍历搜索字符串,复杂度是O(m)。在不同键被映射到“同一个位置”(考虑closed hashing,这“同一个位置”可以由一个普通链表来取代)的时候,需要进行查找的复杂度取决于这“同一个位置”下节点的数目,因此,在最坏情况下,Hash表也是可以成为一张单向链表的(对于Hash冲突问题,请阅读《Hash Collision DoS问题》)。

Trie树可以比较方便地按照key的字母序来排序(整棵树先序遍历一次就好了),这是绝大多数Hash表是不同的(Hash表一般对于不同的key来说是无序的)。

在较理想的情况下,Hash表可以以O(1)的速度迅速命中目标,如果这张表非常大,需要放到磁盘上的话,Hash表的查找访问在理想情况下只需要一次即可;但是Trie树访问磁盘的数目需要等于节点深度。

很多时候Trie树比Hash表需要更多的空间,我们考虑这种一个节点存放一个字符的情况的话,在保存一个字符串的时候,没有办法把它保存成一个单独的块。Trie树的节点压缩可以明显缓解这个问题,后面会讲到。

和后缀树相比

Trie树和其它数据结构的比较

后缀树压缩存储了一段文本的所有可能的后缀,如给定单词“banana”,可能的后缀包括:a、na、ana、nana、anana、banana这几种,上图已经将所有可能全部放在树中表示出来了,“$”表示一个后缀的结束,同时,还做到了尽量的分支压缩(分支压缩的说明在下文中也有提及)。对于给定长度为n的文本构造后缀树,它的定义要点包括:

  • 树有n个叶子节点,分别从1到n来命名;
  • 除了根节点,所有的非叶子节点至少有两个孩子;
  • 每一条边代表原文本的一个非空子串;
  • 不存在两条边以同一个字符开串标记且以同一个字符结尾;
  • 在从根节点到叶子 i 的路径上,连接所有字符串标记形成的字符串,都表示了一个原文本的后缀子串。

构造后缀树根据文本长度需要消耗线性的时间。和Trie树相比,后缀树做到了用空间换时间,考虑全文搜索的情况,后缀树把所有可能的后缀子串都索引化了,就避免了Trie树深度遍历整棵树的过程。在算法题中许多关于“前缀子串问题上,我们经常使用Trie树来求解,但是如果问题仅仅涉及“子串”,往往选用后缀树;另外,还有一个重要的使用在文本压缩算法上,通过后缀树可以找到重复率高的文本,实现重复文本抽取,放到字典映射表中去。

Trie树的改进

1. 按位Trie树(Bitwise Trie):原理上和普通Trie树差不多,只不过普通Trie树存储的最小单位是字符,但是Bitwise Trie存放的是位而已。位数据的存取由CPU指令一次直接实现,对于二进制数据,它理论上要比普通Trie树快。

2. 节点压缩。

  • ① 分支压缩:对于稳定的Trie树,基本上都是查找和读取操作,完全可以把一些分支进行压缩。例如,前图中最右侧分支的inn可以直接压缩成一个节点“inn”,而不需要作为一棵常规的子树存在。Radix树就是根据这个原理来解决Trie树过深问题的。
  • ② 节点映射表:这种方式也是在Trie树的节点可能已经几乎完全确定的情况下采用的,针对Trie树中节点的每一个状态,如果状态总数重复很多的话,通过一个元素为数字的多维数组(比如Triple Array Trie)来表示,这样存储Trie树本身的空间开销会小一些,虽说引入了一张额外的映射表。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

One comment

  1. 匿名 说道:

    trie树是radix-search tree的一种,此类树最有用的是它的“radix”性质,即:对于树中任意一个节点,以该节点为根的子树中的所有节点的键值,都以该节点键值为前缀。
    如果只看重查找性能,一般不会选择trie树。

发表评论

电子邮件地址不会被公开。

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Preview on Feedage: