Trying to implement Rabin Karp algorithm using bloom filter and rolling hash

132 Views Asked by At

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
0

There are 0 best solutions below