Chapter 7.7A, Problem 6E

Explanation of Solution

Explanation:

• Huffman coding is a data compression method.
• The probability of each symbol present in the message is calculated to create the Huffman code.
• The probabilities of the symbols are used for creating a binary tree which in turn used to assign the code words.
• The tree traversal assigns bit pattern assignments for each symbol present in the message.
• The star bright rhyme is as follows,

  STAR LIGHT STAR BRIGHT

  FIRST STAR I SEE TONIGHT

  I WISH I MAY I WISH I MIGHT

  GET THE WISH I WISH TONIGHT

• The code for the above rhyme and Huffman tree is created as follows,
• Replace the space and new line characters with <ws> and tabulate all the occurrences of the letters present in the rhyme.

Letter	Count
A	4
B	1
E	4
F	1
G	6
H	10
I	16
L	1
M	2
N	2
O	2
R	5
S	9
T	13
W	4
Y	1
<ws>	22

• In the following tree diagram, the nodes represent all the letters and their respective frequencies and they are represented in the increasing order.

• In the following tree diagram, nodes with smallest frequencies are joined to create the binary tree. Here, B and F are aggregated together that includes smallest frequency of 1 and similarly, L and Y are also aggregated...