【数据结构】前缀树/字典树/Trie

【前缀树】

  用来保存一个映射(通常情况下 key 为字符串  value 为字符串所代表的信息)

  例如:一个单词集合 words = {  apple, cat,  water  }   其中 key 为单词      value 代表该单词是否存在

      words[ ‘apple‘ ] = 存在     而     word[ ‘ abc‘ ] = 不存在

  图示:一个保存了8个键的trie结构,"A", "to", "tea", "ted", "ten", "i", "in", and "inn".

      键不需要被显式地保存在节点中。图示中标注出完整的单词,只是为了演示trie的原理。

  

          

【应用】

  trie树常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。

  补充:

Trie是一种非常简单高效的数据结构,但有大量的应用实例。

(1) 字符串检索

事先将已知的一些字符串(字典)的有关信息保存到trie树里,查找另外一些未知字符串是否出现过或者出现频率。

举例:

@  给出N 个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。

@  给出一个词典,其中的单词为不良单词。单词均为小写字母。再给出一段文本,文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如,若rob是不良单词,那么文本problem含有不良单词。

(2)字符串最长公共前缀

Trie树利用多个字符串的公共前缀来节省存储空间,反之,当我们把大量字符串存储到一棵trie树上时,我们可以快速得到某些字符串的公共前缀。

举例:

@ 给出N 个小写英文字母串,以及Q 个询问,即询问某两个串的最长公共前缀的长度是多少?

解决方案:首先对所有的串建立其对应的字母树。此时发现,对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数,于是,问题就转化为了离线(Offline)的最近公共祖先(Least Common Ancestor,简称LCA)问题。

而最近公共祖先问题同样是一个经典问题,可以用下面几种方法:

1. 利用并查集(Disjoint Set),可以采用采用经典的Tarjan 算法;

2. 求出字母树的欧拉序列(Euler Sequence )后,就可以转为经典的最小值查询(Range Minimum Query,简称RMQ)问题了;

(关于并查集,Tarjan算法,RMQ问题,网上有很多资料。)

(3)排序

Trie树是一棵多叉树,只要先序遍历整棵树,输出相应的字符串便是按字典序排序的结果。

举例:

@ 给你N 个互不相同的仅由一个单词构成的英文名,让你将它们按字典序从小到大排序输出。

(4) 作为其他数据结构和算法的辅助结构

  如后缀树,AC自动机等

【模板】

  该模板参考白书P209,用数组存储字典树

/*
字典树模板(注意数组初始化问题)
by chsobin
给定n个单词的集合,询问q次:一个单词是否在集合中
此处附加信息为节点存不存在
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxnode = 100;    //maxnode = 单词长度*单词数 

int ch[maxnode][27];
int val[maxnode];        //附加信息
int sz = 1;                //节点总数 

//插入字符串s,附加信息为v。注意v必须非零,0代表本节点不是单词节点
void insert(char * s, int v){
    int u=0;
    int n = strlen(s);
    int c;
    for(int i=0;i<n;++i){
        c = s[i] - ‘a‘;
        if(!ch[u][c]){
            ch[u][c] = sz++;    //新建节点
        }
        u = ch[u][c];
    }
    val[u] = v;  //1表示该节点为单词
} 

bool find(char * s){
    int u=0;
    int n = strlen(s);
    int c;
    for(int i=0;i<n;++i){
        c = s[i] - ‘a‘;
        if(ch[u][c]==0) return false;    //单词不存在
        u = ch[u][c];
    }
    if(val[u]) return true;    //判断是否为单词节点
    else return false;
} 

int main(){
    int n, q;
    char str[30];
    scanf("%d%d", &n, &q);
    while(n--){
        scanf("%s", str);
        insert(str, 1);        //附加信息为1表示该节点为单词节点
    }
    while(q--){
        scanf("%s", str);
        if(find(str)) printf("yes\n");
        else printf("No\n");
    }
    return 0;
}

【例题】

  hdu1251

/*
字典树/前缀树/Trie
2018年1月28日18:42:23
by chsobin

题目大意:给出n个单词(单词长度<=10),
            q个问题,问以给定字符串开头的单词有多少
朴素思想:遍历 O(qn)
字典树:建树 O(10n) 查询 O(10q)
        建树过程中维护节点额外信息val[i]表示建树过程中经过节点i的单词
*/
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 1000000;
struct Trie{
    int ch[maxn][27];
    int val[maxn];
    int sz;
    Trie(){
        sz = 1;
        memset(val, 0, sizeof(val));
        memset(ch[0], 0, sizeof(ch[0]));
    }

    void insert(char * s){
        int n = strlen(s);
        int u = 0;
        int c;
        for(int i=0;i<n;++i){
            c = s[i] - ‘a‘;
            if(!ch[u][c]){
                memset(ch[sz], 0, sizeof(ch[sz]));
                ch[u][c] = sz++;
            }
            u = ch[u][c];
            val[u]++;
        }
    }

    int find(char * s){
        int n = strlen(s);
        int u = 0;
        int c;
        for(int i=0;i<n;++i){
            c = s[i] - ‘a‘;
            if(!ch[u][c]){
                return 0;
            }
            u = ch[u][c];
        }
        return val[u];
    }
};
Trie trie;
char s[15];
int main(){
    while(gets(s),strcmp(s,"")){
        trie.insert(s);
    }
    while(gets(s)!=NULL){
        printf("%d\n", trie.find(s));
    }
    return 0;
}

