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/
Trie在ACM中已經(jīng)十分普及，也是一種非常有效的索引結(jié)構(gòu)，好處就不多說(shuō)了。
它的本質(zhì)就是一個(gè)確定的有限狀態(tài)自動(dòng)機(jī)（DFA），關(guān)于它的實(shí)現(xiàn)也是有好幾種，ACM中用的最多也是最容易實(shí)現(xiàn)的就是多路查找樹(shù)。
但是Trie最大的缺點(diǎn)就是占用空間過(guò)大，很容易爆內(nèi)存，當(dāng)然在ACM里對(duì)Trie樹(shù)也有相應(yīng)的優(yōu)化，如限定高度，對(duì)分支較少的節(jié)點(diǎn)使用非隨機(jī)訪問(wèn)的結(jié)構(gòu)（減少寬度），但這些都是犧牲部分查找效率換取的。
這里介紹一種實(shí)現(xiàn)，Double-Array Trie（雙數(shù)組字典樹(shù)），其實(shí)它就是雙數(shù)組，跟樹(shù)結(jié)構(gòu)沒(méi)啥關(guān)系。他能在一定程度上減少內(nèi)存的浪費(fèi)。
兩個(gè)數(shù)組，一個(gè)是base[]，另一個(gè)是check[]。設(shè)數(shù)組下標(biāo)為i ，如果base[i], check[i]均為0，表示該位置為空。如果base[i]為負(fù)值，表示該狀態(tài)為終止態(tài)（即詞語(yǔ)）。check[i]表示該狀態(tài)的前一狀態(tài)。
定義 1. 對(duì)于輸入字符 c, 從狀態(tài) s 轉(zhuǎn)移到狀態(tài) t, 雙數(shù)組字典樹(shù)滿足如下條件:
從定義1中，我們能得到查找算法，對(duì)于給定的狀態(tài) s 和輸入字符 c ：
插入的操作，假設(shè)以某字符開(kāi)頭的 base 值為i，第二個(gè)字符的字符序列碼依次為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。
我們知道雙數(shù)組的實(shí)現(xiàn)方法是當(dāng)狀態(tài)有新轉(zhuǎn)移時(shí)才分配空間給新?tīng)顟B(tài)，或可以表述為只分配需要轉(zhuǎn)移的狀態(tài)的空間。當(dāng)遇到無(wú)法滿足上述條件時(shí)再進(jìn)行調(diào)整，使得其 base 值滿足上述條件，這種調(diào)整只影響當(dāng)前節(jié)點(diǎn)下一層節(jié)點(diǎn)的重分配，因?yàn)樗泄?jié)點(diǎn)的地址分配是靠 base 數(shù)組指定的起始下標(biāo)所決定的。
我們先得到重分配算法：
Procedure Relocate(s : state; b : base_index) |
foreach input character c for the state s |
base[b + c] := base[base[s] + c]; |
foreach input character d for the node base[s] + c |
check[base[base[s] + c] + d] := b + c |
check[base[s] + c] := none |
如：有兩個(gè)單詞ac和da，先插入單詞ac，這時(shí)的 base 數(shù)組
插入單詞da的d時(shí)，發(fā)現(xiàn)該地址已被c占用，我們進(jìn)行重分配
從上圖可見(jiàn)a和d的位置重新分配了， base 值從0變成了1。
假設(shè)，Tire里有n個(gè)節(jié)點(diǎn)，字符集大小為m，則DATrie的空間大小是n+cm，c是依賴于Trie稀疏程度的一個(gè)系數(shù)。而多路查找樹(shù)的空間大小是nm。
注意，這里的復(fù)雜度都是按離線算法（offline algorithm）計(jì)算的，即處理時(shí)已經(jīng)得到整個(gè)詞庫(kù)。在線算法（online algorithm）的空間復(fù)雜度還和單詞出現(xiàn)的順序有關(guān)，越有序的單詞順序空間占用越小。
查找算法的復(fù)雜度和被查找的字符串長(zhǎng)度相關(guān)的，這個(gè)復(fù)雜度和多路查找樹(shù)是一樣的。
插入算法中，如果出現(xiàn)重分配的情況，我們要附加上掃描子節(jié)點(diǎn)的時(shí)間復(fù)雜度，還有新base值確定的算法復(fù)雜度。假如這兒我們都是用暴力算法（for循環(huán)掃描），那插入算法時(shí)間復(fù)雜度是O(nm + cm2)。。
實(shí)際編碼過(guò)程中，DATrie代碼難度大過(guò)多路查找樹(shù)，主要是狀態(tài)的表示不如樹(shù)結(jié)構(gòu)那樣的清晰，下標(biāo)很容易搞混掉。
有個(gè)地方需要注意的是，base值正數(shù)表示起始偏移量，負(fù)數(shù)表示該狀態(tài)為終止態(tài)，所以在查找新base值時(shí)，要保證查到的值是正數(shù)。
如：空Trie狀態(tài)下，插入d時(shí)，因?yàn)榈谝粋€(gè)空地址是1，所以得到base=1-4=-3，這樣base正負(fù)的含義就被破壞了。
關(guān)于優(yōu)化：
- 查找空地址優(yōu)化
base[i], check[i]均為0，表示該位置為空。我們可以把這部分給利用起來(lái)，全為0的標(biāo)記所包含的信息實(shí)在太少了。我們利用base和check數(shù)組組成一個(gè)雙向鏈表。
定義 2. 設(shè) r1, r2, … ,rcm 為空閑地址有序序列，則我們的雙向鏈表可定義為 :
check[r[i]] = -r[i+1] ; 1 <= i <= cm-1 |
base[r[i+1]] = -r[i] ; 1 <= i <= cm-1 |
由于我們把base[0]作為根節(jié)點(diǎn)，所以初始化時(shí)就可以把base[0]排除在鏈表之外，而check[0]可以被作為鏈表的頭節(jié)點(diǎn)。
設(shè)節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移集為P = {c1, c2, …, cp}，依靠鏈表我們能得到新的空地址查找算法：
while s <> 0 and s <= c[1] do |
if s = 0 then return FAIL; |
while i <= p and check[s + c[i] - c[1]] < 0 do |
if i = p + 1 then return s - c[1]; |
優(yōu)化后的空地址查找算法時(shí)間復(fù)雜度為O(cm2)，而重分配算法的時(shí)間復(fù)雜度為O(m2)，則總的時(shí)間復(fù)雜度為O(cm2 + m2) = O(cm2)。
重分配或刪除節(jié)點(diǎn)后，原先的地址被作廢，可以重新加入鏈表，這樣如果遇到原狀態(tài)轉(zhuǎn)移集的子集時(shí)，就可以派上用場(chǎng)了。
其實(shí)這部分的優(yōu)化就是使用了閑置信息域做成了鏈表，所以這部分的插入和刪除優(yōu)化原理就很容易理解了，時(shí)間復(fù)雜度為O(cm)。
while check[t] <> 0 and t < s do |
- 數(shù)組長(zhǎng)度的壓縮
當(dāng)有節(jié)點(diǎn)刪除時(shí)，我們不僅可以把它加回到鏈表中，還可以重新為最大非空節(jié)點(diǎn)的狀態(tài)重新確定base值，因?yàn)閯h除可能導(dǎo)致它的前面有空間容納下它的狀態(tài)轉(zhuǎn)移集。這樣我們可能又得以刪除一些空值狀態(tài)，使得數(shù)組長(zhǎng)度有希望被壓縮。
- 字符后綴的壓縮
這個(gè)思想借鑒于后綴樹(shù)，我們可以將沒(méi)有分支的后綴單獨(dú)存放，但這個(gè)結(jié)構(gòu)肯定獨(dú)立于DATrie，所以在這就不詳述了。詳情見(jiàn)[Aoe1989]。
整體而言，在ACM中，DATrie略高的編碼復(fù)雜度和過(guò)低的插入效率，應(yīng)用面不會(huì)太廣。但現(xiàn)實(shí)問(wèn)題中，詞庫(kù)大小一般比較穩(wěn)定，在離線算法也有很大的優(yōu)化余地，此時(shí)DATrie的空間優(yōu)勢(shì)就會(huì)比較明顯。畢竟Trie高效的檢索效率這一優(yōu)點(diǎn)是值得研究探討的。
這篇日志寫(xiě)的夠長(zhǎng)了，等有空再把DATrie測(cè)試報(bào)告給整理下吧。唉，發(fā)現(xiàn)自己語(yǔ)言組織能力越來(lái)越差了，寫(xiě)的連自己有時(shí)都看不下去，要多堅(jiān)持記下技術(shù)日志了～～
以下是只加入空地址查找優(yōu)化后的DATrie代碼，對(duì)于字符集表的映射結(jié)構(gòu)也是個(gè)需要持續(xù)討論的問(wèn)題，在這個(gè)代碼里只支持英文字母。
1
#define ALPHASIZE 30
2#define MAX 10000
3#define ALPHAID(x) (1+x-'a')
4#define IDALPHA(x) (x-1+'a')
5#define EMPTY(x) (basei[x] < 0 && check[x] < 0)
6#define DELETE_FREE_NODE(x) check[-basei[x]] = check[x]; \
7 basei[-check[x]] = basei[x]; \
8 maxsize = max(maxsize, x)
9#define ADD_FREE_NODE(x) basei[x] = MAX; \
10 check[x] = MAX; \
11 abnodes ++
12class DATire
13
{
14
public:
15
void init() {
16 // double circular linked list (except 0)
17 for (int i = 1; i < MAX; i ++) {
18 check[i] = -(i+1);
19 basei[i] = -(i-1);
20
}
21 basei[1] = 0; // so check[0] can be updated
22 check[MAX-1] = 1;
23 // basei[0] is root-index
24 // check[0] point to first free cell
25 basei[0] = 0;
26 check[0] = -1;
27 // stat
28 diffwords = 0;
29 maxsize = 0;
30 nodes = 1;
31 abnodes = 0;
32 }
33 void print(int s, char* buf, int d) {
34 if (basei[s] < 0)
35 puts(buf);
36 int si = abs(basei[s]);
37 for (int i = si+1; i <= si + ALPHASIZE; i ++) {
38 if (check[i] == s) {
39 buf[d] = IDALPHA(i-si); buf[d+1] = '\0';
40 print(i, buf, d+1);
41 buf[d] = '\0';
42 }
43 }
44 }
45 bool insert(string word) {
46 int s = 0, t;
47 for (int i = 0; i < word.length(); i ++) {
48 char ch = word[i];
49 t = abs(basei[s]) + ALPHAID(ch);
50 if (s == check[t])
51 s = t;
52 else if (EMPTY(t)) {
53 DELETE_FREE_NODE(t);
54 basei[t] = t;
55 check[t] = s;
56 s = t;
57 nodes ++;
58 }
59 else {
60 int newb = findb(s, ALPHAID(ch));
61 if (newb == -1)
62 return false;
63 else {
64 relocate(s, newb);
65 i --;
66 }
67 }
68 }
69 if (basei[s] > 0)
70 diffwords ++;
71 basei[s] = -abs(basei[s]);
72 return true;
73 }
74 bool find(string word) {
75 int s = 0, t;
76 int i;
77 for (i = 0; i < word.length(); i ++) {
78 char ch = word[i];
79 t = abs(basei[s]) + ALPHAID(ch);
80 if (s == check[t])
81 s = t;
82 else
83 break;
84 }
85 return (i == word.length() && basei[s] < 0);
86 }
87protected:
88 int findb(int s, int newc) {
89 ns = 0;
90 int i, j;
91 int si = abs(basei[s]);
92 for (i = si+1; i <= si + ALPHASIZE; i ++) {
93 if (check[i] == s)
94 sonc[ns ++] = i - si;
95 }
96 sonc[ns ++] = newc;
97 int minson = min(sonc[0], newc);
98 // i < si, the new place must be after old place
99 // i < minson, the negative base value has other meaning
100 for (i = -check[0]; i != 0 && (i < si || i < minson); i = -check[i]) ;
101 for (; i != 0; i = -check[i]) {
102 for (j = 0; j < ns; j ++) {
103 if (! EMPTY(i + sonc[j] - minson))
104 break;
105 }
106 if (j == ns) {
107 ns --;
108 assert(i - minson >= 0);
109 return i - minson;
110 }
111 }
112 return -1;
113 }
114 void relocate(int s, int b) {
115 for (int i = ns-1; i >= 0; i --) {
116 int news = b + sonc[i];
117 int olds = abs(basei[s]) + sonc[i];
118 DELETE_FREE_NODE(news);
119 check[news] = s;
120 basei[news] = basei[olds];
121 int isi = abs(basei[olds]);
122 for (int j = isi+1; j <= isi + ALPHASIZE; j ++) {
123 if (check[j] == olds)
124 check[j] = news;
125 }
126 ADD_FREE_NODE(olds);
127 }
128 basei[s] = (basei[s] < 0 ? -1 : 1) * b;
129 }
130protected:
131 int basei[MAX];
132 int check[MAX];
133 // helper
134 int sonc[ALPHASIZE];
135 int ns;
136public:
137 // stat
138 int maxsize; // used memory size
139 int nodes; // trie nodes
140 int abnodes; // abandoned trie nodes
141 int diffwords; // diff words
142 // free nodes = maxsize-nodes-abnodes
143
};