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 $13$

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.