19-08-2013, 04:06 PM
Huffman Codes
Huffman Code.pdf (Size: 851.68 KB / Downloads: 60)
Problem Description:
As a professor who gives the final exam problem on Huffman
codes, he is encountering a big problem: the Huffman codes are not
unique. The students are submitting all kinds of codes, and he needs a
computer program to help him determine which ones are correct and
which ones are not. Hence, in this project, our task is to make a program
to determine whether the given codes are Huffman codes or not.
Some background of the algorithms:
Among all of the algorithms we use here, the most significant one is
the Huffman’s algorithm. The Huffman Tree algorithm provides a method
for compressing data stream with redundant information. Redundant
information exists when symbols with different distribution are
represented by the same amount of bits. A symbol can be any
consecutive sequence of bits, and the data stream can be divided into
symbols in many ways. The basic idea is to exploit the non-uniform
distribution of symbols, and reduce the total number of bits in the data
stream. This can be achieved by replacing common symbols with short
bit sequences and rare symbols with long bit sequences.
Part 2 Efficency
When testing the runtime of the program, we use the library
function “clock()” to record the start and the end and then we can
calculate the runtime. When the input is small, the runtime is so small
that is almost zero which is hard to catch. So we use a loop making the
program runs a lot of time, then we can calculate the average runtime.