__Home__ __Schedule__ Lab

__Home__

__Schedule__Lab

**Computer Systems Organization**

**CSCI-UA.0201(007), Fall 2019**

**Lab-2: Rabin-Karp Substring Matching**

Home Lab代写 Lab-2: Rabin-Karp Substring Matching.In this lab, you will write a program called rkgrep to find whether one (or more) patterns appears in a file

**Due: 10/19**

In text document processing, it is sometimes the case that we need to find out whether a (smaller) string appears somewhere in another (larger) string as a substring. For example, the UNIX utility *grep* allows you to search for one or more patterns in a file.

In this lab, you will write a program called *rkgrep* to find whether one (or more) patterns appears in a file. The goal of this lab is to help you improve your C programming skills e.g. manipulating arrays, pointers, number and character representation, bit operations etc.

**Obtaining the lab code Home Lab代写**

First, click on Lab2’s github classroom invitation link (posted in Piazza) and select your NYU email address. Next, clone your repo by typing the following

$ cd cso-labs $ git clone https://github.com/nyu-cso-fa19/lab2-<YourGithubUsername>.git lab2

This lab’s files are located in the *lab2*/ subdirectory. The files you will be modifying are *rkgrep.c* and *bloom.c* .

**Part I: Naive matching**

The most naive way of doing substring matching is to individually check whether a pattern string P matches the substring of length * m *at position

*0,*

*1,*

*2,**in the document string Y.*

*…, n-m*Here, * m *is the length of the pattern string P and

*is the length of document string Y. In other words, we are going to check whether P is the same as Y[0..m-1], Y[1..m], …, Y[n-m…n-1], where Y[0..m-1] is the substring of length m starting at position 0 of Y, Y[1..m] is the substring at position 1, and so on.*

*n*As an example, suppose the pattern string is “dab”, the document string is “abracadabra”. then you would check whether “ada” is the same as the substring at position 0 (“abr”), at position 1 (“bra”), … until you find a match at position 6.Home Lab代写

This naive algorithm is slow. If the pattern string is of length * m*, each check takes

*O(m)**time in the worst case. Since there are total*

*n**checks, the naive algorithm takes*

*O(m*n)**to perform the substring match. Nevetheless, naive matching is extremely simple and so let’s get started on that.*

Your job: Complete the function *naive_substring_match* in *rkgrep.c* file and test it by typing:

$ make $ ./rkgrep_test -a naive

**Part II: Rabin-Karp Substring Matching Home Lab代写**

The __Rabin-Karp____ ____substring____ ____matching____ ____algorithm__ (short for RK) was invented in the eighties by two renowned computer scientists, Michael Rabin and Richard Karp.

To check whether a given pattern string P appears as a substring in document string Y, RK uses the idea of hashing: A hash function turns a string of arbitary length into a b-bit hash value with the property that collision (two different strings having the same hash value) is unlikely.

At a high level, RK works by computing a hash for the pattern string of length m, hash(P), as well as hashes for all n-m+1 substrings of length m in the document string Y, hash(Y[0..m-1]), hash(Y[1..m]), …, hash(Y[n-m..n-1]), where Y[0..m-1] is the substring of length * m *at position 0 of Y, Y[1..m] is the substring at position 1 of Y, and so on. If hash(P) is identical to the hash at position i of Y, we can then perform the usual byte-by-byte comparison of P with the substring at position i to determine if P indeed matches at position i of Y.

There are many nice hash functions out there (such as MD5, SHA-256). but unfortunately, none of them would make RK any faster since they would take O(m) time to compute each of the n-m+1 hashes from Y. RK’s magical ingredient is its invention of a “rolling” hash function. Specifically, given hash(Y[i..i+m-1]), RK takes only constant time instead of O(m) time to compute the hash for the next substring, hash(Y[i+1..i+m]).

**Let’s see how the rolling hash is done in RK. Home Lab代写**

Specifically, we’ll treat each byte as a “digit” in a base-256 representation. For example, the string ‘ab’ corresponds to two digits with one being 97 (the ASCII value of ‘a’), and the other being 98 (the ASCII value of ‘b’). The decimal value of ‘ab’ in base-256 can be calculated as 256*97+98 = 24930. For a string P of length m, its RK hash is calculated as:

