3

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

谢谢。

4

1 回答 1

4

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% 的文档中。

于 2009-08-04T12:23:08.283 回答