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

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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了白话算法与数据结构之【字典树】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4598字，纯文字阅读大概需要7分钟。

内容图文

 1. 什么是trie树

  1.Trie树 （特例结构树）  

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

2.  三个基本特性：

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

3 .例子

       和二叉查找树不同，在trie树中，每个结点上并非存储一个元素。
       trie树把要查找的关键词看作一个字符序列。并根据构成关键词字符的先后顺序构造用于检索的树结构。
       在trie树上进行检索类似于查阅英语词典。
      一棵m度的trie树或者为空，或者由m棵m度的trie树构成。

     例如，电子英文词典，为了方便用户快速检索英语单词，可以建立一棵trie树。例如词典由下面的单词成：a、b、c、aa、ab、ac、ba、ca、aba、abc、baa、bab、bac、cab、abba、baba、caba、abaca、caaba

技术分享


       

  如给出字符串"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。


2. trie树的实现

1．插入过程

对于一个单词，从根开始，沿着单词的各个字母所对应的树中的节点分支向下走，直到单词遍历完，将最后的节点标记为红色，表示该单词已插入trie树。

2. 查找过程

其方法为：

(1) 从根结点开始一次搜索；

(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；

(3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
(4) 迭代过程……
(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。其他操作类似处理.

       即从根开始按照单词的字母顺序向下遍历trie树，一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色，则表示该单词不存在，若最后的节点标记为红色，表示该单词存在。如下图中：trie树中存在的就是abc、d、da、dda四个单词。在实际的问题中可以将标记颜色的标志位改为数量count等其他符合题目要求的变量。  

      技术分享


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.删除

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


代码实现:(hihocoder1014)

输入

输入的第一行为一个正整数n，表示词典的大小，其后n行，每一行一个单词（不保证是英文单词，也有可能是火星文单词哦），单词由不超过10个的小写英文字母组成，可能存在相同的单词，此时应将其视作不同的单词。接下来的一行为一个正整数m，表示小Hi询问的次数，其后m行，每一行一个字符串，该字符串由不超过10个的小写英文字母组成，表示小Hi的一个询问。

在20%的数据中n, m<=10，词典的字母表大小<=2.

在60%的数据中n, m<=1000，词典的字母表大小<=5.

在100%的数据中n, m<=100000，词典的字母表大小<=26.

本题按通过的数据量排名哦～

输出

对于小Hi的每一个询问，输出一个整数Ans,表示词典中以小Hi给出的字符串为前缀的单词的个数。

样例输入
5
babaab
babbbaaaa
abba
aaaaabaa
babaababb
5
babb
baabaaa
bab
bb
bbabbaab
样例输出
1
0
3
0
0
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

struct node{
    int Count;
    node *next[26];
    node(){  //初始化数据
        memset(next,NULL,sizeof(next));
        Count=0;
    }
};

node *p,*root=new node();

void Insert(char *s)//插入新单词
{
    int i,k;
    for(p=root,i=0;s[i];++i)
    {
        k=s[i]-'a';
        if(p->next[k]==NULL) p->next[k]=new node();
        p=p->next[k];
        p->Count++;  //记录此字母出现的次数
    }
}

int Search(char *s)
{
    int i,k;
    for(p=root,i=0;s[i];++i)
    {
        k=s[i]-'a';
        if(p->next[k]==NULL) break; //一旦查找不到，立即跳出
        p=p->next[k];
    }
    if(s[i]) return 0;//s[i]!=0表示中间
    return p->Count;
}

int main ()
{
    #ifdef xxz
    freopen("in.txt","r",stdin);
    #endif // xxz
    int n,m;
    char s[100],s2[100];
    while(cin>>n)
    {
        getchar();
        for(int i = 0; i < n; i++)
        {
            gets(s);
            Insert(s);
        }
        cin>>m;
        getchar();
        for(int i = 0; i < m; i++)
        {
            gets(s2);
            cout<<Search(s2)<<endl;
        }
    }
    return 0;
}


3. 查找分析

       在trie树中查找一个关键字的时间和树中包含的结点数无关，而取决于组成关键字的字符数。而二叉查找树的查找时间和树中的结点数有关O(log2n)。
       如果要查找的关键字可以分解成字符序列且不是很长，利用trie树查找速度优于二叉查找树。如：
       若关键字长度最大是5，则利用trie树，利用5次比较可以从26^5＝11881376个可能的关键字中检索出指定的关键字。而利用二叉查找树至少要进行技术分享次比较。

3. trie树的应用：

1. 字符串检索，词频统计，搜索引擎的热门查询

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

        举例：

       1）有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

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

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

       4）1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串

       5）寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

2. 字符串最长公共前缀

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

      1) 给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少.  解决方案：

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

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

        1.  利用并查集（Disjoint Set），可以采用采用经典的Tarjan 算法；

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


3.  排序

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

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

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

       如后缀树，AC自动机等。



原文：http://blog.csdn.net/u013445530/article/details/46640789

内容总结

以上是互联网集市为您收集整理的白话算法与数据结构之【字典树】全部内容，希望文章能够帮你解决白话算法与数据结构之【字典树】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1082270.html

来源：【匿名】