前段時(shí)間逛論壇图甜，發(fā)現(xiàn)了一篇高效的字典樹(shù)實(shí)現(xiàn)論文，很有意思叮称。

簡(jiǎn)書(shū)專用圖

常見(jiàn)的字典樹(shù)實(shí)現(xiàn)方法

class Node{                            
  uint node ;
  uint[] next;  
};```                      
或者類似如下結(jié)構(gòu)

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

第一種保證了查找效率，但是對(duì)于字典樹(shù)這種稀疏數(shù)組，空間利用率比較低笼痹，特別是遇到中文日文這種，會(huì)造成空間極大浪費(fèi)酪穿。因此凳干，部分選擇了第二種實(shí)現(xiàn)，當(dāng)然第二種可以保證空間被济，但是卻是在犧牲了效率的基礎(chǔ)上的改進(jìn)救赐。map的查找速度```O(logn)```肯定不如數(shù)組```O(1)```快。
####另一種高效實(shí)現(xiàn)
下面介紹另一種實(shí)現(xiàn)只磷，它將字典樹(shù)用base, check數(shù)組存儲(chǔ)起來(lái)经磅，不僅壓縮了數(shù)組，而且不降低查找效率钮追。這就是雙數(shù)組字典樹(shù)(Double array trie) 预厌。這種字典樹(shù)原理很簡(jiǎn)單，即下面的等式

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

對(duì)于base和check數(shù)組雖然```雙數(shù)組字典樹(shù)```論文作者并沒(méi)有特意描述它的含義元媚，簡(jiǎn)單來(lái)說(shuō)base數(shù)組和check數(shù)組更像一種父子關(guān)系轧叽。check數(shù)組存儲(chǔ)當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)苗沧。

而我那天看到的論文是在此基礎(chǔ)上的改進(jìn)。論文中配圖下的小標(biāo)題犹芹，作者取名為```ReducedTrie```
它和原生的雙數(shù)組字典樹(shù)的最明顯的區(qū)別在于崎页，它多了一個(gè)tail數(shù)組，這個(gè)數(shù)組的含義就像它的英文含義一樣腰埂。reducedTrie的base, check數(shù)組僅存儲(chǔ)前綴部分飒焦，而非前綴部分全部放到tail數(shù)組中。

那么如何定位tail數(shù)組的位置呢屿笼？在base數(shù)組之中牺荠，每個(gè)字符串結(jié)尾的字符的base值為其后綴在tail的下標(biāo)的負(fù)值。舉例說(shuō)```base[10] = -12 ```不那么說(shuō)明```tail[12]```數(shù)組之后直到結(jié)束字符都是后綴驴一。

好處很明顯肿孵，節(jié)約了base, check的空間減少了非前綴部分的計(jì)算璃弄，同樣也有缺點(diǎn)喳坠，最大的缺點(diǎn)個(gè)人覺(jué)得是在存儲(chǔ)為文件上丈钙，由于之前只需要base, check數(shù)組，并且是兩個(gè)數(shù)組成對(duì)出現(xiàn)胸懈，因此很容易將字典樹(shù)壓縮離線存儲(chǔ)為一個(gè)文件担扑，而tail數(shù)組和base, check數(shù)組并無(wú)關(guān)系，因此需要兩個(gè)文件存儲(chǔ)趣钱。另一點(diǎn)就是tail數(shù)組的碎片太多涌献，這個(gè)后面說(shuō)插入會(huì)講到。
####具體實(shí)現(xiàn)
其實(shí)講了tail數(shù)組的作用之后首有，再結(jié)合雙數(shù)組字典樹(shù)燕垃，就能夠很快理解這個(gè)結(jié)構(gòu)了。
##### insert
插入是比較復(fù)雜的部分井联。分為四種情況處理卜壕。論文原文如下
```
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.當(dāng)數(shù)組為空則直接插入新節(jié)點(diǎn).(體現(xiàn)節(jié)點(diǎn)為空檢查check數(shù)組為0即可)
2.沒(méi)有任何沖突的插入.
3.插入新節(jié)點(diǎn)時(shí)發(fā)生了一種不需要修改base數(shù)組烙常，但是必須修改tail和多添加base字符用以解決沖突的沖突印叁。
4.插入新節(jié)點(diǎn)發(fā)生了類似3的情況，但是base數(shù)組的值必須被清空
```
如果你實(shí)現(xiàn)過(guò)雙數(shù)組字典樹(shù)军掂，那么你很快就明白了作者所說(shuō)的沖突原意。如果沒(méi)有實(shí)現(xiàn)過(guò)昨悼，那么用白話說(shuō)下來(lái)蝗锥，就是以下兩種。

- 當(dāng)base為負(fù)值(base[i] <0 說(shuō)明此節(jié)點(diǎn)為終結(jié)點(diǎn))而需要新插入節(jié)點(diǎn)率触，那么這就算一種沖突终议，解決這種沖突，必須要對(duì)比tail數(shù)組。舉個(gè)論文中的例子穴张，bachelor與badge细燎，當(dāng)插入bachelor時(shí)，b節(jié)點(diǎn)在樹(shù)中皂甘，achelor都在tail數(shù)組中玻驻，所以插入badge時(shí)候，b節(jié)點(diǎn)比對(duì)完了偿枕，base就為負(fù)值了璧瞬，這時(shí)候就需要比對(duì)badge的a和tail中的a。由于``` a == a ```因此直接插入一個(gè)新節(jié)點(diǎn)就可以繼續(xù)走下去了渐夸。

  那么如果遇到節(jié)點(diǎn)不同呢嗤锉？還是上面的例子，走完a就來(lái)到了（c墓塌，d）顯然不相等瘟忱，那么需要新建兩個(gè)節(jié)點(diǎn)。原理和上面所說(shuō)的相同苫幢。

- 當(dāng)base[pre]>0時(shí)访诱， 并且check[base[pre] + char ] != pre那么說(shuō)明發(fā)生了需要更改base值的沖突。這種沖突的本質(zhì)是由于兩個(gè)節(jié)點(diǎn)的base值相同态坦，因此必須更改其中一個(gè)值來(lái)解決沖突盐数。需要更改的base的節(jié)點(diǎn)就是pre和check[ base[pre] + char] 其中的一個(gè)。

 那么更改哪一個(gè)伞梯？選擇從兩個(gè)節(jié)點(diǎn)中選擇孩子節(jié)點(diǎn)少的玫氢。因?yàn)閎ase值改變了意味著他們的孩子節(jié)點(diǎn)的base值也要隨著改變，如果節(jié)點(diǎn)的孩子也有孩子```暫稱為孫子吧```谜诫，那么```孫子```節(jié)點(diǎn)的父親也是要更改的漾峡。孩子節(jié)點(diǎn)有了新值，那么舊值就可以清0了喻旷。新節(jié)點(diǎn)就可以插入了

 但是在這其中有個(gè)巨坑的點(diǎn)生逸，就是如果沖突的兩個(gè)節(jié)點(diǎn)剛好是父子關(guān)系，那么一定要更新好父親的下標(biāo)且预。

可能上面說(shuō)的還是不能解惑槽袄，那我下面放出具體解決上面兩種沖突的實(shí)現(xiàn)代碼
```
其中xCheck(List list)是從1查找一個(gè)的值q，能夠讓list中的任何一個(gè)變量x都滿足check[q+x]=0
moveTail(int x)即在x位置開(kāi)始直到讀到結(jié)束字符這段區(qū)間內(nèi)锋谐，tail向左移動(dòng)一位
writeTail(int[] value, int x)從value數(shù)組的x位置開(kāi)始向tail數(shù)組寫(xiě)入遍尺。
put(int key, value) 緩存pre節(jié)點(diǎn)的孩子
初始化時(shí)候base[1] = 1 check[1] = 1
```
第一種沖突
```java
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<Integer> 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為當(dāng)前節(jié)點(diǎn)位置
- @param node2為另一個(gè)已存在的與node1發(fā)生沖突的節(jié)點(diǎn)
- @param newNodeValue為需要插入的節(jié)點(diǎn)值