`hash(P[0...m-1]) = 256m-1*P[0]+256m-2*P[1]+...+2561*P[m-2]+P[m-1] (1)`

Next, let us see how a rolling calculation of the hash values is done. Let yi=hash(Y[i…i+m-1]). We can compute yi+1 from yi in constant time, by observing that

y_{i+1}= 256m-1*Y[i+1] + 256m-2*Y[i+2] + ... + Y[i+m] = 256 * ( 256m-2*Y[i+1] + ... Y[i+m-1]) + Y[i+m] = 256 * ((256m-1*Y[i] + 256m-2*Y[i+1] + ... Y[i+m-1]) - 256m-1*Y[i]) + Y[i+m] = 256 * ( y_{i}- 256m-1 * Y[i]) + Y[i+m] = 256 * y_{i}- 256m * Y[i] + Y[i+m] (2)

Note that in order to achieve constant time calculation, we have to remember the value of 256m in a variable instead of re-computing it each time.Home Lab代写

Now we’ve seen how rolling hash works. The only fly in the ointment is that these base-256 hash values are too huge to work with efficiently and conveniently. Therefore, we perform all the computation in modulo q, where q is chosen to be a large prime. (for those with a joint math major: why a prime instead of non-prime?)

**Use modulo operations for all arithmetic**

All the arithmetic operations done in Rabin-Karp, including addition, multiplication, exponentiation, should be done over a finite field using modulo operations.

With RK hashes, collisions are infrequent, but still possible. Therefore once we detect some yi = hash(P), we should compare the actual strings Y[i..i+m-1] and P[0..m-1] to see if they are indeed identical.

RK speeds up substring matching significantly. In particular, RK’s runtime is O(n) (since hash collusion is rare) compared with O(n*m) for the naive algorithm.

Your job: Implement the RK substring matching algorithm by completing the *rk_substring_match* procedure. To make your implementation modular and allows unit testing, we ask you to implement RK hash by writing two procedures, *rkhash_init* and* rkhash_next* .Home Lab代写

The procedure* long long rkhash_init(const char *charbuf, int m, long long *h)* takes as input a string pointer and a length m and returns the RK hash computed from scratch according to equation (1). It also returns the value of 256m by storing it in the long long variable pointed to by the third argument h.

The procedure rkhash_next(long long curr_hash, long long h, char leftmost, char rightmost) computes the next rolling hash given the current RK hash according to (2). Suppose yi is the current RK hash covering substring Y[i…i+m-1), then one can compute yi+1 over substring Y[i+1…i+m] by invoking rkhash_next(yi, h, Y[i], Y[i+m]). The second argument of rkhash_next must contain 256m.

**Use modulo arithmatic**

When calculating the hash values, you should use the given modulo arithmatic functions,

*madd , mdel , mmul .*

Testing: Test your implementation by typing

$ make $ ./rkgrep_test -a rk

The test prints out the measured running time. You should observe that the running time for RK is significantly faster than that of the naive algorithm.

**Part III: Multi-pattern RK Matching with a Bloom Filter Home Lab代写**

It turns out that RK is not the most efficient algorithm for performing single-pattern substring matching (i.e. matching just one pattern in a document). RK’s advantage is that it can efficiently match many patterns in the same document by storing the rolling hashes of the document and re-using it across patterns.

Let us assume that when we do multi-pattern matching, most of the patterns will not have any matches in the document. In this case, we can use a bloom filter to “store” rolling hashes in a kind of super-compressed way.

**A Bloom filter is a bitmap of h bits initialized to zeros in the beginning.**

To insert value v into the bitmap, we use *f** *hash functions to map v into f positions in the bitmap and set each position to be one. For example, for a 8-bit bitmap and f=2, if v is mapped to positions 1,5, then the bitmap after insert v would be 01000100. Subsequently, suppose we also inserted v’ which is mapped to positions 0,3, the resulting bitmap would be 11010100.

