国外科技感强的网站,朔州网站建设哪家便宜,快速设计一个网站,南宁网站优化Trie树的应用: 除了本文引言处所述的问题能应用Trie树解决之外#xff0c;Trie树还能解决下述问题#xff08;节选自此文#xff1a;海量数据处理面试题集锦与Bit-map详解#xff09;#xff1a; 3、有一个1G大小的一个文件#xff0c;里面每一行是一个词#xff0c;词的…Trie树的应用: 除了本文引言处所述的问题能应用Trie树解决之外Trie树还能解决下述问题节选自此文海量数据处理面试题集锦与Bit-map详解 3、有一个1G大小的一个文件里面每一行是一个词词的大小不超过16字节内存限制大小是1M。返回频数最高的100个词。 9、1000万字符串其中有些是重复的需要把重复的全部去掉保留没有重复的字符串。请怎么设计和实现 10、 一个文本文件大约有一万行每行一个词要求统计出其中最频繁出现的前10个词请给出思想给出时间复杂度分析。 13、寻找热门查询搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来每个查询串的长度为1-255字节。假设目前有一千万个记录这些查询串的重复读比较高虽然总数是1千万但是如果去除重复和不超过3百万个。一个查询串的重复度越高说明查询它的用户越多也就越热门。请你统计最热门的10个查询串要求使用的内存不能超过1G。 (1) 请描述你解决这个问题的思路 (2) 请给出主要的处理流程算法以及算法的复杂度。 有了Trie后缀树就容易理解了。本文接下来的第二部分介绍后缀树
前缀树
前缀树又名字典树单词查找树Trie树是一种多路树形结构是哈希树的变种和hash效率有一拼是一种用于快速检索的多叉树结构。
典型应用是用于统计和排序大量的字符串但不仅限于字符串所以经常被搜索引擎系统用于文本词频统计。它的优点是最大限度地减少无谓的字符串比较查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
Trie树也有它的缺点Trie树的内存消耗非常大。
性质不同字符串的相同前缀只保存一份。
操作查找插入删除。
举个栗子给出一组单词inn, int, at, age, adv,ant, 我们可以得到下面的Trie 从上面可以发现一些Trie树的特性
1根节点不包含字符除根节点外的每一个子节点都包含一个字符。
2从根节点到某一节点的路径上的字符连接起来就是该节点对应的字符串。
3每个节点的所有子节点包含的字符都不相同。
4每条边对应一个字母。每个节点对应一项前缀。叶节点对应最长前缀即单词本身。
单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支root-i-in。同理ate, age, adv, 和ant共享前缀a所以他们共享从根节点到节点a的边。
前缀树的应用
前缀树还是很好理解它的应用也是非常广的。
1字符串的快速检索
字典树的查询时间复杂度是O(logL)L是字符串的长度。所以效率还是比较高的。字典树的效率比hash表高。
hash表
通过hash函数把所有的单词分别hash成key值查询的时候直接通过hash函数即可都知道hash表的效率是非常高的为O(1)当然这是对于如果我们hash函数选取的好计算量少且冲突少那单词查询速度肯定是非常快的。那如果hash函数的计算量相对大呢且冲突律高呢这些都是要考虑的因素。
还有就是hash表不支持动态查询什么叫动态查询当我们要查询单词apple时hash表必须等待用户把单词apple输入完毕才能hash查询。当你输入到appl时肯定不可能hash吧。
字典树tries树
对于单词查询这种还是用字典树比较好但也是有前提的空间大小允许字典树的空间相比较hash还是比较浪费的毕竟hash可以用bit数组。 2字符串排序
从上图我们很容易看出单词是排序的先遍历字母序在前面。
减少了没必要的公共子串。 3最长公共前缀
inn和int的最长公共前缀是in遍历字典树到字母n时此时这些单词的公共前缀是in。
4自动匹配前缀显示后缀
我们使用辞典或者是搜索引擎的时候输入appl后面会自动显示一堆前缀是appl的东东吧。
那么有可能是通过字典树实现的前面也说了字典树可以找到公共前缀我们只需要把剩余的后缀遍历显示出来即可。
后缀树
后缀树就是把一串字符的所有后缀保存并且压缩的字典树。相对于字典树来说后缀树并不是针对大量字符串的而是针对一个或几个字符串来解决问题。比如字符串的回文子串两个字符串的最长公共子串等等。
性质一个字符串构造了一棵树树中保存了该字符串所有的后缀。
操作就是建立和应用。 1建立后缀树
比如单词banana它的所有后缀显示到下面的。0代表从第一个字符为起点终点不用说都是字符串的末尾。
以上面的后缀我们建立一颗后缀树。如下图为了方便看到后缀我没有合并相同的前缀。
前面简介的时候我们说了后缀树是把一个字符串所有后缀压缩并保存的字典树。所以我们把字符串的所有后缀还是按照字典树的规则建立就成了下图的样子。这就是后缀树的压缩可见更加节省空间。 最长回文问题的解决:
思维的突破点在于考察回文的半径而不是回文本身。所谓半径就是回文对折后的字串。比如回文MADAM 的半径为MAD半径长度为3半径的中心是字母D。显然最长回文必有最长半径且两条半径相等。还是以MADAM为例以D为中心往左我们得到半径 DAM以D为中心向右我们得到半径DAM。二者肯定相等。因为MADAM已经是单词XMADAMYX里的最长回文我们可以肯定从D往左数的字串 DAMX与从D往右数的子串DAMYX共享最长前缀DAM。而这正是解决回文问题的关键。现在我们有后缀树怎么把从D向左数的字串DAMX变成后缀 呢 到这个地步答案应该明显把单词XMADAMYX翻转XMADAMYXXYMADAMXDAMX就变成后缀了就行了。于是我们把寻找回文的问题转换成了寻找两坨后缀的LCA的问题。当然我们还需要知道 到底查询那些后缀间的LCA。很简单给定字符串S如果最长回文的中心在i那从位置i向右数的后缀刚好是S(i)而向左数的字符串刚好是翻转S后得到的字符串S‘的后缀S(n-i1)。这里的n是字符串S的长度。 可能上面的阐述还不够直观我再细细说明下 1、首先还记得本第二部分开头关于后缀树的定义么 “先说说后缀的定义顾名思义甚至通俗点来说就是所谓后缀就是后面尾巴的意思。比如说给定一长度为n的字符串SS1S2..Si..Sn和整数i1 i n子串SiSi1...Sn便都是字符串S的后缀。” 以字符串SXMADAMYX为例它的长度为8所以S[1..8], S[2..8], ... , S[8..8]都算S的后缀我们一般还把空字串也算成后缀。这样我们一共有如下后缀。对于后缀S[i..n]我们说这项后缀起始于i。
S[1..8], XMADAMYX 也就是字符串本身起始位置为1 S[2..8], MADAMYX起始位置为2 S[3..8], ADAMYX起始位置为3 S[4..8], DAMYX起始位置为4 S[5..8], AMYX起始位置为5 S[6..8], MYX起始位置为6 S[7..8], YX起始位置为7 S[8..8], X起始位置为8 空字串记为$。 2、对单词XMADAMYX而言回文中心为D那么D向右的后缀DAMYX假设是S(i)当N8i从1开始计数i4时便是S(4..8);而对于翻转后的单词XYMADAMX而言回文中心D向右对应的后缀为DAMX也就是S(N-i1)(N8i4便是S‘5..8 。此刻已经可以得出它们共享最长前缀即LCADAMYXDAMXDAM。有了这套直观解释算法自然呼之欲出
预处理后缀树使得查询LCA的复杂度为O(1)。这步的开销是O(N)N是单词S的长度 对单词的每一位置i(也就是从0到N-1)获取LCA(S(i), S‘(N-i1)) 以及LCA(S(i1), S’(n-i1))。查找两次的原因是我们需要考虑奇数回文和偶数回文的情况。这步要考察每坨i所以复杂度是O(N) 找到最大的LCA我们也就得到了回文的中心i以及回文的半径长度自然也就得到了最长回文。总的复杂度O(n)。
参考博客
https://blog.csdn.net/v_july_v/article/details/6897097
https://blog.csdn.net/u013949069/article/details/78056102
