发表于 |

前段时间逛论坛，发现了一篇高效的字典树实现论文，很有意思。

常见的字典树实现方法

1
2
3
4
5
6
7
class Node{                            
  uint node ;
  uint[] next;  
};
```                      

或者类似如下结构

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

1
2
3
4
5
6
7
8
9
第一种保证了查找效率，但是对于字典树这种稀疏数组，空间利用率比较低，特别是遇到中文日文这种，会造成空间极大浪费。因此，部分选择了第二种实现，当然第二种可以保证空间，但是却是在牺牲了效率的基础上的改进。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数组虽然

1
2

而我那天看到的论文是在此基础上的改进。论文中配图下的小标题，作者取名为```ReducedTrie

它和原生的双数组字典树的最明显的区别在于，它多了一个tail数组，这个数组的含义就像它的英文含义一样。reducedTrie的base, check数组仅存储前缀部分，而非前缀部分全部放到tail数组中。

那么如何定位tail数组的位置呢？在base数组之中，每个字符串结尾的字符的base值为其后缀在tail的下标的负值。举例说

1
2
3
4
5
6
7
8
9
10

好处很明显，节约了base, check的空间减少了非前缀部分的计算，同样也有缺点，最大的缺点个人觉得是在存储为文件上，由于之前只需要base, check数组，并且是两个数组成对出现，因此很容易将字典树压缩离线存储为一个文件，而tail数组和base, check数组并无关系，因此需要两个文件存储。另一点就是tail数组的碎片太多，这个后面说插入会讲到。

## 具体实现

其实讲了tail数组的作用之后，再结合双数组字典树，就能够很快理解这个结构了。

### insert

插入是比较复杂的部分。分为四种情况处理。论文原文如下

  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
    2

    拙略地翻一下，大致是

1.当数组为空则直接插入新节点.(体现节点为空检查check数组为0即可)
2.没有任何冲突的插入.
3.插入新节点时发生了一种不需要修改base数组，但是必须修改tail和多添加base字符用以解决冲突的冲突。
4.插入新节点发生了类似3的情况，但是base数组的值必须被清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14

如果你实现过双数组字典树，那么你很快就明白了作者所说的冲突原意。如果没有实现过，那么用白话说下来，就是以下两种。

- 当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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

第一种冲突

```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为当前节点位置
  • @param node2为另一个已存在的与node1发生冲突的节点
  • @param newNodeValue为需要插入的节点值

请注意巨坑点 :))))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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这篇原文或者翻译版。

搜索就很简单了，按照文章最开始的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

对于删除操作，只需要找到每个单词最后一个节点，释放它即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

字典树最常见的用途就是前缀匹配和前缀提示，trie树建立成功之后就可以根据输入的前缀去寻找从这个节点出发所有可能的字符串。这里采用深度优先遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
}

总结

好了，还记得之前我所说过这种结构的缺点中的一点是建立过程tail数组的碎片化严重吗？为什么这么说呢，因为在处理第一种冲突的时候，会不断地移动的tail数组，比如bachelor和badge，原本tail数组中是achelor#由于对比a==a成功，所以向左移动一位，chelor?#而这个’?’的部分，就无法被后续的节点插入使用，当然也是有解决办法的，需要在树建立成功之后整块移动。

我在论坛上看到一种看法说这种写法在插入时发生冲突概率这么大，有什么实用性呢？其实这种结构在插入过程慢一点是无所谓的，字典树用途主要看它的查找效率。我们完全可以用长时间建立然后存储每个节点的值，第二次直接读进内存，就可以直接使用，建立过程只需要一次即可。

//第一次码这么多字，好累啊

//不过双数组字典树性能真的很强

测试源代码：ReducedTrie