dm-pybloom 3.0.4

dm_pybloom
=======

.. 图片:: https://travis-ci.org/jaybaird/python-bloomfilter.svg?branch=master
:target: https://travis-ci.org/jaybaird/python -bloomfilter

``dm_pybloom`` 是一个模块，它包括一个 Bloom Filter 数据结构以及可伸缩 Bloom Filters 的实现
，如：

P. Almeida、C.Baquero、N. Preguiça、D. Hutchison、Scalable Bloom Filters、
（ GLOBECOM 2007), IEEE, 2007。

如果您了解需要提前
留出多少位来存储整个集合，那么布隆过滤器非常有用。可扩展的布隆过滤器允许您的布隆过滤
器位作为误报概率和大小的函数而增长。

过滤器在容量为：M * ((ln 2 ^ 2) / abs(ln p)) 时为“满”，其中 M
是位数，p 是误报概率。当
达到容量时，创建一个新的过滤器，它比上一个过滤器更大
，误报概率更小，散列
函数数量更多。

.. code-block:: python

>>> from dm_pybloom import BloomFilter
>>> f = BloomFilter(capacity=1000, error_rate=0.001)
>>> [f.add(x) for x in range(10)]
[False , 假, 假, 假, 假, 假, 假, 假, 假, 假]
>>> all([(x in f) for x in range(10)])
True
>>> 10 in f
False
>>> 5 in f
True
>>> f = BloomFilter(容量=1000, error_rate=0.
>>> for i in xrange(0, f.capacity):
... _ = f.add(i)
>>> (1.0 - (len(f) / float(f.capacity))) <= f. error_rate + 2e-18
True

>>> from dm_pybloom import ScalableBloomFilter
>>> sbf = ScalableBloomFilter(mode=ScalableBloomFilter.SMALL_SET_GROWTH)
>>> count = 10000
>>> for i in xrange(0, count):
... _ = sbf.add(i)
...
>>> (1.0 - (len(sbf) / float(count))) <= sbf.error_rate + 2e-18
True

# len(sbf) 可能不等于整个输入长度。0.01% 的误差远
低于默认的 0.1% 误差阈值。随着容量的增加，
#error 将接近 0.1%。