精简数据结构（Succinct Data Structures）

Succinct Data Structures

Source | HN Comments

文章介绍了精简数据结构（succinct data structures）的概念，这类数据结构以紧凑方式存储数据，同时保持数据的可用性，不像压缩数据需要解压才能使用。文章重点介绍了位向量、rank/select 位向量、小波矩阵、FM-index 和平衡括号树等几种精简数据结构，并阐述了它们在不同场景下的应用，例如字符串处理、文本搜索和树结构表示。文章还提到了在 Rust 语言中实现这些数据结构的库，并展望了它们在 XML 处理和编程语言编译器等领域的应用潜力。

Succinct Data Structures

By Martijn Faassen
2025-02-28
Tags:
computer science,
xml,
rust

Introduction

几个月前，为了寻找加速代码的灵感，我阅读了一些计算机科学论文。我并不擅长这个，但我并不介意感到困惑或不知所措，我也乐于承认自己的无知。1。我偶然发现了一篇15年前的论文2，其中介绍了一些对我来说全新的概念。我努力去理解它们。

那么该怎么办呢？你需要寻找更多的论文来帮助解释。这是一种冒险的行为，因为它们可能会让你更加困惑，但这是不可避免的。我发现了一篇关于一个相关数据结构的论文，其中提到了一个网站上的源代码。源代码是用 C++ 编写的，而我正在使用 Rust，但我还是决定看一看。但是当我访问该网站时，资源已经不存在了。所以我给网站的所有者发了邮件，他碰巧是一位计算机科学教授。

这位教授 (Gonzalo Navarro) 非常友善，并立即回复了我3 4。在我们的谈话中，我才意识到我看到了他的名字出现在该领域的_很多_论文中。原来我不小心和精简数据结构（succinct data structures）领域的专家聊上了天，而几天前我才刚刚发现它们的存在。无知可以带你走得很远。

那么什么是 succinct data structures 呢？如果你在近几十年上过计算机科学课程，你可能听说过，但我作为一名程序员之前从未接触过它们，或者即使接触过，我也立刻忘记了。但现在我认为它们是具有迷人属性的数据结构。

我们都使用数组和 hashmaps 5，各种树也很常见。我们不必完全理解它们的工作原理，也能有效地利用它们的特性。现在我开始想知道为什么人们不更频繁地使用这些 succinct data structures。

所以我决定谈谈它们。

Succinct Data Structures

为了介绍 succinct data structures，将它们与压缩进行比较很有用。你可以使用压缩来缩小表示数据所需的空间。压缩可以用于节省磁盘空间、通过网络传输更少的数据或节省内存。但是，要对压缩数据进行任何有用的操作，例如访问或查询它，您首先需要再次解压缩它。然后，如果您想节省空间，则需要再次压缩它。

Succinct data structures 是不同的：它们像压缩一样以紧凑的方式存储其内容，但数据的紧凑形式具有有用的属性。你仍然可以使用它！

这个领域似乎是最近才在计算机科学中出现的；许多重要的数据结构都是在过去 25 年中发明的。

在本文中，我将介绍一些我遇到的 succinct data structures。我不声称自己在这个领域有任何专业知识——我只对这些数据结构中的许多结构的工作原理有模糊的概念。嘿，我几个月前才发现它们的存在！但正如我所说，您不必知道它们是如何工作的才能使用它们。

Rust

在系统编程中，人们比平时更关心数据结构的特定特征（内存、性能）。我觉得它们在这个领域有很多潜在的应用。许多关于紧凑数据结构的原始研究工作都是用 C++ 完成的。我自己喜欢使用 Rust 进行系统编程，所以我寻找了 Rust 中的实现。我将分享我发现的内容，希望其他使用 Rust 的开发人员会觉得它们很有趣。但总体概述并不局限于 Rust，所以如果你对 Rust 不感兴趣，我也邀请你继续阅读。

Bit Vectors

考虑一个位向量（数组）。例如 [0, 1, 0, 1, 1, 0, 1, 0]

让我们花点时间考虑一下位向量。我要说的内容非常明显，但我认为突出显示它是有用的。上面的位向量有 8 个条目长。这意味着它适合一个字节的内存。

在 64 位计算机上，64 位适合一个本机整数。这是一个 64 个条目的位向量，它适合 8 个字节，如果您考虑到普通数组需要这么多的字节才能容纳_单个_整数值，那就算是很不错了。即使是 Rust 中的 bool 也需要一个字节的存储空间。

位向量本身不是 succinct data structures。最终，计算机内存是一个巨大的位数组。但 succinct data structures 试图让每一位都发挥作用。

同样重要的是要注意，数据结构可能会将自身呈现为位向量，但实际上以某种特殊方式在内部存储信息，从而使某些操作速度很快。这就是我们接下来要看到的。

Rank/Select Bit Vector

