I have set up a bloom filter that uses 3 hash functions to set the bit array using a set of patterns.
I then have a sliding window on my text and every step it calculates the hash value of the window and finds if it matches the filter or not.
Now, I want to implement it using a rolling hash function to get O(1) complexity on the hashing.
How can I pass the result value of the rolling hash function to the filter in order for it to search?
The closest I could think of is the use 3 rolling hash functions and use them for the filter as well.
Here's what I have managed to do so far, not entirely sure about it:
class FiltreBloom:
def __init__(self, taille_filtre, primes):
self.taille_filtre = taille_filtre
self.primes = primes
self.collisions = 0
# initialisation
self.bits = [0]*self.taille_filtre
def add(self, motif):
# add motif to filter
for prime in self.primes:
h = FiltreBloom.hach(motif, prime) % self.taille_filtre
if self.bits[h] == 1:
self.collisions += 1
else:
self.bits[h] = 1
def contain(self, word):
for prime in self.primes:
value = FiltreBloom.hach(word, prime) % self.taille_filtre
if self.bits[value] == 0:
return False
return True
def hach(motif, prime):
h = 0
taille_motif = len(motif)
for i in range(taille_motif):
h += ord(motif[i])*256**(taille_motif - i - 1)
h = h % prime
return h