BloomFilter

A Bloom filter is a space-efficient probabilistic data structure Wiki

Installation

Add this line to your application's Gemfile:

gem 'bloom_filter'

And then execute:

$ bundle install

Or install it yourself as:

$ gem install bloom_filter

Usage

After installation the instance can be created. And two parameters can be used to describe the bloom filter:

• first - number of items that are be inserted(default: 100)
• second - False Positive probability(default: 0.01)

bloom_filter = BloomFilter::Filter.new(1000, 0.001)

Methods

add(value) - add item into filter

includes?(value) - check if filter includes the value

contains?(value) - alias of includes?(value)

count - returns number of inserted items

capacity - returns initial capacity

probability - returns initial probability

bit_size - returns number of bits in the bit array

get_bit(position) - returns value of a bit(true/false) in the bit array, rises an error if position is out of range of the bit array

set_bit(position) - set a bit to TRUE in the bit array, rises an error if position is out of range of the bit array

clear_bit(position) - set a bit to FALSE in the bit array, rises an error if position is out of range of the bit array

union_with(bloom_filter) - unions current bloom filter with another one, bloom filters should be the instances of this module and have the same initial params(capacity, probability)

intersect_with(bloom_filter) - intersects current bloom filter with another one, bloom filters should be the instances of this module and have the same initial params(capacity, probability)

Contributing

Bug reports and pull requests are welcome on GitHub at https://github.com/superedriver/bloom_filter