Trie树

Posted on | In
Words count in article: 1.8k | Reading time ≈ 8

Trie树

​ 字典树又称Trie树，是单词查找树，是一种树形结构，也是哈希书的变种。典型应用于统计中，排序和保存大量字符串（但不仅仅限于字符串），所以经常被搜索引擎系统用于文本字频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无所谓的字符串比较，查询效率要比哈系树高

Trie树地3个基本性质：

  1. 根节点不包含字符，根节点外地每一个节点都只包含一个字符
  2. 从根节点到某一个节点，路径上经过的字符连接起来，为该点对应地字符串
  3. 每个节点的所有子节点包含的字符都不相同

所以每一个节点最多可以有26个子节点，对应26个字母（假设全部都为小写）。可以利用指针存储（比较浪费空间），也可以利用孩子兄弟表示法，也就是说可以利用左孩子右兄弟（比较难以理解）。一般指针表示最简单最直观。

这里，我们如果只是想记录单词是否存在，那么end[]中可存放一个布尔值，如果我们想记录单词的个数，那么我们就需要存放一个数字，再次遇到的时候就++。所以我们要知道不一定是到了叶子，才是一个单词

字典树的创建

前一个[]中的数字是根的下标，后面一个是指针域。trie[1][1] = 2 的2是创建了第二个节点的意思，每个节点都是26个域。

然后判断第二个字符（i）s[1]-\’a\’ = 8 那么在 trie[2][8] 上判断是不是等于0，是等于0，我们把它改为3，表明创建了第三个节点

第三个字符（k）s[2]-‘a’ = 10 那么判断trie[3][10] 上判断是不是等于0，如果等于0，我们把它改成4，表明创建了第四个节点

第四个字符（e）s[3]-‘a’ = 4 那么判断trie[4][4] 上判断是不是等于0，如果等于0，我们把它改成5，表明创建了第五个节点

处理完毕后加上一个end[]标记，表示这是一个单词。

那么我如果再想要插入bin，那么发现trie[1][1] 不是0，那么说明b节点已经被创建过了，那么直接去找他就行了。

同样i也创建过了， n没创建过，那么就新建一个节点trie[3][13] = 4 ,同时加上end标记

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
void insert(string s)
{
    int len = s.length(),p=1;
    for(int i = 0;i<len;i++)
    {
        int ch=s[i]-'a';
        if(!trie[p][ch])
            trie[p][ch] = ++tot;
        p=trie[p][ch];
    }
    end[p] = true;
}

字典树的查找

代码实现

1
2
3
4
5
6
7
8
9
10
11
bool search(string s)
{
    int len = s.length(),p=1;
    for(int i = 0;i<len;i++)
    {
        p = trie[p][s[i]-'a'];
        if(!p)
            return false;
    }
    return end[p];
}

性能分析

树高最高是len，那么假设树都是满的，那么就有26^len^ 级别的

但这是最基础的解法，我们是可以优化的。

应用

  1. 我们可以利用哈希，对每一个单词统计，然后找最高的100个单词。还可以创建一棵字典树，然后找频率最高的100个词，利用end[]统计
  2. 过
  3. 过
  4. 可以利用end[]来标记，如果end=true 的话，什么也不用做即可。然后先序遍历即可； 如果要保留原来的顺序，那么可以碰到一单词，然后立即查询有没有，有的话立即删除；如果没有就保留
  5. 和第一题一样
  6. 去重+统计（把end[]改成 int型数组）

构建查找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
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
const int maxz=26;//不同字符个数，例如数字10，小写字母26
int trie[maxn][maxz];
bool endWord[maxn];//标识单词结束
int n,tot;//字符串数,下标

void insert(string s)//将字符串s插入到字典树中
{
    int len=s.length(),p=1;
    for(int i=0;i<len;i++)
    {
        int ch=s[i]-'a';//转换成数字
        if(!trie[p][ch])
            trie[p][ch]=++tot;//记录下标
        p=trie[p][ch];
    }
    endWord[p]=true;//标记单词结束
}

