摘要：另一種高效實現下面介紹另一種實現，它將字典樹用數組存儲起來，不僅壓縮了數組，而且不降低查找效率。這就是雙數組字典樹。

字典樹的心得體會

class Node{                            
  uint node ;
  uint[] next;  
};

或者類似如下結構

class Node{
  uint node;
  map<> next;
}

第一種保證了查找效率，但是對于字典樹這種稀疏數組，空間利用率比較低，特別是遇到中文日文這種，會造成空間極大浪費。因此，部分選擇了第二種實現，當然第二種可以保證空間，但是卻是在犧牲了效率的基礎上的改進。map的查找速度O(logn)肯定不如數組O(1)快。

下面介紹另一種實現，它將字典樹用base, check數組存儲起來，不僅壓縮了數組，而且不降低查找效率。這就是雙數組字典樹(Double array trie) 。這種字典樹原理很簡單，即下面的等式

if (check[base[pre] + string.charAt(i) ] == pre) 
   pre = base[pre] + string.charAt(i) 

對于base和check數組雖然雙數組字典樹論文作者并沒有特意描述它的含義，簡單來說base數組和check數組更像一種父子關系。check數組存儲當前節點的父親節點。

而我那天看到的論文是在此基礎上的改進。論文中配圖下的小標題，作者取名為ReducedTrie
它和原生的雙數組字典樹的最明顯的區別在于，它多了一個tail數組，這個數組的含義就像它的英文含義一樣。reducedTrie的base, check數組僅存儲前綴部分，而非前綴部分全部放到tail數組中。

那么如何定位tail數組的位置呢？在base數組之中，每個字符串結尾的字符的base值為其后綴在tail的下標的負值。舉例說base[10] = -12 不那么說明tail[12]數組之后直到結束字符都是后綴。

好處很明顯，節約了base, check的空間減少了非前綴部分的計算，同樣也有缺點，最大的缺點個人覺得是在存儲為文件上，由于之前只需要base, check數組，并且是兩個數組成對出現，因此很容易將字典樹壓縮離線存儲為一個文件，而tail數組和base, check數組并無關系，因此需要兩個文件存儲。另一點就是tail數組的碎片太多，這個后面說插入會講到。

其實講了tail數組的作用之后，再結合雙數組字典樹，就能夠很快理解這個結構了。

插入是比較復雜的部分。分為四種情況處理。論文原文如下

1. Insertion of the new word when the double-array is empty. 
2. Insertion of the new word without any collisions. 
3. Insertion of the new word with a collision; in this case, additional characters must be added to the BASE and characters must be removed from the TAIL array to resolve the collision, but nothing already in the BASE array must be removed. 
4. When insertion of the new word with a collision as in case 3 occurs, values in the BASE array must be moved.

拙略地翻一下，大致是

1.當數組為空則直接插入新節點.(體現節點為空檢查check數組為0即可)
2.沒有任何沖突的插入.
3.插入新節點時發生了一種不需要修改base數組，但是必須修改tail和多添加base字符用以解決沖突的沖突。
4.插入新節點發生了類似3的情況，但是base數組的值必須被清空

如果你實現過雙數組字典樹，那么你很快就明白了作者所說的沖突原意。如果沒有實現過，那么用白話說下來，就是以下兩種。

當base為負值(base[i] <0 說明此節點為終結點)而需要新插入節點，那么這就算一種沖突，解決這種沖突，必須要對比tail數組。舉個論文中的例子，bachelor與badge，當插入bachelor時，b節點在樹中，achelor都在tail數組中，所以插入badge時候，b節點比對完了，base就為負值了，這時候就需要比對badge的a和tail中的a。由于 a == a 因此直接插入一個新節點就可以繼續走下去了。

那么如果遇到節點不同呢？還是上面的例子，走完a就來到了（c，d）顯然不相等，那么需要新建兩個節點。原理和上面所說的相同。

當base[pre]>0時， 并且check[base[pre] + char ] != pre那么說明發生了需要更改base值的沖突。這種沖突的本質是由于兩個節點的base值相同，因此必須更改其中一個值來解決沖突。需要更改的base的節點就是pre和check[ base[pre] + char] 其中的一個。

那么更改哪一個？選擇從兩個節點中選擇孩子節點少的。因為base值改變了意味著他們的孩子節點的base值也要隨著改變，如果節點的孩子也有孩子暫稱為孫子吧，那么孫子節點的父親也是要更改的。孩子節點有了新值，那么舊值就可以清0了。新節點就可以插入了

但是在這其中有個巨坑的點，就是如果沖突的兩個節點剛好是父子關系，那么一定要更新好父親的下標。

可能上面說的還是不能解惑，那我下面放出具體解決上面兩種沖突的實現代碼

其中xCheck(List list)是從1查找一個的值q，能夠讓list中的任何一個變量x都滿足check[q+x]=0
moveTail(int x)即在x位置開始直到讀到結束字符這段區間內，tail向左移動一位
writeTail(int[] value, int x)從value數組的x位置開始向tail數組寫入。
put(int key, value) 緩存pre節點的孩子
初始化時候base[1] = 1 check[1] = 1

第一種沖突

