6.02 Lab #10: Huffman Coding

Deadlines

Useful links

Instructions

See Lab #1 for a longer narrative about lab mechanics. The one-sentence version:

Complete the tasks below and submit your task files on-line before the deadline.

As always, help is available in 32-083 (see the Lab Hours web page).

Goal

Construct Huffman codes given symbol probabilities and experiment with various encodings of images to minimize the length of fax-style transmissions. The compression scheme you will develop is the basic idea used in fax transmissions in practice.

Task 1: Creating Huffman codes (1 point)

The process of creating a variable-length code starts with a list of message symbols and their probabilities of occurrence. As described in section 22.3 of the lecture notes, our goal is to encode more probable symbols with shorter binary sequences, and less probable symbols with longer binary sequences. The Huffman algorithm builds the binary tree representing the variable-length code from the bottom up, starting with the least probable symbols.

Please write a Python function to build a Huffman code from a list of probabilities and symbols:

(encoding_dictionary,tree) = huffman(plist)
Given plist, a sequence of tuples (prob,symbol), use the Huffman algorithm to build the binary tree representing an optimal variable-length code for messages consisting of the listed symbols. Use instances of the Tree class to represent leaves and interior nodes of the tree.

After the tree has been constructed, perform a recursive walk of the tree to build an encoding dictionary that maps symbols to their corresponding Huffman code.

Return a tuple containing the encoding dictionary and a Tree instance representing the root of the binary tree.

Please note: Python's heapq module can be especially helpful when one has to repeatedly select the smallest element of a list. A heap queue is a list whose elements are organized so that removing the minimimum element is fast, taking constant time independent of the size of the list. Adding a new element takes an amount of time that is logarithmic in the size of the list.

The heap queue operations use the "<" operator to compare list elements, so we've defined how "<" works on Tree instances by adding a __lt__ method to the Tree class.

lab10_1.py is the template file for this task: 

# template file for Lab #10, Task 1
import heapq
import lab10

# an object representing a node in a Huffman tree.
class Tree:
    def __init__(self,p,left,right=None):
        self.p = p          # probability associated with node
        self.left = left    # left child (any Python value if leaf)
        self.right = right  # right child (None if leaf)
        # depth ensures the algorithm prefers to combine shallow
        # trees when selected items of equal probability
        self.depth = 1 if right is None \
                     else 1 + max(self.left.depth,self.right.depth)

    # compare two tree nodes, sorting first by probability then
    # by depth of tree.  This is the low-level function called
    # by min or the less-than operator when the arguments are
    # instances of Tree.
    def __lt__(self,other):
        return self.p < other.p or \
               (self.p == other.p and self.depth < other.depth)

    # return True if this instance is a leaf of the tree
    def isLeaf(self):
        return self.depth == 1

    # recursive procedure to construct encoding dictionary
    # by walking the tree to find all the leaf nodes.
    def walk(self,encode_dict,prefix):
        if self.isLeaf():
            encode_dict[self.left] = prefix
        else:
            self.left.walk(encode_dict,prefix+[0])
            self.right.walk(encode_dict,prefix+[1])

# arguments:
#   plist -- sequence of (probability,object) tuples
# return:
#   (dict,tree) where
#     dict is a dictionary mapping object -> binary encoding
#     tree is the Huffman tree built by the algorithm.
def huffman(plist):
    # initialize set of tree nodes as leaves of the tree
    tlist = [Tree(p,obj) for p,obj in plist]

    # Build Huffman tree by processing tlist until there is only a
    # single tree object left in the list (ie, the root of the
    # Huffman tree).  Consider using the heapq module.  You can
    # make a new node in the Huffman tree by calling
    #     Tree(probability,left_child,right_child).

    # your code here...

    # walk the Huffman tree, adding an entry to the encoding
    # dictionary each time we find a leaf
    root = tlist[0]
    encoding_dict = {}
    root.walk(encoding_dict,[])

    # return (encoding dictionary,huffman tree)
    return (encoding_dict,root)

