Implement a Bloom filter class called BloomFilter according to the provided BloomFilter.h. Your Bloom filter should have no false negatives and as low a false positive probability as you can achieve....

Please see attached PDF


Implement a Bloom filter class called BloomFilter according to the provided BloomFilter.h. Your Bloom filter should have no false negatives and as low a false positive probability as you can achieve. Note that while a typical Bloom filter utilizes bitmaps, in this exercise you are asked to implement a Bloom filter which utilizes characters instead. The Bloom filter should contain the following methods and members: • BloomFilter – Constructor of an empty Bloom filter of a given length ‘len’. • insert – Accepts a string ‘item’ and inserts it to the Bloom filter. • exists – Accepts a string ‘item’ and checks whether item is in the filter. Returns true if the item is probably in the filter, and false if the item is definitely not in the filter. • output – Returns a string of characters representing the Bloom filter. • length – Specifies the length of the Bloom filer, in chars. • bf – The bloom filter, as a string of chars. Submit your implementation in MyBloomFilter.cpp, along with a brief explanation of your implementation in a comment at the top of the file. Your code should compile and run on c++17 with the provided BloomFilter.h, as well as a main file similar to the provided main.cpp. These are the points to consider for this task: • Designing good hash functions for the Bloom filter. • Determining the ideal number of hashes to use. • Managing the translation from bit-based Bloom filters to a char-based Bloom filter. BloomFilter.h: #ifndef BloomFilter_h #define BloomFilter_h #include using namespace std; class BloomFilter { public: /** * Instantiate an empty Bloom filter of length 'len' chars. */ //BloomFilter (int len){ length=len; } BloomFilter (int len); /** * Inserts item into the filter */ void insert(string item); /** * Checks whether item is in the filter. * Returns true if the item is probably in the filter * false if the item is definitely not in the filter */ bool exists(string item); /** * Returns a string of characters representing the Bloom filter */ string output(); protected: int length; /** The length of the Bloom filter, in chars. */ char *bf; /** The Bloom filter */ }; #endif /* BloomFilter_h */ main.cpp: #include #include "BloomFilter.h" using namespace std; int main(){ string my_str = "aab"; /* Try different sizes here */ BloomFilter my_filter(10); cout< "my="" empty="" filter="" looks="" like:="" "="">< my_filter.output()="">< endl;="" my_filter.insert(my_str);="" cout="">< "inserting="" "="">< my_str="">< endl;="" cout="">< "my="" filter="" now="" looks="" like:="" "="">< my_filter.output()="">< endl;="" cout="">< "is="" "="">< my_str="">< "="" in="" my="" filter?="" ";="" if="" (my_filter.exists(my_str))="" cout="">< "\t\tyes."="">< endl;="" else="" cout="">< "\t\tno."="">< endl;="" string="" fake_str="bab" ;="" cout="">< "is="" "="">< fake_str="">< "="" in="" my="" filter?="" ";="" if="" (my_filter.exists(fake_str))="" cout="">< "\t\tyes."="">< endl;="" else="" cout="">< "\t\tno."="">< endl; } endl;="">