用 Bloom Filter 求交集

昨天面试时被问到一个问题，有 A,B两个集合，元素均为64位的整数，其中 A 含有一千亿个元素，B 含有一百万个元素，怎么求它们的交集？当时考虑了一下，求交集无非就是使用 HashTable、位向量之类的，考虑一下这两个方法。

1. 元素最少的集合 B 有一百万个元素，如果放在内存之中，也就大概占用 8M 左右，而 HashTable 插入一百万条数据是很快的。不过当时是被 A 集合吓到了，一千亿个64位的数，估计现在还没有内存能全部容下，只能是分布储存在不同机器上，不过不管怎么样，无论如何都必须要将 A 集合遍历一遍，查看每个元素是否在 B 集合中，这样就能求得交集。

2. 和集合有关的问题，位向量使用比较多，这里有个问题是元素均为64位，如果直接开辟一个 2^64bit 的向量，内存绝对是不够的。而 B 中只有一百万个元素，这个位向量一定非常稀疏，所以可以考虑位向量的压缩储存——采用多级位向量，不过这样实现起来非常麻烦。有趣的是，当这个级数达到64时，就有点 Tire 树的感觉了。

使用 Bloom Filter

当时很想说 Bloom Filter，不过 Bloom Filter 虽然空间效率和查找速度都很好，但它偏偏就是一个随机数据结构：它能准确的告诉你某个元素不在集合中，却有可能会把不属于这个集合的元素误认为属于这个集合。关于 Bloom Filter 的原理和理论基础，请看 Bloom Filter概念和原理。这里我就实际使用过程总结一下：

1. 三个重要数据及其计算

   M--Bloom Filter 实质也是个位向量，M 代表其位数;N--表示将映射到 Bloom Filter 上的集合元素个数;K--最优哈希函数个数。
   由 f = (1-e^(-KN / M))^K 和 K = (M / N)*ln2 得出错误率 f 和 K 大致的关系是 f = 0.5^k，确定一个错误率，然后可得到 K，再得到 M/N，然后得到准确的错误率。这里的错误率是指在查询 Q 次后，出现错判的概率。

2. 哈希函数的选择

   在实际操作中，哈希函数的选择很重要，K 个哈希值最好是独立的和均匀分布的。在第一次试着解决上面的交集问题时，我使用的 K 个哈希函数只是简单的和 K 个质数相乘，结果发现 A 中的元素全在 B 中，这错误率高得真是离谱。最后参照 Leveldb 中的 Hash 处理方法，才将错误率降到理论水平。

对于 Bloom Filter 的其它方面，比如改进什么的这里不谈，主要是实际使用一下，下面就开始动手写代码。

测试一下

要在自己电脑上完成上面问题是不可能的，数据量太大了，这里将 A,B 集合的元素调整为一千万个和十万个，其它条件不变。测试数据的生成比较简单，直接在 0-2^64 的范围内随机产生相应数目的整数即可，这里有个问题，因为范围太大，很可能生成的两个集合没有交集，处理方式是在生成 A 的时候随机从 B 中选几个数过来，不过这样可能造成 A 中元素不唯一。

先使用 HashTable 方法，求出个具体值，以便和使用 Bloom Filter 方法的结果比较，代码如下(省略了读取文件并生成数字集合的代码):

def main():
    # 此方法省略
    set_a = get_nums("testdatabig_a.txt")
    set_b = get_nums("testdatabig_b.txt")
    set_temp = []

    # 使用 Python Dict，使用 HashTable 实现
    dict_a = dict((k, 1) for k in set_a)
    for number in set_b:
        if dict_a.has_key(number):
            set_temp.append(number)

    print "common number count: %d" % len(set_temp)

    with open("testresult.txt", "w+") as f:
        for num in set_temp:
            f.write(str(num)+' ')

事实证明 Python Dict 实现效率是很高的，很快得出结果：交集共有一千个元素。然后下面是使用 Bloom Filter 实现的求交。这里我令 M/N = 24 和 K = 16，算出来的理论错误率是 0.001%，即一千万次查询大概会出现 100 个错误。

from bitarray import bitarray

#The Bloom Filter. k = 16, m/n = 24
K = 16
M_N = 24

def init_bloom_filter(sizes, numbers):
    bset = bitarray(sizes)
    bset.setall(False)
    for number in numbers:
        delta = (number >> 33) | (number << 31)
        for i in xrange(K):
            bitpos = number % sizes
            bset[bitpos] = True
            number += delta;
    return bset


def test_number_in(bset, sizes, number):
    delta = (number >> 33) | (number << 31)
    for i in xrange(K):
        bitpos = number % sizes
        if (bset[bitpos] == False):
            return False
        number += delta;
    return True


def main():
    set_a = get_nums("testdatabig_a.txt")
    set_b = get_nums("testdatabig_b.txt")

    sizes = len(set_a) * M_N
    print "N = %d M = %d K = %d" %(len(set_a), sizes, K)
    print "False positive rate %f%%" % 
          (((1- (math.e) ** (-K/(M_N*1.0))) ** K)*100)

    bset = init_bloom_filter(sizes, set_a)
    common = []
    for number in set_b:
        if test_number_in(bset, sizes, number):
            common.append(number)

    print "common number count: %d" % len(common)

Python 没有自带 bitarray,所以需要先安装 bitarray 这个包，对于 K 个不同哈希值的处理，参考了 Leveldb 中 Bloom Filter 的实现，最终结果是：

file testdatabig_a.txt number count 100000
file testdatabig_b.txt number count 10000000
N = 100000 M = 2400000 K = 16
False positive rate 0.000987%
common number count: 1095

可以看出误判了95个，和估计值差不多。

为什么选择 Bloom Filter

在这个问题的处理上，Bloom Filter 和 HashTable、位向量相比，没占优势啊，而且结果还是有错误率的。因为处理的是整数集合，所以在空间使用上，这里 Bloom Filter 并没有表现出自己独特的风采，不过如果 A,B 集合中储存的是字符串呢，比如 URL 什么的，在使用 HashTable 时则会十分费空间，而位向量则不能处理这个问题，这个时候 Bloom Filter 的优势就体现出来了。

参考资料：

1. Bloom Filter概念和原理 -- 原理以及理论
2. BloomFilter–大规模数据处理利器 -- 对 K 值和 M/N 值选取作了详细阐述
3. Bloom Filters by Example -- 生动有趣详细多料，对哈希函数的选择做了说明
4. python-bloomfilter -- Python 实现的 Bloom Filter