Simple File Compressor Phase I

Phase I

Introduction

The goal in this project is to write a file compression program. The program takes as input the name of a file, compresses it and writes the result as a new file.

How does the compression algorithm work?

The compression algorithm works as follows:

• The dictionary contains initially all characters (strings of length 1).
• Initialize the pointer to the first character in the file.
• Repeat until the end of the file
  • Advance the pointer in the file as long as there is a match in the dictionary.
  • Write the corresponding dictionary index to the output file.
  • Add the string plus the next character to the dictionary.
  • Remove the string from the input and advance the pointer.

Phase I of the project

In Phase I, you are required to develop a simple compression program:

• The compression algorithm takes first as input the name of the file to be compressed.
• The program initializes the dictionary (assume that the file contains only lower case English letters and the space. The dictionary is initialized with the space as the first entry, followed by the letters in alphabetical order). The dictionary is implemented as a linked list.
• The program then reads the file and writes the result in a new file with the same name as the input file plus the ".cmp.txt" extension. The output values are separated by a return to line.

The skeleton of the classes for this project is as follows:

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

class TestCompressor {
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”);
}
}