C++ and pascal expert programmer required for a task
Budget: $30 – $250 USD
This programming project focuses on building a lossless data compression algorithm using Dynamic Huffman Codes. In 1952, David Huffman developed a way to find a set of optimal prefix codes for a given set of input symbols. Essentially, Huffman Codes are variable-length bit strings which uniquely represent a set of input symbols. The main benefit offered by this scheme is that the more common the input symbol, the fewer the number of bits that are required to represent it. Clearly, this is advantageous when compressing data. However, this approach to data compression requires full knowledge of the source distribution of symbols to build the Huffman Codes. It cannot adapt to changing conditions in the input data such as changing symbol distributions or new symbols in the input stream.
Dynamic Huffman Coding extends the original algorithm to allow Huffman Codes to be built “on-the-fly” without any initial knowledge of the source distribution of symbols. Therefore, changing distributions and new symbols can easily be incorporated into the coding scheme. In fact, there are two popular related implementations of this algorithm, namely Faller-Gallagher-Knuth (FGW) and Vitter. The main focus of this programming project will be on the Vitter’s implementation of the algorithm. A paper produced by Jeffrey Vitter to help explain his implementation of the algorithm in PASCAL has been supplied to you to help you understand how to implement this algorithm yourself. As part of this project you will be expected to convert this PASCAL implementation of the algorithm to C++ by making design/implementation decisions about data structure, naming conventions, OO structure and run-time issues (such as exception handling and logging).
Dynamic Huffman Coding extends the original algorithm to allow Huffman Codes to be built “on-the-fly” without any initial knowledge of the source distribution of symbols. Therefore, changing distributions and new symbols can easily be incorporated into the coding scheme. In fact, there are two popular related implementations of this algorithm, namely Faller-Gallagher-Knuth (FGW) and Vitter. The main focus of this programming project will be on the Vitter’s implementation of the algorithm. A paper produced by Jeffrey Vitter to help explain his implementation of the algorithm in PASCAL has been supplied to you to help you understand how to implement this algorithm yourself. As part of this project you will be expected to convert this PASCAL implementation of the algorithm to C++ by making design/implementation decisions about data structure, naming conventions, OO structure and run-time issues (such as exception handling and logging).