Rank/select 位向量是许多其他向量构建在其上的核心 succinct data structure。当我寻找源代码时，我才意识到这些不仅仅是普通的位向量，而且还支持特殊操作 rank 和 select。

让我们看一下之前的位向量：[0, 1, 0, 1, 1, 0, 1, 0]。

我们给每个条目一个索引（从 0 到 8，不包括 8）。

rank 操作给定一个索引，计算数组中在该索引之前有多少位已被设置：

因此，rank(0) 为 0，因为此位置尚未设置任何位，rank(1) 为 1，rank(2) 也为 1（该位置有一个 0，因此没有设置更多位）。 rank(3) 为 2。 rank(7) 为 4。

select 操作是 rank 的逆运算。您可以给它一个 rank 并获取设置该位的索引。

因此 select(1) 为 1，select(2) 为 3，select(3) 为 4，select(4) 为 6。只是您看到 1 的后续索引。

rank/select 位向量的简洁实现可以在恒定时间内执行这些操作。仅需要比位向量本身占用的数据多一点的数据来支持这些操作。

Use cases

那么它的用例是什么？让我们考虑一个简单的例子。

假设你有一个大字符串，它实际上由很多小字符串组成。你想跟踪所有这些字符串的起始位置。现在你可以使用很多数据结构来做到这一点，而且通常它们会更好，但让我们使用 rank/select 位向量。

这是一个带有位置信息的字符串：

Hello$I am a string$I'm amazing$Traditional banana
01234567890123456789012345678901234567890123456789
0     10    20    30    40

请注意特殊的 $ 标记。在实践中，这些可以编码为 \0。

因此，这个大字符串有 4 个子字符串，我们可以将其视为一个数组：

["Hello", "I am a string", "I'm amazing", "Traditional banana"]

我们可以用一个数字来标识每个子字符串，该数字是该数组的索引：

Hello$I am a string$I'm amazing$Traditional banana
0  1       2      3

现在让我们考虑一个 rank/select 位向量。对于此字符串中子字符串的起始位置，在每个位置都有一个 $，您可以在其中设置一个位。

所以你得到这个：

Hello$I am a string$I'm amazing$Traditional banana
00000100000000000001000000000001000000000000000000
   5       19     31

现在，当您拥有此字符串中的任何位置时，您可以使用 rank 有效地确定它属于哪个子字符串 - 您将获得一个子字符串标识符。例如，位置 12 位于“I am a string”中，rank(12) 得到我 1。

如果您将 1 添加到标识符，您将获得下一个子字符串标识符 - 一个有用的属性。

您可以使用 select 将子字符串标识符转换回位置。例如，select(1) 得到你 6，字符串中第一个 $ 的位置，即 "I am a string" 的开头。将 1 添加到该字符串，您就有了下一个子字符串的开头。因此，如果您想找到字符串的结尾，您可以将 1 添加到子字符串标识符并对其执行 select。

这允许您以紧凑的方式维护数据块中切片的唯一标识符。

使用普通的 rank/select 位向量，您将使用 1 位乘以字符串的长度作为开销，再加上一点点。对于一百万字节长的字符串，那是 128 KB 的额外空间，以及一些零钱。但是，如果设置的位相对不常见，您可以使用_稀疏_ rank/select 位向量非常有效地存储此附加信息，所占用的空间远小于原始位向量所需的空间。

Rust

在 Rust 中，我真的很喜欢使用 vers，它具有出色的性能，并且在原始位向量上的开销非常小。作者反应非常迅速，并且正在开发一系列令人兴奋的新功能。

另一个值得使用的库是 sucds。特别令人感兴趣的是它的 SArray 实现，它是一个稀疏实现。但是，我认为 vers 在高效构建这些数据结构方面比 sucds 具有更好的设计。因此，我很高兴地报告 vers 也在添加稀疏实现。

Wavelet Matrix

wavelet matrix 听起来像是科幻小说中的东西。 “医生，小波矩阵不同步了！我们无法回到 1985 年！” 相关的其他结构是 wavelet trees，包括 quad wavelet tree，它也有一个非常酷的科幻名字。

这些数据结构所做的是将 rank/select 推广到“任意字母表”。位向量的字母表由 0 和 1 组成，但许多现实世界的数据都有更大的字母表。在 succinct data structure 空间中特别令人感兴趣的是 DNA，它的字母表由其核苷酸“G”、“C”、“A”和“T”组成，大小为 4。另一个非常常见的字母表是文本。如果您使用 UTF-8 并存储其字节，则其字母表的大小为 256。6

通常，字母表越小越好：数据结构需要的空间越少，速度也越快。

因此，让我们考虑 ASCII 等文本字母表中的字符串“banana”。

banana
012345

我们现在可以在字母表中对特定符号进行 rank 和 select 操作。让我们考虑字母（符号）a：

banana
 1 2 3

