精华内容
下载资源
问答
  • Trie树

    千次阅读 2020-06-20 15:04:39
    Trie树 文章目录Trie树一、什么是Trie树1.定义2.基本性质3.优点:4.缺点:5.bit-wise Trie6.压缩Trie1.压缩分支条件:7.外存Trie二、Trie树的基本操作实现1.Trie树的原理2.Trie树的操作1.插入2.查找3.删除3.Trie树的...

    Trie树

    一、什么是Trie树

    • Trie,又经常叫前缀树,字典树等等。它有很多变种,如后缀树,Radix Tree/Trie,PATRICIA tree,以及bitwise版本的crit-bit tree。当然很多名字的意义其实有交叉。

    在这里插入图片描述

    上图就是由单词at,bee,ben,bt,q组成的Trie树

    1.定义

    • 在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串
    • 与二叉查找树不同,不是直接保存在节点中,而是由节点在树中的位置决定
    • 一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串
    • 一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。
    • trie中的键通常是字符串,但也可以是其它的结构
    • trie的算法可以很容易地修改为处理其它结构的有序序列,比如一串数字或者形状的排列。比如,bitwise trie中的键是一串位元,可以用于表示整数或者内存地址

    2.基本性质

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

    3.优点:

    可以最大限度地减少无谓的字符串比较,故可以用于词频统计和大量字符串排序。

    • 跟哈希表比较:
    • 最坏情况时间复杂度比hash表好
    • 没有冲突,除非一个key对应多个值(除key外的其他信息)
    • 自带排序功能(类似Radix Sort),中序遍历trie可以得到排序

    4.缺点:

    • 虽然不同单词共享前缀,但其实trie是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针(不包含卫星数据)。

    • 每个结点的子树的根节点的组织方式有几种。

    • 1>如果默认包含所有字符集,则查找速度快但浪费空间(特别是靠近树底部叶子)。

    • 2>如果用链接法(如左儿子右兄弟),则节省空间但查找需顺序(部分)遍历链表。

    • 3>alphabet reduction: 减少字符宽度以减少字母集个数。

    • 4>对字符集使用bitmap,再配合链接法。

    • 如果数据存储在外部存储器等较慢位置,Trie会较hash速度慢(hash访问O(1)次外存,Trie访问O(树高))。

    • 长的浮点数等会让链变得很长。可用bitwise trie改进。

    5.bit-wise Trie

    类似于普通的Trie,但是字符集为一个bit位,所以孩子也只有两个。

    可用于地址分配,路由管理等

    虽然是按bit位存储和判断,但因为cache-local和可高度并行,所以性能很高。跟红黑树比,红黑树虽然纸面性能更高,但是因为cache不友好和串行运行多,瓶颈在存储访问延迟而不是CPU速度

    6.压缩Trie

    1.压缩分支条件:

    • 1,Trie基本不变
    • 2,只是查询
    • 3,key跟结点的特定数据无关
    • 4,分支很稀疏

    若允许添加和删除,就可能需要分裂和合并结点。此时可能需要对压缩率和更新(裂,并)频率进行折中。

    7.外存Trie

    某些变种如后缀树适合存储在外部,另外还有B-trie等。

    应用场景

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

    举例:
    1,给出N 个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。
    2,给出一个词典,其中的单词为不良单词。单词均为小写字母。再给出一段文本,文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如,若rob是不良单词,那么文本problem含有不良单词。

    3,1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。

    • (2)文本预测、自动完成,see also,拼写检查
    • (3)词频统计
    • (4)排序

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

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

    • (5)字符串最长公共前缀

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

    举例: 给出N 个小写英文字母串,以及Q 个询问,即询问某两个串的最长公共前缀的长度是多少?
    解决方案:首先对所有的串建立其对应的字母树。此时发现,对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数,于是,问题就转化为了离线(Offline)的最近公共祖先(Least Common Ancestor,简称LCA)问题。
    而最近公共祖先问题同样是一个经典问题,可以用下面几种方法:

    1. 利用并查集(Disjoint Set),可以采用采用经典的Tarjan 算法;
    2. 求出字母树的欧拉序列(Euler Sequence )后,就可以转为经典的最小值查询(Range Minimum Query,简称RMQ)问题了;
    • (6)字符串搜索的前缀匹配

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

    • Trie树检索的时间复杂度可以做到n,n是要检索单词的长度,
      如果使用暴力检索,需要指数级O(n2)的时间复杂度。

    • 7) 作为其他数据结构和算法的辅助结构

    如后缀树,AC自动机等

    后缀树可以用于全文搜索

    二、Trie树的基本操作实现

    1.Trie树的原理

    • 利用串构建一个字典树,这个字典树保存了串的公共前缀信息,因此可以降低查询操作的复杂度。
    • 下面以英文单词构建的字典树为例,这棵Trie树中每个结点包括26个孩子结点,因为总共有26个英文字母(假设单词都是小写字母组成)。

    则可声明包含Trie树的结点信息的结构体:

    #define MAX 26
    
    typedef struct TrieNode               //Trie结点声明 
    {
        bool isStr;                      //标记该结点处是否构成单词 
        struct TrieNode *next[MAX];      //儿子分支 
    }Trie;
    

    其中next是一个指针数组,存放着指向各个孩子结点的指针

    如给出字符串"abc",“ab”,“bd”,“dda”,根据该字符串序列构建一棵Trie树。
    则构建的树如下:
    在这里插入图片描述

    • Trie树的根结点不包含任何信息,第一个字符串为"abc",第一个字母为'a',因此根结点中数组next下标为'a'-97的值不为NULL,其他同理,红色结点表示在该处可以构成一个单词
    • 很显然,如果要查找单词"abc"是否存在,查找长度则为O(len),len为要查找的字符串的长度。而若采用一般的逐个匹配查找,则查找长度为O(len*n),n为字符串的个数。显然基于Trie树的查找效率要高很多
    • 但是却是以空间为代价的,比如图中每个结点所占的空间都为(26*4+1)Byte=105Byte,那么这棵Trie树所占的空间则为105*8Byte=840Byte,而普通的逐个查找所占空间只需(3+2+2+3)Byte=10Byte

    2.Trie树的操作

    在Trie树中主要有3个操作,插入、查找和删除。一般情况下Trie树中很少存在删除单独某个结点的情况,因此只考虑删除整棵树。

    1.插入

    • 假设存在字符串str,Trie树的根结点为root。i=0,p=root。
    • 1)取str[i],判断p->next[str[i]-97]是否为空,若为空,则建立结点temp,并将p->next[str[i]-97]指向temp,然后p指向temp;若不为空,则p=p->next[str[i]-97];
    • 2)i++,继续取str[i],循环1)中的操作,直到遇到结束符’\0’,此时将当前结点p中的isStr置为true。

    2.查找

    • 假设要查找的字符串为str,Trie树的根结点为root,i=0,p=root

    • 1)取str[i],判断判断p->next[str[i]-97]是否为空,若为空,则返回false;若不为空,则p=p->next[str[i]-97],继续取字符。

    • 2)重复1)中的操作直到遇到结束符'\0',若当前结点p不为空并且isStr为true,则返回true,否则返回false。

    3.删除

    删除可以以递归的形式进行删除

    3.Trie树的模拟实现

    #include <iostream>
    #include<cstdlib>
    #define MAX 26
    using namespace std;
     
    typedef struct TrieNode                     //Trie结点声明 
    {
        bool isStr;                            //标记该结点处是否构成单词 
        struct TrieNode *next[MAX];            //儿子分支 
    }Trie;
     
    void insert(Trie *root,const char *s)     //将单词s插入到字典树中 
    {
        if(root == NULL || *s == '\0')
            return;
        
        int i;
        Trie *p = root;
        while(*s != '\0')
        {
            if(p->next[*s - 'a'] == NULL)        //如果不存在,则建立结点 
            {
                Trie *temp = (Trie *)malloc(sizeof(Trie));
                for(i = 0;i < MAX;i++)
                {
                    temp->next[i] = NULL;
                }
                temp->isStr = false;
                p->next[*s - 'a'] = temp;
                p = p->next[*s - 'a'];   
            }   
            else
            {
                p = p->next[*s - 'a'];
            }
            s++;
        }
        p->isStr = true;                  //单词结束的地方标记此处可以构成一个单词 
    }
     
    int search(Trie *root,const char *s)  //查找某个单词是否已经存在 
    {
        Trie *p = root;
        while(p != NULL && *s != '\0')
        {
            p = p->next[*s - 'a'];
            s++;
        }
        return (p != NULL && p->isStr == true);      //在单词结束处的标记为true时,单词才存在 
    }
     
    void del(Trie *root)                      //释放整个字典树占的堆区空间 
    {
        int i;
        for(i = 0;i < MAX;i++)
        {
            if(root->next[i] != NULL)
            {
                del(root->next[i]);
            }
        }
        free(root);
    }
     
    int main(int argc, char *argv[])
    {
        int i;
        int n,m;                              //n为建立Trie树输入的单词数,m为要查找的单词数 
        char s[100];
        Trie *root = (Trie *)malloc(sizeof(Trie));
        for(i = 0;i < MAX;i++)
        {
            root->next[i] = NULL;
        }
        root->isStr = false;
        scanf("%d",&n);
        getchar();
        for(i = 0;i < n;i++)                 //先建立字典树 
        {
            scanf("%s",s);
            insert(root,s);
        }
        while(scanf("%d",&m) != EOF)
        {
            for(i = 0;i < m;i++)                 //查找 
            {
                scanf("%s",s);
                if(search(root,s) == 1)
                    printf("YES\n");
                else
                    printf("NO\n");
            }
            printf("\n");   
        }
        del(root);                         //释放空间很重要 
        return 0;
    }
    
    展开全文
  • trie

    2019-09-27 13:04:09
    关键词:trie trie树 数据结构 前几天学习了并查集和trie树,这里总结一下trie。 本文讨论一棵最简单的trie树,基于英文26个字母组成的字符串,讨论插入字符串、判断前缀是否存在、查找字符串等基本...

    文章作者:yx_th000 文章来源:Cherish_yimi (http://www.cnblogs.com/cherish_yimi/) 转载请注明,谢谢合作。
    关键词:trie trie树 数据结构

        前几天学习了并查集和trie树,这里总结一下trie。
        本文讨论一棵最简单的trie树,基于英文26个字母组成的字符串,讨论插入字符串、判断前缀是否存在、查找字符串等基本操作;至于trie树的删除单个节点实在是少见,故在此不做详解。

    l        Trie原理

    Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

     

    l        Trie性质

    好多人说trie的根节点不包含任何字符信息,我所习惯的trie根节点却是包含信息的,而且认为这样也方便,下面说一下它的性质 (基于本文所讨论的简单trie树)

    1.    字符的种数决定每个节点的出度,即branch数组(空间换时间思想)

    2.    branch数组的下标代表字符相对于a的相对位置

    3.    采用标记的方法确定是否为字符串。

    4.    插入、查找的复杂度均为O(len),len为字符串长度

    l        Trie的示意图

     

    如图所示,该trie树存有abc、d、da、dda四个字符串,如果是字符串会在节点的尾部进行标记。没有后续字符的branch分支指向NULL





    l       
    Trie
    Trie的优点举例

    已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法:

    1.    最容易想到的:即从字符串集中从头往后搜,看每个字符串是否为字符串集中某个字符串的前缀,复杂度为O(n^2)。

    2.    使用hash:我们用hash存下所有字符串的所有的前缀子串。建立存有子串hash的复杂度为O(n*len)。查询的复杂度为O(n)* O(1)= O(n)。

    3.    使用trie:因为当查询如字符串abc是否为某个字符串的前缀时,显然以b,c,d....等不是以a开头的字符串就不用查找了。所以建立trie的复杂度为O(n*len),而建立+查询在trie中是可以同时执行的,建立的过程也就可以成为查询的过程,hash就不能实现这个功能。所以总的复杂度为O(n*len),实际查询的复杂度只是O(len)。


    解释一下hash为什么不能将建立与查询同时执行,例如有串:911,911456输入,如果要同时执行建立与查询,过程就是查询911,没有,然后存入9、91、911,查询911456,没有然后存入9114、91145、911456,而程序没有记忆功能,并不知道911在输入数据中出现过。所以用hash必须先存入所有子串,然后for循环查询。

    而trie树便可以,存入911后,已经记录911为出现的字符串,在存入911456的过程中就能发现而输出答案;倒过来亦可以,先存入911456,在存入911时,当指针指向最后一个1时,程序会发现这个1已经存在,说明911必定是某个字符串的前缀,该思想是我在做pku上的3630中发现的,详见本文配套的“入门练习”。

    l        Trie的简单实现(插入、查询)

     

    View Code
     1 /*
    2 trie树:
    3 利用trie树 查找单词 的简单程序
    4 */
    5 #include<iostream>
    6 using namespace std;
    7
    8 struct trie
    9 {
    10 bool is;//标记是否是个单词
    11 trie *next[26];// 分别代表26个字母
    12 trie():is(false)
    13 {
    14 memset(next,0,sizeof(next));
    15 }
    16 };
    17
    18 trie *root;
    19
    20 void insert(const char *word)
    21 {
    22 trie *p=root;
    23 while(*word)
    24 {
    25 if(p->next[*word-'a']==NULL)//说明出现新单词 开辟空间村上
    26 {
    27 trie *temp=new trie();
    28 p->next[*word-'a']=temp;
    29 }
    30 p=p->next[*word-'a'];
    31 word++;
    32 }
    33 p->is=true;//单词遍历结束 标记一下说明到此处有个单词
    34 }
    35
    36 int search(const char *word)
    37 {
    38 trie *p=root;
    39 while(*word&&p)
    40 {
    41 p=p->next[*word-'a'];
    42 word++;
    43 }
    44 return (p&&p->is);// 若以上循环 是有word结束 即p!=null 若此时P->is!=0说明
    45 } // 单词库中有这个单词 若是以p结束 说明是新单词 单词库没有
    46
    47 void deletet(trie *root)
    48 {
    49 int i;
    50 for(i=0;i<26;++i)
    51 {
    52 if(root->next[i]!=NULL)
    53 deletet(root->next[i]);//递归删除各点
    54 }
    55 delete root;
    56 }
    57
    58 int main()
    59 {
    60 char ch[80];
    61 int i;
    62 root=new trie();
    63 for(i=0;i<4;++i)//输入单词库
    64 {
    65 cin>>ch;
    66 insert(ch);
    67 }
    68 while(1)// 查询单词
    69 {
    70 cin>>ch;
    71 cout<<search(ch)<<endl;
    72 }
    73 system("pause");
    74 return 0;
    75 }

     

    转载于:https://www.cnblogs.com/zhixingqiezhixing/archive/2012/02/11/2346874.html

    展开全文
  • trie树

    2019-10-01 02:35:40
    Trie树也称字典树,因为其效率很高,所以在在字符串查找、前缀匹配等中应用很广泛,其高效率是以空间为代价的。 一.Trie树的原理 利用串构建一个字典树,这个字典树保存了串的公共前缀信息,因此可...

    描述摘自网络:

    http://www.cnblogs.com/dolphin0520/archive/2011/10/11/2207886.html

     Trie树

           Trie树也称字典树,因为其效率很高,所以在在字符串查找、前缀匹配等中应用很广泛,其高效率是以空间为代价的。

    一.Trie树的原理

        利用串构建一个字典树,这个字典树保存了串的公共前缀信息,因此可以降低查询操作的复杂度。

        下面以英文单词构建的字典树为例,这棵Trie树中每个结点包括26个孩子结点,因为总共有26个英文字母(假设单词都是小写字母组成)。

        则可声明包含Trie树的结点信息的结构体:

    struct TrieNode
    {
        bool isWord;
        TrieNode *next[MAX];
    };

    其中next是一个指针数组,存放着指向各个孩子结点的指针。

        如给出字符串"abc","ab","bd","dda",根据该字符串序列构建一棵Trie树。则构建的树如下:

        

    Trie树的根结点不包含任何信息,第一个字符串为"abc",第一个字母为'a',因此根结点中数组next下标为'a'-97的值不为 NULL,其他同理,构建的Trie树如图所示,红色结点表示在该处可以构成一个单词。很显然,如果要查找单词"abc"是否存在,查找长度则为 O(len),len为要查找的字符串的长度。而若采用一般的逐个匹配查找,则查找长度为O(len*n),n为字符串的个数。显然基于Trie树的查找 效率要高很多。

    但是却是以空间为代价的,比如图中每个结点所占的空间都为(26*4+1)Byte=105Byte,那么这棵Trie树所占的空间则为105*8Byte=840Byte,而普通的逐个查找所占空间只需(3+2+2+3)Byte=10Byte。

    二.Trie树的操作

        在Trie树中主要有3个操作,插入、查找和删除。一般情况下Trie树中很少存在删除单独某个结点的情况,因此只考虑删除整棵树。

    1.插入

      假设存在字符串str,Trie树的根结点为root。i=0,p=root。

      1)取str[i],判断p->next[str[i]-97]是否为空,若为空,则建立结点temp,并将p->next[str[i]-97]指向temp,然后p指向temp;

       若不为空,则p=p->next[str[i]-97];

      2)i++,继续取str[i],循环1)中的操作,直到遇到结束符'\0',此时将当前结点p中的isStr置为true。

    2.查找

      假设要查找的字符串为str,Trie树的根结点为root,i=0,p=root

      1)取str[i],判断判断p->next[str[i]-97]是否为空,若为空,则返回false;若不为空,则p=p->next[str[i]-97],继续取字符。

      2)重复1)中的操作直到遇到结束符'\0',若当前结点p不为空并且isStr为true,则返回true,否则返回false。

    3.删除

      删除可以以递归的形式进行删除。

     

    代码自己实现:

    #include <iostream>
    #include <cassert>
    using namespace std;
    
    #define MAX 26
    
    struct TrieNode
    {
        bool isWord;
        TrieNode *next[MAX];
    };
    
    TrieNode* createNewNode()
    {
        TrieNode* pNew = new TrieNode;
        pNew->isWord=false;
        for (int i=0; i<MAX; i++)
        {
            pNew->next[i] = NULL;
        }
        return pNew;
    }
    
    //向trie tree中添加单词
    void insertWord(TrieNode* pRoot, const char* word)
    {
        assert(pRoot!=NULL);
        assert(word!=NULL);
        TrieNode* p = pRoot;
        while (*word!='\0')
        {
            if (p->next[*word-'a']==NULL)
            {
                TrieNode* pNext = createNewNode();
                p->next[*word-'a'] = pNext;
            }
            p=p->next[*word-'a'];
            word++;
        }
        p->isWord=true;
    
    }
    
    
    // 查找某单词是否存在
    bool searchWord(TrieNode* pRoot, const char *word)
    {
        assert(pRoot!=NULL);
        assert(word!=NULL);
        TrieNode* p = pRoot;
        while(p!=NULL && *word!='\0')
        {
            p=p->next[*word-'a'];
            word++;
        }
        return (p!=NULL && p->isWord == true);
    }
    
    // 删除trie tree
    void deleteTree(TrieNode *pRoot)
    {
        if (pRoot==NULL)
        {
            return;
        }
        for (int i=0; i<MAX; i++)
        {
            deleteTree(pRoot->next[i]);
        }
        delete pRoot;
    
    }
    
    
    int main(int arrgc, char* argv[])  
    {  
        // 建立根节点
        TrieNode* pRoot = createNewNode();
        
        insertWord(pRoot,"hello");
        insertWord(pRoot,"helloboy");
        insertWord(pRoot,"boy");
        insertWord(pRoot,"world");
    
        cout<<searchWord(pRoot,"boy");
    
        deleteTree(pRoot);
        return 0;
    }  

     

    转载于:https://www.cnblogs.com/cyttina/archive/2012/10/30/2746094.html

    展开全文
  • TRIE树

    2020-03-28 23:16:51
    答案是用TRIE树。 网上学习了下,大致就是建立一颗树,按单词顺序,从上到下建树,不同单词,前缀相同的复用。 这个算法的用处: 1.快速查找相同前缀的单词,类似于搜索或输入时的提示 2.统计词频 相关文章:...

    今天周六,在家休息的时候,做了一道面试题,是关于算法的:如何查单词最快?答案是用TRIE树。

    网上学习了下,大致就是建立一颗树,按单词顺序,从上到下建树,不同单词,前缀相同的复用。

    这个算法的用处:

    1.快速查找相同前缀的单词,类似于搜索或输入时的提示

    2.统计词频

     

    相关文章:

    TRIE树详解-简书:https://www.jianshu.com/p/6f81da81bd02

    展开全文
  • Trie

    2019-07-31 16:04:18
    Trie树的基本性质: 根节点不包含字符,除根节点外的每一个子节点都包含一个字符 从根节点到某一个节点,路径上经过的字符连接起来,为该字节对应的字符串。 每一节点的所有子节点包含的字符互不相同。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,788
精华内容 5,515
关键字:

trie树