5. 用位向量表示集合¶

判断某个值是否是某个特定集合的成员，是在记录序列中查找键的一种特殊情况。 因此，本书讨论的任何查找方法都可以用来检查集合成员关系。 不过，我们也可以利用这个问题所限定的特殊条件，来开发另一种表示方法。

当集合的值落在有限范围内时，我们可以用一个位数组来表示集合， 为每个潜在的成员分配一个位位置。 确实在集合中的成员，在其对应的位上存储值 1； 不在集合中的成员，在其对应的位上存储值 0。 例如，考虑 0 到 15 之间的素数集合。 图 25. 显示了相应的位数组。 要确定某个特定的值是否为素数，我们只需检查对应的位。 这种表示方案称为 位向量 或 位图。 第 Graphs 章的若干图算法中使用的 mark 数组， 就是这种集合表示的一个例子。

如果集合能放入单个计算机字中，那么集合并、交、差都可以通过逻辑位运算来完成。 集合 \(A\) 和 \(B\) 的并是按位 OR 函数（在 Java 中其符号为 | ）。 集合 \(A\) 和 \(B\) 的交是按位 AND 函数（在 Java 中其符号为 & ）。 例如，如果我们要计算 0 到 15 之间既是素数又是奇数的数的集合， 只需计算如下表达式

集合差 \(A - B\) 在 Java 中可以用表达式 A&~B 实现 （ ~ 是按位取反的符号）。 对于无法放入单个计算机字的更大集合， 可以对构成整个位向量的各计算机字依次执行相应的运算。

这种从位向量计算集合的方法有时应用于文档检索。 考虑这样一个问题：从一个文档集合中挑选出少数包含选定关键字的文档。 对每个关键字，文档检索系统存储一个位向量，每个文档对应一位。 如果用户想知道哪些文档包含某个特定的三个关键字， 就把对应的三个位向量做 AND 运算。 结果为 1 的那些位位置对应的就是想要的文档。 另一种做法是为每个文档存储一个位向量， 用来指示该文档中出现的那些关键字。 这样的组织结构称为 签名文件。 可以对这些签名进行操作，以找出具有所需关键字组合的文档。 .. odsascript:: AV/Development/BitArrayCON.js