python - 使用并集或交集函数时如何获取布隆过滤器集的大小？

Question

我正在尝试获取布隆过滤器集的大小，同时将布隆过滤器的并集和交集函数与 python 包(https://github.com/jaybaird/python-bloomfilter.git)一起使用

我虽然在执行函数“联合”或“交集”之后，然后我可以通过添加 len() 函数来获得结果，但它只打印出“0”输出。

from pybloom import BloomFilter
bf1 = BloomFilter(1000)
bf2 = BloomFilter(1000)

# After adding some elements to bf1 and bf2
print(len(bf1.union(bf2)))
# expected max(len(bf1), len(bf2)) but the result was 0

找到文档页面后，发现len()选项在'union'函数后被禁用，其实际结果len()为0。

相反，我想以某种方式估计布隆过滤器集的大小。你知道如何计算它的大小吗？

Answer 1

该实现仅复制 BloomFilter 的 bitarray ，即 self.bitarray。 previous filters 中的元素 self.count不算在内。

因此它不会合并元素 - 但执行位数组或。

---

更新:

在大多数情况下，您不需要估计计数。它提供了一个 precise count当你调用 add 时元素的数量，你可以只调用 len(bf3)。不幸的是，新创建的 bf3 还没有被调用 add 所以 len(bf3) == 0。

对于近似元素数量的公式，

- m / k * ln(1- n / m)

你有

import math.log as ln

m = bf3.bitarray.length()
n = bf3.bitarray.count()
k = bf3.num_slices

# given m=20, n=8, approximate n elements as 5.89