标准trie树应用之串的快速检索

缘起

trie树又称为字典树、前缀树. 它是AC自动机算法的基础（关于AC自动机后面我会写文章）. 不过说到这里，我不得不补充一下，为什么字符串算法在算法中的地位那么的高? 因为不论计算机技术发展的如何日新月异，高速迅猛. 软件技术离不开三件东西

  1. 编译原理
  2. 操作系统
  3. 网络原理

而它们三者之基石就是无关具体技术，而纯在思想层面的——数据结构和算法（足见数据结构和算法之重要性）. 而编译原理其实就是在处理规则化的人类语言——高级编程语言（如C/C++、Java、Python等等），将高级编程语言变成机器可以“懂”的语言. 这个过程（不论是生成机器码的过程还是生成机器码的执行的过程）关系到代码的高效程度（也就是所谓代码的质量）. 所以你说字符串算法重不重要? 字符串算法往大了说，就是展示、解析、转换信息的算法. 人类的文明无不是建立在信息的基础之上. 在海量信息的今天，高效字符串处理——不论是不是计算机层面的，都日益重要. 我是不是逼话多了点?

它的典型应用如下

1
2
给定n个单词组成熟词表T，以及一篇全用英文小写字母组成的文章，请你按照最早出现的顺序写出所有不在T中的生
词.

分析

算法很简单，就是使用T中的单词组成一棵标准trie树, 然后顺次读入文章中的单词，一旦发现它不在trie中，就输出它再将它插如到trie中（则后面继续出现此单词就不会输出它了, 即不会重复输出了）

这里首先要介绍一下trie树这种数据结构. 万言不如一图. 例如，使用 gkm, abc, abcd,abd, abce, ack, ac, acke, ackf, acgh ,adm这11个单词建立trie树如下

其中，用圈圈住的表示一个单词的结尾. 可见，trie是一棵多叉树. 本例是26叉树

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

#include <stdio.h>
#include <algorithm>
#include <cstdlib>
#define LOCAL

using namespace std;

const int SIZE = 26, MAX_N = 16; // SIZE 是26个英文字母，即每个trie节点的出度都有26, 而MAX_N表示单词的字母个数最多16个.

typedef struct TrieNode
{
	int ch; // 本节点的字符(使用int表示字符是个好习惯)
	TrieNode *next[SIZE]; // 指向下一个节点的指针
	bool end; // 是否是一个单词的终结, 这个域千变万化, 这也早就了trie的灵活
	TrieNode(int ch=0):ch(ch),end(false) {memset(next, 0, sizeof(next));}
}TrieNode,*Trie;

void init(Trie &root) // 初始化trie
{
	root = new TrieNode;
}

void insert(Trie root, char *key, int flag) // key 是需要插入的单词, flag=0表示是使用T构造trie的过程, flag=1表示是后面读取文章单词的的过程，两者区别在于后者在没有发现的时候需要输出单词,前者不需要
{
	Trie p = root; // 移动指针
	int i = 0;
	while(key[i])
	{
		if (!p->next[key[i]-'a']) p->next[key[i]-'a'] = new TrieNode(key[i]); // 如果尚未建立节点的话, 就开辟
		p = p->next[key[i]-'a']; // 跑到下一个节点
		i++;
	}
	if (!p->end) // 说明trie中尚未有此单词
	{
		if (flag) puts(key); // 其实如果是软件工程做项目的话, 应该将flag设置为一个私有域, 然后暴露设置它的接口, 但是这是算法题, 就算了
		p->end = true;
	}
}

void del(Trie &root) // 递归删除整棵trie,一般情况下Trie树中很少存在删除单独某个结点的情况，因此只考虑删除整棵树。(这可能是因为Trie树源自哈希树，而哈希树也不进行物理删除操作，删除最多也只是懒惰删除)
{
	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);
#endif
	Trie root = 0;
	init(root);
	int t;
	scanf("%d", &t); // t个熟词
	char key[100];
	while(t--)
	{
		scanf("%s", key);
		insert(root, key, 0);
	}
	while(~scanf("%s", key)) insert(root, key, 1); // 读取剩下的文章
	return 0;
}
/*
测试数据
25 i when of a is and to when very school balcony book here trees read corners attracts and special in the which i when balcony
our school is very beautiful  when i walk into the main gate  i can see a lot of green trees and colorful flowers  i find a special corner  which attracts me a lot  the corner is covered by tall trees and i can sit in the balcony  i like to read books or chatting with my friends here  we talk happily  i have so much fun here  
*/

trie的强大之处就在于它的时间复杂度，它插入和查询的时间都是O(k), k是插入和查询的key的长度. 其实和哈希表相比，trie在时间复杂度上是有优势的——hash这种结构号称是O(1)的，但其实不论是查找还是插入，总要计算哈希值吧? 其实计算的复杂度就已经是O(k)了，而且相比trie，还要考虑哈希冲突的问题. 所以其实哈希表比trie是要差的，但是trie的缺点也很明显——就是占用内存比较多（毕竟，连冲突都不需要处理）. 因为是多叉树.