Background: Huffman Encoding Trees

We consider the problem of representing text as a sequence of ones and zeros (bits). For example, the ASCII standard code used to represent text in computers encodes each character as a sequence of seven bits, and 128 characters are encoded in total. In general, if we want to distinguish n different symbols, we will need to use log base 2 of n bits per symbol.

As a simpler example, consider encoding only A, B, C, D, E, F, G, and H. We can choose a code with three bits per character, for example:

A 000   C 010   E 100   G 110
B 001   D 011   F 101   H 111

With this code, the message:

BACADAEAFABBAAAGAH

is encoded as the string of 54 bits:

001000010000011000100000101000001001000000000110000111

Codes such as ASCII and the A-through-H code above are known as fixed-length codes, because they represent each symbol in the message with the same number of bits. It is sometimes advantageous to use variable-length codes, in which different symbols may be represented by different numbers of bits. If our messages are such that some symbols appear very frequently and some very rarely, we can encode data more efficiently (i.e., using fewer bits per message) if we assign shorter codes to the frequent symbols. Consider the following alternative code for the letters A through H:

A 0     C 1010   E 1100   G 1110
B 100   D 1011   F 1101   H 1111

With this code, the same message as above is encoded as the string:

100010100101101100011010100100000111001111

This string contains 42 bits, so it saves more than 20% in space in comparison with the fixed-length code shown above.

One of the difficulties of using a variable-length code is knowing when you have reached the end of a symbol in reading a sequence of zeros and ones. One solution is to design the code in such a way that no complete code for any symbol is the beginning (or prefix) of the code for another symbol. Such a code is called a prefix code. In the example above, A is encoded by 0 and B is encoded by 100, so no other symbol can have a code that begins with 0 or with 100.

In general, we can attain significant savings if we use variable-length prefix codes that take advantage of the relative frequencies of the symbols in the messages to be encoded. One particular scheme for doing this is called the Huffman encoding method, after its discoverer, David Huffman. A Huffman code can be represented as a binary tree whose leaves are the symbols that are encoded.

Each symbol at a leaf is assigned a weight (which is its relative frequency), and each non-leaf node contains a weight that is the sum of all the weights of the leaves lying below it. The weights are not used in the encoding or the decoding process. We will see below how they are used to help construct the tree.

The figure below shows the Huffman encoding tree for the A-through-H prefix code given above. The weights at the leaves indicate that the tree was designed for messages in which A appears with relative frequency 8, B with relative frequency 3, and the other letters each with relative frequency 1.

10001010

Initial leaves:
{(A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)}

{(A 8) (B 3) ({C D} 2) (E 1) (F 1) (G 1) (H 1)}

{(A 8) (B 3) ({C D} 2) ({E F} 2) (G 1) (H 1)}

{(A 8) (B 3) ({C D} 2) ({E F} 2) ({G H} 2)}

{(A 8) (B 3) ({C D} 2) ({E F G H} 4)}

{(A 8) ({B C D} 5) ({E F G H} 4)}

{(A 8) ({B C D E F G H} 9)}

{({A B C D E F G H} 17)}

Question 1: Implementing Huffman Encoding Trees

(1A) Complete this abstract data type for representing a Huffman encoding tree. Leaves of the tree are represented by a sentence consisting of the word "leaf", the letter at the leaf, and the weight.

A Huffman encoding tree consists of a branch0, a branch1, and a weight. When we make a tree, we obtain the weight of the tree as the sum of the weights of the input trees (or leaves). By storing the weight as the third element of a tree, we can reuse the weight procedure for leaves to retrieve the weight of trees as well.

(1B) Implement decode_one, which takes as arguments a Huffman encoding tree and a word that consists of zeros and ones. It outputs the same word, but with the first letter decoded. The word procedure concatenates two words. The first and butfirst procedures can apply to either words or sentences.

(1C) Implement encodings, a procedure that returns a sentence of two-element sentences (pairs). Each of these pairs contains a letter and an encoding for that letter. The input is a Huffman encoding tree, and the output contains all letters encoded in that tree. The output should be ordered according to the order of leaves in a left-to-right traversal of the tree.

Hint: Feel free to introduce a helper procedure.

(1D) Implement Huffman, a procedure that takes a sentence of trees (or leaves) and outputs an optimal Huffman encoding tree. The elements of the input sentence are sorted from lowest to highest weight.

Hint: Keep the input to recursive calls to Huffman sorted, by using the provided insert procedure, which always outputs a sorted sentence.

Question 2: Recursive Hexagons

Write a procedure called hax that draws the following recursive illustration when passed two arguments, a side length d and recursive depth k. In this example, k is 5.

To see how this illustration is constructed, consider this annotated version that gives the relative lengths of lines of the component shapes in the figure.