文档章节

软考程序员课程精讲之Trie树的优点

软考希赛教育
 软考希赛教育
发布于 2017/06/26 17:43
字数 568
阅读 4
收藏 0

   欲参加2017年下半年软考程序员考试的同学,现在可以着手复习了。下面是希赛小编为大家整理的部分软考程序员课程中的知识点,下文主讲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必定是某个字符串的前缀。

 

© 著作权归作者所有

共有 人打赏支持
软考希赛教育
粉丝 1
博文 104
码字总数 98019
作品 0
长沙
私信 提问
Google 面试题 | 字典里面的最长单词

专栏 | 九章算法 网址 | http://www.jiuzhang.com 三角形分割线 给定一个字符串列表words,找到words最长的word,使得这个word可用words中的其他word一次一个字符地构建。如果有多个可选答案...

02/10
0
0
Aho-Corasick算法的Java实现与分析

简介 Aho-Corasick算法简称AC算法,通过将模式串预处理为确定有限状态自动机,扫描文本一遍就能结束。其复杂度为O(n),即与模式串的数量和长度无关。 思想 自动机按照文本字符顺序,接受字符...

SuShine
08/03
0
0
Trie 树实现与应用

Trie树 基本概念  Trie树又称字典树,它是用来查询字符串的一种数据结构。它每一个节点都有26个子节点,所以是26叉树。优点查询字符串的时候速度快,缺点浪费大量空间。  当一个字符串长为...

sdoyuxuan
01/24
0
0
我的CCIE自学之路

写在最前面 最近发现很多在校生/初入社会的年轻人,比较迷茫… 下面给大家分享一下我的网络工程师自学之路,希望对大家有所帮助。本人就读于某矿业大学,信息安全专业(这个跟在音乐院校,学...

永恒2222
2017/11/01
0
0
Trie Tree 实现中文分词器

Trie Tree 简介 Trie Tree,又称单词字典树、查找树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频...

大海之中
07/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

day150-2018-11-17-英语流利阅读-待学习

歪果仁也疯狂:海外版抖音的征途 毛西 2018-11-17 1.今日导读 海外版抖音 TikTok 于 2017 年 5 月上线海外,至今覆盖全球 150 多个国家和地区,月活跃用户数已突破 5 亿。然而,“出海”的抖...

飞鱼说编程
今天
11
0
分布式学习最佳实践:从分布式系统的特征开始(附思维导图)

什么是分布式系统 回到顶部   分布式系统是由一组通过网络进行通信、为了完成共同的任务而协调工作的计算机节点组成的系统。分布式系统的出现是为了用廉价的、普通的机器完成单个计算机无法...

dragon_tech
今天
4
0
TOKEN设计

TOKEN设计 Api_Token 首先需要知道API是什么? API(Application Programming Interface)即应用程序接口。你可以认为 API 是一个软件组件或是一个 Web 服务与外界进行的交互的接口。而我们在...

DrChenXX
今天
3
0
浅谈“李氏代换”——从纪念金庸和斯坦李说起

李氏代换(LSP)简介 李氏代换是软件设计的一个原则,又名依赖倒转原则或依赖倒置原则,其衍生原则有接口分离原则等。该原则由Barbara Liskov于1988年提出。 该原则指出,程序中高级别的元素...

SamYjy
今天
38
0
JavaScript实现在线websocket WSS测试工具 -toolfk程序员工具网

本文要推荐的[ToolFk]是一款程序员经常使用的线上免费测试工具箱,ToolFk 特色是专注于程序员日常的开发工具,不用安装任何软件,只要把内容贴上按一个执行按钮,就能获取到想要的内容结果。T...

toolfk
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部