Trie树

https://segmentfault.com/a/1190000008877595
https://www.jianshu.com/p/6f81da81bd02
https://blog.csdn.net/lisonglisonglisong/article/details/45584721

Trie树,前缀树,词典树,用于词频统计、字符串查找、模糊匹配等。它将字符串整理成树,比如以下Trie树由“清华”、“清华大学”、“清新”、“中华”、“华人”五个中文词构成,叶子节点是单词的词频:

Trie 树中的词只可共用前缀,Trie 树中任何一个完整的词,都必须是从根节点开始至叶子节点结束,这意味着对一个词进行检索也必须从根节点开始,至叶子节点才算结束。

Double-array Trie 树

双数组 Trie 树是目前 Trie 树各种实现中性能和存储空间均达到很好效果的实现。

在双数组Trie树中,我们首先对词典出现的字符进行编码,比如例树的字符编码表为:

清-1,华-2,大-3,学-4,新-5,中-6,人-7

那么“华”的位置应该在Base Array 中的的第5位(base[2]+code("华")=3+2=5):

而所有词的首字,则是通过根节点的转移基数推算而来。因此,对于字典中已有的词,只要我们每次从根节点出发,根据词典中各个字符的编码值,结合每个节点的转移基数,通过简单的加法,就可以在Base Array 中实现词的链路关系。以下是“清华”、“清华大学”、“清新”、“中华”、“华人”五个词在 Base Array 中的链路关系:

Base Array 的构造

可见 Base Array 不仅能够表达词典中每个字符的状态,而且还能实现高效的状态转移。那么,Base Array 又是如何构造的呢?

事实上,同样一组词和字符编码,以不同的顺序将字符写入 Trie 树中,获得的 Base Array 也是不同的,以“清华”、“清华大学”、“清新”、“中华”、“华人”五个词,以及字符编码:[清-1,华-2,大-3,学-4,新-5,中-6,人-7] 为例,在不考虑叶子节点的情况下,两种处理方式获得的 base array 为:

  1. 首先依次处理“清华”、“清华大学”、“清新”、“中华”、“华人”五个词的首字,然后依次处理所有词的第二个字…直到依次处理完所有词的最后一个字,得到的 Base Array 为:
  2. 依次处理“清华”、“清华大学”、“清新”、“中华”、“华人”五个词中的每个字,得到的 Base Array 为:

可以发现,不同的字符处理顺序,得到的 Base Array 存在极大的差别:两者各状态的转移基数不仅完全不同,而且 Base Array 的长度也有差别。然而,两者获得的方法却是一致的,下面以第一种字符处理顺序讲解一下无叶子节点的 Base Array 构建:

  1. 首先人为赋予根节点的转移基数为 1(可自定义,详见下文),然后依次将五个词中的首字”清”、“中”、“华”写入数组之中,写入的位置由base[1]+code(字符)确定,每个位置的转移基数(base[i])等于上一个状态的转移基数(此例也即base[1]),这个过程未遇到冲突,最终结果见下图:


2. 然后依次处理每个词的第二个字,首先需要处理的是“清华”这个词的“华”字,程序先从根节点出发,通过 base[1]+code(“清”)=2找到“清”节点,然后以此计算“华”节点应写入的位置,通过计算base[2]+code(“华”)=3寻找到位置 3,却发现位置3<已有值,于是后挪一位,在位置4写入“华”节点,由于“华”节点未能写入由前驱节点“清”预测的位置,因此为了保证通过“清”能够找到“华”,需要重新计算“清”节点的转移基数,计算公式为4-code(“华”)=2,获得新的转移基数后,改写“清”节点的转移基数为2,然后将“华”节点的转移基数与“清”节点保持一致,最终结果为:
3. 重复上面的步骤,最终获得整个 Base Array:

通过以上步骤,可以发现 base array 的构造重点在于状态冲突的处理,对于双数组 Trie 而言,词典构造过程中的冲突是不可避免的,冲突的产生来源于多词共字的情况,比如“中华”、“清华”、“华人”三个词中都有“华”,虽然词在 Trie 树中可以共用前缀,但是对于后缀同字或者后缀与前缀同字的情况却只能重新构造新的节点,这势必会导致冲突。一旦产生冲突,那么父节点的转移基数必须改变,以保证基于前驱节点获得的位置能够容纳下所有子节点(也即保证 base[i]+code(n1)、base[i]+code(n2)、base[i]+code(n3)….都为空,其中n1、n2、n3...为父节点的所有子节点字符,base[i]为父节点新的转移基数,i为父节在数组中的位置)这意味着其他已经构造好的子节点必须一并重构。
因此,双数组 Trie 树的构建时间比较长,有新词加入,运气不好的话,还可能能导致全树的重构:比如要给词典添加一个新词,新词的首字之前未曾写入过,现在写入时若出现冲突,就需要改写根节点的转移基数,那么之前构建好的词都需要重构(因为所有词的链路都是从根节点开始)。上例中,第二种字符写入顺序就遇到了这个问题,导致在词典构造过程中,根节点转移基数被改写了两次,全树也就被重构了三次:

