Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More
Socket
Sign inDemoInstall
Socket

simplebloom

Package Overview
Dependencies
Maintainers
1
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

simplebloom

A dumb but fast bloom filter.

  • 1.0.6
  • Source
  • PyPI
  • Socket score

Maintainers
1

simplebloom

simplebloom is a (probably) dumb but fast bloom filter. To quote Wikipedia <https://en.wikipedia.org/wiki/Bloom_filter>_:

A Bloom filter is a space-efficient probabilistic data structure,
conceived by Burton Howard Bloom in 1970, that is used to test
whether an element is a member of a set.
False positive matches are possible, but false negatives are not
– in other words, a query returns either "possibly in set" or
"definitely not in set".
Elements can be added to the set, but not removed [...];
the more items added, the larger the probability of false positives.

The included BloomFilter class is quite dumb as it's fixed size, only supports strings, and always uses the blake2s hash function included with Python 3.6+. But at least it's fast, hey?

Speed

~1.4 million elements/s on an i7-6700HQ, both adding and checking.

Usage

Note that around 98% of the execution time is spent creating UUIDs.

::

import uuid
from simplebloom import BloomFilter

keys = [uuid.uuid4().hex for _ in range(100000)]
bf = BloomFilter(len(keys))

for k in keys:
    bf += k

with open('test.filter', 'wb') as fp:
    bf.dump(fp)

with open('test.filter', 'rb') as fp:
    bf = BloomFilter.load(fp)

for k in keys:
    assert k in bf

other_keys = [uuid.uuid4().hex for _ in range(1000000)]
fp = 0
for k in other_keys:
    fp += k in bf
print(bf.false_positive_prob, fp / len(other_keys))

The BloomFilter class

A simple but fast bloom filter. Elements must be strings.

Add an element and check whether it is contained::

bf = BloomFilter(1000)
bf += 'hellobloom'
assert 'hellobloom' in bf

false_positive_prob defaults to 1 / num_elements.

The number of bits in the filter is num_bits = num_elements * log(false_positive_prob) / log(1 / 2**log(2)), rounded to the next highest multiple of 8.

The number of hash functions used is num_hashes = round(num_bits / num_elements * log(2)) .

Parameters: num_elements: expected max number of elements in the filter false_positive_prob: desired approximate false positive probability

BloomFilter.__iadd__ / add element


Use the "inplace add" syntax to add elements ``bf += k``,
where bf is the ``BloomFilter`` and ``k`` a string.


``BloomFilter.__contains__`` / contains element

Use the "contains" syntax to check if an element is (probably) in the filter k in bf, where bf is the BloomFilter and k a string.

BloomFilter.load


Load a filter from a path or file-like::

    bf = BloomFilter.load('bloom.filter')

    with open('bloom.filter', 'rb') as fp:
        bf = BloomFilter.load(fp)

Parameters:
    - fp: path or file-like


``BloomFilter.loads``

Load a filter from a buffer::

data = bf.dumps()
bf = BloomFilter.loads(data)

Parameters: data: filter data

BloomFilter.dump


Dump filter to a path or file-like::

    bf.dump('bloom.filter')

    with open('bloom.filter', 'wb') as fp:
        bf.dump(fp)

Parameters:
    - fp: path or file-like


``BloomFilter.dumps``

Returns filter data as buffer::

data = bf.dumps()
bf = BloomFilter.loads(data)

Developing

Extension code is generated by Cython. Install Cython to make and build changes to the extension.

Keywords

FAQs


Did you know?

Socket

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

Packages

npm

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc