Python中的现代高性能bloom过滤器？

Question

我正在寻找一个Python中的生产质量bloom filter实现来处理相当多的项目（比如1亿到1亿个项目，0.01%的假阳性率）。

Pybloom是一个选项，但它似乎显示了它的年龄，因为它定期在Python 2.5上抛出DeprecationWarning错误。乔·格雷戈里奥也有an implementation。

需求是快速查找性能和稳定性。我也愿意为特别好的c/c++实现创建Python接口，如果有一个好的Java实现，我甚至愿意为Jython创建Python接口。

如果没有这一点，有没有关于位数组/位向量表示的建议，可以处理约16E9位？

Answer 1

作为对帕兰德的回应，他说“普通的做法似乎是使用SHA1之类的东西，并将这些位分割成多个散列”，虽然从普通做法（PyBloom也使用它）的意义上来说，这可能是真的，但仍然不意味着它是正确的做法；-）

对于Bloom过滤器，hash函数的唯一要求是，给定期望的输入，其输出空间必须均匀分布。虽然加密散列确实满足了这一要求，但它也有点像用火箭筒射击苍蝇。

相反，请尝试FNV Hash，它只使用一个XOR和每个输入字节一个乘法，我估计它比SHA1快几百倍：）

FNV散列不是加密安全的，但您不需要它。它有点imperfect avalanche behaviour，但您也没有使用它进行完整性检查。

关于一致性，注意第二个链接只对32位FNV散列进行了卡方检验。最好使用更多的比特和FNV-1变体，它交换XOR和MUL步骤以获得更好的比特分散性。对于Bloom过滤器，还有一些捕获，例如将输出统一映射到位数组的索引范围。如果可能的话，我建议将位数组的大小四舍五入到最接近的2次方，并相应地调整k。这样可以获得更好的精度，并且可以使用简单的异或折叠来映射范围。

另外，这里还有一个参考资料，解释了为什么在需要a general purpose hash时不需要SHA1（或任何加密散列）。

Answer 2

最终我找到了pybloomfiltermap。我没用过，但看起来很合算。

Answer 3

我最近也走上了这条路；虽然听起来我的应用程序有点不同。我对大量字符串的近似集合运算感兴趣。

您需要一个快速的位向量。根据您希望在bloom过滤器中放入的内容，您可能还需要考虑使用的散列算法的速度。你可能会发现这个library很有用。您可能还想修改下面使用的随机数技术，该技术只对您的密钥进行一次哈希运算。

就非Java位数组实现而言：

• Boost有dynamic_bitset
• Java具有内置的BitSet

我用BitVector构建了bloom过滤器。我花了一些时间分析和优化库，并把我的补丁贡献给Avi。转到该位向量链接并向下滚动到v1.5中的确认以查看详细信息。最后，我意识到性能不是这个项目的目标，所以决定不使用它。

这是我撒的一些密码。我可以在python bloom的google代码上写下这个。欢迎提出建议。

from BitVector import BitVector
from random import Random
# get hashes from http://www.partow.net/programming/hashfunctions/index.html
from hashes import RSHash, JSHash, PJWHash, ELFHash, DJBHash


#
# ryan.a.cox@gmail.com / www.asciiarmor.com
#
# copyright (c) 2008, ryan cox
# all rights reserved 
# BSD license: http://www.opensource.org/licenses/bsd-license.php
#

class BloomFilter(object):
    def __init__(self, n=None, m=None, k=None, p=None, bits=None ):
        self.m = m
        if k > 4 or k < 1:
            raise Exception('Must specify value of k between 1 and 4')
        self.k = k
        if bits:
            self.bits = bits
        else:
            self.bits = BitVector( size=m )
        self.rand = Random()
        self.hashes = []
        self.hashes.append(RSHash)
        self.hashes.append(JSHash)
        self.hashes.append(PJWHash)
        self.hashes.append(DJBHash)

        # switch between hashing techniques
        self._indexes = self._rand_indexes
        #self._indexes = self._hash_indexes

    def __contains__(self, key):
        for i in self._indexes(key): 
            if not self.bits[i]:
                return False    
        return True 

    def add(self, key):
        dupe = True 
        bits = []
        for i in self._indexes(key): 
            if dupe and not self.bits[i]:
                dupe = False
            self.bits[i] = 1
            bits.append(i)
        return dupe

    def __and__(self, filter):
        if (self.k != filter.k) or (self.m != filter.m): 
            raise Exception('Must use bloom filters created with equal k / m paramters for bitwise AND')
        return BloomFilter(m=self.m,k=self.k,bits=(self.bits & filter.bits))

    def __or__(self, filter):
        if (self.k != filter.k) or (self.m != filter.m): 
            raise Exception('Must use bloom filters created with equal k / m paramters for bitwise OR')
        return BloomFilter(m=self.m,k=self.k,bits=(self.bits | filter.bits))

    def _hash_indexes(self,key):
        ret = []
        for i in range(self.k):
            ret.append(self.hashes[i](key) % self.m)
        return ret

    def _rand_indexes(self,key):
        self.rand.seed(hash(key))
        ret = []
        for i in range(self.k):
            ret.append(self.rand.randint(0,self.m-1))
        return ret

if __name__ == '__main__':
    e = BloomFilter(m=100, k=4)
    e.add('one')
    e.add('two')
    e.add('three')
    e.add('four')
    e.add('five')        

    f = BloomFilter(m=100, k=4)
    f.add('three')
    f.add('four')
    f.add('five')
    f.add('six')
    f.add('seven')
    f.add('eight')
    f.add('nine')
    f.add("ten")        

    # test check for dupe on add
    assert not f.add('eleven') 
    assert f.add('eleven') 

    # test membership operations
    assert 'ten' in f 
    assert 'one' in e 
    assert 'ten' not in e 
    assert 'one' not in f         

    # test set based operations
    union = f | e
    intersection = f & e

    assert 'ten' in union
    assert 'one' in union 
    assert 'three' in intersection
    assert 'ten' not in intersection
    assert 'one' not in intersection

另外，在我的例子中，我发现对于位向量有一个更快的计数位函数是有用的。将此代码放入BitVector 1.5中，它将为您提供一种更高效的位计数方法：

def fast_count_bits( self, v ):
    bits = (
            0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 )

    return bits[v & 0xff] + bits[(v >> 8) & 0xff] + bits[(v >> 16) & 0xff] + bits[v >> 24]