Trie 三兄弟——标准 Trie、压缩 Trie、后缀 Trie

1.Trie 导引

Trie 树是一种基于树的数据结构，又称单词查找树、前缀树，是一种哈希树的变种。应用于字符串的统计与排序，经常被搜索引擎系统用于文本词频统计。用于存储字符串以便支持快速模式匹配，主要应用在信息检索中，Trie 支持的主要查询操作是模式匹配和前缀匹配。Trie 树可以看着是一个确定有限状态自动机。

2. 标准 Trie

令 S 是取自字母表∑的 s 个集合，满足 S 中不存在一个串是另一个串的前缀。S 的一个标准 Trie（standard trie）是一颗有序书 T，满足如下性质：

• 除了根之外，T 中的每个结点标记有∑的一个字符。
• T 中一个内部结点的子结点的次序有字母表∑上的规范次序确定。
• T 有 s 个外部结点（叶结点），每个外部结点关联 S 中的一个串，满足从根到 T 中一个外部结点 v 的路径上标记连接产生 S 中关联的一个串。

下图是串 {bear,bell,bid,bull,buy,sell,stock,stop} 的标准 Trie

存储总长为 n, 来自大小为 d 的字母表中 s 个串的集合 S 的标准 Trie 具有如下性质：

1. T 中每个内部结点最多有 d 个子结点。
2. T 有 s 个外部结点。
3. T 的高度等于最长串的长度。
4. T 中的结点书为 O(n)。

性能：对于有 n 个英文字母的串来说，在内部结点中定位指针所需要花费 O(d)时间，d 为字母表的大小，英文为 26。由于在上面的算法中内部结点指针定位使用了数组随机存储方式，因此时间复杂度降为了 O(1)。但是如果是中文字，下面在实际应用中会提到。因此我们在这里还是用 O(d)。 查找成功的时候恰好走了一条从根结点到叶子结点的路径。因此时间复杂度为 O(d*n)。但是，当查找集合 X 中所有字符串两两都不共享前缀时，trie 中出现最坏情况。除根之外，所有内部结点都自由一个子结点。此时的查找时间复杂度蜕化为 O(d*(n^2))

中文词语的标准 Trie 树

      由于中文的字远比英文的 26 个字母多的多。因此对于 trie 树的内部结点，不可能用一个 26 的数组来存储指针。如果每个结点都开辟几万个中国字的指针空间。估计内存要爆了，就连磁盘也消耗很大。

      一般我们采取这样种措施：

     (1) 以词语中相同的第一个字为根组成一棵树。这样的话，一个中文词汇的集合就可以构成一片 Trie 森林。这篇森林都存储在磁盘上。森林的 root 中的字和 root 所在磁盘的位置都记录在一张以 Unicode 码值排序的有序字表中。字表可以存放在内存里。

    (2) 内部结点的指针用可变长数组存储。

     特点：由于中文词语很少操作 4 个字的，因此 Trie 树的高度不长。查找的时间主要耗费在内部结点指针的查找。因此将这项指向字的指针按照字的 Unicode 码值排序，然后加载进内存以后通过二分查找能够提高效率。

标准 Trie 的应用举例

标准 Trie 的应用和优缺点

     (1) 全字匹配：确定待查字串是否与集合的一个单词完全匹配。

     (2) 前缀匹配：查找集合中与以 s 为前缀的所有串。

     注意：Trie 树的结构并不适合用来查找子串。这一点和前面提到的 PAT Tree 以及后面专门要提到的 Suffix Tree 的作用有很大不同。

      优点： 查找效率比与集合中的每一个字符串做匹配的效率要高很多。在 o(m) 时间内搜索一个长度为 m 的字符串 s 是否在字典里。

      缺点：标准 Trie 的空间利用率不高，可能存在大量结点中只有一个子结点，这样的结点绝对是一种浪费。正是这个原因，才迅速推动了下面所讲的压缩 trie 的开发。