if __name__ == '__main__':
    # test case 1: four symbols with equal probability
    lab10.test_huffman(huffman,
                       # symbol probabilities
                       ((0.25,'A'),(0.25,'B'),(0.25,'C'),
                        (0.25,'D')),
                       # expected encoding lengths
                       ((2,'A'),(2,'B'),(2,'C'),(2,'D')))

    # test case 2: example from section 22.3 in notes
    lab10.test_huffman(huffman,
                       # symbol probabilities
                       ((0.34,'A'),(0.5,'B'),(0.08,'C'),
                        (0.08,'D')),
                       # expected encoding lengths
                       ((2,'A'),(1,'B'),(3,'C'),(3,'D')))

    # test case 3: example from Exercise 5 in notes
    lab10.test_huffman(huffman,
                       # symbol probabilities
                       ((0.07,'I'),(0.23,'II'),(0.07,'III'),
                        (0.38,'VI'),(0.13,'X'),(0.12,'XVI')),
                       # expected encoding lengths
                       ((4,'I'),(3,'II'),(4,'III'),
                        (1,'VI'),(3,'X'),(3,'XVI')))

    # test case 4: 3 flips of unfair coin
    phead = 0.9
    plist = []
    for flip1 in ('H','T'):
        p1 = phead if flip1 == 'H' else 1-phead
        for flip2 in ('H','T'):
            p2 = phead if flip2 == 'H' else 1-phead
            for flip3 in ('H','T'):
                p3 = phead if flip3 == 'H' else 1-phead
                plist.append((p1*p2*p3,flip1+flip2+flip3))
    expected_sizes = ((1,'HHH'),(3,'HTH'),(5,'TTT'))
    lab10.test_huffman(huffman,plist,expected_sizes)

    # when your code is ready to be submitted, enable the
    # call to lab10.checkoff.
    #lab10.checkoff(huffman,'L10_1')

The template includes code for the Tree class and a start at the huffman function. You should complete the definition of the function by repeatedly processing the list of Tree instances, tlist, until tlist contains only a single instance -- the root of the Huffman tree. On each pass, remove the two Tree instances that have the smallest probability, construct a new Tree instance representing an interior node of the tree with the two instances as its children, computing the appropriate probability for the interior node, and add this new instance back into tlist.

The Python module heapq implements a priority queue data structure that is particularly efficient at letting you select the minimum element of the list. Read about it in the Python documentation and use it -- it'll make it very easy to write the huffman function.

The testing code in the template runs your code through several test cases. You should see something like the following print-out (your encodings may be slightly different, although the length of the encoding for each of the symbols should match that shown below):

When you're ready to submit your code on-line, enable the call to lab10.checkoff.

Task 2: Decoding Huffman-encoded messages (1 point)

Encoding a message is a one-liner using the encoding dictionary returned by the huffman routine -- just use the dictionary to map each symbol in the message to its binary encoding and then concatenate the individual encodings to get the encoded message: 

def encode(encoding_dict,message):
    return numpy.concatenate([encoding_dict[obj]
                              for obj in message])
Decoding uses the Huffman tree, also returned by the huffman routine: use the bits from the encoded message to guide a traversal of the tree starting at the root, consuming one bit each time a branch decision is required. When the traversal reaches a leaf of the tree, that's the next decoded message symbol. This process is repeated until all the encoded message bits have been consumed.

Please write a Python function to decode an encoded message using the supplied Huffman tree:

decoded_message = decode(huffman_tree,encoded_message)
encoded_message is a numpy arrary of binary values, as returned by the encode function shown above. huffman_tree is a Tree instance representing the root of the binary Huffman tree. For non-leaf nodes in the tree, the instance slots left and right access the two descendents of the node.

The isLeaf() method can be called to determine if a Tree instance represents a leaf of the Huffman tree, in which case the left instance slot holds the value of the leaf symbol.

Return the sequence of symbols representing the decoded message.

lab10_2.py is the template file for this task: 

import numpy,random
import lab10
from lab10_1 import huffman

# arguments:
#   encoded_message -- numpy array of 0's and 1's
#   huffman_tree -- instance of Tree, root of Huffman tree
# return:
#   sequence of decoded symbols
def decode(huffman_tree,encoded_message):
    result = []

    # Use successive bits from encoded_message to guide
    # traversal of huffman_tree until a leaf is reached.
    # The value of the left slot will be the next symbol
    # to be appended to result.  Repeat until all the
    # bits of encoded_message have been consumed.

    # your code here...

    # return the result sequence
    return result

if __name__ == '__main__':
    # start by building Huffman tree from probabilities
    plist = ((0.34,'A'),(0.5,'B'),(0.08,'C'),(0.08,'D'))
    cdict,tree = huffman(plist)

    # test case 1: decode a simple message
    message = ['A', 'B', 'C', 'D']
    encoded_message = lab10.encode(cdict,message)
    decoded_message = decode(tree,encoded_message)
    assert message == decoded_message, \
           "Decoding failed: expected %s, got %s" % \
           (message,decoded_message)

    # test case 2: construct a random message and encode it
    message = [random.choice('ABCD') for i in xrange(100)]
    encoded_message = lab10.encode(cdict,message)
    decoded_message = decode(tree,encoded_message)
    assert message == decoded_message, \
           "Decoding failed: expected %s, got %s" % \
           (message,decoded_message)

    # when your code is ready to be submitted, enable the
    # call to lab10.checkoff.
    #lab10.checkoff((decode,cdict,tree),'L10_2')