請(qǐng)注意巨坑點(diǎn) :))))
```java
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;//巨坑點(diǎn)
        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這篇原文或者翻譯版涮拗。
##### search
搜索就很簡(jiǎn)單了乾戏，按照文章最開(kāi)始的
```
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;
}
```
##### delete
對(duì)于刪除操作迂苛，只需要找到每個(gè)單詞最后一個(gè)節(jié)點(diǎn)，釋放它即可鼓择。
```$java
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;
}
```
##### usage
字典樹(shù)最常見(jiàn)的用途就是前綴匹配和前綴提示三幻，trie樹(shù)建立成功之后就可以根據(jù)輸入的前綴去尋找從這個(gè)節(jié)點(diǎn)出發(fā)所有可能的字符串。這里采用深度優(yōu)先遍歷呐能。
```java
private void find( int pre, StringBuilder builder, List<String> 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;
    }
}
```

#### 總結(jié)
好了念搬，還記得之前我所說(shuō)過(guò)這種結(jié)構(gòu)的缺點(diǎn)中的一點(diǎn)是建立過(guò)程tail數(shù)組的碎片化嚴(yán)重嗎？為什么這么說(shuō)呢催跪，因?yàn)樵谔幚淼谝环N沖突的時(shí)候锁蠕，會(huì)不斷地移動(dòng)的tail數(shù)組，比如bachelor和badge懊蒸，原本tail數(shù)組中是achelor#由于對(duì)比```a==a```成功荣倾，所以向左移動(dòng)一位，chelor?#而這個(gè)'?'的部分骑丸，就無(wú)法被后續(xù)的節(jié)點(diǎn)插入使用舌仍，當(dāng)然也是有解決辦法的，需要在樹(shù)建立成功之后整塊移動(dòng)通危。

我在論壇上看到一種看法說(shuō)這種寫(xiě)法在插入時(shí)發(fā)生沖突概率這么大铸豁，有什么實(shí)用性呢？其實(shí)這種結(jié)構(gòu)在插入過(guò)程慢一點(diǎn)是無(wú)所謂的菊碟，字典樹(shù)用途主要看它的查找效率节芥。我們完全可以用長(zhǎng)時(shí)間建立然后存儲(chǔ)每個(gè)節(jié)點(diǎn)的值，第二次直接讀進(jìn)內(nèi)存逆害，就可以直接使用头镊，建立過(guò)程只需要一次即可。

//第一次碼這么多字魄幕，好累啊

//不過(guò)雙數(shù)組字典樹(shù)性能真的很強(qiáng)

測(cè)試源代碼：[ReducedTrie](https://github.com/saltyx/ReducedTrie)