压缩trie

缘起

经过前面几篇文章的论述，我们已经知道了标准trie这种数据结构以及它的具体运用. 但是同时我们也指出了它的弊端——比较吃内存. 所以为了克服这个缺点同时又不影响算法效率. 压缩trie横空出世.

所谓压缩trie算法的思想是, 例如2个单词 monkey 和 moon, 则构建标准trie的时候，他俩在 mo 往后开始分叉. 但是整棵trie中, mon往后就是唯一的了, 所以完全可以将”nkey”这四个单词压缩进入”n”这个节点. 同理，我们也可以将”on”压缩进入”o”这个节点，这就是压缩trie. 万言不及一图

显然，压缩trie并不会影响trie的查询效率（所以如果比赛的时候不卡空间的话，傻瓜才会去用压缩trie）, 但是标准trie的空间复杂度为O(NL), n是单词的个数，L是每个单词的字符数量的上限. 而压缩trie的空间复杂度为O(N). 所以能节省很多空间.

为了阐释本算法，依旧使用 hdu 1251 统计难题 为板题. 它生成压缩trie的过程其实可以以下图说明

​ 图1

上图中的圈圈中的数字就是下面程序中的cnt域. 下面的图画了两个单词彼此有覆盖的情形

​ 图2

图2左半部分的”ey”就是下面代码中的 newNode

其实完全可以把压缩trie理解为一种惰性延展. 就跟线段树打延迟标记一样

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
//#include "stdafx.h"

#include <stdio.h>
#include <string>
//#define LOCAL
//获取子节点的宏展开
#define GETCHILD(i) p->next[key[i]-'a']

const int SIZE =26, MAX_N = 15; // 每个单词最多MAX_N个字符, trie树是26叉树
char key[400005]; // 输入的单词

typedef struct TrieNode
{
	char str[MAX_N]; // 参见图, 可知压缩trie的节点存储的可能不是一个一个的字符，而可能是一个字符串, 所以使用字符数组存储trie节点的数据
	int cnt; // 以当前节点为前缀的单词的个数
	TrieNode *next[SIZE]; // 26个孩子
	TrieNode():cnt(1) {memset(next, 0, sizeof(next)),str[0] = 0;}
} TrieNode, *Trie;

Trie root = new TrieNode; // 根节点

int insert(int flag) // flag为0表示插入, flag=1表示查询
{
	Trie p = root;
	int i = 0,y; // y是下一次key要移动到的地方
	while(key[i])
	{
		if (GETCHILD(i)) // 如果目前有此分支
		{
			int x = 0; // str域的索引,因为要开始进行字符串比较
			y = i;
			if (!flag) // 如果是插入的话
			{
				GETCHILD(i)->cnt++; // 以当前节点为前缀的单词的数量+1
				while(key[y]&&GETCHILD(i)->str[x]&&key[y]==GETCHILD(i)->str[x]) y++,x++; // 开始考虑分裂问题
				if (GETCHILD(i)->str[x]) // 如果GETCHILD的str还有多, 则就需要分裂GETCHILD了,就是图2的左半部分，对应图3
				{
					Trie newNode = new TrieNode; // GETCHILD 分裂出来的新节点
					memcpy(newNode->str, (GETCHILD(i)->str)+x, strlen((GETCHILD(i)->str+x))+1); // +1 是为了拷贝一个 0过来
					newNode->cnt = GETCHILD(i)->cnt-1; // 因为一开始GETCHILD的cnt域+1了
					memcpy(newNode->next, GETCHILD(i)->next, sizeof(GETCHILD(i)->next)); // newNode接管了GETCHILD的所有孩子
					memset(GETCHILD(i)->next, 0, sizeof(GETCHILD(i)->next)); // GETCHILD的孩子清空(因为已经由newNode接管了)
					GETCHILD(i)->next[GETCHILD(i)->str[x]-'a'] = newNode; // GETCHILD唯一的孩子变成了newNode
					GETCHILD(i)->str[x] = 0; // GETCHILD的str变少了
				}
			}
			else // 如果是询问的话, 就要和GETCHILD节点的str 进行对比
			{
				while(key[y]&&GETCHILD(i)->str[x] && key[y]==GETCHILD(i)->str[x]) x++,y++;
				if (!key[y]) return GETCHILD(i)->cnt; // 如果key消耗殆尽
				else if (GETCHILD(i)->str[x]) return 0; // 如果key没有消耗殆尽, 而且 GETCHILD(i)->str[x] 也没有消耗殆尽
			}
		}
		else // 如果没有此分支
		{
			if (!flag) // 如果是插入
			{
				GETCHILD(i) = new TrieNode;
				memcpy(GETCHILD(i)->str,key+i, strlen(key+i)+1); // 将key剩下的全部字符全部拷贝进此节点的str中(这就是压缩trie), +1的原因是把\0也拷贝过去
			}
			return 0; // 以此单词为前缀的单词数量为0,不论询问还是插入, 都要返回了.
		}
		p = GETCHILD(i); // 跳到下一个节点
		i = y; // 再下一次决定跳哪儿,就要用y了, 不能像标准trie那样一步一步的跳动了(标准trie是++).
	}
	return 0; // 其实走不到这里
}

void del(Trie &root)
{
	if (!root) return;
	for (int i = 0; i<SIZE; i++)del(root->next[i]);
	delete root;
	root = 0;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	while(gets(key), key[0]) insert(0);
	while(gets(key)) printf("%d\n",insert(1));
	del(root);
	return 0;
}

ac情况

Status Accepted
Time 109ms
Memory 16908kB
Length 2536
Lang C++
Submitted 2019-07-24 12:01:05
RemoteRunId 29864486

和【1】相比, 时间并没有什么突出的.突出的是内存的使用. 【1】中内存的使用达到了惊人的45668kB，而这里缩减到了1/3. 足见压缩trie的威力. 而且值得高兴的事情是, 我把原先压缩trie的代码从100+行优化到了40+行. 可以说是比较高质量的代码了.

下面还是画几幅有关上述代码的图示

​ 图3

参考

【1】https://yfsyfs.github.io/2019/07/21/hdu-1251-%E7%BB%9F%E8%AE%A1%E9%9A%BE%E9%A2%98-trie/