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”);
}
}
Academic Honesty!
It is not our intention to break the school's academic policy. Projects posted are only used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly fill out the form. Please provide a valid email address and we'll get back to you in less than 24 hours. We will be sending an invoice through PayPal upon confirmation. We are a non profit organization however we need an amount to keep this organization running, and to be able to complete our research and development.