盒子中的猫，或紧凑型数据结构

如果搜索树已扩展到整个RAM，并且即将根植服务器机房中的相邻机架，该怎么办？ 如何处理资源匮乏的倒排索引？ 如果用户收到“手机内存已满”并且应用程序只是重要容器负载的一半，我应该与Android开发联系吗？

通常，是否可以压缩数据结构，使其占用的空间显着减少，但又不会失去其固有的优势？ 这样就可以快速访问哈希表，并且平衡树保留其属性。 是的，你可以！ 为此，出现了计算机科学“简洁数据结构”的方向，探索了数据结构的紧凑表示形式。 自80年代末以来，它一直在发展，现在，它在大数据和高负载的荣耀中处于最佳状态。

同时，Habr上是否会有一位英雄可以连续讲话三遍
[səkˈsɪŋkt]？

紧凑世界的大门

因此，如果满足以下条件，则数据结构被认为是紧凑的（简洁的）：

• 它占用接近信息理论下限的许多位。
• 它不需要预先打开包装即可充分使用。

这意味着无损压缩算法与紧凑的数据结构无关。 毕竟，它们涉及从压缩状态恢复数据以进行处理。

图表，哈希表和其他事物的熟悉的“主流”实现也不是很好。 至少获取指向搜索树中子元素的指针。 他们吃了体面的地方： $$$O（MN）$ 在哪里 $$$M$ -指针的长度，以及 $$$N$ -树中的节点数。 但是简洁的树实现使我们能够将渐近行为改进为 $$$2N + o（N）$ 接近理论下限 $$$2N-Θ（log N）$ 用于木材 $$$N$ 节点。 带指针长度 $$$M = 8$ 字节，这意味着从 $$$O（8N）$ 到完全不同的渐近顺序-只是 $$$2N$ 考虑到 $$$o（N）$ -相对于微不足道的价值 $$$N$ 。

紧凑（简洁）数据结构是位向量，多集，平面图和其他常用经典结构的压缩表示。 它们通常是静态的，只能构建一次，在使用过程中不会改变。 也有例外-简洁的结构，可以快速添加和删除元素。

大多数紧凑型结构都基于所谓的紧凑型可索引字典的概念。 这是位图（位图，位集）的特例。 位图本身是检查元素是否在特定集中的理想选择。 如果元素包含在集合中，则给定索引处的位值将设置为1，否则将其重置为0。一个重要的示例是inode位图ext4，UFS和其他Unix文件系统。 它存储有关inode表中哪些条目繁忙和哪些空闲的数据。

紧凑的可索引字典是相同的位图，但是由两个操作补充：rank和select。 这些行动是精简世界赖以生存的大象。 粗略地说，等级是对元素数量的计数，而select是对元素的搜索：

• $$$rank_x（i）$ 返回等于的位数 $$$x$ 其索引位于段上 $$$[0;我]$ 。 由于 $$$x$ -该位的值，则可以排他地等于0或1。
• $$$select_x（j）$ 返回索引 $$$j$ 等于 $$$x$ 。 常识说没有零发生，只有第一个。 因此$$ $ inline $ j> 0 $ inline $ ：从一个开始进行计算。 也 $$$j$ 不能超过字典中等于的总位数 $$$x$ 。

假设我们有一个可索引的字典，其中设置了7位中的4位。 然后 $$$rank_1$ 和 $$$select_1$ 将采用以下值：

可索引字典的示例及其计算 $$$rank_1$ ， $$$select_1$ 。

细心的读者会注意到选择是排名的倒数。 如果 $$$rank_1（5）= 4$ 然后 $$$select_1（4）= 5$ 。

有人看到了deja vu $$$rank_1（i）$ ？ 所有这些都是因为此操作可以推广汉明权重-序列中非零字符的数量。 对于二进制序列，汉明的权重也称为popcount （人口计数）。

等级/选择也适用于丢弃的位。 这是一个计算示例 $$$rank_0$ 和 $$$select_0$ 对于等于0的位：

紧凑型可索引字典的示例及其计算 $$$rank_0$ ， $$$select_0$ 。

看见一棵树变成叮咬

我们利用这些知识来构建紧凑的前缀树！ 前缀树非常适合按前缀查找字符串。 在他们的帮助下，通常会实现一个搜索提示（最简单）的下拉列表。 前缀树的简洁化方法非常普遍，并且最大程度地展示了紧凑结构的所有葡萄干。 与二叉树不同，二叉树会推导特定的公式，这些公式会干扰整体图像。

三种紧凑表示树的方法最为流行：

