双数组trie树介绍

转自：http://blog./2010/07/15/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，第二个字符的字符序列码依次为c₁, c₂, c₃…c_n，则肯定要满足base[i+c₁], check[i+c₁], base[i+c₂], check[i+c₂], base[i+c₃], check[i+c₃]…base[i+c_n],check[i+c_n]均为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 + cm²)。。

实际编码过程中，DATrie代码难度大过多路查找树，主要是状态的表示不如树结构那样的清晰，下标很容易搞混掉。
有个地方需要注意的是，base值正数表示起始偏移量，负数表示该状态为终止态，所以在查找新base值时，要保证查到的值是正数。
如：空Trie状态下，插入d时，因为第一个空地址是1，所以得到base=1-4=-3，这样base正负的含义就被破坏了。

关于优化：

1. 查找空地址优化

base[i], check[i]均为0，表示该位置为空。我们可以把这部分给利用起来，全为0的标记所包含的信息实在太少了。我们利用base和check数组组成一个双向链表。

定义 2. 设 r₁, r₂, … ,r_cm 为空闲地址有序序列，则我们的双向链表可定义为 :

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 = {c₁, c₂, …, c_p}，依靠链表我们能得到新的空地址查找算法：

{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(cm²)，而重分配算法的时间复杂度为O(m²)，则总的时间复杂度为O(cm² + m²) = O(cm²)。

重分配或删除节点后，原先的地址被作废，可以重新加入链表，这样如果遇到原状态转移集的子集时，就可以派上用场了。
其实这部分的优化就是使用了闲置信息域做成了链表，所以这部分的插入和删除优化原理就很容易理解了，时间复杂度为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;

2. 数组长度的压缩

当有节点删除时，我们不仅可以把它加回到链表中，还可以重新为最大非空节点的状态重新确定base值，因为删除可能导致它的前面有空间容纳下它的状态转移集。这样我们可能又得以删除一些空值状态，使得数组长度有希望被压缩。

3. 字符后缀的压缩

这个思想借鉴于后缀树，我们可以将没有分支的后缀单独存放，但这个结构肯定独立于DATrie，所以在这就不详述了。详情见[Aoe1989]。

整体而言，在ACM中，DATrie略高的编码复杂度和过低的插入效率，应用面不会太广。但现实问题中，词库大小一般比较稳定，在离线算法也有很大的优化余地，此时DATrie的空间优势就会比较明显。毕竟Trie高效的检索效率这一优点是值得研究探讨的。
这篇日志写的够长了，等有空再把DATrie测试报告给整理下吧。唉，发现自己语言组织能力越来越差了，写的连自己有时都看不下去，要多坚持记下技术日志了～～

以下是只加入空地址查找优化后的DATrie代码，对于字符集表的映射结构也是个需要持续讨论的问题，在这个代码里只支持英文字母。

001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156

#define ALPHASIZE               30 #define MAX                     10000 #define ALPHAID(x)              (1+x-'a') #define IDALPHA(x)              (x-1+'a') #define EMPTY(x)                (basei[x] < 0 && check[x] < 0) #define DELETE_FREE_NODE(x)     check[-basei[x]] = check[x]; /                                 basei[-check[x]] = basei[x]; /                                 maxsize = max(maxsize, x) #define ADD_FREE_NODE(x)        basei[x] = MAX; /                                 check[x] = MAX; /                                 abnodes ++ class DATire { public:     void init() {         // double circular linked list (except 0)         for (int i = 1; i < MAX; i ++) {             check[i] = -(i+1);             basei[i] = -(i-1);         }         basei[1] = 0; // so check[0] can be updated         check[MAX-1] = 1;         // basei[0] is root-index         // check[0] point to first free cell         basei[0] = 0;         check[0] = -1;         // stat         diffwords = 0;         maxsize = 0;         nodes = 1;         abnodes = 0;     }     void print(int s, char* buf, int d) {         if (basei[s] < 0)             puts(buf);         int si = abs(basei[s]);         for (int i = si+1; i <= si + ALPHASIZE; i ++) {             if (check[i] == s) {                 buf[d] = IDALPHA(i-si); buf[d+1] = '/0';                 print(i, buf, d+1);                 buf[d] = '/0';             }         }     }     bool insert(string word) {         int s = 0, t;         for (int i = 0; i < word.length(); i ++) {             char ch = word[i];             t = abs(basei[s]) + ALPHAID(ch);             if (s == check[t])                 s = t;             else if (EMPTY(t)) {                 DELETE_FREE_NODE(t);                 basei[t] = t;                 check[t] = s;                 s = t;                 nodes ++;             }             else {                 int newb = findb(s, ALPHAID(ch));                 if (newb == -1)                     return false;                 else {                     relocate(s, newb);                     i --;                 }             }         }         if (basei[s] > 0)             diffwords ++;         basei[s] = -abs(basei[s]);         return true;     }     bool find(string word) {         int s = 0, t;         int i;         for (i = 0; i < word.length(); i ++) {             char ch = word[i];             t = abs(basei[s]) + ALPHAID(ch);             if (s == check[t])                 s = t;             else                 break;         }         return (i == word.length() && basei[s] < 0);     } protected:     int findb(int s, int newc) {         ns = 0;         int i, j;         int si = abs(basei[s]);         for (i = si+1; i <= si + ALPHASIZE; i ++) {             if (check[i] == s)                 sonc[ns ++] = i - si;         }         sonc[ns ++] = newc;         int minson = min(sonc[0], newc);         // i < si, the new place must be after old place         // i < minson, the negative base value has other meaning         for (i = -check[0]; i != 0 && (i < si || i < minson); i = -check[i]) ;         for (; i != 0; i = -check[i]) {             for (j = 0; j < ns; j ++) {                 if (! EMPTY(i + sonc[j] - minson))                     break;             }             if (j == ns) {                 ns --;                 assert(i - minson >= 0);                 return i - minson;             }         }         return -1;     }     void relocate(int s, int b) {         for (int i = ns-1; i >= 0; i --) {             int news = b + sonc[i];             int olds = abs(basei[s]) + sonc[i];             DELETE_FREE_NODE(news);             check[news] = s;             basei[news] = basei[olds];             int isi = abs(basei[olds]);             for (int j = isi+1; j <= isi + ALPHASIZE; j ++) {                 if (check[j] == olds)                     check[j] = news;             }             ADD_FREE_NODE(olds);         }         basei[s] = (basei[s] < 0 ? -1 : 1) * b;     } protected:     int basei[MAX];     int check[MAX];     // helper     int sonc[ALPHASIZE];     int ns; public:     // stat     int maxsize;    // used memory size     int nodes;      // trie nodes     int abnodes;    // abandoned trie nodes     int diffwords;  // diff words                     // free nodes = maxsize-nodes-abnodes };

本文是对《An Implementation of Double-Array Trie》的整理和翻译。