ac 78ms

【参考】

  http://dongxicheng.org/structure/trietree/

原文地址:https://www.cnblogs.com/chsobin/p/8372311.html

时间: 01-27

【数据结构】前缀树/字典树/Trie的相关文章

【学习总结】数据结构-Trie/前缀树/字典树-及其最常见的操作

Trie/前缀树/字典树 Trie (发音为 "try") 或前缀树是一种树数据结构,用于检索字符串数据集中的键. 一种树形结构,是一种哈希树的变种. 典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计. 优点:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高. 应用: 自动补全 END 原文地址:https://www.cnblogs.com/anliux/p/12590368.html

9-11-Trie树/字典树/前缀树-查找-第9章-《数据结构》课本源码-严蔚敏吴伟民版

课本源码部分 第9章  查找 - Trie树/字典树/前缀树(键树) ——<数据结构>-严蔚敏.吴伟民版        源码使用说明  链接??? <数据结构-C语言版>(严蔚敏,吴伟民版)课本源码+习题集解析使用说明        课本源码合辑  链接??? <数据结构>课本源码合辑        习题集全解析  链接??? <数据结构题集>习题解析合辑        本源码引入的文件  链接? Status.h.Scanf.c        相关测试数据

Hash树(散列树)和Trie树(字典树、前缀树)

1.Hash树 理想的情况是希望不经过任何比较,一次存取便能得到所查的记录, 那就必须在记的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和一个唯一的存储位置相对应.因而在查找时,只要根据这个对应关系f找到 给定值K的像f(K).由此,不需要进行比较便可直接取得所查记录.在此,我们称这个对应关系为哈希(Hash)函数,按这个思想建立的表为哈希表. 在哈希表中对于不同的关键字可能得到同一哈希地址,这种现象称做冲突.在一般情况下,冲突只能尽可能地减少,而不能完全避免.因为哈希函数是从

剑指Offer——Trie树(字典树)

剑指Offer--Trie树(字典树) Trie树 Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种.典型应用是统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计.它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高. Trie的核心思想是空间换时间.利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的. Trie树也有它的缺点,Trie树的内存消耗非常大.当然,或许用左儿子右兄弟的方法建树的话,可能会好点.可见,优

# 前缀统计~[字典树]

前缀统计~[字典树] 传送门 题意 给出N个字符串,进行M次询问,每次给出一个字符串,询问N个字符串中有多少个是它的前缀. 思路 字典树Trie入门题. 字典树最典型的应用就是用来存储字符串. 其中每个节点下有26个子节点(对应26个字母),根据新建节点的顺序使用idx为节点编号,根节点和空节点编号都为0,每个叶节点维护一个cnt,标记以这个叶节点结尾的字符串有几个. 使用这种存储方式可以很容易查找一个字符串是否存在,以及出现过几次等等. Code: #include <bits/stdc++.

白话算法与数据结构之【字典树】

1. 什么是trie树 1.Trie树 (特例结构树) Trie树,又称单词查找树.字典树,是一种树形结构,是一种哈希树的变种,是一种用于快速检索的多叉树结构.典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计.它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高.      Trie的核心思想是空间换时间.利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的. Trie树也有它的缺点,Trie树的内存消耗非常大.当然,或许用左儿子

Trie树/字典树

Trie树结构 Trie树是一种树形数据结构,又称为单词查找树.字典树,是一种用于快速检索的多叉树结构.典型应用是统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计.     它的主要设计思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销.它的优点是可以最大限度的减少无谓的字符串比较,查询效率比哈希表高:缺点是内存消耗非常大. Trie树基本特性 根节点不包含字符,除根节点外每一个节点都只包含一个字符 从根节点到某一节点,路径上经过的字符连接起来,为该节点

[转载]Trie树|字典树(字符串排序)

有时,我们会碰到对字符串的排序,若采用一些经典的排序算法,则时间复杂度一般为O(n*lgn),但若采用Trie树,则时间复杂度仅为O(n). Trie树又名字典树,从字面意思即可理解,这种树的结构像英文字典一样,相邻的单词一般前缀相同,之所以时间复杂度低,是因为其采用了以空间换取时间的策略. 下图为一个针对字符串排序的Trie树(我们假设在这里字符串都是小写字母),每个结点有26个分支,每个分支代表一个字母,结点存放的是从root节点到达此结点的路经上的字符组成的字符串. 将每个字符串插入到tr

Trie树&mdash;字典树(单词查找树)

Trie树,又称字典树,单词查找树.它来源于retrieval(检索)中取中间四个字符构成的.用于存储大量的字符串以便支持快速模式匹配.主要应用在信息检索领域. Trie有三种结构:标准Trie(standard trie),压缩Trie,后缀Trie(suffix trie). 1.标准Trie 标准Trie树的结构:所有含有公共前缀的字符串将挂在树中同一个结点下.实际上trie简明的存储于串集合汇总的所有公共前缀.加入有这样一个字符串集合X{bear,bell,bid,bull,buy,se