Question

(b.) Huffman code is a way to encode information using variable-length binary strings to represent symbols depending on the frequency of each individual letter. Specifically, letters that appear more frequently can be encoded into strings of shorter lengths, while rarer letters can be turned into longer binary strings. On average, Huffman code is a more efficient way to encode a message as the number of bits in the output string will be shorter than if a fixed-length code was used. In addition, this encoding scheme is proven to be unambiguous in the sense that we can easily identify the boundaries between letters and uniquely decrypt an encoded message That is, no letter's encoding can be the prefix of another letter's encoding (e.g., we cannot have both 00 and 001 as the encoding for two different letters) Huffman encoding is managed through a full binary tree, called the Huffman tree. Here, the leaf vertices are letters in the original message. For each internal vertices, the left outgoing edges (branches) are labeled with a 0, and right branches are labeled with a 1 The path from the root to the leaf gives us encoding of the corresponding letter in the leaf The following is the algorithm for building Huffman tree (Rosen p.764) procedure Huffman(C: letters ai with frequencies wi ,i-1,...,n) 1. F:- collection of n rooted trees, each consisting of the single vertex ai and weight wz 2. while F is not a single tree Replace the rooted trees T and T of least weights from F with w(T) 2 w(T) with a tree having a new root that has T as its left subtree and T' as its right subtree Label the new edge to T with 0 and the new edge to T' with 1 Assign w(T) +w(T') as the weight of the new tree The Huffman coding for the symbol ai is the concatenation of the labels of the edges in the unique path from the root to the vertex ai (12 points) Construct the Huffman code that enables you to encrypt the same file in part (a) so that you can store it using the least number of bits. Specify the binary representation for each letter and compute the length of the encoded file under Huffman coding

Answer 1

Below is the Huffman tree for this file, created following the steps mentioned in problem:

Human Tr po Root 200 /26 73 30 41 28 /6

Binary represntation of each letter, follow the path from root to each letter:

A - 111, B - 11000, C - 100, D - 101, E - 0, F - 1101, G - 11001

Length of file = Sum for all characters (Number of bits * frequency)

Length = (3* 73) + (5*9) + (3*30) + (3*44) + (1*130)+ (4*28) + (5*16)

Legth of file in bits = 808