Lab 8: Efficient Keyword Search

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.

Overview

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:

1. LinearDictionary
2. 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.

Starting Code

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.

Part I. Implementing 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.

Removing from a 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);

Part II. Implementing HashTable

Hash Table Structure

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:

• We recommend that you use a dynamically allocated array of statically-allocated LinearDictionary objects to represent the buckets of your HashTable.
• One of the constructors allows the user to specify a maximum load factor; the other should use a sensible default value (e.g. 0.75).
• All operations on your HashTable (other than getKeys and getItems) must run in \(O(1)\) average time.
• The 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!)
• Note that hashing functions have been provided in 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.

Part III. Keyword Searcher

$$@@$$PAGE: 1
cows say moo
$$@@$$PAGE: 2
dogs say bark
$$@@$$PAGE: 3
say do trees say bark

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:

• You have the opportunity to design the underlying data structure within this class. At the topmost level you must use a HashTable keyed on the unique words within the document, but you may choose the value associated with these keys. Here are two suggestions:
  1. Use a dynamically allocated HashTable keyed on page numbers and storing the number of occurrences on that page.
  2. Use an instance of a new class that you create. This class could provide a nice layer of abstraction for more clearly accessing the information we care about for this application.
• Whatever data structure you choose, your implementation must find all pages where a word occurs in a document in \(O(1)\) average time.
• Again, we encourage you to write any private helper methods that you need to assist with completing the required public methods for this class: loadWords and search.
• To determine the top ten most relevant pages, you will use the 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.

Part IV. Main Program

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!

Memory

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:

• Commit and push what you have (in case something goes wrong).
• Run 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.

• Note: valgrind may take several minutes to run on the unit tests for this lab.

Coding Style Requirements

You are required to observe some good coding practices:

Source: OpenClipArt.org

• 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.)

Summary of Requirements

When you are finished, you should have

• A completed implementation of LinearDictionary
• A completed implementation of HashTable
• A completed implementation of KeywordSearcher
• A completed main program that ensures the proper number of command-line arguments (you are not required to handle bad filenames)
• No memory errors
• No memory leaks
• Code which conforms to the style requirements
  • Remember to document your newly-declared fields and methods!