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

Question

我正在寻找Python中的生产质量布隆过滤器实现来处理相当多的项目(例如100M到1B项目,误报率为0.01%).

Pybloom是一个选项,但它似乎显示它的年龄,因为它定期抛出Python 2.5上的DeprecationWarning错误.Joe Gregorio也有实施.

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

缺乏这一点,任何关于可以处理~16E9位的位数组/位向量表示的建议？

Answer 1

我最近也走了这条路; 虽然听起来我的应用程序略有不同.我对在大量字符串上逼近集合操作感兴趣.

您确实需要进行关键观察,即需要快速位向量.根据您要在布隆过滤器中放置的内容,您可能还需要考虑所使用的散列算法的速度.您可能会发现此库很有用.您可能还想修改下面使用的随机数技术,该技术一次只能哈希您的密钥.

就非Java位数组实现而言:

• Boost有dynamic_bitset
• Java有内置的BitSet

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

这是我躺在的一些代码.我可以把它放在python-bloom的谷歌代码上.建议欢迎.

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提供更快的count_bits函数很有用.将此代码放入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]

Answer 2

对Parand的反应是,"常见的做法似乎是使用像SHA1这样的东西并将这些位分开形成多个哈希",而这可能是正确的,因为它是常见的做法(PyBloom也使用它),它仍然没有'这意味着它是正确的事情;-)

对于Bloom过滤器,散列函数的唯一要求是,在给定预期输入的情况下,其输出空间必须均匀分布.虽然加密哈希确实满足了这个要求,但它也有点像用火箭筒射击飞行.

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

FNV哈希不是加密安全的,但您不需要它.它有一些略微不完美的雪崩行为,但你也没有用它来进行完整性检查.

关于一致性,请注意第二个链接仅对32位FNV哈希进行卡方检验.最好使用更多的比特和FNV-1变体,它可以交换XOR和MUL步骤,以实现更好的比特色散.对于布隆过滤器,还有一些捕获,例如将输出均匀映射到位阵列的索引范围.如果可能的话,我会说将位阵列的大小四舍五入到最接近的2的幂并相应地调整k.这样你就可以获得更好的精确度,你可以使用简单的XOR折叠来绘制范围.

此外,这里有一个参考,解释了当您需要通用哈希时不需要SHA1(或任何加密哈希)的原因.

Answer 3

最终我找到了pybloomfiltermap.我没有使用它,但看起来它符合要求.

Answer 4

看一下阵列模块.

class Bit( object ):
    def __init__( self, size ):
        self.bits= array.array('B',[0 for i in range((size+7)//8)] )
    def set( self, bit ):
        b= self.bits[bit//8]
        self.bits[bit//8] = b | 1 << (bit % 8)
    def get( self, bit ):
        b= self.bits[bit//8]
        return (b >> (bit % 8)) & 1

FWIW,所有//8和% 8操作都可以用>>3和替换&0x07.这可能会导致速度稍微提高一些隐匿的风险.

此外,更改'B'和8以'L'和32应在大多数硬件上更快.[ 'H'在某些硬件上更改为16可能会更快,但这是值得怀疑的.]