算法设计与分析课件 56 字典树_第1页
算法设计与分析课件 56 字典树_第2页
算法设计与分析课件 56 字典树_第3页
算法设计与分析课件 56 字典树_第4页
算法设计与分析课件 56 字典树_第5页
已阅读5页，还剩8页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析本节要点CONTENTS字典树字典树字典树，又称Trie、单词查找树，是一种树形结构，也是哈希树的一种变种，主要用于统计、排序和存储大量的字符串（但不限于字符串），经常被搜索引擎系统用于文本词频统计。字典树利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。字典树例如，bee是一个单词，beer也是一个单词，可以在每个单词结束的位置都加一个end[]标记，表示从根到这里有一个单词。字典树1．字典树的插入插入操作指将一个字符串插入字典树中。字典树可以采用数组或链表存储，这里采用数组存储实现静态链表。字典树（1）插入一个单词s=“bike”，首先将字符转换为数字，s[0]–‘a’=1，判断trie[1][1]为0，令trie[1][1]=2，相当于创建一个新的节点（节点的存储下标为2）。字典树字典树算法实现字典树2．字典树的查找在字典树中查找一个字符串是否存在，则和插入操作一样，首先将字符转换为数字，在字典树中查找，若查找的位置为0，则说明不存在，否则继续向下查找；在字符串处理完毕后，判断此处是否有单词结束标记，若有，则查找成功。字典树字典树算法实现字典树3．字典树的应用（1）字符串检索。事先将字符串（字典）存储到Trie，查找字符串、出现的频率和搜索引擎的热门查询。（2）前缀统计。统计一个字符串所有前缀单词的个数，只需统计从根到叶子路径上单词出现的个数，也可以判断一个单词是否为另一个单词的前缀。字典树（3）最长公共前缀。两个字符串的最长公共前缀的长度就是它们所在节点最近公共祖先到根的长度。（4）排序。利用字典树进行串排序，对字典树先序遍历，输出的相应字符串便是按字典序排序的结果。（5）作为其他数据结构与算法的辅助结构，例如后缀树、AC自动机等。算法分析时间复杂度：若单词的总长度为N、字符的种类为k、插入的字符串长度为n，则构建字典树的时间复杂度为O(N)，插入字符串的时间复杂度为O(n)。查找的时间复杂度为O(n)。空间复杂度：构

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论