Overview

In the age of big data, there is a constant struggle with regard to storage. For example, a single Whole Genome Sequencing experiment can generate over 100 GB of raw data. For years, computer scientists have attempted to reduce the storage size of files without losing any information. In this assignment, we will be implementing our own file compression tool using the Huffman algorithm.

Task: File Compression and Decompression

In this project, "all" you have to do is implement two programs:

compress

and

decompress
. The usage should be as follows:

File Compression

The
compress
program will take as input an arbitrary file (original_file) and will use Huffman Compression to create a compressed version of the file (compressed_file):

• 
  

  Construct a Huffman code for the contents of
  original_file
  

  
  


• 
  

  Use the constructed Huffman code to encode
  original_file
  

  
  


• 
  

  Write the results (with a header to allow for decompression) to
  compressed_file
  

  
  

File Decompression

The
decompress
program will then take as input a compressed file created by your
compress
program (compressed_file) and will decompress the file (decompressed_file):

• 
  

  Construct a Huffman code by reading the header of
  compressed_file
  

  
  


• 
  

  Use the constructed Huffman code to decode
  compressed_file
  

  
  


• 
  

  Write the results to
  decompressed_file
  

  
  

Note that
decompressed_file
must be
completely identical
to
original_file! In other words, calling
diff
should return no differences:

Reference Solution

You have been provided two programs (refcompress
and
refdecompress), which are a reference solution implementation of this Project. You can use them to help guide you. Note that the reference binaries were compiled to run on Ed, so if you attempt to run them on a different architecture, they will most likely not work.

Note:
Your
compress
is
not
expected to work with
refdecompress, and your
decompress
is
not
expected to work with
refcompress. The provided reference executable files are a matched pair.

Compiling and Running Your Code

We have provided a
Makefile, but
you are free to modify
anything
in the starter code
that you'd like (including the
Makefile
and any of the
.cpp
or
.hpp
files) however you wish (including adding
public
methods). You may also create your own source files and header files. Our only requirements are the following:

• 
  

  You should not import or use any libraries or methods that directly perform the compression or decompression for you.

  
  


• 
  

  You should not change any of the g++ compile flags (CXXFLAGS).

  
  


• 
  

  Your code needs to be compilable and produce two executables,
  compress
  and
  decompress, using the
  make
  command

  
  


• 
  

  Your
  compress
  and
  decompress
  programs can be run as described above after
  make.