压缩前缀树是什么

小嘿 QA 2020-04-21 16:17:30 阅读(...)

在计算机科学中,基数树,或称压缩前缀树,是一种更节省空间的Trie(前缀树)。对于基数树的每个节点,如果该节点是确定的子树的话,就和父节点合并。基数树可用来构建关联数组。 用于IP 路由。 信息检索中用于文本文档的倒排索引。

在计算机科学中,基数树,或称压缩前缀树,是一种更节省空间的 Trie(前缀树)。对于基数树的每个节点,如果该节点是确定的子树的话,就和父节点合并。基数树可用来构建关联数组。 用于 IP 路由。 信息检索中用于文本文档的倒排索引。

基数树是什么

简介

基数树可看做是以二进制位串为关键字的 trie 树,是一种多叉树形结构,同时又类似多层索引表,每个中间节点包含指向多个子节点的指针数组,叶子节点包含指向实际的对象的指针(由于对象不具备树节点结构,因此将其父节点看做叶节点)。基数树也被设计成多道树,以提高磁盘交互性能。同时,基数树也是按照字典序来组织叶节点的,这种特点使之适合持久化改造,加上它的多道特点,灵活性较强,适合作为区块链的基础数据结构,构建持久性区块时较好地映射各类数据集合上。基数树支持插入、删除、查找操作。查找包括完全匹配、前缀匹配、前驱查找、后继查找。所有这些操作都是 O(k)复杂度,其中 k 是所有字符串中最大的长度。

前缀树

在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie 这个术语来自于 retrieval。根据词源学,trie 的发明者 Edward Fredkin 把它读作/ˈtriː/ “tree”。但是,其他作者把它读作/ˈtraɪ/ “try”。trie 中的键通常是字符串,但也可以是其它的结构。trie 的算法可以很容易地修改为处理其它结构的有序序列,比如一串数字或者形状的排列。比如,bitwise trie 中的键是一串位元,可以用于表示整数或者内存地址。trie 树常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。

0个人收藏 收藏

评论交流

泪雪默认头像 请「登录」后参与评论
  1. 加载中..

相关推荐

  • 抖音 Tiktok

    怎么清理抖音垃圾和缓存

    清理抖音缓存首先打开抖音进入主页面,点击右下角我选项,点击右上方的三横图标,接着点击设置选项,点击清理占用空间,点击最上方临时文件后面的清空按钮,最后在弹出的窗口中点击清空即可;还可以通过手机设置中的应用管理来清除数据。
  • Word

    Word转Excel表格怎么转换

    Word转Excel表格首先新建Excel表格,在上方菜单栏点击“插入”,接着在工具栏点击“对象”,在弹窗里点击“由文本创建”然后点击“浏览”,在浏览窗口选择需要转换的Word文档,然后点击“确认”就可以加入并且编辑了。
  • 压缩 Compression

    压缩文件打不开是什么原因

    压缩文件打不开得原因可能是电脑没有安装压缩软件,不支持打开压缩文件包;打开压缩文件的方式错误,需将打开方式调整为压缩软件;压缩文件被设置为保密文件,需要密码才可以打开;压缩文件包出现了损坏,需要对方重新发送才行;电脑中病毒,杀毒后即可打开。
  • 压缩文件 Compressed file

    压缩文件打不开怎么办

    缩文件在创建、上传或下载过程中被损坏导致压缩文件打不开,可以尝试修复,无法修复只能重新下载;电脑压缩文件有病毒,先查杀病毒,完毕之后再重新打开压缩文件;解压软件跟压缩文件有冲突,不兼容,可以更新或更换压缩解压软件。
  • 公告牌 Billboard

    Billboard是什么

    Billboard又名公告牌,是美国娱乐杂志兼媒体品牌。在美国的一个小酒馆中诞生,其主要作用是制作单曲排行榜,该榜单被认为是美国乃至欧美国家流行乐坛最具权威的一份单曲排行榜。
  • 快捷方式 shortcuts

    快捷方式怎么恢复原文件

    文件变成快捷方式恢复的方法首先打开计算机,并点击菜单栏工具;然后点击下拉选项文件夹选项;最后找到并取消勾选隐藏受保护的操作系统文件(推荐),并点击显示隐藏的文件、文件夹和驱动器即可。