When you're ready to submit your code on-line, enable the call to lab10.checkoff.

Task 3: Huffman codes in use: fax transmissions (4 points)

A fax machine scans the page to be transmitted, producing row after row of pixels. Here's what our test text image looks like:

Instead of sending 1 bit per pixel, we can do a lot better if we think about transmitting the image in chunks, observing that in each chunk we have alternating runs of white and black pixels. What's your sense of the distribution of run lengths, for example when we arrange the pixels in one long linear array? Does it differ between white and black runs?

Perhaps we can compress the image by using run-length encoding, where we send the lengths of the alternating white and black runs, instead of sending the pixel pattern directly. For example, consider the following representation of a 4x7 bit image (1=white, 0=black): 

1 1 0 0 1 1 1
1 1 1 0 0 1 1
1 1 1 1 0 0 1
1 1 1 1 1 1 1

This bit image can be represented as a sequence of run lengths: [2,2,6,2,6,2,8]. If the receiver knows that runs alternate between white and black (with the first run being white) and that the width of the image is 7, it can easily reconstruct the original bit pattern.

It's not clear that it would take fewer bits to transmit the run lengths than to transmit the original image pixel-by-pixel -- that'll depend on how clever we are when we encode the lengths! If all run lengths are equally probable then a fixed-length encoding for the lengths (e.g., using 8 bits to transmit lengths between 0 and 255) is the best we can do. But if some run length values are more probable than others, we can use a variable-length Huffman code to send the sequence of run lengths using fewer bits than can be achieved with a fixed-length code.

lab10_3.py runs several encoding experiments, trying different approaches to using Huffman encoding to get the greatest amount of compression. As is often the case with developing a compression scheme, one needs to experiment in order to gain the necessary insights about the most compressible representation of the message (in this case the text image).

Please run lab10_3.py, look at the output it generates, and then tackle the associated lab questions.

Here are the alternative encodings we'll explore:

Baseline 0 -- Transmit the b/w pixels as individual bits
The raw image contains 250,000 black/white pixels (0 = black, 1 = white). We could obviously transmit the image using 250,000 bits, so this is the baseline against which we can measure the performance of all other encodings.

Baseline 1 -- Encode run lengths with fixed-length code
To explore run-length encoding, we've represented the image as a sequence of alternating white and black runs, with a maximum run size of 255. If a particular run is longer than 255, the conversion process outputs a run of length 255, followed by a run of length 0 of the opposite color, and then works on encoding the remainder of the run. Since each run length can be encoded in 8 bits, the total size of the fixed-length encoding is 8 times the number of runs.

Baseline 2 -- Lempel-Ziv compressed PNG file
The original image is stored in a PNG-format file. PNG offers lossless compression based on the Lempel-Ziv algorithm for adaptive variable-length encoding described in section 22.4. We'd expect this baseline to be very good since adaptive variable-length coding is one of the most widely-used compression techniques.

Experiment 1 -- Huffman-encoding runs
As a first compression experiment, try using encoding run lengths using a Huffman code based on the probability of each possible run length. The experiment prints the 10 most-probable run lengths and their probabilities.

Experiment 2 -- Huffman-encoding runs by color
In this experiment, we try using separate Huffman codes for white runs and black runs. The experiment prints the 10 most-probable run lengths of each color.

Experiment 3 -- Huffman-encoding run pairs
Compression is always improved if you can take advantage of patterns in the message. In our run-length encoded image, the simplest pattern is a white run of some length (the space between characters) followed by a short black run (the black pixels of one row of the character).

Experiment 4 -- Huffman-encoding 4x4 image blocks
In this experiment, the image is split into 4x4 pixel blocks and the sixteen pixels in each block are taken to be a 16-bit binary number (i.e., a number in the range 0x0000 to 0xFFFF). A Huffman code is used to encode the sequence of 16-bit values. This encoding considers the two-dimensional nature of the image, rather than thinking of all the pixels as a linear array.

The lab questions will ask you analyze the results. In each of the experiments, look closely at the top 10 symbols and their probabilities. When you see a small number of symbols that account for most of the message (i.e., their probabilities are high), that's when you'd expect to get good compression from a Huffman code.

Here's the code for lab10_3.py: 

