$1.$ File compression with Huffman coding

As discussed in class on Nov. $14,$tries$$and$$Huffman coding$$can be used to compress files$/$messages by analyzing character frequencies and choosing bitcodes accordingly.

A nearly$-$complete$$Huffman$$class is defined for you in$$huffman$.$hh$($code here$).$ It uses a$$TrieNode$$class that stores parent and child links as well as the character being encoded and its frequency in the file being compressed.

The main work of$$Huffman$$happens in the following functions:

compress$()$

Reads input file character by character and counts occurrences $($aka computes frequency$)$ for each, storing the results by ASCII index in the$$char$\_$frequency$$vectorApplies the Huffman trie$-$building algorithm presented in class $11/14$ in$$build$\_$optimal$\_$trie$().$ This function is TO BE WRITTEN BY YOUCreates code look$-$up tables $($string$$to$$char$$decompression$\_$map$$and$$char$$to$$string$$compression$\_$map$)$ from the optimal trie in$$compute$\_$all$\_$codes$\_$from$\_$trie$().$ This function is TO BE WRITTEN BY YOUWrites$$decompression$\_$map$$as a header to the output fileRe$-$reads input file character by character and, using$$compression$\_$map, writes encoded versions to the output file body $($in ASCII or binary depending on$$do$\_$binary$$flag$)$

decompress$()$

Reads the code look$-$up table from header of input file to$$decompression$\_$mapReads rest of input file bitstream, gets character for each variable$-$length code read using$$decompression$\_$map, and writes decoded versions to output file. The ASCII part of this function,$$ascii$\_$decompress$\_$body$()$is TO BE WRITTEN BY YOU

The "forest of tries" discussed in lecture is implemented in the$$Huffman$$class with an$$STL priority queue$$of$$TrieNode$$pointers $($each representing the root of a subtrie$),$ ordered on the combined frequency of each subtrie. This priority queue is called$$trie$\_$pq$.$

The compiled executable is run as follows:$$huff

If the input filename has the suffix$.$huf, it will be$$decompressed$$to a plain$-$text file with an identical name except the suffix is changed to$.$HUF.

If the input filename has any other suffix, it will be$$compressed$$to a file with the suffix$.$huf.

The default compressor creates a binary file as output and the default decompressor expects a binary file as input. Feel free to compare the sizes of compressed files to the originals. However, for grading, compressed output will be written in ASCII and compressed input will also be expected to be ASCII. This is indicated by the optional flag$-$ascii.

The output files will be echoed to the terminal for grading for both compression $($to test your$$build$\_$optimal$\_$trie$()+$compute$\_$all$\_$codes$\_$from$\_$trie$()$combination$)$ and decompression $($to test your$$ascii$\_$decompress$\_$body$()$in isolation$).$ In order to test$$build$\_$optimal$\_$trie$()$alone$,$ another optional flag$-$trie$$will print only a representation of the built trie and not echo the output file.

$2.$ Sample inputs$/$outputs

This tarfile$$contains the following files:

seashells.txt$(20$ total chars because there is a newline, $7$ different chars$)$

seashells.txt$.$huf

output$1,$output$2,$output$3($these are what is written to the terminal, not what is saved in a file$)$

output$1$results from running$./$huff $-$ascii seashells.txt

output$2$results from running$./$huff $-$ascii $-$trie seashells.txt

output$3$results from running$./$huff $-$ascii seashells.txt$.$huf

$3.$ Programming tasks

The$$Huffman$$member functions to finish are in$$main$.$cpp$--$ don't make any changes in$$huffman$.$hh:

$[1$ point$]$Huffman::ascii$\_$decompress$\_$body$()$: This function should read one "bit" $($a $\text{'}0\text{'}$ or $\text{'}1\text{'}$ char$)$ at a time from the input stream until a legal code is assembled, then write the corresponding decoded character to the output stream, and repeat until reaching the end of file

$[2$ points$]$Huffman::build$\_$optimal$\_$trie$()$: This function should create a forest of one$-$node tries $($aka$$trie$\_$pq$)$ representing the characters in the input file and their frequencies, then repeatedly combine the two smallest tries until only one is left according to the following instructions:

$1.$ Remove trie in$$trie$\_$pq$$with SMALLEST frequency, assign to$$first$,$ remove trie in PQ with NEXT SMALLEST frequency, assign to$$second$2.$ Create new$$TrieNode$$and make$$first$$and$$second$$its left and right children, respectively. Set new node's frequency to the sum of$$first$$and$$second$\text{'}$s frequencies, and then put the whole thing back into the priority queue

$[2$ points$]$Huffman::compute$\_$all$\_$codes$\_$from$\_$trie$()$: The function should recursively traverse the trie rooted at$$T$$to determine the$$huffcode$$string at every leaf and initialize$$compression$\_$map$$and$$decompression$\_$map$$with this information