Using the frequency table shown below, build a Huffman Encoding Tree. Resolve ties by giving single letter groups precedence over multiple letter groups, then alphabetically. Do not worry about punctuation or capitalization.
Print out the tree by doing a preorder traversal. Print the resulting code. An example is given below for a 3-letter alphabet. You may use any reasonable format.
- – 3 The tree in preorder is: XYZ: 6, X: 3, YZ: 3, Y: 1, Z: 2
- – 1
- – 2 The code is X = 0; Y = 10, Z = 11;
In your write-up, consider whether you achieved any useful data compression with this method. Compare to conventional encoding. How would your results be affected by using a different scheme to break ties, for example, if you had given precedence to alphabetical ordering and then to the number of letters in the key? What other structures did you use and why?
Encode the following strings, plus several others of your choice:
Sally sells seashells by the seashore.
Peter Piper picked a peck of pickled peppers a peck of pickled peppers Peter Piper picked.
Houston, the Eagle has landed. Is that your final answer?
Decode the following strings:
01011001010110011111011011
10110000101010011011101101100010110010101100010111000110111
11111110001000111111101011111011001111111000100011111000001010000001110 010111
- – 19
- – 16
- – 17
- – 11
- – 42 F – 12
G – 14 H – 17 I – 16
- – 5
- – 10 L – 20 M – 19 N – 24 O – 18
- – 13
- – 1 R – 25 S – 35 T – 25
- – 15
- – 5 W – 21
- – 2
- – 8 Z – 3
