algorithm - 用于确定家族中的哪些集合是给定集合的子集的布隆过滤器

Question

我正在尝试使用布隆过滤器来确定集合族中的哪些集合 A1 , A2 ,..., Am是另一个固定集的子集 Q .我希望有人可以验证所述方法的正确性或提供任何改进。

让Q是一组给定的整数，包含来自宇宙集 U = {1,2,...,10000} 的 1-10000 个元素.

此外，假设有一个集合族A1 , A2 ,..., Am每个包含来自同一宇宙集的 1-3 个元素 U .尺寸m大约是 5000。

算法概要:

让有一个集合 k哈希函数。对于 Q 的每个元素应用哈希函数并将其添加到大小为 n 的位集中, 表示为 Q_b .

此外，对于每个 Ai , i = 1,...,m集，将散列函数应用于 Ai 的每个元素，生成位集(大小也是 n )，表示为 Ai_b .

检查是否Ai是 Q 的子集，对两个位集执行逻辑与，Q_b & Ai_b , 并检查它是否等于位集 Ai_b .也就是说，如果 Q_b & Ai_b == Ai_b是假的，那么我们知道 Ai不是 Q 的子集;如果它是真的，那么我们不确定(误报的可能性)，我们需要检查给定的 Ai使用确定性方法。

希望是过滤器告诉我们大部分Ai不在 Q 中的我们可以更仔细地检查返回 true 的那些。

这是解决我的问题的好方法吗？

(附带问题:n 应该有多大？有哪些好的散列函数可以使用？)

Answer 1

如果值的范围相当小(如您的示例所示)，您可以使用具有线性时间复杂度的简单确定性解决方案。

1. 让我们创建一个数组 was(索引从 1 到 10000，即通用集的每个元素一个单元格)，初始填充为 false 值(value)观。

2. 对于 Q 的每个元素 q，我们设置 was[q] = true。

3. 现在我们遍历家庭的所有集合。对于每个集合 A_i，我们遍历该集合的所有元素 x 并检查 was[x] 是否为真。如果不是至少一个 x，则 A_i 不是 Q 的子集。否则就是。

这个解决方案显然是正确的，因为它根据定义检查一组是否是另一组的子集。它也相当简单和确定性。它唯一的潜在缺点是它需要一个包含 10000 个元素的辅助数组，但对于大多数实际用途来说它看起来是可以接受的(无论如何，布隆过滤器也需要一些额外的空间)。