还剩7页未读,继续阅读
文本内容:
剑指树(字典树)Offer——Trie树Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种典Trie型应用是统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计它的优点是最大限度地减少无谓的字符串比较,查询效率比哈希表高的核心思想是空间换时间利用字符串的公共前缀来降低查询时间的开销以达到提高Trie效率的目的树也有它的缺点,树的内存消耗非常大当然,或许用左儿子右兄弟的方法建树Trie Trie的话,可能会好点可见,优化的点存在于建树过程中和二叉查找树不同,在树中,每个结点上并非存储一个元素树把要查找的关键词看trie trie作一个字符序列,并根据构成关键词字符的先后顺序构造用于检索的树结构在树上进行trie检索类似于查阅英语词典个基本性质3根节点不包含字符,每条边代表一个字符L.从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串
2.每个节点的所有子节点包含的字符都不相同3字典树的构建题目给你个长度不超过的单词对于每一个单词,我们要判断他出没出现过,如10000010果出现了,求第一次出现在第几个位置分析这题当然可以用来解决,但是本文重点介绍的是树,因为在某些方面它的用hash trie途更大比如说对于某一个单词,我们要询问它的前缀是否出现过这样就不好搞了,而hash用还是很简单trie假设我要查询的单词是那么在他前面的单词中,以之类开头的我显然不必考虑abed,b,c,d,f而只要找以开头的中是否存在就可以了同样的,在以开头中的单词中,我们只要考a abeda虑以作为第二个字母的,一次次缩小范围和提高针对性,这样一个树的模型就渐渐清晰了b好比假设有这个单词,我们构建的树就是如下图这样的(图b,abc,abd,bed,abed,efg,hii6片来自百度百科)如上图所示,对于每一个节点,从根遍历到他的过程就是一个单词,如果这个节点被标记为红色,就表示这个单词存在,否则不存在那么,对于一个单词,我只要顺着他从根走到对应的节点,再看这个节点是否被标记为红色就可以知道它是否出现过了把这个节点标记为红色,就相当于插入了这个单词这样一来我们查询和插入可以一起完成重点体会这个查询和插入是如何一起完成的,稍后,下文具体解释我们可以看到,树每一层的节点数是八个英文字母级别的所以为了节省空间,trie26i26我们用动态链表,或者用数组来模拟空间的花费,不会超过单词数单词长度X已知个由小写字母构成的平均长度为的单词,判断其中是否存在某个串为另一个串的前n10缀子串下面对比种方法3最容易想到的.即从字符串集中从头往后搜,看每个字符串是否为字符串集中某个字符串1的前缀,复杂度为八On
22.使用hash我们用hash存下所有字符串的所有前缀子串,建立存有子串hash的复杂度为而查询的复杂度为On*len,On*01=On
3.使用trie因为当查询如字符串abc是否为某个字符串的前缀时,显然以b,c,d.…等不是以开头的字符串就不用查找了所以建立的复杂度为而建立+查询在中是可以a trieOn*len,trie同时执行的,建立的过程也就可以称为查询的过程,就不能实现这个功能所以总的复杂hash度为实际查询的复杂度也只是说白了,就是树的平均高度为所以On*len,Olen Trieh len,树的查询复杂度为好比一棵二叉平衡树的高度为则其查询,插入的平Trie0h=0len logN,o均时间复杂度亦为0logN查询树是简单但实用的数据结构,通常用于实现字典查询我们做即时响应用户输入的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搭建的基本算法也很简单,无非是逐一把每个单词的每个字母插入插入前先TrieTrie看前缀是否存在如果存在,就共享,否则创建对应的节点和边比如要插入单词就有下add,面几步考察前缀“a”,发现边a已经存在于是顺着边a走到节点a考察剩下的字符串“dd”的前缀“d”,发现从节点a出发,已经有边d存在于是顺着边走到节点d ad考察最后一个字符“d”,这下从节点ad出发没有边d了,于是创建节点ad的子节点add,并把边标记为ad-add do查找分析在树中查找一个关键字的时间和树中包含的结点数无关,而取决于组成关键字的字trie符数而二叉查找树的查找时间和树中的结点数有关Olog2n如果要查找的关键字可以分解成字符序列且不是很长,利用树查找速度优于二叉trie查找树例如:若关键字长度最大是则利用树,利用次比较可以从八个5,trie5265=11881376可能的关键字中检索出指定的关键字而利用二叉查找树至少要进行次比较应用字符串检索,词频统计,搜索引擎的热门查询
1.事先将已知的一些字符串字典的有关信息保存到树里,查找另外一些未知字符串trie是否出现过或者出现频率举例、有一个大小的一个文件,里面每一行是一个词,词的大小不超过字节,内11G16存限制大小是返回频数最高的个词1M
100、给出个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出2N现的顺序写出所有不在熟词表中的生词、给出一个词典,其中的单词为不良单词单词均为小写字母再给出一段文本,文3本的每一行也由小写字母构成判断文本中是否含有任何不良单词例如,若是不良单词,rob那么文本含有不良单词problem、万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字41000符串请怎么设计和实现?、一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前510个词,请给出思想,给出时间复杂度分析、寻找热门查询搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记6录下来,每个查询串的长度为字节假设目前有一千万个记录,这些查询串的重复读比1-255较高,虽然总数是千万,但是如果去除重复和,不超过百万个一个查询串的重复度越高,13说明查询它的用户越多,也就越热门请你统计最热门的个查询串,要求使用的内存不能10超过京东笔试题简答题与此类似1G请描述你解决这个问题的思路;1请给出主要的处理流程,算法,以及算法的复杂度2字符串最长公共前缀
2.树利用多个字符串的公共前缀来节省存储空间,反之,当我们把大量字符串存储Trie到一棵树上时,我们可以快速得到某些字符串的公共前缀举例trie给出个小写英文字母串,以及个询问,即询问某两个串的最长公共前缀的长1N Q度是多少.解决方案首先对所有的串建立其对应的字母树此时发现,对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数,于是,问题就转化为了离线的最近公共祖先Offline Least简称问题Common Ancestor,LCA而最近公共祖先问题同样是一个经典问题,可以用下面几种方法利用并查集可以采用经典的算法;
1.Disjoint Set,Tarjan求出字母树的欧拉序列后,就可以转为经典的最小值查询
2.Euler Sequence简称问题了;Range MinimumQuery,RMQ排序
3.树是一棵多叉树,只要先序遍历整棵树,输出相应的字符串便是按字典序排序Trie的结果举例给你个互不相同的仅由一个单词构成的英文名,让你将它们按字典序从N小到大排序输出.作为其他数据结构和算法的辅助结构4如后缀树,自动机等AC举例下面以字典树的构建与单词查找为例TrieTreeN ode.j ava在上查看代码片派生到我的代码片|html]view plaincopy printCODEpackage cn.edu.ujn.trieTree;public classTrieTreeNode{记录该字符出现次数int nCount;//记录该字符char ch;////记录子节点TrieTreeNode[]child;final intMAX_SIZE=26;public TrieTreeNode{nCount=l;child=new TrieTreeNode[MAX_SIZE|;}TrieTree.java在上查看代码片派生到我的代码片[html]view plaincopy printCODEpackage cn.edu.ujn.trieTree;public classTrieTree{〃字典树的插入和构建public voidcreateTrieTrieTreeNode node,String str{if str==null||str.length==0{return;char[]letters=str.toCharArray;for inti=0;iletters.length;i++{//用相对于字母的值作为下标索引,也隐式地int pos=letters[i]-*3*;a记录了该字母的值if node.child[pos]==null{node.child[pos]=new TrieTreeNode;}else{node.child[pos].nCount++;node.ch=letters[i];node=node.child[pos];//字典树的查找public intfindCountTrieTreeNode node,String str{二二if strnull||str.length==0{return-1;char[]letters=str.toCharArray;for inti=0;iletters.length;i++{int pos=lettersi]-a;if node.child[pos]==null{return0;}else{node=node.child[pos];return node.nCount;Test.java在上查看代码片派生到我的代码片[html]view plaincopy printCODEpackage cn.edu.ujn.trieTree;public classTest{public staticvoid mainString||args{/***老师交给他很多单词只有小写字母组成,不会有重复的单词出现,Problem Description现在老师要他统计*出以某个字符串为前缀的单词数量单词本身也是自己的前缀.*/String[]strs={banana,band,bee,absolute,“acm”};String[]prefix={“ba“,“band“,“abc”};TrieTree tree=new TrieTree;TrieTreeNode root=new TrieTreeNode;for Strings:strs{tree.createTrieroot,s;}//tree.printAHWords;for Stringpre:prefix{int num=tree.findCountroot,pre;System.out.printlnpre++num;小结看过上面的代码,是否发现这个代码有什么问题呢?尽管这个实现方式查找的效率很高,时间复杂度是是要查找的单词中包含的字母的个数但是确浪费大量存放空指针的存0m,m储空间因为不可能每个节点的子节点都包含个字母的所以对于这个问题,字典树存在26的意义是解决快速搜索的问题,所以采取以空间换时间的作法也毋庸置疑树占用内存较大,例如处理最大长度为、全部为小写字母的一组字符串,则Trie20可能需要个节点来保存数据而这样的树实际上稀疏的十分厉害,可以采用左儿子右兄2620弟的方式来改善,也可以采用需要多少子节点则添加多少子节点来解决不要类似网上的示例,每个节点初始化时就申请一个长度为的数组26上提到了采用三数组和二数组来解决Wiki TrieTripple-Array TrieTrieDouble-Array Trie该问题,此外还有压缩等方式来缓解该问题示例优化TrieTreeNode.java在上查看代码片派生到我的代码片[html]view plaincopy printCODEpackage cn.edu.ujn.trieTreeMap;import java.util.HashMap;import java.util.Map;public classTrieNode{记录该字符出现次数int nCount;////记录子节点MapCharacter,TrieNode childdren;public TrieNode{nCount=1;childdren=new HashMapCharacter,TrieNode;TrieTree.java在上查看代码片派生到我的代码片[html]view plaincopy printCODEpackage cn.edu.ujn.trieTreeMap;//利用动态创建节点Mappublic classTrieTree{//字典树的插入和构建public voidinsertTrieNode node,String word{for inti=0;iword.length;i++{Character c=new Characterword.charAti;if!node.childdwww.shanxiwang.netren.containsKeyc{node.childdren.putc,new TrieNodeO;}else{node.childdren.getc.nCount++;node=node.childdren.getc;//字典树的查找public intsearchTrieNode node,String word{for inti=0;iword.length;i+4-{Character c=new Characterword.charAti;if!node.childdren.containsKeyc{return0;node=node.childdren.getc;return node.nCount;Test.java在上查看代码片派生到我的代码片|html]view plaincopy printCODE packagecn.edu.ujn.trieTreeMap;public classTest{public staticvoid mainString[]args{/***老师交给他很多单词只有小写字母组成,不会有重复的单词出现,Problem Description现在老师要他统计*出以某个字符串为前缀的单词数量单词本身也是自己的前缀.*/String!]strs二{banana,band,“bee,absolute,“acm”};String[]prefix={ba\“band“,“abc”};TrieTree tree=new TrieTree;TrieNode node=new TrieNode;for Strings:strs{tree.insertnode,s;//tree.printAllWords;for Stringpre:prefix{int num=tree.searchnode,pre;System.out.printlnpre++num;计算结果如下:累Servers OConsole_______________;terminatedTest7[Java Application]E Vba2b3n band1abc0经过以上方法的改进,可避免冗余节点的存在将字典树的优势进一步放大当然,也可以使用左儿子右兄弟的形式创建字典树此方法后续介绍〜文件读入在上查看代码片派生到我的代码片[html]view plaincopy printCODE packagecn.edu.ujn.trieTreeMap;import java.io.BufferedReader;import java.io.File;import java.io.FilelnputStream;import java.io.InputStreamReader;public classTest{public staticvoid mainString[]args{/***老师交给他很多单词只有小写字母组成,不会有重复的单词出现,Problem Description现在老师要他统计*出以某个字符串为前缀的单词数量单词本身也是自己的前缀.*/String[]strs={banana,band,bee,absolute,acm”};String[]prefix={“网易:软件”,“band,“abc”};TrieTree tree=new TrieTree;Tri eNodenode=new TrieNode;二BufferedReader brnull;try Filefile=new FilenC://Users//SHQ//Desktop//Offer.txtn;〃读取语料库words.txt二br newBufferedReadernew InputStreamReadernewFilcInputStrcamfile.gctAbsolutcPath/GBKn;String word=,,n;while word=br.readLine!=null{tree.insertnode,word;}catch Exceptione{//TODO:handle exceptione.printStackTrace;/*for Strings:strs{tree.insertnode,s;}*///tree.printAllWords;for Stringpre:prefix{int num=tree.searchnode,pre;System.out.printlnpre+“+num;Offer,txt文本内谷如下:计算结果如下•»Servers OConsolet7[Java Application]E:\Andrc软件mWO•*}m«o-胸号K8353l07068«
63.coe杭构保逐夕演学与现班理爹论计日;”提里论奸试机与开件人工与短发学爆士量与汽识方并二智疑讣式!ibq|可知计算结果正确而且出现了中文字符,对于数字的操作同理而利用第一种方法就无法实现固定分配内存只能使用动态分配机制tMbaabnerlndci1300t an,«.,R*9yQft8X9KBa9«8。