Due on Wednesday, November 28 at 11:59 PM. This is a team lab. You and your assigned lab partner(s) will complete this lab together. Make sure that you are familiar with the Partner Etiquette guidelines. You may discuss the concepts of this lab with other classmates, but you may not share your code with anyone other than course staff and your lab partner(s). Do not look at solutions written by students other than your team. If your team needs help, please post on the Piazza forum or contact the instructor or ninjas. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.
We will be using Teammaker to form teams. You can log in to that site to indicate your preferred partner. Once you and your partner have specified each other, a GitHub repository will be created for your team. If you have any trouble using Teammaker, contact your instructor.
Imagine that you are reading a large PDF document, such as our cs35 textbook by Shaffer, and you want to find the most relevant pages where priority queues are described. If you search for those keywords in the document, you will most likely be given a sequential list of pages where they occur, rather than a prioritized list, where pages with the most occurrences are first.
In this lab you will write a program that reads in documents, and then repeatedly searches the document for particular keywords. For each search, the program efficiently finds the ten most relevant pages that contain that keyword.
To accomplish this you will build two new implementations of the Dictionary
ADT:
LinearDictionary
HashTable
Then you will create a KeywordSearcher
class that employs your Dictionary
implementations along with an existing implementation of a PriorityQueue
to quickly search documents for keywords.
Your starting code can be found in the appropriate repository for your team. The following is a description of the repository’s initial comments; bolded files are those which you must change in completing the lab.
adts/
: As with your last lab, the ADT interface declarations are stored here. The most notable addition for this lab is stlMaxPriorityQueue.h
.linearDictionary.h/linearDictionary-inl.h
: The LinearDictionary class you will be implementing to store collisions within your HashTable.hashTable.h/hashTable-inl.h
: The HashTable class you will be implementing.keywordSearcher.h/keywordSearch.cpp
: The KeywordSearcher class you will be implementing.hashFunctions.h/hashFunctions.cpp
: The functions used to hash values of different types.tests.cpp
: The unit testing program you will use to confirm that your LinearDictionary and HashTable are correct.manualTests.cpp
: A sandbox test program for you to use while you develop your program.textifyPDF.py
: A python program that can be used to convert a PDF document into a text document that is keyword searchable.LinearDictionary
We recommend that you implement a LinearDictionary
as a vector of key, value pairs. All of the operations should run in \(O(n)\) time. You may be thinking: “Why would I want such an inefficient implementation of the Dictionary
ADT?” The answer is that, for very small dictionaries, simpler implementations perform much better as they have a smaller constant overhead.
We will use the LinearDictionary
to represent the chain of collisions in our HashTable
. Because we expect each chain to be relatively short, the LinearDictionary
provides a nice abstraction that will be efficient enough for our purposes.
Unit tests have been provided for this lab; once you have completed your LinearDictionary
implementation, the appropriate unit tests should pass.
vector
In order to implement the remove
operation of your LinearDictionary
, you’ll need to learn about how to remove from a vector
.
The vector
class provides a means to remove an element from the end of a list (pop_back
) but doesn’t give a clear interface for removing elements e.g. from an arbitrary index. Vectors provide a general function called erase
which can delete entire contiguous regions:
vector<int> vec = ...;
vec.erase(vec.begin() + start_index, vec.begin() + end_index);
The above function works much like a Python slice: the start index is included but the end index is not. Thus, remove_range_from_vector(1,3)
would remove the second and third elements (indices 1 and 2) from the vector. If you want to delete a single element from a vector, you can do something like this:
vector<int> vec = ...; // whatever defines this vector
int index = ...; // e.g. 4
vec.erase(vec.begin() + index, vec.begin() + index + 1);
HashTable
Once your LinearDictionary
implementation is complete, you can begin implementing a chaining hash table as we discussed in class. (You will not implement a linear probing hash table.) The figure at right shows an example of a chaining hash table with size 3, capacity 4, and storing integer keys with string values.
Here are some important details about this class:
LinearDictionary
objects to represent the buckets of your HashTable
.0.75
).HashTable
(other than getKeys
and getItems
) must run in \(O(1)\) average time.HashTable
must maintain a reasonable load factor in order to operate efficiently. You will likely want to create some private helper methods to assist with increasing the table’s capacity when the load factor becomes too high. (Don’t forget to document those methods according to the Coding Style Requirements below!)hashFunctions.h
and hashFunctions.cpp
for keys of type int
and string
.Once you have completed your HashTable
implementation, the appropriate unit tests should pass.
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||
Once your implementations of the LinearDictionary
and HashTable
are complete, you can begin implementing the class KeywordSearcher
. The figure at right shows an example document that is available in the test_data
directory called tiny.txt
. Notice that each new page is marked by a special set of characters: $$@@$$PAGE:
. You can assume that all documents that you read in will follow this format. The figure also shows a conceptual view of the kind of data structure that your KeywordSearcher
should construct. This class will use a hash table keyed on the unique words within a document. Associated with each word is another structure that tracks the page numbers where that word occurs and the number of times it appears on that page.
Here are some important details about this class:
HashTable
keyed on the unique words within the document, but you may choose the value associated with these keys. Here are two suggestions:
HashTable
keyed on page numbers and storing the number of occurrences on that page.loadWords
and search
.STLMaxPriorityQueue
class (see its interface in the adts
directory). Notice that one of its constructors takes a vector<pair<P, V>>
as an argument and will heapify it. By using the number of occurrences of a word as the priority, and the page number as the value, you can use the resulting priority queue to efficiently find the top ten most relevant pages by repeatedly removing the maximum from it. Note that use of a priority queue is required; your top ten algorithm must run in \(O(m)\) time, where \(m\) is the number of matching pages. You can’t simply sort the matching pages; this would take \(O(m \log m)\) time.Once you have completed your KeywordSearcher
implementation, the appropriate unit tests should pass.
The final part of your lab is to implement the main program, which will read in a document as a text file, and allow the user to repeatedly search the document for particular keywords. For each keyword search, it returns the top ten pages within the document that contain that keyword the most times. If the word doesn’t appear on at least ten pages, then it should return as many pages as it can. It should also gracefully handle the case where the word does not appear at all within the document.
For instance, here is a sample run of the program done on the the contents of the textbook for this class:
./keywordSearch test_data/DataStructuresAndAlgorithmAnalysis.txt
File loaded
Please enter a search word or '!' to quit: priority
The word priority appears in the file...
on page 220 (11 occurrences)
on page 197 (8 occurrences)
on page 204 (7 occurrences)
on page 206 (5 occurrences)
on page 421 (5 occurrences)
on page 612 (3 occurrences)
on page 422 (2 occurrences)
on page 203 (2 occurrences)
on page 425 (2 occurrences)
on page 543 (2 occurrences)
Please enter a search word or '!' to quit: queue
The word queue appears in the file...
on page 150 (23 occurrences)
on page 148 (22 occurrences)
on page 149 (12 occurrences)
on page 152 (9 occurrences)
on page 153 (8 occurrences)
on page 151 (8 occurrences)
on page 417 (7 occurrences)
on page 147 (7 occurrences)
on page 166 (5 occurrences)
on page 220 (5 occurrences)
Please enter a search word or '!' to quit: swarthmore
The word swarthmore does not appear in the file.
Please enter a search word or '!' to quit: !
Goodbye!
For this lab, your program is required to run without memory errors or leaks. You should use valgrind
as you proceed in your testing to track memory errors. When you have a complete first draft of your implementation:
valgrind ./tests
to make sure that the test program does not cause memory errors.Once memory errors are cleared, run valgrind --leak-check=full ./tests
to identify and correct memory leaks.
valgrind
may take several minutes to run on the unit tests for this lab.You are required to observe some good coding practices:
You should pick meaningful variable names.
// Good
int* pixels = new int[size];
// Bad
int* p = new int[size];
You should use correct and consistent indentation. Lines of code within a block (that is, surrounded by {
and }
) should be indented four spaces further than the lines surrounding them.
// Good
if (condition) {
cout << "Test" << endl;
}
// Bad
if (condition) {
cout << "Test" << endl;
}
You should use a block whenever possible, even if it’s not necessary. This helps you avoid subtle or messy bugs in the future.
// Good
if (condition) {
cout << "Something" << endl;
}
// Bad
if (condition)
cout << "Something" << endl;
Any new methods or fields in your header files should have comments explaining their purpose and behavior. You are permitted to omit documentation for methods that are inherited from other classes; that is, if your class has a foo
method because its superclass has a foo
method, you don’t need to document that method.
// Good
public:
/**
* Saves the image represented by this object to a file.
* @param filename The name of the file to save.
* @return The number of pixels in the saved image.
* @throws runtime_error If the image could not be saved due to an I/O error.
*/
int save(std::string filename);
// Bad
public:
int save(std::string filename);
Your method/field documentation does not have to be in the format above, but you must describe the method’s behavior, its parameters, its return value, and any exceptions that it may throw. (If you’re indifferent, the above syntax is a good one to know; it’s a de facto standard used by Javadoc, Doxygen, and other tools that automatically process source code comments into other formats like searchable webpages.)
When you are finished, you should have
LinearDictionary
HashTable
KeywordSearcher
main
program that ensures the proper number of command-line arguments (you are not required to handle bad filenames)