欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

字典树(前缀树)

程序员文章站 2022-06-04 12:43:58
...

本文转载自:https://blog.csdn.net/weixin_39778570/article/details/81990417

什么是字典树?

 

叫前缀树更容易理解

字典树的样子

字典树(前缀树)

Trie又被称为前缀树、字典树,所以当然是一棵树。上面这棵Trie树包含的字符串集合是{in, inn, int, tea, ten, to}。每个节点的编号是我们为了描述方便加上去的。树中的每一条边上都标识有一个字符。这些字符可以是任意一个字符集中的字符。比如对于都是小写字母的字符串,字符集就是’a’-‘z’;对于都是数字的字符串,字符集就是’0’-‘9’;对于二进制字符串,字符集就是0和1。

比如上图中3号节点对应的路径0123上的字符串是inn,8号节点对应的路径0568上的字符串是ten。终结点与集合中的字符串是一一对应的。

原理


下面我们来讲一下对于给定的字符串集合{W1, W2, W3, … WN}如何创建对应的Trie树。其实上Trie树的创建是从只有根节点开始,通过依次将W1, W2, W3, … WN插入Trie中实现的。所以关键就是之前提到的Trie的插入操作。
具体来说,Trie一般支持两个操作:
1. Trie.insert(W):第一个操作是插入操作,就是将一个字符串W加入到集合中。
2. Trie.search(S):第二个操作是查询操作,就是查询一个字符串S是不是在集合中。

假设我们要插入字符串”in”。我们一开始位于根,也就是0号节点,我们用P=0表示。我们先看P是不是有一条标识着i的连向子节点的边。没有这条边,于是我们就新建一个节点,也就是1号节点,然后把1号节点设置为P也就是0号节点的子节点,并且将边标识为i。最后我们移动到1号节点,也就是令P=1。

字典树(前缀树)

这样我们就把”in”的i字符插入到Trie中了。然后我们再插入字符n,也是先找P也就是1号节点有没有标记为n的边。还是没有,于是再新建一个节点2,设置为P也就是1号节点的子节点,并且把边标识为n。最后再移动到P=2。这样我们就把n也插入了。由于n是”in”的最后一个字符,所以我们还需要将P=2这个节点标记为终结点。

字典树(前缀树)

现在我们再插入字符串”inn”。过程也是一样的,从P=0开始找标识为i的边,这次找到1号节点。于是我们就不用创建新节点了,直接移动到1号节点,也就是令P=1。再插入字符n,也是有2号节点存在,所以移动到2号节点,P=2。最后再插入字符n这时P没有标识为n的边了,所以新建3号节点作为2号节点的子节点,边标识为n,同时将3号节点标记为终结点:

字典树(前缀树)
将后面的字符串int tea ten to都插入之后,就得到了我们一开始给出的Trie:

字典树(前缀树)

综上所述,在Trie中插入一个字符串W的伪代码如下:

字典树(前缀树)
下面我们再讲一下如何查询Trie树中是不是包含字符串S,也就是之前提到的查找操作。查找其实比较简单。我们只要从根节点开始,沿着标识着S[1] -> S[2] -> S[3] … -> S[S.len]的边移动,如果最后成功到达一个终结点,就说明S在Trie树中;如果最后无路可走,或者到达一个不是终结点的节点,就说明S不在Trie树中。

字典树(前缀树)

如果是查找”te”,就会从0开始经过5最后到达6。但是6不是终结点,所以te没在Trie树中。如果查找的是”too”,就会从0开始经过5和9,然后发现之后无路可走:9号节点没有标记为o的边连出去。所以too也不在Trie中。

综上所述,在Trie树中查找一个字符串的伪代码如下:

字典树(前缀树)
代码实现

数组方式实现
要写代码实现一个Trie首先就要确定如何存储一个Trie结构。这里用一个二维数组来存储:

int trie[MAX_NODE][CHARSET];
int k;
其中MAX_NODE是trie中最大能存储的节点数目,CHARSET是字符集的大小,k是当前trie中包含有多少个节点。Trie[i][j]的值是0表示trie树中i号节点,并没有一条连出去的边,满足边上的字符标识是字符集中第j个字符(从0开始);trie[i][j]的值是正整数x表示trie树中i号节点,有一条连出去的边,满足边上的字符标识是字符集中第j个字符,并且这条边的终点是x号节点。

简要实现:

#include <bits/stdc++.h>
typedef long long ll;
const int maxx=10010;
const int maxn=26;
const int inf=0x3f3f3f3f;
using namespace std;
int Trie[maxx][maxn]= {0}; //maxx表示Trie中最大能储存的节点数目,maxn表示字符集的大小
int k=1;//k是Trie中包含了多少个节点。
int color[maxx]= {0};
void insert(char *w)
{
    int len=strlen(w);
    int p=0;//根结点
    for(int i=1; i<=len; i++)
    {
        int c=w[i]-'a';
        if(Trie[p][c]==0)//如果没有标识为w[i]的边
        {
            Trie[p][c]=k;//创建一个新的子节点
            k++;
        }
        p=Trie[p][c];
    }
    color[p]=1;//标记p为终结点
}
int search(char *s)
{
    int len=strlen(s);
    int p=0;
    for(int i=1; i<=len; i++)
    {
        int c=s[i]-'a';
        if(Trie[p][c]==0)
            return 0;
        p=Trie[p][c];
    }
    return color[p]==1;//标记p为终结点
}
int main()
{
    int t,q;
    char s[20];
    scanf("%d%d",&t,&q);
    while(t--)
    {
        scanf("%s",s);
        insert(s);
    }
    while(q--)
    {
        scanf("%s",s);
        if(search(s)!=0)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

 

相关标签: 字典树