• BP（平衡括号）-平衡括号序列。
• DFUDS（深度优先一元度序列）-通过深度搜索对单位编码节点进行排序的序列。
• LOUDS（级别排序的一元度序列）-按级别排序的单位编码节点的序列。

将“一元级”转换为“单个编码节点”的可疑逻辑链是什么？ 那好 这些名称中的一元度表示一种根据子节点的数量使用一系列单位对树节点进行编码的方法，预告片中始终为零。

这三种表示树的方法通过快速操作的存在而结合在一起：查找父级； 找到第一个后代； 找到最后的后代； 找到左右相邻的节点。 其他操作的基本可能性和有效性因方法而异。

让我们关注LOUDS方法。 了解了这一点之后，与其他两个对象打交道将并不困难。 此外，去年，LOUDS树木庆祝了自己的30岁生日！ LOUDS树的其他有用操作在 $$$O（1）$ ：找到节点的后代数量； 计算节点所有后代（第一个后代，第二个， $$$我$ th等）； 找到 $$$我$ 后代。 LOUDS的缺点是缺乏一种有效的算法来计算子树节点的数量。

该方法的本质很简单：将树节点的密钥和所有有价值的信息存储在规则数组中，并将树结构表示为位序列。 共有两个静态结构。 但是，无需为指向树节点的指针分配内存：它们之间的转换是通过使用公式来实现的，其中使用了有效的等级/选择。

警告，前缀树：

准备使用LOUDS方法进行压缩的前缀树。

准备以二进制形式表示的树：

1. 将树附加到假根上。 他将很快发挥自己的作用。
2. 与BFS（宽度优先搜索）一样，我们从左到右逐级对树的所有节点进行编号。 假根将被忽略，而实根将被零索引。
3. 对节点进行编码。 树节点由对应于直接后代的单元序列加零编码。 如果节点有四个子节点，则其编码为11110，如果没有，则编码为0。假根首先编码。 它只有一个后代，因此其代码为10。

带有编号节点的前缀树。 节点被编码。

在逐层树遍历的过程中，形成了一个紧凑的可索引字典-从顶部到底部和从左到右粘在一起的编码节点的比特序列。 我们有一个21位的序列。 顺便说一句，它称为LBS（LOUDS位字符串）。

前缀树的紧凑型可索引字典。

构建紧凑的LOUDS前缀树。 木材用LBS $$$N$ 节点（假不算）需要 $$$2N + 1$ 一点。 仍然最有趣的是-将遍历树的公式转换为位图。

搜索第一个孩子 。 从节点过渡 $$$我$ 它的第一个子节点按照以下公式执行：

$$

$$firstChild（i）= select_0（i + 1）-i$$

$$$我$ -这是前一块板中以紫色粘贴的节点号。

查找索引为3（字母“ a”）的节点的第一个后代：

$$

$$firsthild（3）= select_0（3 +1）-3 = select_0（4）-3 = 9-3 = 6$$

第一个子节点在索引6处，这是字母“ k”。 我们将公式应用于树的根：

$$

$$firstChild（0）=选择_0（0 + 1）-0 =选择_0（1）= 1$$

我们找到了一个索引为1的工作表，即字母“ and”。 汇合！ 显然为什么需要假的根：索引节点的魔术。 在继续节点的后代之前，要避免奇怪的错误 $$$我$ 找出这些后代的数量会很高兴。 确实，对于树上的叶子，这并不奇怪，该公式给出的结果不足。 要在第一个后代之后找到下一个后代，您需要添加1。这是合乎逻辑的，因为一个节点的后代始终在附近，没有间隙。 但是，在遍历它们时，您需要及时停止-确定哪个后代被认为是最后一个。

搜索节点的最后一个后代 $$$我$ 分两个阶段进行：确定节点代码中最后一个单元的索引-它是指定给定后代的元素； 然后确定孩子本身的索引：

$$

$$lastChildPos（i）= select_0（i + 2）-1$$

收到节点代码中最后一个单元的索引后，有必要验证此索引处的位是否确实已设置。 如果不是，则结论表明其本身：这是一个没有后代的节点，是一片叶子。 如果该位置1，则继续：

$$

$$lastChild（i）= rank_1（lastChildPos（i）-1）$$

查找节点2的最后一个后代（字母“ k”）。

$$

$$lastChildPos（2）= select_0（2 + 2）-1 = select_0（4）-1 = 9-1 = $$$

索引8的位为1，因此，节点2不是叶子，我们可以找到其最后一个子节点的索引：

$$

$$lastChild（i）=等级_1（8-1）= 5$$

后代的数量。 确定后代数量的最简单方法是从节点的最后一个后代的索引中减去其第一个后代的索引，然后加1：

$$

