WisKeyのLullaby

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中已經十分普及，也是一種非常有效的索引結構，好處就不多說了。

它的本質就是一個確定的有限狀態自動機（DFA），關于它的實現也是有好幾種，ACM中用的最多也是最容易實現的就是多路查找樹。

但是Trie最大的缺點就是占用空間過大，很容易爆內存，當然在ACM里對Trie樹也有相應的優化，如限定高度，對分支較少的節點使用非隨機訪問的結構（減少寬度），但這些都是犧牲部分查找效率換取的。

這里介紹一種實現，Double-Array Trie（雙數組字典樹），其實它就是雙數組，跟樹結構沒啥關系。他能在一定程度上減少內存的浪費。

兩個數組，一個是base[]，另一個是check[]。設數組下標為i ，如果base[i], check[i]均為0，表示該位置為空。如果base[i]為負值，表示該狀態為終止態（即詞語）。check[i]表示該狀態的前一狀態。

從定義1中，我們能得到查找算法，對于給定的狀態 s 和輸入字符 c ：

插入的操作，假設以某字符開頭的 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 數組指定的起始下標所決定的。

我們先得到重分配算法：

如：有兩個單詞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代碼，對于字符集表的映射結構也是個需要持續討論的問題，在這個代碼里只支持英文字母。

  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{
 14public:
 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};