http://blog.huang-wei.com/2010/07/15/double-array-trie%EF%BC%88%E5%8F%8C%E6%95%B0%E7%BB%84%E5%AD%97%E5%85%B8%E6%A0%91%EF%BC%89/
Double-Array
Trie(双数组字典树)
Trie在ACM中已经十分普及,也是一种非常有效的索引结构,好处就不多说了。
它的本质就是一个确定的有限状态自动机(DFA),关于它的实现也是有好几种,ACM中用的最多也是最容易实现的就是多路查找树。
但是Trie最大的缺点就是占用空间过大,很容易爆内存,当然在ACM里对Trie树也有相应的优化,如限定高度,对分支较少的节点使用非随机访问的结构(减少宽度),但这些都是牺牲部分查找效率换取的。
这里介绍一种实现,Double-Array Trie(双数组字典树),其实它就是双数组,跟树结构没啥关系。他能在一定程度上减少内存的浪费。
两个数组,一个是base[],另一个是check[]。设数组下标为i ,如果base[i], check[i]均为0,表示该位置为空。如果base[i]为负值,表示该状态为终止态(即词语)。check[i]表示该状态的前一状态。
定义 1. 对于输入字符 c, 从状态 s 转移到状态 t, 双数组字典树满足如下条件:
check[base[s] + c] = s
base[s] + c = t
|
从定义1中,我们能得到查找算法,对于给定的状态 s 和输入字符 c :
t := base[s] + c;
if check[t]
= s then
next
state := t
else
fail
endif
|
插入的操作,假设以某字符开头的 base 值为i,第二个字符的字符序列码依次为c1,
c2, c3…cn,则肯定要满足base[i+c1], check[i+c1], base[i+c2], check[i+c2], base[i+c3], check[i+c3]…base[i+cn],check[i+cn]均为0。
我们知道双数组的实现方法是当状态有新转移时才分配空间给新状态,或可以表述为只分配需要转移的状态的空间。当遇到无法满足上述条件时再进行调整,使得其 base 值满足上述条件,这种调整只影响当前节点下一层节点的重分配,因为所有节点的地址分配是靠 base 数组指定的起始下标所决定的。
我们先得到重分配算法:
Procedure Relocate(s : state; b : base_index)
{ Move base for state s to a
new place beginning at b }
begin
foreach
input character c for the state s
{
i.e. foreach c such that check[base[s] + c]] = s }
begin
check[b
+ c] := s; { mark owner }
base[b
+ c] := base[base[s] + c]; { copy data }
{
the node base[s] + c is to be moved to b + c;
Hence,
for any i for which check[i] = base[s] + c, update check[i] to b + c }
foreach
input character d for the node base[s] + c
begin
check[base[base[s]
+ c] + d] := b + c
end;
check[base[s]
+ c] := none { free the cell }
end;
base[s]
:= b
end
|
如:有两个单词ac和da,先插入单词ac,这时的 base 数组
插入单词da的d时,发现该地址已被c占用,我们进行重分配
从上图可见a和d的位置重新分配了, base 值从0变成了1。
假设,Tire里有n个节点,字符集大小为m,则DATrie的空间大小是n+cm,c是依赖于Trie稀疏程度的一个系数。而多路查找树的空间大小是nm。
注意,这里的复杂度都是按离线算法(offline
algorithm)计算的,即处理时已经得到整个词库。在线算法(online algorithm)的空间复杂度还和单词出现的顺序有关,越有序的单词顺序空间占用越小。
查找算法的复杂度和被查找的字符串长度相关的,这个复杂度和多路查找树是一样的。
插入算法中,如果出现重分配的情况,我们要附加上扫描子节点的时间复杂度,还有新base值确定的算法复杂度。假如这儿我们都是用暴力算法(for循环扫描),那插入算法时间复杂度是O(nm +
cm2)。。
实际编码过程中,DATrie代码难度大过多路查找树,主要是状态的表示不如树结构那样的清晰,下标很容易搞混掉。
有个地方需要注意的是,base值正数表示起始偏移量,负数表示该状态为终止态,所以在查找新base值时,要保证查到的值是正数。
如:空Trie状态下,插入d时,因为第一个空地址是1,所以得到base=1-4=-3,这样base正负的含义就被破坏了。
关于优化:
<!--[if !supportLists]-->1. <!--[endif]-->查找空地址优化
base[i], check[i]均为0,表示该位置为空。我们可以把这部分给利用起来,全为0的标记所包含的信息实在太少了。我们利用base和check数组组成一个双向链表。
定义 2. 设 r1,
r2, … ,rcm 为空闲地址有序序列,则我们的双向链表可定义为 :
check[0] = -r[1]
check[r[i]] = -r[i]+1 ; 1 <= i <= cm-1
check[r[cm]] = 0
base[0] = -r[cm]
base[r[1]] = 0
base[r[i+1]] = -r[i] ; 1 <= i <= cm-1
|
由于我们把base[0]作为根节点,所以初始化时就可以把base[0]排除在链表之外,而check[0]可以被作为链表的头节点。
设节点的状态转移集为P = {c1, c2,
…, cp},依靠链表我们能得到新的空地址查找算法:
{find least free cell s such
that s > c[1]}
s := -check[0];
while s <> 0 and s <= c[1] do
s :=
-check[s]
end;
if s = 0 then return FAIL; {or reserve some additional
space}
{continue searching for the
row, given that s matches c[1]}
while s <> 0 do
i :=
2;
while i <= p and check[s + c[i] - c[1]] < 0 do
i
:= i + 1
end;
if i = p + 1 then return s - c[1]; {all
cells required are free, so return it}
s :=
-check[-s]
end;
return FAIL; {or
reserve some additional space}
|
优化后的空地址查找算法时间复杂度为O(cm2),而重分配算法的时间复杂度为O(m2),则总的时间复杂度为O(cm2 + m2) = O(cm2)。
重分配或删除节点后,原先的地址被作废,可以重新加入链表,这样如果遇到原状态转移集的子集时,就可以派上用场了。
其实这部分的优化就是使用了闲置信息域做成了链表,所以这部分的插入和删除优化原理就很容易理解了,时间复杂度为O(cm)。
t := -check[0];
while check[t] <> 0 and t < s
do
t :=
-check[t]
end;
{t now points to the cell
after s' place}
check[s] := -t;
check[-base[t]] := -s;
base[s] := base[t];
base[t] := -s;
|
<!--[if !supportLists]-->2. <!--[endif]-->数组长度的压缩
当有节点删除时,我们不仅可以把它加回到链表中,还可以重新为最大非空节点的状态重新确定base值,因为删除可能导致它的前面有空间容纳下它的状态转移集。这样我们可能又得以删除一些空值状态,使得数组长度有希望被压缩。
<!--[if !supportLists]-->3. <!--[endif]-->字符后缀的压缩
这个思想借鉴于后缀树,我们可以将没有分支的后缀单独存放,但这个结构肯定独立于DATrie,所以在这就不详述了。详情见[Aoe1989]。
整体而言,在ACM中,DATrie略高的编码复杂度和过低的插入效率,应用面不会太广。但现实问题中,词库大小一般比较稳定,在离线算法也有很大的优化余地,此时DATrie的空间优势就会比较明显。毕竟Trie高效的检索效率这一优点是值得研究探讨的。
这篇日志写的够长了,等有空再把DATrie测试报告给整理下吧。唉,发现自己语言组织能力越来越差了,写的连自己有时都看不下去,要多坚持记下技术日志了~~
以下是只加入空地址查找优化后的DATrie代码,对于字符集表的映射结构也是个需要持续讨论的问题,在这个代码里只支持英文字母。
+ expand source
本文是对《An Implementation of
Double-Array Trie》的整理和翻译。
相关推荐
double-array-trie原理与算法实现探索,dat算法分析
基于Double-Array Trie树的垃圾邮件过滤器的php扩展,它可以检测短信中是否存在...过滤关键词扩展,用于检查一段文本中是否出现敏感词,基于Double-Array Trie树实现。 更多详情、使用方法,请下载后阅读README.md文件
双数组Trie(Double-ArrayTrie)是trie树的一个简单而有效的实现,由两个整数数组构成,一个是base[],另一个是check[]。设数组下标为i,如果base[i],check[i]均为0,表示该位置为空。如果base[i]为负值,表示该状态为...
支持从构建Double-Array,将磁盘上的字典减少为Trie的一半。 查找性能提高了25%。 待办事项清单 文档/评论 基准 从unicode切换到字节版本 gofmt -tabs=false -tabwidth=4 -r= ' rune /*Key_type*/ -> byte /*Key_...
对双数纽Trie 树(Double-Array Trie)分词算法进行了优化:在采用Trie 树构造 双数纽Trie 树的过程中,优先处理分支节点多的结点,以减少冲突;构造一个空状态序列; 将冲突的结点放入Hash表中,不需要重新分配...
darts, Double-Array Trie System. ver 0.32. Linux/Unix.
darts-clone-java 用Java编写的Double-ARray Trie System克隆。 该库基于称为“快速高效”库的 。入门设置要使用Maven添加依赖项,请使用以下命令: < dependency> < groupId>...
double_array Trie 敏感词过滤系统 算法 敏感词过滤 trie double_array Trie
关键词过滤扩展,用于检查一段文本中是否出现敏感词,基于 Double-Array Trie 树实现。 依赖环境 PHP 7 + libdatrie (Version >= 0.2.4) 安装 因为本项目依赖于 libdatrie, 所以需要先安装 , 再安装本扩展。 $ wget ...
Double Array Trie是TRIE树的一种变形,它是在保证TRIE树检索速度的前提下,提高空间利用率而提出的一种数据结构,本质上是一个确定有限自动机(deterministic finite automaton,简称DFA)。 所谓的DFA就是一个能实现...
IT笔试面试--Trie树前缀树常考题目及解析,包含了Trie树的常考题目,以及详细的解析
本程序实现了以上5个要求,实验报告是根据Trie树的学习与实现过程而写的。 内含源代码 适合人群:想要了解trie树的程序员 能学到什么:Trie树是一种比较独特的数据结构。它对于字符串的搜索有比较高的效率。尤其在...
aho-corasick-node 基于DoubleArray Trie的Aho-Corasick字符串匹配算法的Node实现。安装npm install aho-corasick-node --save用法建造const AhoCorasick = require ( 'aho-corasick-node' ) ;const keywords = [ 'b...
为了提高性能并减少内存使用,该程序使用Double Array Trie而不是常用的Linked List Trie 。 在基准测试中, it is 10 times faster than the most popular AC algorithm implement in golang @ github and tenth ...
ACM Trie树 模板,字典树模板,数据结构
Double Array Trie 的实现
提出一种基于双数组trie树的多模式复杂事件检测方法,通过构建多模式匹配自动机模型减少查询过程中冗余的检测和计算,并利用双数组trie树充分压缩存储空间,从而提高了复杂事件处理的效率。仿真实验表明,提出的方案...
前端开源库-doublearray双数组trie的Doublearray、javascript实现
这个是一个double-array的实现,就是用数组来存储trie,以减少空间的利用率。
对双数组Trie树(Double-Array Trie)分词算法进行了优化:在采用Trie树构造双数组Trie树的过程中,优先处理分支节点多的结点,以减少冲突;构造一个空状态序列;将冲突的结点放入Hash表中,不需要重新分配结点.然后...