$$childrenCount（i）=lasthild（i）-firsthild（i）+ 1$$

但是假设节点 $$$我$ 有一个邻居节点 $$$我+ 1$ 位于与 $$$我$ 。 然后子孙的数量 $$$我$ 可以定义为节点的第一个后代的索引之间的差 $$$我+ 1$ 和 $$$我$ ：

$$

$$childrenCount（i）=firsthild（i + 1）-firsthild（i）$$

节点的后代也按顺序编号。 如果是第一个子孙 $$$我$ 那是吗 $$$j$ 然后第二个- $$$j + 1$ 依此类推，直到这个级别上相邻节点的后代 $$$我+ 1$ （如果有）。

索引为1的叶子“ and”的后代数量预期为零：

$$

$$childrenCount（1）=（select_0（2 + 1）-2）-（select_0（1 + 1）-1）= 3-3 = 0$$

父级搜索节点 $$$我$ 按以下公式组织：

$$

$$父母（i）=等级_0（select_1（i + 1）-1）-1$$

我们将使用它来搜索节点6的父节点（字母“ k”）：

$$

$$父母（6）=等级_0（select_1（7）-1）-1 =等级_0（9）-1 = 3$$

这是节点3，字母“ a”。

了解了子代索引和父代索引的公式后，遍历整棵树就很容易了。 最主要的是不要忘记处理根和叶的边界条件。

关于BP和DFUDS方法的几个科比。 两种方法都有空间渐近性- $$$2N + o（N）$ 取材于 $$$N$ 节点，并且两者在以开括号和闭括号的形式表示树节点时都相似。

BP （平衡括号）将树转换为一系列括号，每个节点成对。 为了做到这一点，树深入了人间。 每个节点访问两次。 第一次访问时，记录了括号，第二次访问时，记录了括号。 它们之间是孩子的括号。

以位图的形式表示括号的顺序很方便，其中1是左括号，0是右括号。 精炼了与BP配合使用的所有公式，以便快速搜索。 与LOUDS不同，BP使您可以快速计算子树的大小并确定两个节点的最接近的公共祖先。 但是找到 $$$我$ -第一个后代比在LOUDS中复杂得多。

DFUDS （深度优先一元序列）与BP和LOUDS相似。 借助BP，它将深度的树木行走及其支架表示形式结合在一起。 括号的原理与LOUDS中编码节点的原理相同。 在遍历树之前，我们预先在括号序列中添加一个左括号。 然后，在遍历节点时，我们根据后代的数量加上一个封闭的括号将其括起来。 事实证明，在DFUDS中存储后代的局部性高于BP。 子树大小的计算和最近的共同祖先的搜索 $$$O（1）$ 。 但是确定子树的高度并找到父树 $$$j$ 级-DFUDS的繁重操作。

为了清楚起见，我们以小树为例比较LOUDS，BP和DFUDS方法。

树的节点用橙色编号，就像在宽度上行走（对于LOUDS）一样，蓝色-就像在深度上行走时（对于BP和DFUDS）一样。

LOUDS，BP和DFUDS树视图。