There are many reasonable conventions with which we can use a byte array to represent a bitmap. In this lab, we expect you follow one specific convention and interpret bits in the Big- Endian convention within a byte. For example, we use a 2-byte-array to represent a 16-bit bitmap. The first byte represents the first 8-bit of the bitmap. And the most-significant-bit of the first byte represents the first bit of the bitmap. The most-significant-bit of the second byte represents the 9-th bit of the bitmap. Suppose the bitmap is 11010100 01000001, then the array content should be {0xe4, 0x41}.Home Lab代写

**We can query the bloom filter to find out whether a value v might be present.**

To do this, we check all f mapped positions of v. If all f bits are set in these mapped positions, then v is probably among the set of values inserted in the bitmap. We say that v is probably present because there can be false positives, i.e. v may not actually be present since a different value v’ may happen to have been mapped to the same positions as v (with a very small probability if the bitmap is large enough). Note that there are no false negatives (i.e. if bloom filter says v is not present, then v is definitely not present).

**To use bloom filter for multi-pattern RK matching**

we first create a bloom filter and insert all n- m+1 hashes for substrings of length m in the document to the bloom filter. Then, for each of the k patterns (assuming they all have the same length m), we check whether or not it is present in the bloom filter. If not, we can declare that the pattern is not present in the document and move on to check the next pattern. If yes, we then invoke our regular single- pattern RK function to confirm whether the pattern is indeed a match or not.Home Lab代写

If most patterns are non-matches, then this algorithm is very fast as it only takes a constant time to query the bloom filter.

Your job: First implement the Bloom filter functions by implementing the* bloom_query* , and *bloom_add* in the source file *bloom.c* .

To help you implement *bloom_add* and *bloom_query* , we provide you with a specific hash function implementation to map a value into a bitmap position, i.e.* int hash_i(int i, long long x)* . This function will hash a given Rabin-Karp hash value x into an *int* value according to the i-th hash function. Where i ranges from 0 to *BLOOM_HASH_NUM-1.* ( *BLOOM_HASH_NUM* is a global constant specifying the number of hash functions that you should use.) Note that you need to confine the resulting hash value to the appropriate range [0, bloom_bitmap_size) by using the modulo operation.

**Testing: After you are done with the bloom filter implementation, test its correctness by typing Home Lab代写**

$ make $ ./rkgrep_test -a bloom

Once your bloom filter passes the test, you can implement the multi-pattern RK matching by implementing the rk_create_doc_bloom and rk_substring_match_using_bloom in the source file rkgrep.c . Afterwards, test your implementation by typing:

$ make $ ./rkgrep_test -a rkbloom

Once you finish all parts, you can run all tests by simply typing ./rkgrep_test . This would run the tests for all parts one by one.Home Lab代写

**Programming style:**

As is the case with Lab-1, you will be graded for style and we will deduct up to 20% of total lab points for bad style based on our subjective evaluation. Please read this style guide and follow the advice.

**Handin Procedure**

To handin your files, simply commit and push them to github.com

$ git commit -am "Finish lab2" $ git push origin

We will fetching your lab files from Github.com at the specified deadline and grade them.

**Bonus exercise: Boyer-Moore string matching Home Lab代写**

The Rabin-Karp algorithm is pretty fast, but it still needs to scan every single character in the document string. Can we run faster than that? Can we avoid even having to look at every character in the document string? Surprisingly, the answer is yes, and the algorithm that achieves this sub-linear performance is called the Boyer-Moore string searching algorithm.

**This algorithm is the one used by the UNIX command ***grep* .

*grep*.

For the bonus exercise, implement Boyer-Moore by reading the first 4 sections of the original __Boyer-Moore ____paper__. You need to implement the *init_delta1* , *find_rpr* , *init_delta2* and *boyer_moore* functions in the *bmgrep.c* file.Home Lab代写

Test your implementation by typing:

$ make $ ./bmgrep_test

更多其他: prensentation代写 Case study代写 Academic代写 Review代写 Resume代写 Case study代写 心理学论文代写 哲学论文代写 计算机论文代写

您必须登录才能发表评论。