压缩 Trie

压缩 Trie 类似于标准 Trie，但它能保证 Trie 中的每个内部结点至少有两个字结点。通过把单子结点链压缩进各条边中来执行这个规则。设 T 是一棵标准 Trie，如果 T 的一个内部结点 v 有一个子结点且它不是根，则称为这个内部结点是内部结点是冗余的（redundant）。

如果

串{bear,bell,bid,bull,buy,sell,stock,stop}的压缩 Trie

压缩 Trie 的性质和优势：

     与标准 Trie 比较，压缩 Trie 的结点数与串的个数成正比了，而不是与串的总长度成正比。一棵存储来自大小为 d 的字母表中的 s 个串的结合 T 的压缩 trie 具有如下性质：

     (1) T 中的每个内部结点至少有两个子结点，至多有 d 个子结点。

     (2) T 有 s 个外部结点。

     (3) T 中的结点数为 O(s)

存储空间从标准 Trie 的 O(n)降低到压缩后的 O(s)，其中 n 为集合 T 中总字符串长度，s 为 T 中的字符串个数。

压缩 Trie 应用举例

假定串的集合 S 是 S[0],S[1],...,S[s-1]的一个数组，使用三元组 (i,j,k) 隐式地表示存储的标记 X，满足 X =S[i][j,...,k]；即 X 是 S[i]的子串，由从 j 到 k 所包含的字符组成。

后缀 Trie

后缀 Trie 的字符串集合是由指定字符串的后缀子串构成的。比如、完整字符串 "minimize" 的后缀子串组成的集合 S 分别如下：

         s1=minimize

         s2=inimize

         s3=nimize

         s4=imize

         s5=mize

         s6=ize

         s7=ze

         s8=e

 然后把这些子串的公共前缀作为内部结点构成一棵 "minimize" 的后缀树，如下图所示：

节省空间

因为长度为 n 的串 X 的后缀总长度为 n(n+1)/2，显式存储 X 的所有后缀所需空间为 O(n²)。而后缀 Trie 隐式地表示这些串所需空间为 O(n)。

后缀 Trie 创建（图示）

当插入子串时，发现叶子结点中的关键字与子串有公共前缀，则需要将该叶子结点分裂。如上图第 3 到 4 步。否则，重新创建一个叶子结点来存放后缀，如上图第 1 到 2 步。

Suffix Trie 的子串查询

     如果在后缀树 T 中查找子串 P，我们需要这样的过程：

     (1) 从根结点 root 出发，遍历所有的根的孩子结点：N1,N2,N3....

     (2) 如果所有孩子结点中的关键字的第一个字符都和 P 的第一个字符不匹配，则没有这个子串，查找结束。

     (3) 假如 N3 结点的关键字 K3 第一个字符与 P 的相同，则匹配 K3 和 P。

          若 K3.length>=P.length  并且 K3.subString(0,P.length-1)=P，则匹配成功，否则匹配失败。

          若 K3.length<=P.length  并且 K3=P.subString(0, K3.length-1)，则将子串 P1=P.subString(K3.length, P.length); 即取出 P 中排除 K3 之后的子串。然后 P1 以 N3 为根结点继续重复(1)~   (3) 的步骤。直到匹配完 P1 的所有字符，则匹配成功。否则匹配失败。

查询效率：很显然，在上面的算法中。匹配成功正好比较了 P.length 次字符。而定位结点的孩子指针，和 Trie 情况类似，假如字母表数量为 d。则查询效率为 O(d*m)，实际上，d 是固定常数，如果使用 Hash 表直接定位，则 d =1.

        因此，后缀树查询子串 P 的时间复杂度为 O(m)，其中 m 为 P 的长度。但是构造后缀 Trie 的时间为 O(dn)。

后缀 Trie 应用

标准 Trie 树只适合前缀匹配和全字匹配，并不适合后缀和子串匹配。而后缀 Trie 在这方面则非常合适。