Difference between revisions of "CISC220 F2021 Lab9"

From class_wiki
Jump to: navigation, search
(→‎1. File compression with Huffman coding)
(→‎1. File compression with Huffman coding)
 
(18 intermediate revisions by the same user not shown)
Line 9: Line 9:
  
 
The main work of ''Huffman'' happens in the following functions:
 
The main work of ''Huffman'' happens in the following functions:
−
* ''compress(in_filename, out_filename, do_binary)'' : Reads in_filename character by character and counts occurrences (aka computes a frequency) for each, storing the result by ASCII index in the char_counter vector.
+
* ''compress(in_filename, out_filename, do_binary)''  
 +
** Reads in_filename character by character and counts occurrences (aka computes frequency) for each, storing the result by ASCII index in the ''char_counter'' vector
 +
** Applies the Huffman trie-building algorithm presented in class 11/9 in ''build_optimal_trie()''. This function is UNFINISHED, as it calls ''merge_two_least_frequent_subtries()'' which you must write
 +
** Writes code table (the decompression_map) to out_filename
 +
** Re-reads in_filename character by character and writes encoded versions to out_filename (in ASCII or binary depending on do_binary)
 
* ''decompress(in_filename, out_filename, do_binary)''  
 
* ''decompress(in_filename, out_filename, do_binary)''  
 +
** Reads the code table from in_filename
 +
** Reads in_filename character by character and writes decoded versions to out_filename
  
−
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.
+
The "forest of tries" discussed in lecture on 11/9 is implemented with an STL 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
 
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.
 
is where you will be writing code.
  
−
The Huffman memberfunctions to finish in main.cpp:
+
The Huffman member functions to finish in main.cpp:
  
−
* '''[1 point]''' ''merge_two_least_frequent_subtries()''  
+
* '''[2 points]''' ''merge_two_least_frequent_subtries()'' : This function should do the following (there are further hints in the comments):
−
* '''[1 point]''' ''compute_all_codes_from_trie(TrieNode *T)''  
+
** (1) remove trie in PQ with SMALLEST frequency, assign to first
−
* '''[1 point]''' ''calculate_huffman_file_size()''
+
** (2) remove trie in PQ with NEXT SMALLEST frequency, assign to second
 +
** (3) make new trie node (new_root) and plug first and second tries in as children, set new_root's frequency to first->frequency + second->frequency, and insert in new_root in PQ
 +
* '''[1 point]''' ''compute_all_codes_from_trie(TrieNode *T)'' :  The function should recursively traverse the binary tree (trie) rooted at T to determine the huffcode string at every leaf.  If T is a leaf, make sure to execute the compression_map and decompression_map assignments
 +
* '''[1 point]''' ''calculate_huffman_file_size()'' : Return how many bits Huffman-coded version of the file takes.  This is the sum of the frequency * huffcode length over every leaf
  
−
===2. Testing===
+
===2. Testing [1 point] ===
  
−
* '''[1 point]''' ''short_doi.txt'' requires x bytes in raw form.  How many bytes does it take when compressed using your completed Huffman class?
+
* [http://nameless.cis.udel.edu/class_data/220_f2014/data/cleaned_doi.txt DOI] (about 1K total words), [http://nameless.cis.udel.edu/class_data/220_f2014/data/cleaned_bts.txt BTS] (~14K words), and [http://nameless.cis.udel.edu/class_data/220_f2014/data/cleaned_greatexp.txt GE] (~185K words) require 8588 bits, 83964 bits, and 1013761 bytes, respectively according to the Unix ''ls'' command
 +
* How many *bytes* are required for each of these files after compression when you set the ''-debug'' flag in (a) "custom" form (shortest fixed-length code) and (b) using the variable-length Huffman code that your completed class generates?
  
 
===3. Submission===
 
===3. Submission===

Latest revision as of 16:31, 10 November 2021

Lab #9

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 frequency in the file being compressed.

The main work of Huffman happens in the following functions:

  • compress(in_filename, out_filename, do_binary)
    • Reads in_filename character by character and counts occurrences (aka computes frequency) for each, storing the result by ASCII index in the char_counter vector
    • Applies the Huffman trie-building algorithm presented in class 11/9 in build_optimal_trie(). This function is UNFINISHED, as it calls merge_two_least_frequent_subtries() which you must write
    • Writes code table (the decompression_map) to out_filename
    • Re-reads in_filename character by character and writes encoded versions to out_filename (in ASCII or binary depending on do_binary)
  • decompress(in_filename, out_filename, do_binary)
    • Reads the code table from in_filename
    • Reads in_filename character by character and writes decoded versions to out_filename

The "forest of tries" discussed in lecture on 11/9 is implemented with an STL 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 member functions to finish in main.cpp:

  • [2 points] merge_two_least_frequent_subtries() : This function should do the following (there are further hints in the comments):
    • (1) remove trie in PQ with SMALLEST frequency, assign to first
    • (2) remove trie in PQ with NEXT SMALLEST frequency, assign to second
    • (3) make new trie node (new_root) and plug first and second tries in as children, set new_root's frequency to first->frequency + second->frequency, and insert in new_root in PQ
  • [1 point] compute_all_codes_from_trie(TrieNode *T) : The function should recursively traverse the binary tree (trie) rooted at T to determine the huffcode string at every leaf. If T is a leaf, make sure to execute the compression_map and decompression_map assignments
  • [1 point] calculate_huffman_file_size() : Return how many bits Huffman-coded version of the file takes. This is the sum of the frequency * huffcode length over every leaf

2. Testing [1 point]

  • DOI (about 1K total words), BTS (~14K words), and GE (~185K words) require 8588 bits, 83964 bits, and 1013761 bytes, respectively according to the Unix ls command
  • How many *bytes* are required for each of these files after compression when you set the -debug flag in (a) "custom" form (shortest fixed-length code) and (b) using the variable-length Huffman code that your completed class generates?

3. Submission

  • 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
Retrieved from "http://nameless.cis.udel.edu/class_wiki/index.php?title=CISC220_F2021_Lab9&oldid=2051"