微信号:inkfish-talk

介绍:分享人工智能相关技术的学习和实践收获

从Trie到Double Array Trie

2016-07-17 00:52 inkfish


上周大伙讨论Double Array Trie的时候,表示难以想象DAT的作者当初是怎么设计出这样的数据结构的。我当时分享了"事后诸葛亮"的猜测分析。稍作整理再闲聊一下,务虚,少细节。



Trie

Trie是一种树状数据结构,常用于词典存储,也称前缀树。


看一个简单的例子,假设字符集只有三个字符{a, b, c},  词典包含5个词{aaa, ac, b, c, cbc}。 为了方便处理词前缀同为词的情况(如:c, cbc同为词),增加字符#作为词结束符,词典记为{aaa#, ac#, b#, c#, cbc#}。


下图即为上述词典的Trie(空心的非根节点其实并不存在,为描述方便保留):


这样Trie树在计算机里面如何存储呢? 不同的存储有什么不同的优缺点?下面就简单聊聊。



Trie的第一种形式


struct Node{

   InfoType* info; // 存储节点相关信息

   char* children_char; // 存储转移字符

   Node* children_node; // 存储转移后子节点

}


在查找的时候,next_node = goto(Node* current_node, char next_char), 我们需要遍历 children_char[]。如果找到current_node.children_char[i] = next_char, 则next_node = current_node.children_node[i], 否则, next_node = NULL。


上述操作逻辑会比较耗时,一般会把children_char/children_node按children_char排序,在查找的时候,使用二分查找代替遍历。单次goto操作时间复杂度为O(log|V|) (|V|为字符集大小)。如果一个单词的长度为K,那么,Trie的查找时间复杂度为O(K*log|V|)。



Trie的第二种形式


struct Node{

   InfoType* info; // 存储节点相关信息

   Node children_node[|V|]; // 存储转移后子节点

}

与第一种形式不同的地方在于,新的形式省去children_char, 假设字符集大小为|V|,申请大小为|V|的children_node,而其中children_node[i]表示从当前节点经过i-th字符达到的下一个节点。


在查找的时候,next_node = goto(Node* current_node, char next_char),我们只需要直接返回current_node.children_node[id(next_char)] (id(next_char)为next_char在字符集中的序号)。单次goto操作时间复杂度为O(1)。如果一个单词的长度为K,那么,Trie的查找时间复杂度为O(K)。


比较一下第一种形式和第二种形式,第一种只保存存在子树的分支,需要额外存储转移字符,查找时间复杂度较高;第二种保存所有分支,不管是否存在子树,查找时间复杂度较低,但存在空间浪费。



Trie的第二种形式的变种 - Triple Array Trie

对第二种形式,做一点点变换,把所有非空节点的children_node拼接在一起,表示为数组形式。可称之为Triple Array Trie

  • Base[i]存储第i个节点的children_node从哪个位置开始

  • Children_node[i]存储下一个节点的编号

  • Check[i]存储父亲节点的编号 (在当前情况下是冗余的,并非必需)



Triple Array Trie满足:

  • Children_node[Base[current_node] + next_char] = next_node

  • Check[Base[current_node] + next_char] = current_node


大胆的尝试

上述变种,只是形式上的变化,并没有解决浪费的空间(上图中标记空心圆的位置)。是否可以充分利用这些空位呢?


答案是肯定的!


不同节点的children_node可以重叠而重用空位。


上图所示,节点3和节点4的children_node区域完全重叠,且最终这些区域都被完全使用。


Base[3] = Base[4], 如果next_node = Children_node[Base[3] + c]我们怎么区分next_node就是从goto(3,c)过来的,还是goto(4, c)过来的呢? (根据Check判断)



再进一步

上面提到,Triple Array Trie满足:

  • Children_node[Base[current_node] + next_char] = next_node

  • Check[Base[current_node] + next_char] = current_node


能否缩少存储,比如去掉Children_node? 考虑到Children_node主要起到记录下一个节点的编号的作用。如果没有事先定义的编号,而把节点标号和数组索引统一,可以减少Children_node数组。或者换一个角度说,构造一个Children_node[x] = x的节点编号系统。


当上述目标达成的时候,我们实际上得到Double Array Trie, 仅通过两个数组Base/Check存储Trie结构:

  • Base[current_node] + next_char = next_node

  • Check[Base[current_node] + next_char] = current_node


上面举例对应的Double Array Trie如下:


可以看到Children_node[x]  = x, 实际编号的Trie树(不存在的节点没有再被编号):


后话

至此,大概描述从Trie到Double Array Trie的一个推演过程。Double Array Trie主要在保证高效查找性能(时间复杂度O(K))的情况下,缩少存储。常应用于静态的Trie树,比如离线构造Trie树供在线查找使用(比如分词程序依赖的词典)。更多的算法细节可以参考文献。


更多内容,欢迎关注公众号: inkfish-talk


 
inkfish 更多文章 从优化的角度看正则项 从贝叶斯的角度看正则项 谈谈分类器的损失函数(1) 谈谈分类器的损失函数(2) 也谈深度残差网络
猜您喜欢 妙用php中的register_shutdown_function和fastcgi_finish_request 关于Docker 1.12中的最新功能,你需要了解这些 比较全面的MySQL优化参考(上篇) 传鸿海已提议收购夏普液晶屏业务 苹果参与投资 【千锋资讯】移动互联网大会视频新鲜出炉!