Advanced C Programming

Spring 2021 ECE 264 :: Purdue University

⚠ This is a PAST SEMESTER (Spring 2021).
Due 4/26

Huffman 6: encode tree to file

Overview

This is part 6 in an 8-part series in which you are implementing the Huffman Coding algorithm to compress files.

  1. HW14: Implement priority queue for future use
  2. HW15: Calculate character frequencies from a file
  3. HW16: Create a priority queue of trees from the character frequencies in a file.
  4. HW17: Build a single Huffman tree.
  5. HW18: Implement functions to write arbitrary bits to a file, for future use.
  6. HW19: Write the Huffman Tree to the disk. ◀◀◀ this homework
  7. HW20: Write the encoded file contents to the disk.
  8. huffman_8: Create a command-line interface for compressing files.

In this homework you will use your code from HW18 to write the Huffman coding table to a file.

The coding table consists of a mapping from each character found in the input, to a sequence of bits. It isn't actually stored in the form of a “table” (or array). It is part of the Huffman tree itself. You will traverse the tree to find each character and the bits used to encode it.

Input

The input to your code will be a Huffman tree like this:

Output

Your code will write the bits for the coding table to a file using the functions you wrote in HW18, according to the algorithm in article .

Here's how the Huffman tree above would be represented. You will write this only. Do not write anything before or after this.

101100110('f')101101000('h')101101100('l')0(×2)100100000('‿')0(×5)0(×10)101110101('u')101111001('y')101100001('a')0(×3)0(×6)101101101('m')101101110('n')101110011('s')0(×4)0(×8)0(×14)0(×24)

In case of any discrepency between this example and the article , the article shall take priority.

Algorithm

You must read the article completely and carefully. Do not ask for help if you have not first read that.

See the article and Huffman walkthrough for a complete description of how the tree is converted to bits.

Here's a synopsis. If this doesn't make sense, go back to the article . You do a post-order traversal.

  1. Traverse the left subtree of the root (i.e., encode it to the file).
  2. Traverse the right subtree of the root (i.e., encode it to the file).
  3. Visit the root.

Every time you “visit” a root (including the root of a subtree):

  • If it is a leaf (i.e., character), you write one bit: 1. Then, you write the entier character (8 bits). Example: If the character is 'A', you will write 101000001. The 1 is to signify that it is a leaf. The 01000001 is to specify the character itself.
  • If it is a non-leaf (i.e., cluster)), you write one bit: 0.

Getting Started

There is no starter code. However, we recommend creating a new directory for each step of the Huffman series.

  1. You should have already read the article and Huffman walkthrough . If you have not done so already, please do so before you proceed.
  2. Create a directory for HW19 and change into it.
    you@ecegrid-thin1 ~ $ mkdir hw19
    you@ecegrid-thin1 ~ $ cd hw19
  3. Copy all of your files from HW17 and the bit_writer.[ch] files from your HW18 into your HW19 directory.
    you@ecegrid-thin1 ~/hw19 $ cp ../hw17/{*.[ch],Makefile} -t ./
    you@ecegrid-thin1 ~/hw19 $ cp ../hw18/bit_writer.[ch] -t ./
  4. Update your Makefile with the new ASG_NICKNAME.
    you@ecegrid-thin1 ~/hw19 $ vim Makefile
    You should now have this: ASG_NICKNAME=HW19 You also need to make sure all of the files listed in the Requirements table will be included when you run make submit.
  5. Edit your huffman.h to add the declarations for write_coding_table(…). No other edits are necessary.
    you@ecegrid-thin1 ~/hw19 $ vim huffman.h

Requirements

  1. Your submission must contain each of the following files, as specified:
    file contents
    huffman.c functions
    write coding table(TreeNode✶ root, BitWriter✶ a writer)
    → return type: void
    Write the coding table represented in the Huffman tree to the file referenced by a_writer.
    • Follow the algorithm given in the article and Huffman walkthrough .
    • Use the functions you created in HW18.
    • Don't worry about what comes before or after this in the file. Just write the coding table.
    All functions that were present in HW17
    huffman.h types All types that were present in HW17.
    declarations All declarations that were present in HW17, plus the one added for HW19 (specified above).
    test_huffman.c functions
    main(int argc, char✶ argv[])
    → return type: int
    • 100% code coverage is required for huffman.c.
      • Direct testing of frequencies.c and priority_queue.c is optional for HW19.
    • Use your miniunit.h.
    priority_queue.h ⋯
    same as before
    priority_queue.c ⋯
    same as before
    bit_writer.h ⋯
    same as before
    bit_writer.c ⋯
    same as before
    frequencies.h ⋯
    same as before
    frequencies.c ⋯
    same as before
    miniunit.h ⋯
    as usual
    clog.h ⋯
    as usual
    Makefile ⋯
    as usual
  2. Submissions must meet the code quality standards and other course policies on homework.

Submit

To submit HW19 from within your hw19 directory, type 

make submit

That should result in the following command: 264submit HW19 huffman.c huffman.h frequencies.c frequencies.h priority_queue.c priority_queue.h test_huffman.c bit_writer.c bit_writer.h miniunit.h clog.h Makefile

Pre-tester ●

The pre-tester for HW19 has been released and is ready to use.

Q&A

  1. How will these bits be used? How can this possibly be used to deconstruct a Huffman tree?

    Read the article ! We can see from the web logs that many of you are not doing that.

Updates

There are no updates to HW19 so far.