Computer Science 2530
Spring 2019
Programming Assignment 8

Table of contents

1. Purpose of this assignment
2. Plagiarism
3. Background
4. Huffman's algorithm
5. The Assignment
6. Additional requirements
7. Tracing
8. A refinement plan
9. Issues to Be Aware of
10. Submitting your work
11. Late submissions
12. Asking questions

Purpose of This Assignment

---

This assignment has you use trees. It also does less hand-holding than previous assignments. It is the largest assignment that you are assigned, and gives you experience in implementing a multi-module program.

It is crucial to get started early. This program will take a lot of time to write. You will need to write approximately 24 functions. Make a plan for getting this assignment done early without trying to do too much in one day.

Use the methods that we have studied in this course. Do not cut corners. Do not revert to novice methods! They will not speed you up. They will slow you down.

Read the entire assignment before you start on it.

Plagiarism

---

When faced with a large assignment near the end of a term, many students turn to plagiarism, especially if they have waited too long to start on the assignment.

Do not fall into that trap and submit a plagiarized assignment. Doing so will cost you points. Keep in mind that you must get an overall score of 50% or better on the programming assignments in order to pass this course, and that a plagiarized assignment gets a negative score. Submitting plagiarized or partially plagiarized work can cause you to fail this course.

Background

---

Data compression is concerned with economical ways to encode information for storing files using limited disk space or for transfering files over a network. Data compression is critical for transmitting videos over the internet and storing high-definition videos.

Sophisticated data compression algorithms for text files take into account sequences of characters that occur often, so that they can encode those sequences in an efficient way. For example, if the word Rumpelstiltskin occurs often, then there will be a short code for that word.

A much simpler kind of data compression for text files works on individual characters, without paying attention to how characters are grouped. This assignment has to do with that simple form of data compression, using an algorithm called Huffman coding.

A file is a sequence of bits. Codes such as Ascii and Unicode use a fixed number of bits to encode each character. For example, in the 8-bit Ascii code, the letters 'a', 'b' and 'c' have the following encodings.

In the 16 bit Unicode standard, the codes for 'a', 'b' and 'c' are as follows.

Some characters are used more than others. In fact, you very likely don't use some characters at all (especially if you are using Unicode!). For an economical encoding, instead of using the same number of bits for every character, it would be better to use shorter codes for characters that occur more frequently, and to have no code at all for a character that is not used.

For example, suppose that a document contains only the letters a, b and c, and suppose that the letter b occurs far more often than either a or c. An alternative character encoding is as follows.

That code has the property that no character code is a prefix of any other character code. Using that kind of character code (called a prefix code) allows you to break apart a string of bits into the characters that it encodes without having any character boundaries stored. For example, string of bits "01001110" encodes "babca". To decode a string, you repeatedly remove a prefix that encodes a character. Since no code is a prefix of any other code, there is only one way to select the next character.

Huffman's Algorithm

---

There is an algorithm that is due to Huffman for finding efficient prefix codes. The input to the algorithm is a table of characters with their frequencies.

Trees and codes

A tree is used to define a prefix code. Each node of the tree is either a leaf or a nonleaf. Each leaf contains a character. Each nonleaf has two children, the left child and the right child. We think of the left child as the '0' child and the right child as the '1' child. An example is the following tree.

You find the code for a character by following the path from the root of the tree to that character, writing down the 0's and 1's that you see along the path. For example, in the tree above, the code for 'b' is 01 and the code for 'a' is 10. What is the code for 'c'? A different code is given by the following tree.

where 'b' has code 0, 'a' has code 10, 'd' has code 110 and 'c' has code 111.

A tree can be thought of as a composite character. A tree with leaves a and c stands for the combination of a and c. A character by itself is thought of as a tree that has just one leaf.

Huffman's algorithm

The algorithm to create the tree starts by making each character into a tree that is just a leaf holding that character. Each tree has a frequency, which is the number of occurrences of the character in the file. For example, if the frequency counts are

a 500
b 230
c 300
d 250
e 700

(Note. A frequency is associated with an entire tree, not with each node of a tree. Initially, each tree has just one node, but as the algorithm runs the trees will grow. You still have just one frequency per tree.)

Now the algorithm repeatedly performs the following steps, as long as there are still at least two trees left in the collection of trees.

1. Remove the two trees that have the lowest frequencies from the collection of trees. Suppose that they are trees S and T. Suppose that tree S has frequency F_S and tree T has frequency F_T.

2. Build a tree that looks as follows.

   

   Say that this tree has frequency F_S + F_T, the sum of the frequencies of S and T.

3. Add the new tree, with its new frequency, to the collection of trees.

The number of trees decreases each time because you remove two trees and put back just one tree. When there is only one tree left, the algorithm is done. That tree is the result.

A notation for trees

