How can I make use of numpy's vector operations for a Bloom Filter implementation? I started from https://www.geeksforgeeks.org/bloom-filters-introduction-and-python-implementation/ and modified for naive ndarray support.
Remark: I'm not bound to mmh3 - this was just the only library that allowed me to make use of seeded hashing for generating multiple hash functions.
import numpy as np
import math
import mmh3
from bitarray import bitarray
class BloomFilter(object):
def __init__(self, items_count: int = 100_000, fp_prob : float = 0.01):
self.fp_prob = fp_prob
self.size = self.get_size(items_count, fp_prob)
self.hash_count = self.get_hash_count(self.size, items_count)
self.bit_array = bitarray(self.size)
self.bit_array.setall(0)
def add(self, item):
if type(item) is np.ndarray:
for i in item.reshape(-1):
self.add(i)
else:
digest = self.digest(item)
for pos in digest:
self.bit_array[pos] = True
def digest(self, item):
return [mmh3.hash(item, seed=i) % self.size for i in range(self.hash_count)]
def contains(self, item):
if type(item) is np.ndarray:
return np.array(
[self.contains(i) for i in item.reshape(-1)],
dtype=np.bool8
).reshape(item.shape)
else:
return all(self.bit_array[pos] for pos in self.digest(item))
@classmethod
def get_size(self, n, p):
return int(-(n * math.log(p))/(math.log(2)**2))
@classmethod
def get_hash_count(self, m, n):
return int((m/n) * math.log(2))
items = np.random.randint(size=1_000_000, low=0, high=2**60, dtype=np.int64)
set_of_items = BloomFilter(items.size, 0.001)
set_of_items.add(items)
items2 = np.random.randint(size=100_000, low=0, high=2**60, dtype=np.int64)
existing = set_of_items.contains(items2)
new_items = items2[~existing]
print(f"#{len(new_items)}")