字符串匹配之字典树与双数组字典树

admin 管理员组

文章数量: 1087652

字符串匹配之字典树与双数组字典树

字典树：

姓名：
Trie
曾用名：
字典树 ；单词查找树
也叫前缀索引树
把每个字符串按照前缀的顺序插入到树形结构中
作用：
单词查找 ；字符串排序：时间复杂度位 O ( n ) O(n) O(n)

根节点：整本字典
根节点的子节点：按照前后顺序，分别存储a.b.c.d…当该字母在本树中，没有引申出来的单词，也可能不存在该字母
子节点分红白两色
红色：可以与根节点独立成词
白色：不可与根节点独立成词
也就是红色节点的数量就是单词的数量

字典树如何做字符串排序？
答：将字符串插入到字典树中，然后进行深度优先遍历，得到的字符串就是排好序的
时间复杂度为O(n)

正式字典树插入写法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BASE 26typedef struct Node {int flag;struct Node *next[BASE];
} Node;Node *getNewNode() {Node *p = (Node *)malloc(sizeof(Node));p->flag = 0;memset(p->next, 0, sizeof(p->next));return p;
}void insert(Node *p, const char *s) {for (int i = 0; s[i]; i++) {int ind = s[i] - 'a';if (p->next[ind] == NULL) p->next[ind] = getNewNode();p = p->next[ind];}p->flag = 1;return ;
}void clear(Node *root) {if (root == NULL) return ;for (int i = 0; i < BASE; i++) {clear(root->next[i]);}free(root);return ;
}void output(Node *root, int k, char *s) {s[k] = 0;if (root->flag) {printf("%s\n", s);}for (int i = 0; i < BASE; i++) {if (root->next[i] == NULL) continue;s[k] = 'a' + i;output(root->next[i], k + 1, s);}return ;
}int main() {int n;char str[100];scanf("%d", &n);Node *root = getNewNode();for (int i = 0; i < n; i++) {scanf("%s", str);insert(root, str);}output(root, 0, str);clear(root);return 0;
}

练习题：
最大异或对
异或运算的性质：二进制位不同
如果想要最大，那么求得异或的位数尽量不一样，
所以尽可能让第一位不一样，然后尽可能让第二位不一样，以此类推（贪心）

把每一位看成一个二进制串，插入到字典树中去，如果有不同的边走，就去不同的边，否则去相同的边

代码演示
算法，以及面试写法

#include<iostream>
using namespace std;
#define MAX_N 100000
#define BASE 31
struct Node{Node *next[2];
} tree[MAX_N * BASE + 5];int cnt = 0;Node *getNode() {return &tree[cnt++];
}void insert(Node *root, int x) {for (int i = 30; i >= 0; i--) {int ind = !!(x & (1 << i));//归一化if (root->next[ind] == NULL) root->next[ind] = getNode();root = root->next[ind];}return ;
}int query(Node *root, int x) {int ans = 0;for (int i = 30; i >= 0; i--) {int ind = !(x & (1 << i));if (root->next[ind]) {ans |= (1 << i);root = root->next[ind];} else {root = root->next[!ind];}}return ans;
}int n;
int val[MAX_N + 5];
int main() {cin >> n;int ans = 0, a;cin >> a;n--;Node *root = getNode();insert(root, a);while (n--) {cin >> a;ans = max(query(root, a), ans);insert(root, a);}cout << ans << endl;return 0;
}

思考：如何使得异或结果尽可能大
结论：参与异或运算的两个数字，参与异或运算的每一位尽可能不同
问题转换为：确定一个数字的情况下，找到从高位到低位与当前数字尽量不同的另外一个数字
把每个数字看成一个二进制字符串，插入到字符串中，采用贪心策略

双数组字典树

作用：
实现离线存储结构
动态插入极其浪费时间，只做查询操作

回忆：完全二叉树结构
问：完全二叉树是程序上的数据结构还是逻辑思维上的数据结构
答：思维逻辑的树形结构：对应到程序中是一段连续的数组空间

问：完全二叉树在程序实现方面相比于普通的二叉树有什么好处？
答：节省空间：不需要左右子树的地址，只要知道当前位置的地址就知道左右子树的地址
记录式改计算式 ： 好处： 节省空间

在原来字典树中，假设有n个字典，理论上需要n - 1 条边，但是实际上却是k * n 条边，k可能等于26 ，可能等于52（字符），如果有中文就会很疯狂，所以原来字典树的弊端就是浪费大量的存储空间
所以应运而生了双数组字典树：
双数组字典树借鉴了完全二叉树的思想，父节点和子节点的关系可以通过计算得到的，
结论：双数组字典树中根本不存储边的信息

双数组字典树

1. 顾名思义：两个数组代表一棵字典树结构
2. base 数组信息于子节点编号相关，base + i就是第i 个子节点编号
3. check 数组信息负责做【亲子鉴定】，check数组中用正负表示是否独立成词
4. 不擅长进行动态插入操作
5. 一次建立，终身使用
6. 为了方便，基于普通字典树实现的双数组字典树
7. 增加了fail 数组，可以完成基于双数组字典树的AC自动机
8. 超小规模实验结果：双数组子弟阿叔压缩效率是25 倍
9. 非常方便的输出到文件中，进行机器之间的共享

假如3号节点的base值是6 5号节点的base值是10
那么3号节点的第5个节点和5号节点的第1个节点都是11
那么通过check数组来确定11的父亲是谁

记录是否独立成词：
check数组里面的值都是正值（不用0节点）
如果独立成词，该点check值记录为负值

代码演示：
输出结果为check 和 base 数组

#include<iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
using namespace std;#define BASE 26
typedef struct Node {int flag;struct Node *next[BASE];
} Node;typedef struct DBNode {int base, check;
} DANode;Node *getNewNode() {Node *p = (Node *)malloc(sizeof(Node));p->flag = 0;memset(p->next, 0, sizeof(p->next));return p;
}inline int code(char c) {return c - 'a';}int insert(Node *root, const char *str) {int cnt = 0;Node *p = root;for (int i = 0 ; str[i]; i++) {int ind = code(str[i]);if (p->next[ind] == NULL) {p->next[ind] = getNewNode();cnt++;}p = p->next[ind];}p->flag = 1;return cnt;
}void clear_trie(Node *root) {if (root == NULL) return ;for (int i = 0; i < BASE; i++) {clear_trie(root->next[i]);}free(root);return ;
}int get_base_value(Node *root, DANode *tree, int ind) {int base = 1, flag;do {base += 1;flag = 1;for (int i = 0; i < BASE && flag; i++) {if (root->next[i] == NULL) continue;if (tree[base + i].check) flag = 0;//不等于0，说明该店已经被占用了}} while (flag == 0);return base;
}int transform_double_array_trie(Node *root, DANode *tree, int ind) {if (root == NULL) return 0;if (root->flag) tree[ind].check = -tree[ind].check;int base = get_base_value(root, tree, ind);tree[ind].base = base;for (int i = 0; i < BASE; i++) {if (root->next[i] == NULL) continue;tree[base + i].check = ind;}int max_ind = ind;for (int i = 0; i < BASE; i++) {int a = transform_double_array_trie(root->next[i], tree, base + i);if (a > max_ind) max_ind = a;}return max_ind;
}int main() {int n, cnt = 0;char str[1000];scanf("%d", &n);Node *root = getNewNode();for (int i = 0; i < n; i++) {scanf("%s", str);cnt += insert(root, str);}//整个字典树有cnt 个节点size_t tree_size = sizeof(DANode) * (cnt * BASE);DBNode *tree = (DANode *)malloc(tree_size);memset(tree,0, tree_size);int max_ind = transform_double_array_trie(root, tree, 1);//将字典树转换为双数组字典树,最后一个变量时下标for (int i = 0; i <= max_ind; i++) {printf("(%d | %d, %d)\t", i, tree[i].base, tree[i].check);if ((i + 1) % 4 == 0) printf("\n");}printf("\n");free(tree);clear_trie(root);return 0;
}

可以利用真实数据集，测试双数组字典树的压缩效率

二叉字典树：

1. 计算机中所有信息都是二进制存储的
2. 任何信息都可以看成一个二进制串
3. 插入二进制串的字典树，就是二叉字典树
4. 二叉字典树可以存储任意信息
5. 节省空间，浪费时间，本质：时间换空间的算法思维
6. 哈夫曼编码 + 二叉字典树更配，既节省了空间，又在最大限度上节省了查找时间

本文标签： 字符串匹配之字典树与双数组字典树