用 Bloom Filter 求交集 2013-11-14 22:00

昨天面试时被问到一个问题,有 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))^KK = (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 方法的结果比较,代码如下(省略了读取文件并生成数字集合的代码):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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 = 24K = 16,算出来的理论错误率是 0.001%,即一千万次查询大概会出现 100 个错误。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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 的实现,最终结果是:

1
2
3
4
5
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