`
huangwei1024
  • 浏览: 8045 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
文章分类
社区版块
存档分类
最新评论

Double-Array Trie(双数组字典树)

阅读更多

 

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(双数组字典树)

TrieACM中已经十分普及,也是一种非常有效的索引结构,好处就不多说了。

它的本质就是一个确定的有限状态自动机(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

如:有两个单词acda,先插入单词ac,这时的 base 数组

插入单词dad时,发现该地址已被c占用,我们进行重分配

从上图可见ad的位置重新分配了, base 值从0变成了1

假设,Tire里有n个节点,字符集大小为m,则DATrie的空间大小是n+cmc是依赖于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的标记所包含的信息实在太少了。我们利用basecheck数组组成一个双向链表。

定义 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的整理和翻译。

 

3
0
分享到:
评论
2 楼 huangwei1024 2011-03-24  
leogao_emcom 写道
我倒是想了解一下它的应用领域哦

中文词库,或者对字典树进行压缩处理
1 楼 leogao_emcom 2011-03-05  
我倒是想了解一下它的应用领域哦

相关推荐

    双数组 DoubleArray Trie树的数组实现 双数组字典

    双数组Trie(Double-ArrayTrie)是trie树的一个简单而有效的实现,由两个整数数组构成,一个是base[],另一个是check[]。设数组下标为i,如果base[i],check[i]均为0,表示该位置为空。如果base[i]为负值,表示该状态为...

    DoubleArrayTrie(双数组Trie树)

    Trie树,又称“前缀树”或“字典树”,是一种有序树,用于存储关联数组,其中的键通常是字符串。每个内部节点代表一个字符串的前缀,而叶子节点则代表完整的字符串。通过这种方式,Trie树可以快速地查找和插入字符串...

    双数组字典树的-java实现,用于敏感词过滤

    双数组字典树(Double Array Trie,简称DAT)是一种高效的数据结构,主要用于字符串搜索和匹配,尤其在处理大量敏感词过滤的场景下表现突出。它是由日本科学家原望治(Hideo Hiraoka)提出的,相比传统的Trie树,DAT...

    IT笔试面试--Trie树前缀树常考题目及解析

    ##### 双数组(Double-Array) 这是一种高效的Trie树实现方式,通过两个数组来存储节点信息,从而大幅度减少了存储空间的需求。双数组结构包括一个基本数组和一个检查数组,基本数组用来存储节点信息,检查数组用来...

    an efficient implemention of double array trie

    本文档主要介绍了一种高效的字典树(Trie)结构实现方法——双数组字典树(Double Array Trie)。该实现方式旨在结合矩阵形式的快速访问特性和列表形式的紧凑性,从而在减少内存占用的同时保持较高的查询效率。 ###...

    libdatrie_0.1.2.orig.tar.gz_TRIE_double array_double array trie_

    "double array trie" 是双数组Trie的完整表达,它是一种优化的字典树实现,特别适合于大量词汇的快速查找。 **描述分析:** "Double Array Trie 的实现" 描述了libdatrie库的核心功能,即提供了一个双数组Trie的...

    双数组 Trie源码

    **双数组 Trie(Double-Array Trie)源码详解** 在计算机科学中,Trie,也称为前缀树或字典树,是一种用于存储键值对的数据结构,它以高效的键查找速度著称。双数组 Trie(Double-Array Trie,DART)是 Trie 结构的...

    double_array Trie

    Trie,又称前缀树或字典树,是一种高效的字符串搜索数据结构。它是一种数字化的搜索树,由Edward Fredkin于1960年引入,并以“trie”命名,由“retrieval”一词简化而来。Trie可以被视为一种确定性有限自动机(DFA)...

    双数组Trie树算法优化及其应用研究.pdf

    本文主要探讨了一种针对双数组Trie树(Double-Array Trie)算法的优化策略,并通过实验验证了该策略的有效性。双数组Trie树是一种高效的数据结构,常用于构建词典等应用场景中的快速查找。该文提出的新策略是:在...

    这是针对大数据集优化了的双数组字典树,使得在大数据集上构建速度也比较满意,查询速度不随数据集的增加而增加,同时解决了.zip

    双数组字典树(Double Array Trie,简称DAT)是一种高效的数据结构,主要用于字符串的存储和检索。这种数据结构由日本的原田康夫提出,它在处理大量字符串数据时表现出优秀的性能,尤其在查找和前缀匹配方面。本文将...

    java数组-基于java实现的双数组Trie树.zip

    双数组Trie树(Double Array Trie)是Trie树的一种优化实现,由日本的Hideo Bannai和Ichiro Hamana在1992年提出。它通过使用两个数组(一个用于表示字符位置,另一个用于表示子节点位置)来存储树的信息,从而节省...

    DoubleArrayTrie:双端trie树的python实现

    DoubleArrayTrie 双端trie树的python实现 版本翻译于 将其改写成python3.5版本 ...在存储值很多且多有冲突、字符编码范围较大的情况下,双数组Trie树很可能在序列化到硬盘以及加载到内存的占用空间都远大于字典Trie树

    Improved DoubleArrayTrie

    DoubleArrayTrie(DAT),也称为双数组字典树,是一种高效的数据结构,主要用于存储字符串集合,并进行快速的前缀匹配查询。它由日本的Makoto Matsumoto和Takao Nishizeki在1990年代提出,广泛应用于搜索引擎、文本...

    二十六叉字典树

    为了进一步提高Trie树的空间效率和查询速度,引入了双数组Trie(Double-Array Trie)的概念。 - **基本思想**:使用两个线性数组`base[]`和`check[]`来表示Trie树。 - `base[]`:数组中的每个元素对应Trie树中的一个...

    rust-darts:Rust中的Double Array Trie

    Double Array Trie,又称为双数组字典树,是由Takuya Ooura在1990年提出的。它主要适用于字符串搜索和前缀匹配,具有快速查找和插入操作的特性。与传统的Trie(字典树)相比,DART在空间效率和查询速度上有显著优势...

    双数组辞典生成程序

    双数组Trie(Double-Array Trie),也称为Darts,是Trie数据结构的一种优化实现。Trie,又称“前缀树”或“字典树”,是一种用于存储动态集合或关联数组的搜索树,其中每个节点代表一个字符串的前缀。双数组Trie的...

    DoubleArrayTrie:高级结构双数组Trie树(DoubleArrayTrie) java实现

    DoubleArrayTrie Java编写的DoubleArrayTrie介绍用法// construct and buildDoubleArrayTrie dat = new DoubleArrayTrie(); for(String word: words) { dat.Insert(word); } System.out.println(dat.Base.length);...

    字典树 acm 数据结构

    \n\n为了解决这些问题,双数组Trie(Double-Array Trie)应运而生。双数组Trie由Aoe和J提出,它通过两个线性数组base[]和check[]来表示Trie树,极大地降低了空间占用并提升了查询效率。base[]数组中的每个元素代表树...

    17.4-201700301147-杜瀛川-数据结构课程设计大课设报告1

    - **空间优化**:双数组Trie(Double-Array Trie)是一种优化的Trie实现,旨在节省内存。 - **图形化显示**:提供了Trie的可视化界面,便于用户查看和理解数据结构。 - **字典排序**:实现了基于Trie的字典排序,...

    《自然语言处理入门》第02章 词典分词.pptx

    双数组字典树(Double-Array Trie,DAT)是一种更优化的数据结构,用于存储词典并实现高效的搜索操作。 2.6 AC自动机 Aho-Corasick(AC)自动机是在字典树基础上的扩展,能同时处理多个模式串的匹配问题,提高搜索...

Global site tag (gtag.js) - Google Analytics