blooms 1.0.0

Examples

This library makes it possible to concisely create, populate, and query simple Bloom filters. The example below constructs a Bloom filter that is 32 bits (i.e., four bytes) in size:

>>> from blooms import blooms
>>> b = blooms(4)

It is the responsibility of the user of the library to hash and truncate the bytes-like object being inserted so that only those bytes that contribute to the object’s membership are considered:

>>> from hashlib import sha256
>>> x = 'abc' # Value to insert.
>>> h = sha256(x.encode()).digest() # Hash of value.
>>> t = h[:2] # Truncated hash.
>>> b @= t # Insert the value into the Bloom filter.
>>> b.hex()
'00000004'

When testing whether a bytes-like object is a member of an instance, the same hashing and truncation operations should be applied:

>>> sha256('abc'.encode()).digest()[:2] @ b
True
>>> sha256('xyz'.encode()).digest()[:2] @ b
False

The @= operator also accepts iterable containers:

>>> x = sha256('x'.encode()).digest()[:2]
>>> y = sha256('y'.encode()).digest()[:2]
>>> z = sha256('z'.encode()).digest()[:2]
>>> b @= [x, y, z]
>>> b.hex()
'02200006'

The union of two Bloom filters (both having the same size) can be computed using the built-in | operator:

>>> c = blooms(4)
>>> c @= sha256('xyz'.encode()).digest()[:2]
>>> d = c | b
>>> sha256('abc'.encode()).digest()[:2] @ d
True
>>> sha256('xyz'.encode()).digest()[:2] @ d
True

It is also possible to check whether the members of one Bloom filter are a subset of the members of another Bloom filter:

>>> b.issubset(c)
False
>>> b.issubset(d)
True

A method is provided for determining the saturation of a Bloom filter. The saturation is a float value (between 0.0 and 1.0) that represents an upper bound on the rate with which false positives will occur when testing bytes-like objects (of a specific length) for membership within the Bloom filter:

>>> b = blooms(32)
>>> from secrets import token_bytes
>>> for _ in range(8):
...     b @= token_bytes(4)
>>> b.saturation(4)
0.03125

It is also possible to determine the approximate maximum capacity of a Bloom filter for a given saturation limit. For example, the output below indicates that a saturation of 0.05 will likely be reached after more than 28 insertions of bytes-like objects of length 8:

>>> b = blooms(32)
>>> b.capacity(8, 0.05)
28

In addition, conversion methods to and from Base64 strings are included to support concise encoding and decoding:

>>> b.to_base64()
'AiAABg=='
>>> sha256('abc'.encode()).digest()[:2] @ blooms.from_base64('AiAABg==')
True

If it is preferable to have a Bloom filter data structure that encapsulates a particular serialization, hashing, and truncation scheme, the recommended approach is to defined a derived class. The specialize method makes it possible to do so in a concise way:

>>> encode = lambda x: sha256(x).digest()[:2]
>>> blooms_custom = blooms.specialize(name='blooms_custom', encode=encode)
>>> b = blooms_custom(4)
>>> b @= bytes([1, 2, 3])
>>> bytes([1, 2, 3]) @ b
True

The user of the library is responsible for ensuring that Base64-encoded Bloom filters are converted back into an an instance of the appropriate derived class.