It is a little awkward to draw pictures of the trees, so a notation for describing trees is useful. A leaf is shown as the character at that leaf. A nonleaf is shown as the two subtrees, surrounded by parenthese and separated by a comma. For example, tree

is written (e,c). Tree

is written (b,(a,c)). Tree

is written ((c,b),(a,d)). We use this notation to demonstrate the algorithm.

Example

Suppose there are five letters, a, b, c d and e. After counting the characters in a document, suppose that you get the following counts.

The initial collection of trees (all leaves) with their frequencies is as follows.

Removing the two with the smallest frequencies and combining them yields a tree with frequency 480. It is inserted into the collection, yielding the following.

The next step combines c with (b,d), yielding tree (c,(b,d)), with a frequency of 300 + 480 = 780. The collection of trees and frequencies is now

Now combine a and e, yielding

The last step combines the last two trees, yielding

The final tree is ((c,(b,d)),(a,e)), which is the following tree.

The Assignment

---

For this assignment you will write two applications. Files huffman.cpp and unhuffman.cpp will each contain a main function and will be run separately.

The first application: huffman

The first application, called huffman, gets two file names, which I will refer to as A and B, from the command line, where A is argv[argc − 2] and B is argv[argc − 1]. It should do the following.

1. Count how many occurrences of each character are in file A.

2. If requested, show the character frequencies on the standard output, showing only characters that occur at least once.

3. Construct a Huffman tree T for those characters.

4. If requested, show the tree on the standard output, using the notation described above.

5. Construct a Huffman code from the Huffman tree (ignoring characters that do not occur at all).

6. If requested, show the Huffman code on the standard output.

7. Open file B and write a binary description of the Huffman tree T into B.

8. Reread file A and, using the constructed Huffman code, write an encoded version of file A into file B (after the tree). Close the files.

For example, command

  ./huffman data.txt data.cmp

The second application: unhuffman

The second application, called unhuffman, will also be given two file names, A and B, on the command line. It reads file A, which must be a file that was written by your huffman application, and it writes file B, which must be the decoded version of A. For example, command

  ./unhuffman data.cmp newdata.txt

The compressed file contains a binary description of a Huffman tree followed by a sequence of character codes. Your unhuffman algorithm should start by reading and building the tree. If requested, unhuffman should show the tree that it gets from file A.

Then it uses the tree to get character codes from file A and write the decoded characters into file B.

Input restriction

Assume that the original file has at least two different characters in it. Your program is not required to work correctly on a file that has no characters or only one character, possibly repeated.

Additional Requirements

---

As always, you are required to follow the design that is explained below.

In this assignment, you are allowed to add additional functions. You can also add parameters to required functions that are not mentioned in the design, provided that the roles of those parameters are clearly documented.

Tracing

---

You are required to provide for tracing, as outlined above (at if requested lines). If the command line contains -t, then tracing is turned on. Otherwise, tracing is turned off.

In Linux, it is conventional for options such as -t to occur before file names on commands. Command

  ./huffman -t data.txt data.cmp

Your huffman/unhuffman programs are required to contain tracing as follows, if tracing is turned on.

1. The huffman program should show the character frequencies, the Huffman tree that it produces, and the Huffman code that it gets. For example, the output of huffman with tracing turned on might look as follows.

   The character frequencies are:
   
   a 500
   b 230
   c 300
   d 250
   e 700
   
   The Huffman tree is: ((c,(b,d)),(a,e))
   
   A Huffman code is as follows.
   
   a 10
   b 010
   c 00
   d 011
   e 11
   

2. The unhuffman program should show the tree that it reads from the binary file. If it is not identical to the tree that was produced by huffman, there is trouble, so check that (by inspecting it).

A Refinement Plan

---

  int x = c;

  unsigned x = (unsigned) c;

#ifndef TREE_H
#define TREE_H

  // Each node is either a leaf or a nonleaf.  Type
  // NodeKind has just two values: leaf and nonleaf.

  enum NodeKind {leaf, nonleaf};

  // An object of type Node is node in a Huffman tree.
  // The variables are as follows.
  //
  // kind   tells whether the node is a leaf.
  //
  // ch     is the character stored in a leaf.
  //        It should only be used for leaves.
  //
  // left
  // right  These are the left and right subtrees.
  //        They should only be used for nonleaves.

  struct Node 
  {
    NodeKind kind;
    char     ch;
    Node*    left;
    Node*    right;

    // Create a leaf holding character c.

    Node(char c)
    {
      kind = leaf;
      ch   = c;
    }

    // Create a nonleaf with left subtree L
    // and right subtree R.

    Node(Node* L, Node *R)
    {
      kind  = nonleaf;
      left  = L;
      right = R;
    }      
  };

  typedef Node* Tree;

#endif

  #include "tree.h"
  typedef Tree ItemType;
  typedef int  PriorityType;

   Tree t = new Node('a');

   Tree t = new Node(r,s);

  strcat(A,B);

  diff file1 file2