如果您发现英语作品中的公式有所不同，请不要感到惊讶。 在数学家中，有很多人从一个索引开始。 一些开发人员认为等级和范围辅音一词，因此他们使等级的时间减半。 $$$[0;我）$ 。 由于需要保持等级/选择的对称性，他们计算 $$$选择（i）$ 怎么 $$$选择（i + 1）$ 。 但是这种形式的某些公式看起来较短。

稀疏阵列：摇动但不要混合

稀疏数组是从字面上创建用于压缩的另一种结构。 此类数组的大小有时比填充元素的数量大几个数量级。 空元素可以采用默认值，也可以标有null。 每当需要存储许多对象及其之间的关系时，稀疏的数组就会出现在地平线上。 立即想到社交网络上的朋友图，搜索引擎排名算法，类似Excel的表格，芯片中包含数十亿个晶体管的电路模拟器。

这样的数组通常是Lovecraftian风格的独眼巨人，天真地实现它们不适合RAM，实际上是空的。 根据内存和速度的要求，稀疏数组会变成更紧凑的哈希表，邻接表，二叉树...或简洁表。

假设我们有一个稀疏的字符串数组。 附加一个紧凑的可索引字典。 它会给什么？

带有位图的稀疏数组。

现在，无需直接访问原始数组，就可以轻松检查感兴趣的索引中是否有元素。 没有什么可以通过丢弃所有未填充的元素来缩小原始数组的：

没有空元素的数组。

计算压缩数组中的索引。 检查元素的存在之后，最好在原始数组中访问其值，即映射索引 $$$我$ 在索引字典索引中 $$$j$ 在压缩数组中。 毫不奇怪，排名被用于此：

$$

$$j = rank_1（i）-1$$

让我们检查一下第八元素的情况： $$$位图[8] = 0$ 。 因此，在原始数组中没有这样的元素。 那元素7呢？ $$$位图[7] = 1$ 。 获得其价值： $$$rank_1（7）-1 = 3-1 = 2$ 。 在索引2处为“开始”。

计算源数组中的索引。 当然，在数组中，您将需要按值搜索元素！ 如果数据未排序，则搜索将减少为搜索 $$$O（N）$ 在哪里 $$$N$ -非空元素的数量。 对于找到的物品 $$$j$ 可能需要获取其索引 $$$我$ 好像阵列没有收缩。 为此，请使用select（等级的倒数）：

$$

$$i = select_1（j + 1）$$

例如，找到“ C ++”行。 在紧凑数组中，它位于索引0处。它在原始数组中的索引为 $$$select_1（0 + 1）= 3$ 。

在带有行的示例中，显着节省了内存。 如果将数组设计为存储具有多个字段的类，则节省的费用将变得更加重要。 此外，在紧凑型数组中搜索比在大型且稀疏数组中搜索更快：处理器可以更好地缓存它。 与数字，字符串或特殊自定义类型的常规数组相比，按位索引的字典更有可能适合高速缓存行。

当然要储存 $$$2 ^ {30}$ 元素描述的方法不合适。 它的适用性在索引增长出现问题的地方结束。 但是，当然，这种压缩数组及其变体的方法有其独特的优势。 一个日常的例子是BitTorrent协议的实现。 位图包含有关下载的文件段的信息，并且同级交换它们的段的索引。 一个空间示例是漫游者，航海家和新视野站使用的分段数据传输选项，在跨海王星空地上耕作。

所描述的前缀树和稀疏数组的简洁化示例建立在共同的基础上。 它基于对排名/选择操作有效性的坚定信念。 没有它，紧凑但足够快的结构的整个理论就会在接缝处破裂。 在学位论文之外使用紧凑结构的适当性取决于等级和选择速度。

实际上，可以非常有效地实施以下操作： $$$O（1）$ ; 选择- $$$O（日志（log N））$ ，这几乎是恒定的。 当然，这并非没有技巧。 而且由于在任何复杂情节的作品中都必须轻描淡写，所以我将在这里停止。

有趣的事实

就信息论而言，占用资源的理论下限是多少？ 假设一个数据结构存储了很多 $$$N$ 元素。 为了识别它们而不会发生冲突，您需要不少于 $$$X = log_2N$ 。 $$$X$ 并且有一个由Hartley公式确定的下界。 在某些特殊情况下，如果具有有关所存储数据性质的信息，则可以更有效地压缩结构。

简洁的字符串是数据结构吗？ 它包含 $$$N$ 字符，并以空ASCII字符结尾。 所以这需要 $$$N + 1$ 位置，因此...她是简洁的，更具体地说是隐性的！ 这就引出了下一个问题。

所有简洁的结构都一样紧凑吗？ 简洁的研究领域定义了多达三种类型的紧凑结构，它们在空间复杂度上有所不同：

• 紧凑- $$$O（N）$ 。 线性复杂度从 $$$N$-存储的项目数。就压缩结构的要求而言，最“免费”。可以这么说，在真正的硬核之前进行热身。如果我们在谈论字符串，那么下面的示例是合适的：可变长度的字符串序列。字符串被一个接一个地存储，没有任何分隔符。为了搜索单独的行，形成了位图，其中除了具有与行的开头相对应的索引的位之外，所有位都被重置为0。这种结构需要$$$O(2N)$ ( 2 , ) select .
• succinct — $$$N + o(N)$ 。 — , succinct data structures . : (Pascal string), . $$$N + log(N)$ 。
• implicit — $$$N + O(1)$ 。 , . : (heap) . $$$N + 1$ 。

? , , . succinct- . , -, FM-, RMQ (range minimum queries), LCP (longest common prefix), , succinct'. -.

, , . 不仅如此。 , , X, .

succinct — , «- ». Succinct — . , , succinct. , . (IME) Google, . MAPS.ME succinct- .

, . ., 97 % -: . 3 %.

接下来是什么？

, succinct:

• rank/select Bitmagic Library.
• , succinct. .
• MIT, succinct.
• , 18 .
• , succinct.
• RRR — .

, :

• C ++中的简洁数据结构库项目。
• C ++中的BitMagic项目。
• 带有Python中Elias-Fano简洁实现的软件包。
• 在Rust中实现一些简洁的结构。