Question

Cost of a prefix-free encoding The basic intuition behind Huffman's algorithm is that frequent symbols should have short encodings and infrequent symbols should have long encodings. This intuition also has effect in English: typical words like 1, you, is, and, to, from, and so on are short, and rarely used words like velociraptor are longer.

Answer 1

Step 1:

Minimum total cost of prefix-free encoding:

We take a text with “m” different together symbol and its occurrences of f_{1 ,} f_2, f₃ and cost per bit for i^th symbol is denoted as c_i.

_{Cost of encoding :}

Huffman’s algorithm:

Cost =   f_i . l_i

im m i=1 =

Here :

“f_i” denotes as frequency distribution of the i^th character.

“li”denotes as length of the i^th character.

The cost of prefix-free encoding represented as follows:

Cost = f_i . l_i . c_i

im m i=1 =

Where,

“f_i. c_i” denotes as frequency of the i^th character.

“l_i” denotes as length of the i^{th character.}

  

Step 2:

Minimum cost of prefix-free encoding:

Huffman encoding is an easy method.

• Each tree contains only one node, which corresponds to each character.

• Join the pair of tree with the small range of frequency until to get the root node.

• Then, check the tree for each symbol and traverse the tree to write the code character.

1. Here, “0” bit for left side traversal of tree.

2. “1” bit for right side traversal of tree

• Depth of the leaf in i^th word in tree d_i is equal to the length of the i^th word “$1616832958457_blob$” with that leaf.
• Then, the minimum cost of prefix-free encoding can also be represented as,

Cost = f_i . d_i

im m i=1 =

Where,

fi denotes as frequency distribution of the “i^th” character.

d_i denotes as depth of the “i^th” character.

Hence, Huffman encoding is known as the minimum cost of prefix-free encoding.

Step 3:

For example:

Construction of the Huffman encoding tree:

Inputs are,

• character A with frequency of 31%,character C with frequency of 20%, character G with frequency of 9%, and character T with frequency of 40%.

• Huffman encoding is displayed under with example of a tree and frequency of the character with square brackets.

2 % 1 6o 1 T [40 A [31 29 1 G [q C[ 20

From the Huffman encoding tree,

• Get the tree for character “A” which is from root node, 01.

• Get the tree for character “C” which is from the root node , 000.

• Get the tree for character “G” which is from the root node , 001.

• Get the tree for character “T” which is from the root node , 1.

Hence, the Huffman encoding table is shown below:

Step 4:

Character	CodeWord
A	01
C	000
G	001
T	1

The time complexity of the following encoding is : O(m*logm)

This can be optimised to : O(m)

1. Create two empty queue.

2. Then each leaf node must create a distinct character and then we need to enqueue it to first queue in increasing order of their respective frequency.

3. The nodes of with minimum frequency are dequed depending on the front of the queue.

1. If second size is 0 then deque the first queue.

2. If first queue size is 0 then deque the second queue.

3. If both the above not satisfied compare the front of the queue and take the minimum.

4. create nodes with frequency equal to sum of the nodes. Then repeat step 3 and 4 while there is more than one node in the queue. The left node is the root node.

Hence, this character is the minimum cost prefix code for this distribution.

Hope this helps! please give a thumbs up, if any queries kindly ask in the comment section.