可见不同的节点构建顺序,对 Base Aarry 的构建速度、空间利用率都有影响。建议实际应用中应首先构建所有词的首字,然后逐一构建各个节点的子节点,这样一旦产生冲突,可以将冲突的处理局限在单个父节点和子节点之间,而不至于导致大范围的节点重构。

5.4.3 叶子节点的处理

上面关于 Base Array 的叙述,只涉及到了根节点、分支节点的处理,事实上,Base Array 同样也需要负责叶子节点的表达,但是由于叶子节点的处理,具体的实现各不一致,因此特地单列一节予以论述。

一般词的最后一个字都不需要再做状态转移,因此有人建议将词的最后一个节点的转移基数统一改为某个负数(比如统一设置为-2),以表示叶子节点,按照这种处理,对于示例而言,base array 是这样的:

但细心的童鞋可能会发现,“清华” 和 “清华大学” 这两个词中,只有“清华大学”有叶子节点,既是公共前缀又是单个词的“清华”实际上无法用这种方法表示出叶子节点。

也有人建议为词典中所有的词增加一个特殊词尾(比如将“清华”这个词改写为“清华\0”),再将这些词构建为树,特殊字符词尾节点的转移基数统一设置设为-2,以此作为每个词的叶子节点[4]。这种方法的好处是不用对现有逻辑做任何改动,坏处是增加了总节点的数量,相应的会增加词典构建的时长和空间的消耗。

最后,个人给出一个新的处理方式:直接将现有 base array 中词尾节点的转移基数取负,而数组中的其他信息不用改变。

以树例为例,处理叶子节点前,Base Array 是这样子的:

处理叶子节点之后,Base Array 会是这样子的:

每个位置的转移基数绝对值与之前是完全相同的,只是叶子节点的转移基数变成了负数,这样做的好处是:不仅标明了所有的叶子节点,而且程序只需对状态转移公式稍加改变,便可对包括“清华”、“清华大学”这种情况在内的所有状态转移做一致的处理,这样做的代价就是需要将状态转移函数base[s]+code(字符)改为|base[s]|+code(字符),意味着每次转移需要多做一次取绝对值运算,不过好在这种处理对性能的影响微乎其微。
对此,其他童鞋若有更好的想法, 欢迎在底部留言!

5.4.4 Check Array 的构造

“双数组 Trie 树”,必定是两个数组,因此单靠 Base Array 是玩不起来的….上面介绍的 Base Array 虽然解决了节点存储和状态转移两个核心问题,但是单独的 Base Array 仍然有个问题无法解决:

Base Array 仅仅记录了字符的状态,而非字符本身,虽然在 Base Array,字典中已有的任意一个词,其链路都是确定的、唯一的,因此并不存在歧义;但是对于一个新的字符串(不管是检索字符串还是准备为字典新增的词),Base Array 是不能确定该词是否位于词典之中的。对于这点,我们举个例子就知道了:

如果我们要在例树中确认外部的一个字符串“清中”是否是一个词,按照 Trie 树的查找规则,首先要查找“清”这个字,我们从根节点出发,获得

|base[1]|+code(“清”)=3,然后转移到“清”节点,确认清在数组中存在,我们继续查找“中”,通过

|base[3]|+code(“中”)=9获得位置

9,字符串此时查询完毕,根据位置

9的转移基数

base[9]=-2确定该词在此终结,从而认为字符串“清中”是一个词。而这显然是错误的!事实上我们知道 “清中”这个词在 base array 中压根不存在,但是此时的 base array 却不能为此提供更多的信息。
为了解决这些问题,双数组 Trie 树专门设计了一个 check 数组: check array 与 base array 等长,它的作用是标识出 base array 中每个状态的前一个状态,以检验状态转移的正确性。 因此, 例树的 check array 应为:

