Discrete Wavelets with Applications - Spring 2009

Final Project C:
Huffman Trees, Coding, and Decoding

Prepare a 20 minute presentation. You will be graded on the mathematical correctness of the presentation,  the quality and completeness of  the notebook you prepare, and the quality of your oral presentation. All group members must participate equally in the presentation.

SetDirectory[NotebookDirectory[]];
<<DW.m;<<DW1.m;

Problem 1

Write a program to display a Huffman Coding Tree for a given vector of symbols.

The output should look something remotely similar to the tree below (This command will not run on your computer since you don't have 'DW1.m'):

HuffmanTree[{t,w,o,t,w,o,s,t,o,t,o,u,l,o,u,s,e}]

An intermediate solution is to display the information step - by - step :

?HuffmanTreeStep

HuffmanTreeStep[{t,w,o,t,w,o,s,t,o,t,o,u,l,o,u,s,e},1]

The basic command to plot trees is 'TreePlot' :

TreePlot[{1->2,1->3,1->4,3->5,6->7},VertexLabeling->True]

Problem 2

Write a module to take a word and its Huffman codes for it and create the new coded bit stream.

Problem 3

Write a module that takes the coded bit stream and the Huffman codes and produces the original word.