Description
Generate a Huffman Code for the letters in some alphabet, one
must start with a set of letters from the alphabet along with
their frequencies.
Method:
First, build a list which holds references to (binary) nodes
containing the letters in the alphabet, their frequencies of
occurrences, and left and right subtree references (initially null).
This could be viewed as a forest of single node trees. There will
be exactly one node in the list for each letter.
Second, systematically transform the list into a list with only one
element in it where the element points to the root of the
Huffman Code Tree for that alphabet (a single binary tree). This
transformation takes place as follows: repeatedly take two
elements in the list which have the lowest frequencies and make
them the left and right subtrees of the new element in the list
(lowest frequency goes in the left – for ease of grading). The
frequency of the new element is the sum of the frequencies of
the two that it embodies. This new element will replace the two
elements just used in the list.
If you use a priority queue for your list of nodes, they will always
be kept in order for you.
a. Print out the frequency table and the Huffman Code for
each letter of the Gettysburg address.
b. Encode the Gettysburg address.
c. Print the encoded Gettysburg address.
d. Decode your compressed file and print out the Gettysburg
address.
e. Print out the compression ratio that was achieved.
Assignment 15
Four score and seven years ago our fathers brought forth on this
continent, a new nation, conceived in Liberty, and dedicated to the
proposition that all men are created equal.
Now we are engaged in a great civil war, testing whether that nation, or any
nation so conceived and so dedicated, can long endure. We are met on a
great battle-field of that war. We have come to dedicate a portion of that
field, as a final resting place for those who here gave their lives that that
nation might live. It is altogether fitting and proper that we should do this.
But, in a larger sense, we cannot dedicate — we cannot consecrate — we
cannot hallow — this ground. The brave men, living and dead, who
struggled here, have consecrated it, far above our poor power to add or
detract. The world will little note, nor long remember what we say here, but
it can never forget what they did here. It is for us the living, rather, to be
dedicated here to the unfinished work which they who fought here have
thus far so nobly advanced. It is rather for us to be here dedicated to the
great task remaining before us — that from these honored dead we take
increased devotion to that cause for which they gave the last full measure
of devotion — that we here highly resolve that these dead shall not have
died in vain — that this nation, under God, shall have a new birth of freedom
— and that government of the people, by the people, for the people, shall
not perish from the earth.
Due May 13
th
