language-agnostic - 结合布隆过滤器

Question

我正在使用布隆过滤器来检查集中的重复数据。但是，需要将两组数据的结果组合到一个过滤器中，以检查两组数据是否存在重复。我在伪 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

这听起来是否正确？我正在就是否有可能按照我的意图进行大量内部辩论，因为有关源数据的大部分信息都丢失了(这是布隆过滤器的重点)。

Answer 1

您可以推导出一个公式来估计布隆过滤器的项目数量:

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

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