17. 简洁数据结构 I

17. Succinct Structures I

频道:MIT OpenCourseWare · 时长:1:20:11 · 发布:2013-12-18 · 播放:16860

在 YouTube 观看

简介

Erik Demaine 的 MIT 6.851 高级数据结构讲座,介绍简洁数据结构,涵盖 rank、select 和 trie。这是 2012 年春季课程的一部分。

HN 为什么推荐

HN 推荐它作为来自权威专家的清晰、高质量的简洁数据结构入门。

Erik Demaine [1] 在 2012 年 MIT 6.851 高级数据结构课程中做了两场关于简洁数据结构的精彩讲座 [2] — HN, 2018

算法与数据结构 · 大学讲座与课程

中文字幕节选

以下内容根据知识共享许可协议提供。 您的支持将帮助MIT OpenCourseWare 继续免费提供高质量的教育资源。 如需捐款或查看来自数百门MIT课程的 更多材料,请访问MIT OpenCourseWare,网址是osw.mit.edu。 ERIK DEMAINE:好的。今天我们开始数据结构的新章节。 这将持续两节课, 所以本周讲简洁数据结构,目标是实现非常小的空间。 首先要做的是定义“小”的含义。 大多数简洁数据结构也是静态的, 尽管也有少数是动态的。 我们将重点讨论静态数据结构。 总的来说,关键是将你熟悉的数据结构 进行改造——今天我们将讨论两种。 一种是二叉trie,它有杀手级 应用,特别是用于二叉后缀树。 所以可以是压缩trie,等等。 但这里我们假设字母表是二进制的。 很多内容已经推广到更大的字母表。 我会稍微介绍一下。 但为了简单起见,在讲座中我将坚持使用二进制字母表。 我们要看的另一个数据结构 是位向量,即一行n个比特。 你想进行有趣的操作, 比如在常数时间内找到第i个1比特。 这些在线性空间中是容易实现的, 线性空间意味着O(n)个字。 比如如果你想实现一个trie,每个节点有一个指针,两个指针 每个节点,那很容易。 位向量你可以存储一个包含所有1的位置的数组。 所以线性空间很容易实现,但线性空间不是最优的。 我们将追求三种意义上的小空间。 最好的版本是隐式的。 隐式数据结构意味着你使用最优的比特数 加上一个常数。 但这里我们关注的是比特,不是字。 如果你转换一个线性字数据结构, 字是O(n)乘以w比特,来存储像n比特向量这样的东西, 你应该只使用O(n)比特,而不是O(nw)比特。 理想情况下,如果你使用n比特加上一个常数,那就完美了。 加上一个常数本质上 是因为有时最优数量不是整数。 存储非整数个比特很困难,所以加一个常数。 我的意思是,如果加上O(log n)比特之类的,我也不太介意。 但通常,这里的目标是常数。 有时你真的可以得到零。 但次优的是简洁数据结构, 目标是达到opt加上opt的小o比特。 所以关键是要在前面得到一个常数因子1。 然后在这个范围内最差的情况仍然相当不错。 它是O(opt)比特。 例如,如果你存储一个n比特向量, 如果你使用O(n)比特,那仍然比O(nw)比特好。 通常,紧凑至少节省一个因子 w,相对于你通常所说的线性空间数据结构。 所以这是大的节省,因子w。 但这里有一个常数。 有时你想去掉那个常数,使其为1。 如果你有,比如说,另一个sqrt(n)或小o 的n比特额外空间,那也不算太糟。 但当然,理想情况是不需要额外空间,而这就是隐式的。 现在,这有点令人困惑。 我通常把这一领域称为简洁数据结构,来指代所有这三种。 但中间那种被称为简洁。 通常目标是追求简洁, 因为隐式非常困难,而紧凑 有点像朝着简洁的热身。

HN 上的讨论

我绝对不是这个领域的专家,但最近我对学习“简洁数据结构”产生了兴趣,据我理解,它在生物信息学中有其用武之地。学习这个主题一直很有挑战性,因为大部分信息来自计算机科学论文和文章,这些信息以非常正式、数学化的方式呈现,而我并不习惯。通常,在考虑数据结构和算法时,我们主要关注的是优化速度。空间复杂度通常不是那么重要的考虑因素。简洁数据结构的关键在于创造方法,在实现良好运行时性能的同时,以“压缩”格式表示数据。我认为这在DNA测序等场景中很有用,因为数据集非常庞大。我很期待查看帖子中的一些链接,如果其他人也有兴趣了解更多关于简洁数据结构的知识,以下是我推荐的一些资源:Ben Langmead教授的YouTube频道:[LINK] Alex Bowe的博客有一些不错的内容:[LINK] Erik Demaine教授在MIT高级数据结构课程中的“简洁”讲座,在YouTube上:[VIDEO] Edw… — denvaar, 2022-11
有没有适合程序员(非计算机科学研究人员)的简洁数据结构的实用概述?另外,我几天前刚开始研究简洁动态图数据结构,最终看到了一篇非常有趣的论文,如果有人感兴趣:[LINK] 还会加上这个,介绍简洁数据结构的讲座:[VIDEO] 好了,这是对这条评论的最后一次编辑,但我相信其他人会觉得这有用。我还找到了一本好书(还没读过,但似乎没有多少代码示例,如果有的话),它涵盖了简洁图数据结构以及简洁动态数据结构:[LINK] — faizshah, 2021-09
Erik Demaine [1] 在2012年MIT 6.851高级数据结构课程中做了两个关于简洁数据结构 [2] 的精彩讲座,而Rajeev Raman [3] 刚刚在SIGMOD 2018上做了一个关于简洁数据结构的教程 [4]。注意:SDSL速查表 [LINK] [1] [LINK] [2] MIT 6.851 简洁结构 I [VIDEO] II [LINK] [3] [LINK] [4] SIGMOD 2018教程:通过简洁数据结构实现数据库的内存表示 [LINK] — espeed, 2018-10

相关视频