if (base[pre] < 0) {
    //if current node is an end-point ,then separate or create a new node
    int oldBase = base[pre];
    if (tail[-oldBase] == keyValue[i]) {
        //create a new node
        base[pre] = xCheck(keyValue[i]);
        base[ base[pre]+keyValue[i] ] = oldBase;
        check[ base[pre]+keyValue[i] ] = pre;
        put(pre, keyValue[i]);
        moveTail(-oldBase);
        pre = base[pre] + keyValue[i];
        continue;
    } else {
        //separate
        List list = new ArrayList<>();
        list.add(tail[-oldBase]); list.add(keyValue[i]);
        base[pre] = xCheck(list);
        base[ base[pre]+tail[-oldBase] ] = oldBase;
        base[ base[pre]+keyValue[i] ] = -position;
        check[ base[pre]+tail[-oldBase] ] = check[ base[pre]+keyValue[i] ] = pre;
        writeTail(keyValue, i+1);
        put(pre, tail[-oldBase]);
        put(pre, keyValue[i]);
        moveTail(-oldBase);
        break;// 2 new nodes
    }
} 

第二種沖突

@param node1為當前節點位置

@param node2為另一個已存在的與node1發生沖突的節點

@param newNodeValue為需要插入的節點值

請注意巨坑點 :))))

public int processConflict(int node1, int node2, int newNodeValue) {
    int node = (lists[node1].size()+1) < lists[node2].size() ? node1 : node2;
    int oldNodeBase = base[node];
    if (node == node1) {
        base[node] = xCheck(lists[node], newNodeValue);
    } else {
        base[node] = xCheck(lists[node]);
    }
    for (int i = 0; i < lists[node].size(); i++) {
        int oldNext = oldNodeBase + lists[node].get(i);
        int newNext = base[node] + lists[node].get(i);
        if (oldNext == node1) node1 = newNext;//巨坑點
        base[newNext] = base[oldNext];
        check[newNext] = node;
        if (base[oldNext] > 0) {
            for (int j = 0; j < lists[oldNext].size(); j++) {
                check[ base[oldNext] + lists[oldNext].get(j) ] = newNext;
                put(newNext, lists[oldNext].get(j));
            }
            lists[oldNext] = null;
        }
        base[oldNext] = 0; check[oldNext] = 0;
    }
    base[ base[node1] + newNodeValue ] = -position;
    check[ base[node1] + newNodeValue ] = node1;
    put(node1, newNodeValue);
    return node;
}

如果你還是有所疑惑，建議閱讀An Efficient Implementation of Trie Structures這篇原文或者翻譯版。

搜索就很簡單了，按照文章最開始的

public boolean search(int[] key) {
    int pre = 1;
    for (int i = 0; i < key.length; i++) {
        if (base[pre] < 0) {
            return compareTail(-base[pre], i, key);
        } else if (base[pre] > 0) {
            if (check[ base[pre] + key[i] ] == pre) {
                pre = base[pre] + key[i];
            } else {
                return false;
            }
        } else return false;
    }
    return true;
}

對于刪除操作，只需要找到每個單詞最后一個節點，釋放它即可。

public boolean delete(String key) {
    int []keyValue = string2IntArray(key);
    int pre = 1;
    int index = -1;
    int tempVal;
    int next;
    do {
        index++;
        tempVal = keyValue[index];
        next = base[pre] + tempVal;
        if (check[next] != pre)  {
            return false;
        }
        if (base[next] < 0) break;
        pre = next;
    } while (true);
    if (tempVal == END_FLAG || compareTail(-base[next], index+1, keyValue)) {
        for (int i = 0; i < lists[pre].size(); i++) {
            if (lists[pre].get(i) == tempVal) {
                lists[pre].remove(i);break;
            }
        }
        base[next] = 0; check[next] = 0;
        //info(String.format("%s next[%d] turn to 0",key, next));
        return true;
    }
    return false;
}

字典樹最常見的用途就是前綴匹配和前綴提示，trie樹建立成功之后就可以根據輸入的前綴去尋找從這個節點出發所有可能的字符串。這里采用深度優先遍歷。

private void find( int pre, StringBuilder builder, List list) {
    int next;
    if (base[pre] < 0) {
        builder.append(readTail(-base[pre]));
        list.add(builder.toString());
        return;
    }
    for (int i = 0; i < lists[pre].size(); i++) {
        next = base[pre] + lists[pre].get(i);
        StringBuilder reserved = new StringBuilder(builder.toString());
        if (check[next] == pre) {
            if (lists[pre].get(i) == END_FLAG) {
                find(next, builder, list);
            } else {
                find(next, builder.append((char) lists[pre].get(i).intValue()), list);
            }
        }
        builder = reserved;
    }
}

好了，還記得之前我所說過這種結構的缺點中的一點是建立過程tail數組的碎片化嚴重嗎？為什么這么說呢，因為在處理第一種沖突的時候，會不斷地移動的tail數組，比如bachelor和badge，原本tail數組中是achelor#由于對比a==a成功，所以向左移動一位，chelor?#而這個"?"的部分，就無法被后續的節點插入使用，當然也是有解決辦法的，需要在樹建立成功之后整塊移動。

我在論壇上看到一種看法說這種寫法在插入時發生沖突概率這么大，有什么實用性呢？其實這種結構在插入過程慢一點是無所謂的，字典樹用途主要看它的查找效率。我們完全可以用長時間建立然后存儲每個節點的值，第二次直接讀進內存，就可以直接使用，建立過程只需要一次即可。

測試源代碼：ReducedTrie