bool search(string s)//在字典树中查找该字符串是否存在
{
    int len=s.length(),p=1;
    for(int i=0;i<len;i++)
    {
        p=trie[p][s[i]-'a'];
        if(!p)
            return false;
    }
    return endWord[p];
}

void dfs(int p)
{
    for(int i=0;i<26;i++)
    {
        if(trie[p][i])
        {
            cout<<char(i+'a');
            dfs(trie[p][i]);
        }
    }
    cout<<endl;
}

int main()
{
    string s;
    memset(trie,0,sizeof(trie));
    memset(endWord,false,sizeof(endWord));
    tot=1;
    cin>>n;
    while(n--)
    {
        cin>>s;
        insert(s);
    }
    dfs(1);
    cout<<"输入要查询的字符串："<<endl;
    cin>>s;
    if(search(s))
        cout<<"查询成功！";
    else
        cout<<"查询失败！";
    return 0;
}

例子：

字典树实现

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<iostream>
#include<string>
#include<sstream>
#include<cstring>
using namespace std;
const int maxn=500005;
const int maxz=26;//不同字符个数，例如数字10，小写字母26
int trie[maxn][maxz];
string word[maxn];//翻译单词 存储英文!
int value[maxn];//值的下标
bool end[maxn];//标记结束 
int n,tot;//字符串数,下标 

void insert(string s,int k)//将字符串s插入到字典树中,k的目的是记录单词的下标
{
	int len=s.length(),p=1;
	for(int i=0;i<len;i++)
	{
		int ch=s[i]-'a';//转换成数字
		if(!trie[p][ch]) 
			trie[p][ch]=++tot;//记录下标 
		p=trie[p][ch];
	}
    //插入完毕的时候，令插入的这个单词代表着第k个英语单词
	value[p]=k;//记录下标
	end[p]=1; 
}

int query(string s)
{
	int len=s.length(),p=1;
	for(int i=0;i<len;i++)
	{
		int ch=s[i]-'a';//转换成数字
		p=trie[p][ch];
		if(!p)
			return 0;
	}
	if(end[p])
		return value[p];//返回下标 
	return 0;	
}

int main()
{	
	string s,s1;
	memset(trie,0,sizeof(trie));
	tot=1;
	int i=1;
    //输入一行，有两个单词，所以我们一次读一行，getline
	while(getline(cin,s))
	{
        //如果s为空串，那么break
		if(!s.size())
			break;
        //从一个字符串流里面读取两个单词，一个英文单词存到数组word中，还有一个外文单词存到Trie树
        //还有一种办法就是判断空格，然后切分
		stringstream ss(s);
		ss>>word[i]>>s1;
		insert(s1,i);
		i++;
	}
    //查询
	while(cin>>s)
	{
		int k=query(s);
		if(k)
			cout<<word[k]<<endl;
		else
			cout<<"eh"<<endl;
	}
	return 0;
}

Map实现

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
using namespace std;
map<string,string>mp;//定义两个string的映射
char ch1[20],ch2[20],ch3[40],str[20];

int main()
{  
   while(gets(ch3))
   {
      if(!strlen(ch3))
         break;
      sscanf(ch3,"%s %s",ch1,ch2);//ch1是英语，ch2 是外文
      mp.insert(make_pair(ch2,ch1));//是根据外文查询英文的，所以ch2放前面当索引
   }
   while(gets(str))	// 读入需要查询的字符串
   {
      map<string,string>::iterator it;//定义一个迭代器
      it=mp.find(str);//在map中查询str，如果没查到，it = mp.end()
      if(it!=mp.end())
         cout<<mp[str]<<endl;
      else
         cout<<"eh"<<endl;
   }
   return 0;
}
-------------本文结束，感谢您的阅读-------------