rank(0, 'a') 为 0，因为索引 0 处还没有 a。但 rank(5, 'a') 得到你 rank 3。类似地，select 让你找到字符串中符号的索引：select(2, 'a') 得到你索引 3，即第二个 a 的索引。

wavelet matrix 的实现使用底层的 rank/select 位向量。

Rust

在 Rust 中，vers crate 也有 wavelet matrix 数据结构的实现。

FM-index

FM-index 是一种数据结构，可让你以紧凑的方式存储文本（任何符号向量），但仍然允许重要的查询操作。它占用的空间不会比原始文本多很多（或者在某些情况下，甚至更少）。

这里重要的查询是：

count(pattern)，用于计算存储的文本中存在多少个特定模式（子字符串）。
locate(pattern)，用于给出原始文本中模式的每次出现的索引。

将大量 DNA 数据加载到内存中，然后能够快速找到其中的子字符串的能力在生物信息学中非常有用。但是，任何拥有大量文本并希望支持搜索操作的用例都可以从 FM-Index 中受益。

Rust

在 Rust 中，fm-index crate 提供了此功能。

最初，fm-index crate 使用 fid crate（由同一作者编写）作为其底层的 rank/select 位向量。但我最近已将 fm-index 移植到使用 vers，这大大提高了 fm-index 的性能。

我一直在与 fm-index 的优秀作者合作，以改进其 API 和功能，并且该领域将推出更多功能，包括支持存储和搜索由多个子字符串组成的大型字符串。

Balanced parentheses

让我们考虑一个数据树，其中每个节点都可以有任意数量的子节点。这些在编程中是非常常见的结构。 XML 和 JSON 都可以用这样的树来表示；编程语言 AST 也可以。

如果你想允许树内的任意导航，你需要对树中的节点执行以下操作：

parent(node)：给出该节点作为子节点的节点
first_child(node)：给出节点的第一个子节点
next_sibling(node)：给出节点的下一个兄弟节点（在其父节点内）
previous_sibling(node)：给出节点的前一个兄弟节点（在其父节点内）

通常，这些树就是这样在内存中表示的。沿着这些思路：

struct Node {
parent_idx: Option<usize>,
first_child: Option<usize>,
next_sibling: Option<usize>,
prev_sibling: Option<usize>
}

这是每个节点的相当多的信息：在 64 位操作系统上，此节点占用 32 字节或 256 位。 balanced parentheses 树允许相同的操作，但每个节点仅占用 2 位！好吧，底层 rank/select 位向量也使用了一点开销，管理数据结构中也使用了一点开销，但这仍然非常小。

它是如何做到的？简单来说，它基本上将一棵树编码为一系列括号。让我们考虑一个带有根节点 a 和两个子节点 b 和 c 的单棵树：

  a
 / \
 b  c

这可以表示为“(()())”。

(()())
ab c

外括号编码根节点 a，两个内 () 对编码其子节点。由于我们只有一个左括号 ( 和一个右括号 )，因此这些信息可以存储在 rank/select 位向量中，其中 1 表示打开，0 表示关闭。

(()())
110100

并且由于使用 rank() 和 select() 的各种巧妙操作以及一些补充信息，它可以支持我上面提到的所有导航，以及更多的操作。

Rust

vers 的惊人作者正在 vers crate 的 dev-bp 分支上开发 Rust 实现。我一直在自己的工作中大量使用它，并且看起来很棒！

Building on these structures

您可以使用这些和其他 succinct data structures 构建具有非常有趣属性的新功能。

我正在用 Rust 开发 XML 处理，我开头提到的论文描述了一种使用 succinct data structures 存储 XML 数据的方法。

它使用 balanced parentheses 树来存储 XML 树。这不允许将信息附加到节点，例如 XML 标记信息（即 <p> 和 </p> 中的 p）。但是您可以通过为每个标记维护一个稀疏的 rank/select 位向量来将信息附加到每个节点，该位向量使用附加信息标记相关的括号。

然后，此 rank/select 位向量允许基本的新操作：您可以“跳转”到具有特定标记的第一个后代节点，而无需遍历中间节点！

XML 还包含文本节点。可以通过跟踪哪个左括号具有文本节点标记来将这些节点附加到树中。该论文还使用 FM-Index 来存储文本节点并允许对它们进行快速查询。

虽然 XML 可能是这些技术的一个相当古老的应用，但想象一下一种以这种方式存储其 AST 的编程语言。大型的 AST 可以相对紧凑地存储，但仍然支持有趣的搜索操作，这可能会开辟实现编程语言编译器的新方法。

Conclusion

现在我发现了这些数据结构，我一直在想它们在我所有的编程生涯中都去哪里了。我怀疑它们在通用计算方面有很多未开发的潜力。虽然使用更多内存的数据结构通常可以更有效地执行这些操作中的许多操作，但使用更少内存的能力本身就具有性能影响。直到去年 12 月，我才意识到它们的存在！我相信有很多开发人员可以找到它们的有趣用途。