data-structures - 位数组有哪些常见用途？

Question

我已经使用新手手册中的位数组做了一个示例。我想知道它们可以用来做什么以及它们有哪些常见的数据结构（假设“数组”是相当松散的术语。）

谢谢。

Answer 1

Bit array Wikipedia 文章的Applications部分列出了几个：

由于其紧凑性，位阵列在空间或效率非常重要的领域有许多应用。最常见的是，它们用于表示一组简单的布尔标志或布尔值的有序序列。

上面我们提到位数组用于优先级队列，其中索引 k 处的位被设置当且仅当 k 在队列中；例如，这种数据结构被 Linux 内核使用，并且从硬件中的 find-first-zero 操作中受益匪浅。

位数组可用于分配内存页面、索引节点、磁盘扇区等。在这种情况下，可以使用术语位图。但是，该术语经常用于指代光栅图像，每个像素可能使用多个位。

位数组的另一个应用是布隆过滤器，这是一种概率集合数据结构，可以将大集合存储在小空间中，以换取小的错误概率。也可以基于接受误报或误报的位数组来构建概率哈希表。

位数组及其上的操作对于构建简洁的数据结构也很重要，这些数据结构使用接近最小的可能空间。在这种情况下，诸如找到第 n 个 1 位或计算直到某个位置的 1 位的数量等操作变得很重要。

位数组也是检查压缩数据流的有用抽象，这些数据流通常包含占据部分字节或未按字节对齐的元素。例如，单个 8 位字符的压缩 Huffman 编码表示可以是 1 到 255 位长。

在信息检索中，位数组是非常频繁的术语发布列表的良好表示。如果我们计算严格递增整​​数列表中相邻值之间的间隙并使用一元编码对其进行编码，则当且仅当 n 在列表中时，结果是在第 n 个位置具有 1 位的位数组。n 间隙的隐含概率是 1/2n。这也是参数 M 为 1 的哥伦布编码的特例；这个参数只有在 -log(2-p)/log(1-p) ≤ 1 时才会被选中，或者这个词大约出现在至少 38% 的文档中。