Educational Objectives: Understand and get familiar with the implementation and use of the hash table data structure.
Statement of Work: Implement a hash table ADT and develop a spell checker using the hash table.
Project Description:
This project has two parts. In the first part, you will implement a hash table class template named HashTable. In the second part of the project, you will develop a spell checker using the hash table you developed.
Task 1: Requirements of HashTable Class Template
- Your implementation of HashTable must be in the namespace of cop4530.
- You must provide the template declaration and implementation in two different files hashtable.h (containing HashTable class template declaration) and hashtable.hpp (containing the implementation of member functions). You must include hashtable.hpp inside hashtable.h as we have done in the previous projects. The two files hashtable.h and hashtable.hpp will be provided to you, which are incomplete, but contain some helpful functions that you will need to use in developing the hash table class template.
- You must implement hash table using the technique of chaining with separate lists (separate chaining). That is, the internal data structure of the hash table class template should be a vector of lists. You must use the STL containers for the internal data structure instead of any containers you developed in the previous projects.
- You must at least implement all the interfaces specified below for the HashTable class template.
Public HashTable interfaces (T is the template parameter, i.e., the generic data type)
- HashTable(size_t size = 101): constructor. Create a hash table, where the size of the vector is set to prime_below(size) (where size is default to 101), where prime_below() is a private member function of the HashTable and provided to you.
- ~HashTable(): destructor. Delete all elements in hash table.
- bool contains(const T &x) const: check if x is in the hash table.
- bool insert(const T & x): add x into the hash table. Don't add if x is already in the hash table. Return true if x is inserted; return false otherwise.
- bool insert (T &&x): move version of insert.
- bool remove(const T &x): delete x if it is in the hash table. Return true if x is deleted, return false otherwise.
- void clear(): delete all elements in the hash table
- bool load(const char *filename): load the content of the file with name filename into the hash table. In the file, each line contains a single value to be inserted to the hash table.
- void dump() const: display all entries in the hash table. Elements in one entry of the hash table (linked list) are separated by the tab character ("\t") (see the provided executable for more detailed on the output format).
- bool write_to_file(const char *filename) const: write all elements in the hash table into a file with name filename. Each element occupies one line.
Private HashTable interfaces (T is the template parameter)
- void makeEmpty(): delete all elements in the hash table. The public interface clear() will call this function.
- void rehash(): rehash function. Called when the number of elements in the hash table is greater than the size of the vector.
- size_t myhash(const T &x) const: return the index of the vector entry where x should be stored. For the implementation of this function, please do not use the simple example hash functions we discussed in class. You should use the one provided in STL (std::hash). The example implementation of hash table in the textbook and lecture used this STL hash function, and you should follow the similar steps. Note that std::hash is defined in header file <functional>.
- unsigned long prime_below (unsigned long) and void setPrimes(vector<unsigned long>&): two helper functions to determine the proper prime numbers used in setting up the vector size. Whenever you need to set hash table to a new size "sz", call prime_below(sz) to determine the new proper underlying vector size. Note that setPrimes is only used by prime_below. These two functions have been provided in hashtable.h and hashtable.hpp.
You need to write test programs to test various functions of hash table. Moreover, you must implement the hashtable testing functions in the menu function in the incomplete myspell.cpp. You should complete myspell.cpp that provides the same IO interfaces as the sample executable (proj5.x) when it is executed with './proj5.x'. A sample testing input file, test_hashtable.txt, is provided. You can run './proj5.x < test_hashtable.txt > out' to see the expected output.
Task 2: A Spell Checker
In the second part of the project, you will develop a spell checker. The spell checker will take three command-line parameters: filename of the dictionary, name of the file to be checked (check file), name of the output file where the checked (and may be corrected) content should be written to.
- For the dictionary file, we assume that each line contains a single word. You should load the words in the dictionary into a hash table (using the hash table you developed).
- For the check file, we make the following assumptions: 1) It is a text file; 2) Each line may contain multiple words; 3) Words in the file will not span multiple lines (no wrap back); 4) A line may contain multiple misspelled words.
Your spell checker will read the content of the check file line by line; one line at a time. After a line is read, your program will check word by word in the line if it is a valid word (i.e., if it is in the hash table), where a word is defined as a sequence of English letters from 'a' to 'z' (and the capital cases). When an invalid word is encountered (i.e., the word is not in the hash table), you will print out the line with the invalid word CAPITALIZED, you will then output 10 candidate words for the user to choose (to replace the wrong word). There are two issues that need to be decided for a spell checker: (1) what words are considered candidate words, and (2) which of the candidate words are to be presented to the user and how.
In this assignment, you will identify the candidate words in the following manner. For each character in the word, you will replace it with characters from 'a' to 'z', one at a time, starting from the left-most character. After a replacement is done, you will check if the new word is in the hash table. It becomes a candidate word if it is in the hash table. As an example, consider an invalid word "jest", we will create new words with replacement such as "aest", "best", "cest" ..., "zest" (the first letter "j" is replaced by one character (from 'a' to 'z'), one at a time), and "jast", "jbst", "jcst", ..., "jzst" (the second letter 'e' is replaced by 'a' to 'z', one at a time), etc. For each created word, you will check if it is in the hash table (a valid word), and if so, it is a candidate word.
The second issue is which of and how the candidate words are to be presented to the user. To have a reasonably good user experience, the spell checker will try to present more common words earlier to the user. This is achieved by utilizing a word rank file (wordrank.txt in the provided files). Each line in wordrank.txt contains a word and a number (rank). The smaller the rank, the more frequent the word is used. The word rank file is smaller than the dictionary and only contains a subset of words -- wordrank.txt only has a few thousand words. You must load the file and store it in a map in order to decide the rank of a word quickly. For each candidate word found, the spell checker should find its ranking. The spell checker should present the word with smaller rank earlier to the user. For candidate words not in the rank file, the one found earlier should be present earlier (the specific order of finding candidate words is described earlier). You must the consider all possible candidate words in order to identify the 10 candidate words in order.
The spell checker outputs the 10 candidate words to the user, who will choose one (or choose 'n' for no change). Note that each line may contain multiple invalid words, you need to process them one by one in the same manner. If there are less than 10 candidate words, you should just output these candidate words in order.
At the end of your program (after the spell check is finished), you should store the content of the text file, with invalid words corrected (or no change due to user selection), into the output file. You still need to write the content of the text file into the output file, even if all words in the original text file are valid.
A few notes for Task 2:
You can assume the dictionary only contains lower-case words. Put in another way, you should convert a word in the check file to lower-case before you check if it is in the dictionary (hash table).
You can assume that a word in the check file will only contain alphabetical letters. There will be no special characters such as apostrophe (') in the middle of a word. However, we may have punctuation mark at the end of a word such as comma and period, which is not part of the word and should be ignored when checking against the dictionary (hash table).
- It is a good idea to maintain a vector of (up to 10) sorted candidate words during the process to find the 10 words.
A partially implemented driver program named myspell.cpp is provided to you. This program works in two modes. When the program runs without any command-line parameters (try './proj5.x'), it will test the functions of the hash table. For this purpose, a menu() function is provided in myspell.cpp. You should call this function to display the operations that a user can perform on a hash table. You cannot change the menu() function.
In the second mode of the program, three command-line parameters will be provided (try './proj5.x /usr/share/dict/words test0.txt test0.out'), and the program will work as a spell checker.
Extra-credit oppurtunities (up to 30 points)
A) (10 points) Incorporate a more advanced candidate word selection/presentation algorithm. To get the extra point, in addition to implementing your more advanced scheme, you must articulate and demonstrate why your scheme is better than the default scheme in this project. You must also implement the default scheme in order to get the extra points.
B) (10 or 20 points) Develop a nicer interface for the spell checker. You can implement a text-based interface like the UNIX ispell command for 10 extra points. Or you can develop a nice graphical user interface (GUI) for this project. Your GUI must support at least the user interfaces supported by the plain-text version user manual in the provided code. You can develop this part on Windows (10 bonus points) or you can work on a Linux machine such as linprog.cs.fsu.edu (20 bonus points). There are a number of choices for you to develop a GUI on a Linux machine, including Qt and GTKMM, and wxWidgets.
You must complete and submit the required components of the project on linprog if you decide to go for the GUI project for extra credits. You will not get any bonus points if you only have a GUI but cannot perform the required functions of this project.
Note that, even if you decide to develop the GUI on Windows, the required components of the project still needs to work on linprog and will be graded on linprog.cs.fsu.edu. If you work on the extra-credit part on Windows, you will need to set up an appointment with the instructor to grade the extra-credit part. Similarly, if you develop the GUI on your own Linux machine, you will need to set up an appointment to grade it.
The following partial code has been provided to you.
1. hashtable.h : partial implementation
2. hashtable.hpp : partial implementation
3. myspell.cpp: partial implementation
4. proj5.x: executable of myspell.cpp, compiled on linprog.cs.fsu.edu
5. wordrank.txt: a word rank file.
6. test0.txt, test1.txt, test2.txt: sample files to be checked.
For testing your program, you can use /usr/share/dict/words as the dictionary on linprog.cs.fsu.edu
1. Deliverables: For Part 1, turn in all your source program files (hashtable.h, hashtable.hpp, myspell.cpp, and makefile to produce executable proj5.x) in a tar file via the Canvas system. It is due November 29, 11:59pm.
For Part 2, turn in all your source program files (hashtable.h, hashtable.hpp, myspell.cpp, and makefile to produce executable proj5.x) in a tar file via the Canvas system. The myspell.cpp program should include the spell check functionality. It is due December 8, 11:59pm.
Grading:
Part 1 (40 points):
Part 2 (65 points):
Hints: