philiprehberger-bloom_filter
v0.7.0399,129 downloadsMIT
Space-efficient probabilistic set with configurable false positive rate
$
gem install philiprehberger-bloom_filterREADME
philiprehberger-bloom_filter
Space-efficient probabilistic set with configurable false positive rate
Requirements
- Ruby >= 3.1
Installation
Add to your Gemfile:
gem "philiprehberger-bloom_filter"
Or install directly:
gem install philiprehberger-bloom_filter
Usage
require "philiprehberger/bloom_filter"
filter = Philiprehberger::BloomFilter.new(expected_items: 10_000, false_positive_rate: 0.01)
filter.add('hello')
filter.include?('hello') # => true
filter.include?('world') # => false
Pre-sizing
Compute the optimal bit-array size and hash-function count before allocating a filter — useful for budgeting memory or sharing parameters between processes.
bits = Philiprehberger::BloomFilter.optimal_size(expected_items: 10_000, false_positive_rate: 0.01)
# => 95851
hash_count = Philiprehberger::BloomFilter.optimal_hash_count(size: bits, expected_items: 10_000)
# => 7
Expected False Positive Rate
Estimate the false-positive rate for any custom size, expected-item count, and hash-function count — useful when you've fixed the bit budget or hash count and want to see what FPR you'll actually get.
Philiprehberger::BloomFilter.expected_false_positive_rate(
size: 95_851,
expected_items: 10_000,
hash_count: 7
)
# => ~0.01
Merge Filters
a = Philiprehberger::BloomFilter.new(expected_items: 1000)
b = Philiprehberger::BloomFilter.new(expected_items: 1000)
a.add('alpha')
b.add('beta')
a.merge(b)
a.include?('beta') # => true
Bulk Add
filter = Philiprehberger::BloomFilter.new(expected_items: 10_000)
filter.bulk_add(%w[alpha beta gamma delta])
filter.include?('beta') # => true
Bulk Membership
filter = Philiprehberger::BloomFilter.new(expected_items: 10_000)
filter.bulk_add(%w[alpha beta gamma])
filter.bulk_include?(%w[alpha beta unseen]) # => [true, true, false]
Cardinality Estimation
filter.count_estimate # => ~4.0 (estimated unique items)
Intersection
a = Philiprehberger::BloomFilter.new(expected_items: 1000)
b = Philiprehberger::BloomFilter.new(expected_items: 1000)
a.bulk_add(%w[shared only-a])
b.bulk_add(%w[shared only-b])
result = a.intersection(b)
result.include?('shared') # => true
result.include?('only-a') # => false
Fill Rate
filter.fill_rate # => 0.023 (proportion of set bits)
Equality and Copying
a = Philiprehberger::BloomFilter.new(expected_items: 1000)
b = Philiprehberger::BloomFilter.new(expected_items: 1000)
a.add('hello')
b.add('hello')
a == b # => true
clone = a.copy
clone.add('world')
a.include?('world') # => false (independent copy)
False Positive Rate
filter = Philiprehberger::BloomFilter.new(expected_items: 1000, false_positive_rate: 0.01)
100.times { |i| filter.add("item-#{i}") }
filter.false_positive_rate # => ~0.0001 (actual rate based on current fill)
Superset Check
a = Philiprehberger::BloomFilter.new(expected_items: 1000)
b = Philiprehberger::BloomFilter.new(expected_items: 1000)
a.bulk_add(%w[alpha beta gamma])
b.add('alpha')
a.superset?(b) # => true
Empty Check
filter = Philiprehberger::BloomFilter.new(expected_items: 1000)
filter.empty? # => true
filter.add('hello')
filter.empty? # => false
Union (Non-Mutating)
a = Philiprehberger::BloomFilter.new(expected_items: 1000)
b = Philiprehberger::BloomFilter.new(expected_items: 1000)
a.add('alpha')
b.add('beta')
result = a.union(b)
result.include?('alpha') # => true
result.include?('beta') # => true
a.include?('beta') # => false (a is unchanged)
Subset Check
a = Philiprehberger::BloomFilter.new(expected_items: 1000)
b = Philiprehberger::BloomFilter.new(expected_items: 1000)
a.add('alpha')
b.bulk_add(%w[alpha beta gamma])
a.subset?(b) # => true
Operator Aliases
a = Philiprehberger::BloomFilter.new(expected_items: 1000)
b = Philiprehberger::BloomFilter.new(expected_items: 1000)
a.add('alpha')
b.add('beta')
union = a | b # same as a.union(b)
intersection = a & b # same as a.intersection(b)
Compatibility Check
a = Philiprehberger::BloomFilter.new(expected_items: 1000)
b = Philiprehberger::BloomFilter.new(expected_items: 1000)
a.compatible?(b) # => true, safe to merge / intersect / union
Saturation Check
filter = Philiprehberger::BloomFilter.new(expected_items: 100)
filter.saturated? # => false
200.times { |i| filter.add("item-#{i}") }
filter.saturated?(threshold: 0.5) # => true
Serialization
data = filter.serialize
restored = Philiprehberger::BloomFilter.deserialize(data)
restored.include?('hello') # => true
JSON Serialization
json = filter.to_json
restored = Philiprehberger::BloomFilter.from_json(json)
restored.include?('hello') # => true
API
| Method | Description |
|---|---|
.new(expected_items:, false_positive_rate:) | Create a new bloom filter |
.optimal_size(expected_items:, false_positive_rate:) | Compute optimal bit-array size for a target false positive rate |
.optimal_hash_count(size:, expected_items:) | Compute optimal hash-function count for a given bit-array size |
.expected_false_positive_rate(size:, expected_items:, hash_count:) | Estimate FPR for a custom size, item count, and hash-function count |
#add(item) | Add an item to the filter |
#include?(item) | Check if an item might be in the filter |
#merge(other) | Merge another compatible filter into this one |
#clear | Reset the filter |
#count | Number of items added |
#memory_usage | Bit array size in bytes |
#serialize | Serialize to a hash |
#bulk_add(items) | Add all items from an enumerable |
#bulk_include?(items) | Check membership for many items, returning an array of booleans |
#count_estimate | Estimate unique item count from fill rate |
#intersection(other) | Create filter matching items in both |
#fill_rate | Proportion of set bits (0.0 to 1.0) |
#==(other) | Structural equality comparison |
#copy | Create an independent deep clone |
#false_positive_rate | Actual FP rate based on current fill |
#to_json | Serialize to JSON string |
#superset?(other) | Check if self contains all bits of other |
#empty? | Check if no items have been added |
#union(other) | Non-mutating OR returning a new filter |
#subset?(other) | Check if every set bit in self is also set in other |
#compatible?(other) | Check structural compatibility with another filter |
#saturated?(threshold:) | True if fill rate is at/above threshold |
#|(other) | Operator alias for #union |
#&(other) | Operator alias for #intersection |
#hash / #eql? | Hash key support consistent with #== |
#inspect | Human-readable representation |
.deserialize(data) | Restore a filter from serialized data |
.from_json(str) | Restore a filter from a JSON string |
Development
bundle install
bundle exec rspec
bundle exec rubocop
Support
If you find this project useful: