双数组字典树

发表于 分类于 ， ， 阅读次数： 本文字数： 4.6k 阅读时长 ≈ 4 分钟

0. 前置知识

需要提前有字典树的知识

1. 双数组字典树介绍

双数组字典树英文名为DoubleArrayTrie，他的特点就是使用两个数组来表示一颗字典树，这里有比较有趣了，两个数组是怎么表达出字典树的呢？

2. 双数组介绍

顾名思义，有两个数组，一个是base，另一个是check。

首先介绍数组的下标，数组的下标代表字典树上节点的编号，一个下标对应一个节点。

其实base数组的作用是用来记录一个基础值，这个值可以是随机值，只要不产生冲突就可以了，所以这个值可以用随机数算法获取，当然这样效率不高，高效的做法应该是使用指针枚举技术，ok，现在你已经明白了，base数组是一个不产生冲突的随机数组。

最后，check数组，check数组与base数组相互照应，如果base[i]=check[j] 则说明j是i的儿子，而且i到j的边权恰好为j-base[i]，也可以写作j-check[j]好好理解这句话

从另一个方面而言，双数组字典树的base数组，应该是一个指针数组，他指向了一个长度为字符集大小的数组的首地址，而check数组是一种hash碰撞思路，由于base数组疯狂指向自己，导致产生了很多碰撞，但是由于字典树是一个稀疏图，导致儿子节点指针利用率低，所以base数组疯狂复用这段空间，最后必须要依赖check来解决冲突，

双数组字典树相比于传统字典树，仅仅只在内存方面于增删改查占有优势，但是唯一不好的地方就是删和改会导致base数组内存分裂，难以回收，删和改如果占大头，那么传统字典树的内存效率更高

由于搜索领域几乎不涉及到删和改，所以这个数据结构很nice，字符集多大，就节省了多少倍的空间

数据结构很棒，但是在现在这个内存不值钱的时代，这些指针的储存用hashmap直接无脑顶掉，空间占用也高不了多少，hashmap顶多浪费两倍空间

两倍的空间算不上啥，除非这是唯一的优化点，否则不会优化到这个数据结构上来

3. 图解双数组字典树

首先我们直接给出一颗双数组字典树，下面是三列，第一列是下标，第二列是base，第三列是check， 我们来根据这个双数组还原那颗字典树

1
2
3
4
5
6
7
8
9
10
11
12
13
index base check
0 1 0
66 2 1
68 3 1
69 5 2
70 6 2
71 7 3
73 8 3
74 10 5
75 11 5
81 12 11
85 9 4
91 4 1

从第一行看起，base[0]=1, check[0]=0 ,这说明根节点是0号节点。

graph LR
  0

然后我们来找0节点的子节点，只需要哪些check值为base[0]即可，我们发现check[66],check[68],check[91]满足，所以他们都是0号节点的子节点

对于check[66], 边权为66-check[66]=65 ,是字符A

对于check[68], 边权67, 是字符C

对于check[91], 边权90，是字符Z

所以现在图成了

graph LR
  0--A-->66
  0--C-->68
  0--Z-->91

接着我们看66号节点，base[66]=2,那么他的子节点为69和70，边权分别为69-check[69]=67,70-check[70]=68,分别是C和D

graph LR
  0--A-->66
  0--C-->68
  0--Z-->91
  66--C-->69
  66--D-->70

69的字节点为74和75， 权重为74-5=69和75-5=70， 分别是E和F

graph LR
  0--A-->66
  0--C-->68
  0--Z-->91
  66--C-->69
  66--D-->70
  69--E-->74
  69--F-->75

当然，后面的笔者就不进行模拟了，到此为止。

4. 双数组字典树的构建算法

首先算法的第一步是构建一颗字典树，你需要将这颗字典树构建出来。字典树的代码如下,这个不用多说了

1
2
3
4
5
6
7
8
9
void addTire(const char* str, int len) {
    int root = 1;
    for (int i = 0; i < len; i++) {
        if (tire[root][str[i]] == 0) {
            tire[root][str[i]] = ++tireTot;
        }
        root = tire[root][str[i]];
    }
}

第二步，就是在字典树上进行BFS，在BFS过程中增量构建双数组字典树，当我们BFS到某个节点U的时候，便开始寻找，当前还有哪个base值没有被使用，可以使得这个U的子节点的check值均为0， no BB , show code

先找到U的所有子节点

1
2
3
4
5
6
7
8
vector<int> sonTransList;
for (int i = 0;i < maxCharest;i++) {
    if (tire[tireTop][i] != 0) {
        sonTransList.push_back(i);
        tireQ.push(tire[tireTop][i]);
    }
}
cout << "find son: " << sonTransList.size() << endl;;

然后寻找一个合适的base值，这个值储存在变量begin中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// find begin
while (true) {
    begin++;
    bool ok = true;
    for (int son : sonTransList) {
        if (check[begin + code[son]] != 0) {
            ok = false;
            break;
        }
    }
    if (ok) {
        break;
    }
}

最后就是赋值就好了.

5. 代码

最后附上一个很丑的代码，第三节中介绍的双数组就来源于这个代码的输出。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// ConsoleApplication1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <queue>
#include <iostream>
#include <string>
using namespace std;

string stringData[] = {
        "AC",
        "ACE",
        "ACFF",
        "AD",
        "CD",
        "CF",
        "ZQ"
};



const int maxCharest = 256;
int tire[1000][maxCharest], tireTot = 1;

void addTire(const char* str, int len) {
    int root = 1;
    for (int i = 0; i < len; i++) {
        if (tire[root][str[i]] == 0) {
            tire[root][str[i]] = ++tireTot;
        }
        root = tire[root][str[i]];
    }
}


int code[maxCharest];

void buildDAT() {
    // init code
    for (int i = 0;i < maxCharest;i++) {
        code[i] = i;
    }
    vector<int> tireState2DatState(1000);

    // TODO vector
    vector<int> check(1000), base(1000);

    // bfs
    queue<int> tireQ;
    tireQ.push(1);
    tireState2DatState[1] = 0;

    int begin = 0;

    while (!tireQ.empty()) {
        int tireTop = tireQ.front();
        tireQ.pop();

        vector<int> sonTransList;
        for (int i = 0;i < maxCharest;i++) {
            if (tire[tireTop][i] != 0) {
                sonTransList.push_back(i);
                tireQ.push(tire[tireTop][i]);
            }
        }
        cout << "find son: " << sonTransList.size() << endl;;

        // find begin
        while (true) {
            begin++;
            bool ok = true;
            for (int son : sonTransList) {
                if (check[begin + code[son]] != 0) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                break;
            }
        }

        base[tireState2DatState[tireTop]] = begin;
        for (int i = 0;i < maxCharest;i++) {
            if (tire[tireTop][i] != 0) {
                int son = i;
                if (check[begin + code[son]] != 0) {
                    exit(-1);
                }
                check[begin + code[son]] = begin;
                tireState2DatState[tire[tireTop][i]] = begin + code[son];
            }
        }
        for (int i = 0;i < 1000;i++) {
            if (check[i] != 0 || base[i] != 0) {
                cout << i << " " << base[i] << " " << check[i] << endl;
            }
        }
        cout <<begin<<"--------" << endl;
    }

  
}


int main() {

    for (int i = 0;i < 7;i++) {
        addTire(stringData[i].data(), stringData[i].size());
    }
    buildDAT();


}