<commit_before>Dablooms
========

A Scalable, Counting, Bloom Filter
----------------------------------

### Overview
Bloom filters are a probablistic data structure that provide space-efficient
storage of elements at the cost of possible false postive on membership
queries.

This project aims to demonstrate a novel construction that can scale,
and provide not only the addition of new members, but reliable removal of existing
members.

**Dablooms** implements such a structure that takes additional metadata to classify
elements in order to make an intelligenet decision as to which bloom filter an element
should belong.

### Features
**Dablooms**, in addition to the above, has several features. 
    
* Implemented as a static C library
* Memory mapped
* 4 bit counters
* Pre-write and Post-write counters
* Python wrapper

For performance, the low-level operations are implemented in C. It is
memory mapped which gives us persistence at low cost.  Also, in an effort to
maintain memory efficiency, rather than using integers, or even whole bytes as
counters, we use only 4 bit counters.  Because of the scaling quality this provides
space efficiency without an added cost of additional false positives.

The bloom filter also employees pre-write and post-write counters.  These allow us 
determine failed writes, leaving us with a 'dirty' filter where an element is 
only partially written.

Also included is a wrapper to easily leverage the library in Python.

### Example
    
    >>> import pydablooms
    >>> bloom = pydablooms.Dablooms(capacity=1000,
    ...                            error_rate=.05,
    ...                            filepath='/tmp/bloom.bin',
    ...                            id=1)
    >>> bloom.add('foo', 2)
    1
    >>> bloom.check('bar')
    0
    >>> bloom.delete('foo', 2)
    0
    >>> bloom.check('foo')
    0

### Installing
After you have cloned the repo, type `make`, `make install` (`sudo` maybe needed).

To use a specific version of Python, build directory, or destination 
directory, use the `PYTHON`, `BLDDIR`, and `DESTDIR`, respectively. 

An example build might be `make install PYTHON=python2.7 BLDDIR=/tmp/dablooms/bld DESTDIR=/tmp/dablooms/pkg`

### Testing
To run a quick and dirty test, type `make test`.  This test files uses `dict\words`
and defaults to `/usr/share/dict/words`. If your path differs, you can use the
`WORDS` flag to specific its location, such as `make test WORDS=/usr/dict/words`.

This will run a simple test script that iterates through a word
dictionary and adds each word to dablooms. It iterates again, removing every fifth
element. Lastly, it saves the file, opens a new filter, and iterates a third time 
checking the existence of each word. It prints results of the true negatives, 
false positives, true positives, and false negatives.

The maximum error rate for the filter is, by default, set to .05 (5%) and the
initial capacity is set to 100k.  Since the dictionary is near 500k, we should
have created 4 new filters in order to scale to size.

Check out the performance yourself, and checkout the size of the resulting file!

Background
==========
A Bloom filter is traditionally implemented as an array of `M` bits, where
M is the size of the bloom filter. On initialization all bits are set to zero.
A filter is also parameterized by a constant `k` that defines the number of hash
functions used to set and test bits in the filter.  Each hash function should
output one index in `M`.  When inserting an element `x` into the filter, the bits
in the `k` indices `h1(x), h2(x), ..., hk(X)` are set.

In order to query a Bloom filter, say for element `x`, it suffices to verify if
all bits in indexes `h1(x), h2(x), ..., hk(x)` are set. If one or more of these<commit_msg>README: add hint to try "make help"<commit_after>Dablooms
========

A Scalable, Counting, Bloom Filter
----------------------------------

### Overview
Bloom filters are a probablistic data structure that provide space-efficient
storage of elements at the cost of possible false postive on membership
queries.

This project aims to demonstrate a novel construction that can scale,
and provide not only the addition of new members, but reliable removal of existing
members.

**Dablooms** implements such a structure that takes additional metadata to classify
elements in order to make an intelligenet decision as to which bloom filter an element
should belong.

### Features
**Dablooms**, in addition to the above, has several features. 
    
* Implemented as a static C library
* Memory mapped
* 4 bit counters
* Pre-write and Post-write counters
* Python wrapper

For performance, the low-level operations are implemented in C. It is
memory mapped which gives us persistence at low cost.  Also, in an effort to
maintain memory efficiency, rather than using integers, or even whole bytes as
counters, we use only 4 bit counters.  Because of the scaling quality this provides
space efficiency without an added cost of additional false positives.

The bloom filter also employees pre-write and post-write counters.  These allow us 
determine failed writes, leaving us with a 'dirty' filter where an element is 
only partially written.

Also included is a wrapper to easily leverage the library in Python.

### Example
    
    >>> import pydablooms
    >>> bloom = pydablooms.Dablooms(capacity=1000,
    ...                            error_rate=.05,
    ...                            filepath='/tmp/bloom.bin',
    ...                            id=1)
    >>> bloom.add('foo', 2)
    1
    >>> bloom.check('bar')
    0
    >>> bloom.delete('foo', 2)
    0
    >>> bloom.check('foo')
    0

### Installing
After you have cloned the repo, type `make`, `make install` (`sudo` maybe needed).

To use a specific version of Python, build directory, or destination 
directory, use the `PYTHON`, `BLDDIR`, and `DESTDIR`, respectively. 
Look at the output of `make help` for more options.

An example build might be `make install PYTHON=python2.7 BLDDIR=/tmp/dablooms/bld DESTDIR=/tmp/dablooms/pkg`

### Testing
To run a quick and dirty test, type `make test`.  This test files uses `dict\words`
and defaults to `/usr/share/dict/words`. If your path differs, you can use the
`WORDS` flag to specific its location, such as `make test WORDS=/usr/dict/words`.

This will run a simple test script that iterates through a word
dictionary and adds each word to dablooms. It iterates again, removing every fifth
element. Lastly, it saves the file, opens a new filter, and iterates a third time 
checking the existence of each word. It prints results of the true negatives, 
false positives, true positives, and false negatives.

The maximum error rate for the filter is, by default, set to .05 (5%) and the
initial capacity is set to 100k.  Since the dictionary is near 500k, we should
have created 4 new filters in order to scale to size.

Check out the performance yourself, and checkout the size of the resulting file!

Background
==========
A Bloom filter is traditionally implemented as an array of `M` bits, where
M is the size of the bloom filter. On initialization all bits are set to zero.
A filter is also parameterized by a constant `k` that defines the number of hash
functions used to set and test bits in the filter.  Each hash function should
output one index in `M`.  When inserting an element `x` into the filter, the bits
in the `k` indices `h1(x), h2(x), ..., hk(X)` are set.

In order to query a Bloom filter, say for element `x`, it suffices to verify if
all bits in indexes `h1(x), h2(x), ..., hk(x)` are set. If one or more of these
{'fraction_non_alphanumeric': 0.08311415044713309, 'fraction_numerical': 0.008153603366649132, 'mean_word_length': 3.4421728971962615, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 39, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6827779', 'n_tokens_mistral': 2101, 'n_tokens_neox': 1979, 'n_words': 1095}