CISC220 F2021 Lab9
1. File compression with Huffman coding
As discussed in class on Nov. 9, tries and Huffman coding can be used to compress files/messages by analyzing character frequencies and choosing codes accordingly.
Most of a Huffman class is provided in starter code here. It implements a TrieNode class that stores parent and child links as well as the character being encoded and its freqency. The "forest of tries" discussed in lecture on 11/9 is implemented with a priority queue of TrieNode pointers (each representing the root of a subtrie), ordered on the combined frequency of each subtrie.
Several major functions are unfinished. In order to separate them from the finished ones, they are located in main.cpp -- this is where you will be writing code.
The Huffman memberfunctions to finish in main.cpp:
- [1 point] merge_two_least_frequent_subtries()
- [1 point] compute_all_codes_from_trie(TrieNode *T)
- [1 point] calculate_huffman_file_size()
- [1 point] short_doi.txt requires x bytes in raw form. How many bytes does it take when compressed using your completed Huffman class?
- Make a PDF file <Your Name>_Lab9_README.pdf with your answers to the testing questions above
- Rename your code directory <Your Last Name>_Lab9 and create a single tar/zip/rar file out of it named <Your Last Name>_Lab9.tar (or .zip or .rar, etc.).
- Submit it in Canvas by midnight at the end of Tuesday, November 16