一:什么是Trie树
Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
它有3个基本性质:
1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。
二:树的构建
举个在网上流传颇广的例子,如下:
题目:给你100000个长度不超过10的单词。对于每一个单词,我们要判断他出没出现过,如果出现了,求第一次出现在第几个位置。
分析:这题当然可以用hash来解决,但是本文重点介绍的是trie树,因为在某些方面它的用途更大。比如说对于某一个单词,我们要询问它的前缀是否出现过。这样hash就不好搞了,而用trie还是很简单。
现在回到例子中,如果我们用最傻的方法,对于每一个单词,我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是O(n2 )。显然对于100000的范围难以接受。现在我们换个思路想。假设我要查询的单词是abcd,那么在他前面的单词中,以b,c,d,f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的,在以a开头中的单词中,我们只要考虑以b作为第二个字母的,一次次缩小范围和提高针对性,这样一个树的模型就渐渐清晰了。
好比假设有b,abc,abd,bcd,abcd,efg,hii 这6个单词,我们构建的树就是如下图这样的:
当时第一次看到这幅图的时候,便立马感到此树之不凡构造了。单单从上幅图便可窥知一二,好比大海搜人,立马就能确定东南西北中的到底哪个方位,如此迅速缩小查找的范围和提高查找的针对性,不失为一创举。
ok,如上图所示,对于每一个节点,从根遍历到他的过程就是一个单词,如果这个节点被标记为红色,就表示这个单词存在,否则不存在。
那么,对于一个单词,我只要顺着他从根走到对应的节点,再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色,就相当于插入了这个单词。
这样一来我们查询和插入可以一起完成,所用时间仅仅为单词长度,在这一个样例,便是10。
我们可以看到,trie树每一层的节点数是26i 级别的。所以为了节省空间。我们用动态链表,或者用数组来模拟动态。空间的花费,不会超过单词数×单词长度。
三:前缀查询
已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法:
最容易想到的:即从字符串集中从头往后搜,看每个字符串是否为字符串集中某个字符串的前缀,复杂度为O(n2)。
使用hash:我们用hash存下所有字符串的所有的前缀子串,建立存有子串hash的复杂度为O(n*len)
,而查询的复杂度为O(n)* O(1)= O(n)
。
使用trie:因为当查询如字符串abc是否为某个字符串的前缀时,显然以b,c,d....等不是以a开头的字符串就不用查找了。所以建立trie的复杂度为O(n*len)
,而建立+查询在trie中是可以同时执行的,建立的过程也就可以成为查询的过程,hash就不能实现这个功能。所以总的复杂度为O(n*len)
,实际查询的复杂度也只是O(len)
。(说白了,就是Trie树的平均高度h为len,所以Trie树的查询复杂度为O(h)=O(len)
。好比一棵二叉平衡树的高度为logN,则其查询,插入的平均时间复杂度亦为O(logN)
)。
四:查询
Trie树是简单但实用的数据结构,通常用于实现字典查询。我们做即时响应用户输入的AJAX搜索框时,就是Trie开始。本质上,Trie是一颗存储多个字符串的树。相邻节点间的边代表一个字符,这样树的每条分支代表一则子串,而树的叶节点则代表完整的字符串。和普通树不同的地方是,相同的字符串前缀共享同一条分支。下面,再举一个例子。给出一组单词,inn, int, at, age, adv, ant, 我们可以得到下面的Trie:
可以看出:
每条边对应一个字母。
每个节点对应一项前缀。叶节点对应最长前缀,即单词本身。
单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支,root->i->in。同理,ate, age, adv, 和ant共享前缀"a",所以他们共享从根节点到节点"a"的边。
查询操纵非常简单。比如要查找int,顺着路径i -> in -> int就找到了。
搭建Trie的基本算法也很简单,无非是逐一把每则单词的每个字母插入Trie。插入前先看前缀是否存在。如果存在,就共享,否则创建对应的节点和边。比如要插入单词add,就有下面几步:
1. 考察前缀"a",发现边a已经存在。于是顺着边a走到节点a。
2. 考察剩下的字符串"dd"的前缀"d",发现从节点a出发,已经有边d存在。于是顺着边d走到节点ad
3. 考察最后一个字符"d",这下从节点ad出发没有边d了,于是创建节点ad的子节点add,并把边ad->add标记为d。
五:Trie树的应用
第一:词频统计;第二: 前缀匹配;第三:去重
适用范围:数据量大,重复多,但是数据种类小可以放入内存
基本原理及要点:实现方式,节点孩子的表示方式
扩展:压缩实现。
面试题有:有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。
解答思路:https://my.oschina.net/u/4167465/blog/3077142
转载于:https://my.oschina.net/u/4167465/blog/3080177
分享到:
相关推荐
总的来说,Java实现的字典树TrieTree是一个强大的工具,尤其适用于处理大量字符串数据,如四六级高频词汇的存储和查询。通过理解和运用这种数据结构,我们可以提高算法效率,优化应用程序的性能。
字典树,也被称为前缀树或Trie,是一种用于高效存储和检索字符串的数据结构。它的设计灵感来源于二叉搜索树,但与之不同的是,字典树将字符串的每个字符作为节点,使得具有相同前缀的字符串共享相同的路径。这种特性...
ACM Trie树 模板,字典树模板,数据结构
基于Java链表实现的字典树(trie),实现了增删改查等功能,它说摘要必须大于50字我还能说啥啥啥啥
**哈希 Trie 树(HashTrie)与字典树(Trie树)详解** 哈希 Trie 树,也称为 HashTrie 或者是哈希化的 Trie 树,是一种结合了哈希表和 Trie 数据结构特点的数据结构。它在 Trie 树的基础上引入了哈希函数,提高了...
总结来说,字典树Trie是一种高效的数据结构,特别适合处理大量字符串并需要快速查找公共前缀的情况。虽然它的空间需求较高,但在时间和性能优化方面,Trie在某些应用场景下优于传统的哈希表。通过Python的嵌套字典,...
这个Java程序利用了数据结构——字典树(Trie),也被称为前缀树或PAT树,它在处理字符串相关的搜索问题时表现出色。下面我们将深入探讨字典树的工作原理及其在拼写检错中的应用。 字典树是一种树形数据结构,每个...
字典树,也被称为Trie或前缀树,是一种用于高效存储和检索字符串的数据结构。在计算机科学中,字典树常被用于实现自动补全、关键词搜索、IP路由等功能,因为它能快速查找以特定前缀开头的所有字符串。下面将详细介绍...
在IT领域,字典树(Trie,也称为前缀树或字首树)是一种用于存储动态集合或关联数组的数据结构。它以高效的方式处理字符串查询,尤其适用于查找具有共同前缀的单词。字典树的主要优点是它可以快速地通过共享前缀来...
字典树是一种树形结构,也称为单词查找树或Trie树。它是一种哈希树的变种,典型应用是用于统计、排序和保存大量的字符串(但不仅限于字符串)。字典树的优点是利用字符串的公共前缀来节约存储空间,最大限度地减少...
在IT领域,字典树(Trie,也称为前缀树或字首树)是一种非常重要的数据结构,常用于高效地存储和检索字符串。在这个场景中,标题“字典树查找统计及单词”指的是利用字典树进行单词查找、统计以及可能的分析操作。...
在算法竞赛中,字典树(Trie)是一种常用的数据结构,用于解决字符串匹配问题。下面是字典树的基本概念和实现细节。 字典树的基本概念 字典树是一种树形数据结构,用于存储字符串集合。它的每个节点都可以包含一个...
在编程领域,可变长数组(也称为动态数组)和字典树(又称Trie树或前缀树)是两种非常重要的数据结构。它们在不同的场景下有着广泛的应用,尤其在处理大量数据时能展现出高效的性能。 首先,我们来详细讨论可变长...
字典树,也被称为Trie或前缀树,是一种用于高效存储和检索字符串的数据结构。在C语言中实现字典树,主要涉及到链表、指针操作和动态内存分配等核心概念。以下是对字典树算法及其C语言实现的详细说明: ### 1. 字典...
Trie树中的每个节点通常包含指向26个可能字母(这里是英文字符)的指针,因此得名二十六叉字典树。 #### 2. 二十六叉字典树的基本概念与特性 - **定义**:Trie是一种用于快速检索的二十六叉树结构。 - **关键字的...
字典树,又称为Trie树或前缀树,是一种高效的数据结构,主要用于存储和检索具有公共前缀的字符串。这种数据结构能够大大减少字符串比较的次数,提高查询效率,尤其在处理大量字符串时效果显著。在搜索引擎系统中,...
字典树,也称为前缀树或Trie树,是一种用于存储字符串数据结构,它能够高效地支持诸如查找、插入和删除等操作。由于其在字符串处理上的独特优势,字典树被广泛应用于诸多领域,如文本编辑器的自动补全功能、搜索引擎...
在计算机科学领域,字典树(Trie Tree),也被称为前缀树或关键字树,是一种用于存储字符串集合的高效数据结构。与传统的搜索树相比,字典树能够通过共享公共前缀来节省空间,特别适用于处理大量词汇的查找、插入和...
在IT领域,字典树(Trie)是一种高效的数据结构,用于存储字符串集合。它能够快速地进行前缀查找、插入和删除操作。字典树的每个节点代表一个字符串的前缀,根节点代表空字符串,每个节点的子节点对应一个字符,节点...