import matplotlib.pyplot as p
import numpy,os
import lab10
from lab10_1 import huffman
from lab10_2 import decode

if __name__ == '__main__':
    # read in the image, convert into vector of pixels
    img = p.imread('lab10_fax_image.png')
    nrows,ncols,pixels = lab10.img2pixels(img)

    # convert the image into a sequence of alternating
    # white and black runs, with a maximum run length
    # of 255 (longer runs are converted into multiple
    # runs of 255 followed by a run of 0 of the other
    # color).  So each element of the list is a number
    # between 0 and 255.
    runs = lab10.pixels2runs(pixels,maxrun=255)

    # now print out number of bits for pixel-by-pixel
    # encoding and fixed-length encoding for runs
    print "Baseline 0:"
    print "  bits to encode pixels:",pixels.size

    print "\nBaseline 1:"
    print "  total number of runs:",runs.size
    print "  bits to encode runs with fixed-length code:",\
          8*runs.size

    print "\nBaseline 2:"
    print "  bits in Lempel-Ziv compressed PNG file:",\
          os.stat('lab10_fax_image.png').st_size*8

    # Start by computing the probability of each run length
    # by simply counting how many of each run length we have
    plist = lab10.histogram(runs)

    # Experiment 1: Huffman-encoding run lengths
    cdict,tree = huffman(plist)
    encoded_runs = numpy.concatenate([cdict[r] for r in runs])
    print "\nExperiment 1:"
    print "  bits when Huffman-encoding runs:",\
          len(encoded_runs)
    print "  Top 10 run lengths [probability]:"
    for i in xrange(10):
        print "    %d [%3.2f]" % (plist[i][1],plist[i][0])

    # Experiment 2: Huffman-encoding white runs, black runs
    plist_white = lab10.histogram(runs[0::2])
    cwhite,tree_white = huffman(plist_white)
    plist_black = lab10.histogram(runs[1::2])
    cblack,tree_black = huffman(plist_black)
    encoded_runs = numpy.concatenate(
        [cwhite[runs[i]] if (i & 1) == 0 else cblack[runs[i]]
         for i in xrange(len(runs))])
    print "\nExperiment 2:"
    print "  bits when Huffman-encoding runs by color:",\
          len(encoded_runs)
    print "  Top 10 white run lengths [probability]:"
    for i in xrange(10):
        print "    %d [%3.2f]" % (plist_white[i][1],
                                  plist_white[i][0])
    print "  Top 10 black run lengths [probability]:"
    for i in xrange(10):
        print "    %d [%3.2f]" % (plist_black[i][1],
                                  plist_black[i][0])

    # Experiment 3: Huffman-encoding run pairs
    # where each pair is (white run,black run)
    pairs = [(runs[i],runs[i+1]) for i in xrange(0,len(runs),2)]
    plist_pairs = lab10.histogram(pairs)
    cpair,tree_pair = huffman(plist_pairs)
    encoded_pairs = numpy.concatenate([cpair[pair]
                                       for pair in pairs])
    print "\nExperiment 3:"
    print "  bits when Huffman-encoding run pairs:",\
          len(encoded_pairs)
    print "  Top 10 run-length pairs [probability]:"
    for i in xrange(10):
        print "    %s [%3.2f]" % (str(plist_pairs[i][1]),
                                  plist_pairs[i][0])

    # Experiment 4: Huffman-encoding 4x4 image blocks
    blocks = lab10.pixels2blocks(pixels,nrows,ncols,4,4)
    plist_blocks = lab10.histogram(blocks)
    cblock,tree_block = huffman(plist_blocks)
    encoded_blocks = numpy.concatenate([cblock[b] for b in blocks])
    print "\nExperiment 4:"
    print "  bits when Huffman-encoding 4x4 image blocks:",\
          len(encoded_blocks)
    print "  Top 10 4x4 blocks [probability]:"
    for i in xrange(10):
        print "    0x%04x [%3.2f]" % (plist_blocks[i][1],
                                      plist_blocks[i][0])

    """
    # make sure we didn't goof somehow => display decoded image
    decoded_blocks = decode(tree_block,encoded_blocks)
    decoded_pixels = lab10.blocks2pixels(decoded_blocks,
                                         nrows,ncols,4,4)
    decoded_img = lab10.pixels2img(decoded_pixels,nrows,ncols)
    p.figure()
    p.title('Image decoded from 4x4 encoded blocks')
    p.imshow(decoded_img)
    p.show()
    """

There are lab questions associated with this task.

End of Lab #10!

Don't forget to submit the on-line lab questions!