Python中的现代高性能布隆filter？

我正在寻找一个生产质量布隆filter实现在Python中处理相当大数量的项目（比如100M到1B的项目，误报率为0.01％）。

Pybloom是一种select，但它似乎正在显示其年龄，因为它定期抛出Python 2.5上的DeprecationWarning错误。 乔·格雷戈里奥也有一个实现 。

要求是快速查找性能和稳定性。 我也打开创buildPython接口到特别好的c / c ++实现，甚至是Jython，如果有一个好的Java实现。

缺乏这一点，任何build议就位arrays/位vector表示，可以处理〜16E9位？

Answer 1

我最近也走了这条路。 虽然听起来像我的申请有些不同。 我有兴趣在大量string上近似设置操作。

你做了关键的观察，要求一个快速的位向量。 根据你想放在布隆filter中的内容，你可能还需要考虑所使用的哈希algorithm的速度。 你可能会觉得这个库很有用。 你也可能想要用下面的随机数技术来修补一下，只有一次你的密钥。

就非Java位数组的实现而言：

• Boost有dynamic_bitset
• Java有内置的BitSet

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

这里有一些我躺在身边的代码。 我可能把这个在python盛开的谷歌代码。 build议欢迎。

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 # # [e-mail] / 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也使用它），这也许是正确的，这意味着这是正确的事情;-)

对于布隆filter来说，散列函数的唯一要求是在给定期望input的情况下，其输出空间必须是均匀分布的。 虽然密码哈希值肯定满足这个要求，但也有点像使用火箭筒拍摄苍蝇。

而是尝试使用FNV哈希 ，其中每个input字节只使用一个XOR和一个乘法，估计比SHA1快几百倍

FNV哈希密码不安全，但你并不需要它。 雪崩行为有一些不完美的地方 ，但是你并没有使用它进行完整性检查。

关于统一性，请注意，第二个链接只对32位FNV哈希进行了卡方检验。 最好使用更多的位和FNV-1变体，它们交换XOR和MUL步骤以获得更好的位分散。 对于布隆filter来说，还有几个捕获点，比如将输出均匀地映射到位数组的索引范围。 如果可能的话，我会说位数组的大小为2的最近幂，并相应地调整k 。 这样你就可以获得更好的准确性，并且可以使用简单的XOR折叠来绘制范围。

另外，这里有一个参考解释为什么当你需要一个通用散列时，你不需要SHA1（或任何encryption散列）。

Answer 3

最终我find了pybloomfiltermap 。 我没有使用它，但它看起来像它适合账单。

Answer 4

看看arrays模块。

 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和&0x07replace。 这可能会导致略微更好的速度，有些模糊的风险。

此外，在大多数硬件上，将'B'和“ 8 'L'更改为'L'和32应该更快。 [更改为'H' ，在某些硬件上可能会更快一些，但是值得怀疑]

Answer 5

我已经在http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/上架了一个python bloomfilter实现

它是纯python，具有良好的散列函数，良好的自动化testing，select后端（磁盘，数组，mmap，更多）和更直观的__init__方法的参数，因此您可以指定理想数量的元素和期望的最大错误率而不是有点空灵的数据结构特定的可调参数。

Answer 6

我非常感兴趣的是布卢姆filter变体，他们的performance和理解他们的用例。 关于布卢姆filter变体（包括SIGCOMM，SIGMETRICS等顶级会议上发表的那些）的研究工作有很多，但我不认为他们在主stream语言库中的存在性很强。 你为什么认为是这样？

虽然我的兴趣是语言不可知的，但我想分享一篇关于Bloomfilter变体和Bloomfilter应用程序的文章。

http://appolo85.wordpress.com/2010/08/03/bloom-filter/

我很想了解更多关于Bloom滤镜变体的使用案例，以及它们的devise/实现和其他语言的库。

你认为Bloom的大部分出版物和（代码？）filter变种仅用于增加博士gradle生的发表论文数量吗？
或者是大多数人不想搞乱生产就绪的标准布隆filter实现“工作得很好”：D

Answer 7

您可以尝试使用DSI实用工具的 it.unimi.dsi.util.BloomFilter 。