如图,check array 元素与 base array 一一对应,每个 check array 元素标明了base array 中相应节点的父节点位置,比如“清”节点对应的

check[2]=0,说明“清”节点的父节点在 base array 的0 位(也即根节点)。对于上例,程序在找到位置9之后,会检验 check[9]==2,以检验该节点是否与“清”节点处于同一链路,由于check[9]!=2,那么就可以判定字符串“清中”并不在词典之中。
综上,check array 巧妙的利用了父子节点间双向关系的唯一性(公式化的表达就是base[s]+c=t & check[t]=s是唯一的,其中 s为父节点位置,t为子节点位置),避免了 base array 之中单向的状态转移关系所造成的歧义(公式化的表达就是base[s]+c=t)。

5.4.5 Trie 树的压缩

双数组 Trie 树虽然大幅改善了经典 Trie 树的空间浪费,但是由于冲突发生时,程序总是向后寻找空地址,导致数组不可避免的出现空置,因此空间上还是会有些浪费。另外, 随着节点的增加,冲突的产生几率也会越来越大,字典构建的时间因此越来越长,为了改善这些问题,有人想到对双数组 Trie 进行尾缀压缩,具体做法是:将非公共前缀的词尾合并为一个节点(tail 节点),以此大幅减少节点总数,从而改善树的构建速度;同时将合并的词尾单独存储在另一个数组之中(Tail array), 并通过 tail 节点的 base 值指向该数组的相应位置,以 {baby#, bachelor#, badge#, jar#}四词为例,其实现示意图如下[3]

对于这种改进的效果,看一下别人家的测试就知道了[4]

速度
减少了base, check的状态数,以及冲突的概率,提高了插入的速度。在本地做了一个简单测试,随机插入长度1-100的随机串10w条,no tail的算法需120秒,而tail的算法只需19秒。
查询速度没有太大差别。

内存
状态数的减少的开销大于存储tail的开销,节省了内存。对于10w条线上URL,匹配12456条前缀,内存消耗9M,而no tail的大约16M

删除
能很方便的实现删除,只需将tail删除即可。

对于本文的例树,若采用tail 改进,其最终效果是这一子的:

六、总结

  1. Trie 树是一种以信息换时间的数据结构,其查询的复杂度为O(m)
  2. Trie 的单数组实现能够达到最佳的性能,但是其空间利用率极低,是典型的以空间换时间的实现
  3. Trie 树的哈希实现可以很好的平衡性能需求和空间开销,同时能够实现词典的实时更新
  4. Trie 树的双数组实现基本可以达到单数组实现的性能,同时能够大幅降低空间开销;但是其难以做到词典的实时更新
  5. 对双数组 Trie 进行 tail 改进可以明显改善词典的构建速度,同时进一步减少空间开销

字典树的应用场景

1)、字符串的快速查找

给出N个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。
在这道题中,我们可以用数组枚举,用哈希,用字典树,先把熟词建一棵树,然后读入文章进行比较,这种方法效率是比较高的。

2)、字典树在“串”排序方面的应用

Trie树可以对大量字符串按字典序进行排序,思路也很简单:遍历一次所有关键字,将它们全部插入trie树,树的每个结点的所有儿子很显然地按照字母表排序,然后先序遍历输出Trie树中所有关键字即可。

3)、字典树在最长公共前缀问题的应用

对所有串建立字典树,对于两个串的最长公共前缀的长度即他们所在的节点的公共祖先个数,于是,问题就转化为最近公共祖先问题。

Trie树的结构:

class TrieNode {  
 char c;  
 int occurances;  
 Map<Character, TrieNode> children;  
 }

1、c, 保存的是该节点的数据,只能是一个字符(注意是一个)
2、occurances, 从单词意思应该知道是发生频率的意思。occurances 是指 当前节点所对应的字符串在字典树里面出现的次数。
3、children, 就是当前节点的子节点,保存的是它的下一个节点的字符。

Trie树的插入:

int insert(String s, int pos) {  
 if(s == null || pos >= s.length()) {  
 return 0;  
 }  
 if(children == null) {  
 children = new HashMap<Character, TrieNode>();  
 }  
 char c = s.charAt(pos);  
 TrieNode n = children.get(c);  
 if (n == null) {  
 n = new TrieNode(c);  
 children.put(c, n);  
 }  
 if(pos = s.length() – 1) {  
 n.occurances++;  
 return n.occurances;  
 } else {  
 return n.insert(s, pos + 1);  
 }  
 }
comments powered by Disqus