Issues to Be Aware of

---

1. Start each file from the standard template.

2. Submit all of the files that your programs need. Do not assume that I already have them.

3. Pay attention to warnings. In the past, many students have submitted programs that get serious warnings that point to serious mistakes in the program. I immediately know where to look for a serious mistake. You should too.

4. The comments at the beginning of huffman.cpp and unhuffman.cpp should make it clear how to use each program. Say what the command line should look like.

5. Indent sensibly. In the past, many students have been lax about indentation, presumably because they started too late and did not believe the wisdom of decades of software development that it is sensible to keep the program well-indented while working on it.

6. Use sensible function, parameter and variable names. A function that shows a string should not be called showChar. A variable that is an array of frequencies should not be called charArray.

7. Huffman and unhuffman each get the names of files to open from the command line. Be sure not to read or write files with fixed names. For example, do not assume that the files are called data.txt and data.cmp. If you do, your program will not work when I test it. It is not my job to fix your work.

   Be sure to check for nonexistent files.

8. Only do tracing when tracing is turned on by option -t on the command line. Remember that -t occurs before the file names, if it occurs at all.

9. Follow the coding standards. Do not become lax on those.

10. Write clear, concise and correct contracts for every function and clear, complete comments for every type that you create. Make sure that the contract is correct. The function must do what the contract says it does. The function that counts character frequencies does not count "the number of frequencies of a character that occurs in a file." Each character only has one frequency. It does not do something for one character. Don't say that a function "sorts a Huffman tree." Read your contracts. Be critical of them.

11. Do not write more than one loop in one function body. Do not use one loop to emulate two nested loops.

12. String constants have type const char*. If a function takes a null-terminated string as a parameter, and the function does not change that string, make the parameter have type const char* so that you can pass a string constant as that parameter.

    Do not do a pointer-cast from const char* to char*. That is, do not pass a parameter of the form (char*) s, where s is a string constant. You don't need to do that and doing that kind of thing invites mistakes.

    You should never cast a pointer to an array of type T and say to treat it as a pointer to an array of type R where T and R are different types. The compiler will let you do it because it assumes that you are an expert. You aren't an expert yet.

    An empty string is written "". An empty string is not the same as NULL.

    The standards require you not to use C++ type string. Don't use it.

13. If you get a memory fault, use a debugger, such as gdb, to find the error. If the fault occurs when you run huffman, then start huffman with command

      gdb ./huffman
    

    Be sure that you have compiled huffman with option -g. At the (gdb) prompt, type

      run -t infile outfile
    

    where infile is the file to read and outfile is the file to write. At the memory fault, gdb will show exactly where the program is at the time. Do a backtrace (command bt) to see the run-time stack. Do command print v to print the value of a variable. Look at variables whose values could lead to a memory fault. Pointer 0x0 is a NULL pointer.

14. Watch out for memory leaks. This has been a frequent problem in the past.

15. To create a pointer variable p of type char* that you intend to set equal to something later, write

      char* p;
    

    Don't write

      char* p = new char;
    

    That allocates one byte, which leaks away as soon as you change p to point to something else.

16. Don't use fixed array sizes when it is not necessary. If it is easy to compute how large an array needs to be, then compute the size.

17. If you want to talk about a space character, write ' '. Do not write 32. If you want to talk about character '0', write '0', not 48. If you want to talk about a newline character, write '\n', not 10. You should see a pattern here.

    If you want to say EOF, write EOF, not −1.

18. Do not use long lines. Limit lines to 80 characters. Do not put non-7-bit-ascii characters in your comments. To write a single quote, use the apostrophe character. Don't try to be fancy. If a character is not on the keyboard, don't use it.

19. If s does not change, do not recompute strlen(s) each time around a loop. Computing strlen(s) requires scanning through s to find its end.

Submitting Your Work

---

To turn in your work, log into xlogin, change your directory for the one for assignment 8, and use the following command.

  ~abrahamsonk/2530/bin/submit 8 huffman.cpp unhuffman.cpp tree.h trace.cpp trace.h pqueue.h pqueue.cpp

After submitting, you should receive confirmation that the submission was successful. If you do not receive confirmation, assume that the submission did not work.

Command

  ~abrahamsonk/2530/bin/submit 8

You can do repeated submissions. New submissions will replace old ones.

Late Submissions

---

Late submissions will be accepted for 24 hours after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.

Asking questions

---

To ask a question about your program, first submit it, but use assignment name q8. For example, use command

  ~abrahamsonk/2530/bin/submit q8 huffman.cpp unhuffman.cpp tree.h trace.cpp trace.h pqueue.h pqueue.cpp

Then send me an email with your question. Do not expect me to read your mind. Tell me what your questions are. I will look at the files that you have submitted as q8. If you have another question later, resubmit your new file as assignment q8.