C++

Using the hash function for a Bloom filter from the previous homework, implement a full Bloom Filter to use as a spell checker. The input will be in a text file to be read in through stdin. The first line of the file will contain the number of words in the dictionary, followed by the words themselves one per line, followed by a text to spell check. You may assume that the words will all be lower case both in the dictionary and the text, and that the text has no punctuation.

 7 in the beginning once upon a time in the beginning oncee upon a thyme 

Implement the following functions in addition to the hash function you wrote before: addWord, which adds a word to the Bloom filter, and checkWord, which checks to see if a word is in stored in the Bloom filter.

When the program runs, create a Bloom filter that has 16 times as many values as there are words in the dictionary. (You can use an array of bool or a bitset to store the filter.) Add all of the words from the dictionary to the filter, and then check the words in the text using the Bloom filter.

If a word is found to be misspelled, print out the word, along with the 7 hash values generated from it, and the truth values stored in the Bloom filter for each hash, on one line. To make 7 different hash functions, use the p values: 31, 37, 41, 43, 47, 53, and 59.

Sample Program Run

Running your program on the example file should generate something like what is shown below. (Note that the numbers in the example are incorrect, but the formatting is right.)

Misspelled words: oncee: (h31=4:0) (h37=22:0) (h41=2:0) (h43=88:0) (h47=52:0) (h53=22:0) (h59=88:0) thyme: (h31=13:1) (h37=27:0) (h41=111:1) (h43=89:0) (h47=93:0) (h53=27:0) (h59=41:1)