Consider a text string containing a set of characters and their frequency counts as follows: A: (15), B: (7), C: (6), D: (6) and E: (5). Show that the Shannon-Fano algorithm produces a tree that encodes this string in a total of 89 bits, whereas the Huffman algorithm needs only 87 bits.

Question

Quizplus · Accepted Answer

The Answer is (15)
B : (7)
C : (6)
D : (6)
E : (5)

Shannon-Fano Algorithm:
Step 1: Sort the characters based on their frequency counts in descending order.
A: (15)
B: (7)
C: (6)
D: (6)
E: (5)

Step 2: Split the characters into two groups such that the total frequency count of each group is approximately equal.
Group 1: A (15)
Group 2: B (7), C (6), D (6), E (5)

Step 3: Assign binary codes to each group, with 0 for Group 1 and 1 for Group 2.
Group 1: A (15) - 0
Group 2: B (7), C (6), D (6), E (5) - 1

Step 4: Repeat steps 2 and 3 for each group until each character has its own binary code.
A: 0
B: 10
C: 110
D: 1110
E: 1111

Total bits required = (15*1) + (7*2) + (6*3) + (6*4) + (5*4) = 89 bits

Huffman Algorithm:
Step 1: Create a min-heap of characters based on their frequency counts.
Step 2: Merge the two characters with the lowest frequency counts into a single node, and update the frequency count of the new node.
Step 3: Repeat step 2 until all characters are merged into a single tree.

A: (15)
B: (7)
C: (6)
D: (6)
E: (5)

Merging steps:
1. E (5) + D (6) = ED (11)
2. C (6) + B (7) = CB (13)
3. ED (11) + CB (13) = EDCB (24)
4. A (15) + EDCB (24) = AEDCB (39)

Binary codes:
A: 0
B: 101
C: 100
D: 111
E: 110

Total bits required = (15*1) + (7*3) + (6*3) + (6*3) + (5*3) = 87 bits

Therefore, the Shannon-Fano algorithm produces a tree that encodes the given string in a total of 89 bits, whereas the Huffman algorithm needs only 87 bits.

Consider a Text String Containing a Set of Characters and Their