Anthony Legendre
Jason Peak
Michael Taboada

Submission Contents:
PrefixMatcher.java
ArrayStorage.java
Trie.java
dictionary.txt


Essentially, this program takes a prefix input and returns the results using an Array-based storage class and a 
Trie-based storage class. After receiving the input, the program runs these two implementations in sequence so that 
we may compare their speed and space efficiency. 

ArrayStorage.java utilizes an array of strings, which can expand to fit all the strings needed by any given list of 
words. The structure uses binary search in an alphabetically sorted text file to find the range of words that match the
prefix input. This range of words is added to a linked list and the list is displayed as output.

Trie.java is a tree of node objects in which each node contains an ArrayList containing references to all the children 
of the node in addition to a single character key and an indication of the node's status as a leaf. (Whether or not it 
is a leaf.) At the root of the Trie, the structure searches for matches by starting with the first character in the
prefix. If a match is found in the ArrayList containing the node's childeren, the structure uses binary search in the 
ArrayLists of children for the next characters in the search query until we fail. If the structure succeeds in matching 
all of the characters of input, the last node object encountered in the search is used as the root of the subtree of 
word matches. Then, the structure recursively traverses the subtree (subTrie) and reverse the results to produce the
word match.

Results: While the array-based storage takes up slightly less storage space than the trie; the Trie is significantly 
faster than the array in returning the search for a match.



Instructions:
To compile this program, type 

	javac *.java 

With that done, run the program by typing java prefixMatcher <dictionary>, where the single 
argument is the name of a dictionary file consiting of n words, one word per line. We have 
included the file Dictionary.txt for this purpose. This dictionary file contains ~250k words 
randomized from the linux file /usr/share/dict/words, and it may take up to a minute to load completely.

The simplest command line, then, is 
	
	java PrefixMatcher dictionary.txt