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 10/30. Your final submission for this project on 11/6 should include both data structures from both labs (BSTMap and HashMap) and a full report including both exploration sections--the one for week 1, and the comparative analysis of the 2 different data structures we have implemented on the Reddit comments.

Your checkpoint submission must include the following for you to receive full credit for this project:

• Your fully implemented Binary Search Tree lab (your BSTMap class)
• A complete results section for the week 1 results section of the exploration (i.e. use your BSTMap class to analyze the Reddit comments)

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 topics in Reddit comments over a period of 8 years. 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 Reddit comment files with your code. If everyone hands them in with their code, it takes up a lot of unnecessary space on the server.

Tasks

Testing

As always, as you are coding up this project create testing files for each class you create exercising the public methods implemented in this class.

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.

Specifically, the WordCounter class implements the following methods:
• 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.

1. Week 1 results: Using your WordCounter, analyze the reddit comment files. In order to run your WordCounter on these files, you'll probably need to increase the amount of memory your machine allows Java to utilize: to do so, use the -Xmx4g command. For example, you might write something like

   java -Xmx4g WordCounter

   . You might want to ignore common words, such as those found in this file, which I got from this data set on Kaggle. That list has some words that seem relevant though, up to you if you want to remove some words that you feel are relevant (regardless, make sure you document what words in particular you are ignoring). In particular, you should identify: In particular, you should identify:
   • How do the most frequent words change year by year? Does it match your expectations?[This is no longer a required analysis and is instead a small extension]
   • Pick a few words that matter to you. How do they change year by year? Does it match your expectations?
   Required result: submit a complete results section resonding to this at the project checkpoint on 10/30 (it will also be included in the final report on 11/06).
2. Week 2 results: Analyze the total time it takes for your different data structures in the buildMap method of your WordCounter class year by year. I would average it over several runs per structure for each year to get more accurate results.
3. Analyze the maxDepth() of your data structures after calling the buildMap method of your WordCounter class year by year.
Required result: Submit a complete results section responding to both this and the week 1 results in your project report on 11/06.

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

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

1. Implement your own hash function. How does its performance compare to the built-in string hash function?
2. 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.
3. 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

1. Use an ArrayList or your own LinkedList instead of the BST/HashMap to implement the map and compare processing times.
2. 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.
3. Examine the space efficiency of your implementations. One way to do this would be to refrain from using the -Xmx4096m flag. Count words of files of increasing sizes. See what is the size of the smallest size that crashes your program. Does a smaller file crash the Hashtable code or the BSTMap code? Why?
4. Analyze how the most frequent words change year by year. Does it match your expectations? Consider presenting your results as a graph or table. You may also want to remove punctuation from the parsing and explore things like stemming to get more meaningful results.

---

Report

Your intended audience for your report are your peers not in the class, but who have taken a CS course. Your report should explain the core CS concept used, present the results of your program, and discuss the meaning of the results: what did you discover and does it make sense?

Your project report should contain the following elements. Please include a header for each section.

• Abstract

  A brief summary of the project, in your own words. This should be no more than a few sentences. Give the reader context and identify the key purpose of the assignment. Each assignment will have both a core CS purpose--usually a new data structure--and an application such as a simulation or analysis.

  Writing an effective abstract is an important skill. Consider the following questions while writing it.

  • Does it describe the specific project application?
  • Does it describe the results of your simulation or analysis?
  • Is it concise?
  • Are all of the terms well-defined?
  • Does it read logically and in the proper order?
• Results

  Present your results. Include text output, images, tables, graphs, or qualitative descriptions, as appropriate. Include a discussion as to whether the results make sense and what they mean.

• Extensions

  Describe any extensions you undertook, including text output, graphs, tables, or images demonstrating those extensions. If you added any modules, functions, or other design components, note their structure and the algorithms you used.

• Reflections

  A semi-brief overview of the data structure implemented/used in this project. Why did we implement a HashMap in this project? How does it compare to the BSTMap of last week (we're looking for a summary of the results from the results/extensions sections here, basically).

  As a follow-up, if you use the entrySet method to write your wordCount files, on a non-self-balancing BSTMap you probably won't be able to read in a large file that was written by a BSTMap. Why is this?

• References/Acknowledgements

  A list of people you worked with, including TAs and instructors. Include in that list anyone whose code you may have seen, such as those of friends who have taken the course in a previous semester. If you found a website for help, such as StackOverflow, include a link to the post.

---