language-agnostic - 结合布隆过滤器

我正在使用Bloom过滤器来检查集中的重复数据。但是，需要将两组数据的结果合并到一个过滤器中，以检查两组数据是否重复。我在伪Python中设计了一个函数来执行此任务:

def combine(a : bloom_filter, b : bloom_filter):
    assert a.length == b.length
    assert a.hashes == b.hashes

    c = new bloom_filter(length = a.length, hashes = b.hashes)
    c.attempts = a.attempts + b.attempts
    c.bits = a.bits | b.bits

    # Determining the amount of items
    a_and_b = count(a & b)
    a_not_b = count(a & !b)
    not_a_b = count(!a & b)
    neither = count(!a & !b)
    c.item_count = a_not_b / a.length * a.item_count
                 + not_a_b / b.length * b.item_count
                 + a_and_b / c.length * min(a.item_count, b.item_count)

    return c

这听起来是否正确？由于是否有很多关于源数据的信息丢失了(这是布隆过滤器的关键)，因此我在内部就是否可以按照我的预期进行辩论。

最佳答案

您可以导出一个公式，用于估算布隆过滤器的项目数量:

c = log(z / N) / ((h * log(1 - 1 / N))

N: Number of bits in the bit vector
h: Number of hashes
z: Number of zero bits in the bit vector

这样可以对布隆过滤器中的项目数量提供相当准确的估计。您可以通过简单的减法得出贡献的估算值。

关于language-agnostic - 结合布隆过滤器，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6099562/