Design: This project takes in files with text as an input and keeps a list of the top ten most frequent words across all these documents. The program then prints these top ten words in ascending order (based on frequency) to standard output. If multiple words are tied for the tenth position, the word whose last occurrance happens before the last occurrance of any of the other words is awarded the spot on the list. Additionally, this program assumes that the total number of characters in the files that are passed in do not exceed the length of a String object (2^32 characters).
In order to implement this project, I created three seperate classes: Word, Indexer, and Parser. The Word class holds a String representation of the word along with an integer value representing the frequency of the Word. The Indexer class uses two data structures (a HashMap and a PriorityQueue) in order to store all the words and a list of the top ten words, respectively. The Parser class reads in the text from all the files and adds words to the Indexer, ultimately sorting the top ten words based on frequency and printing the words along with their frequency to standard output.
The Indexer uses a HashMap in order to efficiently access and add words to the index (since lookup and insertion in a HashMap both run in constant time). The PriorityQueue is used to dynamically store a list of the top ten words as the program is running. This structure was chosen simply because it functions like a min heap--the first element in the PriorityQueue has the lowest value. This means that in order to check to see if a word should be added to the list, all that would need to be checked is the first element. Additionally, the size of this structure is capped at ten. This allows all operations dealing with the PriorityQueue to run in constant time (since log(10) is a constant).
The Parser uses a Scanner which reads through all the files that are passed in as arguments. It copies each line of text from the files into a StringBuilder object. StringBuilder objects were used throughout this project due to the inefficiency of String concatenation. It then parses through the String of text, adding each word (a sequence of alphanumeric characters) to the index. This is the most inefficient part of the program--the parser runs through the String twice in order to copy and parse it. Overall, this program has a linear time and space complexity.
Testing: I tested this project in multiple ways. The main way I tested consisted of creating sample text files which had text with known word counts (such as BettyBought.txt). This allowed me to ensure that all words were being counted. Additionally, I used these sample test files (GeneralTest.txt) to ensure that any non-alphanumeric character acted as a delimiter and that the program was case insensitive. One of the test files (FewerThanTenWords.txt) checked to ensure that the program was fine when a file contained fewer than ten distinct words. Lastly, I downloaded some lengthy text files (ScarletLetter.txt and MuchAdo.txt) to ensure that the program could handle large inputs in a short amount of time.
Additionally, I wrote a couple of unit tests to ensure that some of the key methods functioned properly. The two tests I wrote tested the addWord and consume methods. For the addWordGeneralTest, I inserted the word "myself" into an index 50 times and then inserted the word "yourself" once. I then checked the PriorityQueue in the index to ensure that the first element was "yourself" with a frequency of 1 and that the second element was "myself" with a frequency of 50. The consumeGeneralTest passed in a string with lots of non-alphanumeric characters in it to make sure that the consume method ignored those characters.
In order to run the first tests, simply input the filename as an argument in the main method. In order to run the unit tests, simply run the unit tests.