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树的节点压缩可以明显缓解这个问题，后面会讲到。
和后缀树相比
后缀树压缩存储了一段文本的所有可能的后缀，如给定单词"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树本身的空间开销会小一些，虽说引入了一张额外的映射表。
Read full article from Trie树和其它数据结构的比较 | 四火的唠叨
No comments:
Post a Comment