Simple File Compressor Phase II and III

Introduction

In phase I, you have implemented a simple file compressor using List ADT. In these last two phases we wish to improve the performance of this file compressor, and evaluate and compare the performance to measure any possible improvements.

Phase II of the project

Try to improve the performance of the dictionary by using a Binary Search Tree (BST), instead of List. The key of the BST node should be the entry string, and the data of the BST node should be the index (see diagram below). T herefore, you are required to:

• Implement a modified version of the BST, where the key is the entry string (String), and the data is the index (Integer). You will need to modify the methods of the BST to compare strings instead of integers (you need to use the method compareTo when comparing strings).
• Use the modified BST [Integer] instead of the LinkedList[String] in the Dictionary class
• Update the setters/getters/utility methods in the Dictionary class to use the BST. 4. If needed, update the methods in the Compressor class.

An example of how the dictionary should look like See image.

The skeleton of the classes for this phase is as follow:

class Dictionary{
private BST strings;
private int lastIndex;
// setters/getters/utility methods
}

class Compressor {
private Dictionary dict;
// Initializes the dictionary
private void initDictionary() {...}
// Compresses the file fileName
public void compress(String fileName) {...}
// setters/getters/utility methods
}

class TestCompressor2 {
public static void main(String[] args) {
Compressor cmp = new Compressor();
cmp.initDictionary();
long time = System.currentTimeMillis();
cmp.compress(args[0]);
time = System.currentTimeMillis() - time;
System.out.println(time + “ms”);
}
}

Phase III of the project

Having completed previous phases, you are required to analyze the performance of Phase I and Phase II, both mathematically and computationally, and compare the performance improvements between the two phases, if any. Therefore, you are required to:

• Analyze the performance (using Big-­Oh notation) by comparing the List implementation with the Binary Search Tree implementation. Explain why and how one of them is better than the other in this use case specifically.
• Run Phase I and Phase II with the provided test files. You should run 5 tests, and for each test record the times it takes for compressing in milliseconds. List all the runs results in a table. You should also document the average time.
• Compare the theoretical analysis in part 1, with the practical analysis in part 2.
  • If there are any contradictions between theoretical and practical analysis, then state what you think might be the reason (e.g. other external factors that affects the performance, or unsuitability of data structures for input data…).
  • If the results are consistent, and change from List to BST made performance gain, then state whether the gain is minor or major. If minor, then what are the causes in your opinion?