欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-11 12:08:44
...

Trie树和其它数据结构的比较
            
    
    博客分类: Algorithm 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树和其它数据结构的比较
            
    
    博客分类: Algorithm 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树本身的空间开销会小一些,虽说引入了一张额外的映射表。

文章系本人原创,转载请保持完整性并注明出自《四火的唠叨》

相关标签: Trie树 比较