CS231

A Note on Process for 2 Week Project:

This project will be completed in 2 weeks. However to ensure that you are making progress on it during the first week, there is a required checkpoint submission on November 5th as described on the first lab page. Submit your code including the BSTMap.java and the BSTMapTester.java file to the assignment titled "Project 6 CHECKPOINT: BSTMap."

Late submissions: You can use your late days for this checkpoint (if you think it's worthwhile). If you submit this more than 3 days late, you won't get credit for the checkpoint. You can still get credit for the BSTMap part of the main project rubric under the usual system.

Word Frequency

The main purpose of this project is to provide you the opportunity to use your different implementations of MapSet to determine the frequencies of all the words in a given text document. The ability to identify word frequencies in a large corpus has been the basis for a number of different research projects in the digital social sciences. In particular, looking at word usage over time in books and articles has revealed how culture and language change.

In particular, we will analyze the top words in colelction of Reddit comments from 2015, compared to the complete works of William Shakespeare. Download the data files here. The text files are large enough that using a list or an otherwise inefficient implementation will take a prohibitively long time to do the analysis.

Note: please do not hand in the data files with your code. If everyone hands them in with their code, it takes up a lot of unnecessary space on the server.

Tasks

WordCounter Class

The WordCounter is the class that creates and manages a MapSet of word-count pairs KeyValuePair<String, Integer>. You will not be implementing it yourself as the data structures themselves require significant implementation effort for this project. Instead, please download the WordCounter class from this link. However, to use this class in your analysis, please familiarize yourself with the methods it implements. Also note that you will need to change the name of the text file it reads in. At a high level, the WordCounter class has methods for doing two things.

First, the WordCounter needs to be able to Build a MapSet from a text document. The method reads in the text and separates it into words. For each word, it checks to see if the word is already a key in the MapSet. If it isn't, then it adds the Key-Value pair to the MapSet with the word as the key and 1 as the value. If the word is an existing key, then it increments the value associated with that word.

Second, the WordCounter needs to be able to write out a file containing the key-value pairs of the MapSet. The file has the total number of words on the first line, and each word and its count on the subsequent lines (one key-value pair per line). We will refer to a file formatted like this as a word count file.

The class needs a field to hold the MapSet with types <String, Integer>. It also needs a field to hold the total word count.

public WordCounter( String data_structure ) - constructor, where data_structure is either "bst" or "hashmap". It creates the appropriate data structure and store it in the map field.
public ArrayList<String> readWords( String filename ) - given the filename of a text file, read the text file and return an ArrayList list of all the words in the file.
public double buildMap( ArrayList<String> words ) - given an ArrayList of words, put the words into the map data structure. Return the time taken in ms. Record the time using System.currentTimeMillis().
public void clearMap() - clear the map data structure.
public int totalWordCount() - return the total word count from the last time readWords was called.
public int uniqueWordCount() - return the unique word count, which should be the size of the map data structure.
public int getCount( String word ) - return the number of times the word occurred in the list of words. Query the data structure to get the information. Return 0 if the word does not exist in the data structure.
public double getFrequency( String word ) - return the frequency of the word in the list of words. Query the data structure to get the word count and then divide by the total number of words to get the frequency. Return 0 if the word does not exist in the data structure.
public boolean writeWordCount( String filename ) - write a word count file given the current set of words in the data structure. The first line of the file should contain the total number of words. Each subsequent line contains a word and its frequency.

Exploration

The WordCounter class does the majority of the analysis work for you, but you may need to write some additional code to conduct the exploration. You may choose to do this in the main section of the WordCounter class but it's your choice how to implement this. Make sure you tell us how to replicate your results in the report!

Required analysis 1: Make a table of the top 10 words for the reddit comments vs Shakespeare. Do the results match your expectations? Why or why not?
Required analysis 2: Analyze the total time it takes for your different data structures in the buildMap method of your WordCounter class in both datasets. You might want to present this as a table with the results averaged over several runs.
Required analysis 3: Analyze the maxDepth() of your data structures after calling the buildMap method of your WordCounter class in both datasets. Does this help to explain your results from analysis 2? Why or why not?

Extensions

The following are some suggested extensions. You should feel free to pursue your own custom extensions to your project that you find interesting. Please clearly identify your extensions in your report. In your code, make sure the baseline simulations run properly. Making a separate sub-folder for major extensions is recommended.

Extension Ideas Particular to BSTs

Write out your tree to a word count file in an order that will ensure it is a balanced tree when you read it in. Demonstrate that it works.
Explore how badly unbalanced your BSTMap gets without doing self-balancing. One thing you'd first have to do is decide on a metric for what it means to be unbalanced. One reasonable thing to do would be to calculate the Balance Factors of every node in the tree, and caculate the number of nodes that have a balance factor greater than 1 or less then -1.
Implement a self-balancing tree data structure (such as an AVL Tree or an Red-Black Tree) and demonstrate that it works properly.

Extension Ideas Particular to HashMaps

Implement your own hash function. How does its performance compare to the built-in string hash function?
Try implementing more than one collision handling method. For example, (1) use whichever (chaining or probing) you haven't implemented yet, or (2) use a BSTMap instead of a linked list at each table entry for chaining. Compare the performance of the methods.
Try implementing different probing methods. For example, (1) Linear, Quadratic and Double Hashing. Compare the performance of the methods.

Extension Ideas Relating to the Project Application

Use an ArrayList or your own LinkedList instead of the BST/HashMap to implement the map and compare processing times.
Use additional files to test the (time and/or space) efficiency of your implementations. You want to cover a much bigger range of values (in a logarithmic sense) so you can get an accurate curve. There are several datasets of wikipedia pages available online - this will work well.

Congrats, you're done with everything except for your project report where you will communicate your findings from all that code! The project report is an important part of the work in this project, so don't forget to do it!