Complete the rabin_karp_batchmatch procedure in rkmatch.c. In the template code,

Question

Complete the rabin_karp_batchmatch procedure in rkmatch.c. In the template code, we tell you the size of the bitmap to use (in bits) as a procedure argument (bsz). In the rabin_karp_batchmatch procedure, you should invoke the auxilary function bloom_init to allocate and initialize a byte array (i.e. character array) that will pack bsz bits for use as the bloom filter's bitmap. You should then compute all m/k RK hash values corresponding to X's chunks and insert them into the Bloom filter using bloom_add. Subsequently, you scan Y's content and compute a RK value for each of its n-k+1 substrings and query its presence in the Bloom filter using bloom_query. If bloom_query indicates a potential match, you proceed to check that the corresponding substring of Y indeed matches one of the m/k chunks of X.

Keep in mind that unlike simple_substr_match or rabin_karp_match, returning 1 or 0 is no longer sufficient; rabin_karp_batchmatch is invoked only once and therefore must return the total number of chunks of X that have appeared in Y.

bloom.c (the bloom functions that need to used in the method):

bloom.c

rabin_karp_batchmatch:

  * Allocate a bitmap of bsz bits for the bloom filter (using bloom_init)     and insert all m/k RK hashes of qs into the bloom filter (using bloom_add).       Compute each of the n-k+1 RK hashes of ts and check if it's in the filter (using bloom_query).      This function returns the total number of matched chunks.      For testing purpose, you should print out the first PRINT_BLOOM_BITS bits      of bloom bitmap in hex after inserting all m/k chunks from qs.     Important: accoring to our counting rule, each segmented X(size k) should only be counted as once,                so you must maintain a data structure to check if that segmented X(size k) has been counted                already.   */  int  rabin_karp_batchmatch(int bsz, /* size of bitmap (in bits) to be used */      int k,/* chunk length to be matched */      const unsigned char *qs, /* query docoument (X)*/      int m,/* query document length */       const unsigned char *ts, /* to-be-matched document (Y) */      int n /* to-be-matched document length*/)  {        /* Your code here */      /* step 1: allocate bloom filter(bloom_init) and insert query string(segment document X by size k)         one by one by using bloom_add */      /* step 2: print bloom filter's result by using bloom_print */      /* step 3: initiize document Y's first hash value */      /* step 4: compare segmented Y's and segmented X's hash values by using bloom_query,                  if matched, compare each segmented X(size k) to present segmented Y. And                 don't forget the Important reminder */      /* step 5: return matched number */                       return 0;  }  

Explanation / Answer

Below is your function

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.