A networking company uses a compression technique to encode the message before transmitting over the network. Suppose the message contains the following characters with their frequency:
character Frequency
a 5
b 9
c 12
d 13
e 16
f 45
Note : Each character in input message takes 1 byte. If the compression technique used is Huffman Coding, how many bits will be saved in the message?
a)
224
b)
800
c)
576
d)
324
Correct answer is option 'C'. Can you explain this answer?

Question

A networking company uses a compression technique to encode the message before transmitting over the network. Suppose the message contains the following characters with their frequency:
character Frequency
a 5
b 9
c 12
d 13
e 16
f 45

Note : Each character in input message takes 1 byte. If the compression technique used is Huffman Coding, how many bits will be saved in the message?

a)
224
b)
800
c)
576
d)
324

Correct answer is option 'C'. Can you explain this answer?

Answer

Explanation:

Huffman Coding:

Huffman coding is a lossless data compression technique used to compress data without losing any of its content. It works by creating a variable-length code table for encoding a source symbol (such as a character in a file). The table assigns shorter codes for the more frequent characters and longer codes for the less frequent characters.

Steps to solve the problem:

To find out how many bits will be saved in the message using Huffman coding, we need to follow the below steps:

1. Construct a Huffman tree using the given character frequencies.

2. Assign codes to the characters based on the Huffman tree.

3. Calculate the total number of bits required to encode the message using the original method.

4. Calculate the total number of bits required to encode the message using Huffman coding.

5. Find the difference between the two results to get the number of bits saved.

Constructing Huffman Tree:

To construct a Huffman tree, we need to follow the below steps:

1. Arrange the characters in ascending order of their frequencies.

2. Take the two characters with the lowest frequency and create a new node with their sum as the frequency.

3. Repeat step 2 until all the characters are included in the tree.

4. Assign 0 to the left branch and 1 to the right branch of each node.

Using the above steps, we can construct the following Huffman tree:

```
100
/ \
/ \
/ \
f(45) 55
/ \
/ \
/ \
25 d(13)
/ \
/ \
/ \
c(12) e(16)
/ \
/ \
/ \
b(9) a(5)
```

Assigning Codes:

Using the Huffman tree, we can assign codes to the characters as follows:

```
f - 0
d - 10
e - 11
c - 100
b - 101
a - 110
```

Calculating bits required:

To calculate the number of bits required to encode the message using the original method, we can use the formula:

```
bits required = total number of characters x 8
```

Using this formula, we can find that the number of bits required to encode the given message using the original method is:

```
bits required = (5+9+12+13+16+45) x 8 = 360
```

To calculate the number of bits required to encode the message using Huffman coding, we can use the formula:

```
bits required = (frequency of character x length of code) for all characters
```

Using this formula and the codes assigned to the characters earlier, we can find that the number of bits required to encode the given message using Huffman coding is:

```
bits required = (45 x 1) + (13 x 2) + (16 x 2) + (12 x 3) + (9 x 3) + (5 x 3) = 224
```

Calculating bits saved:

To calculate the number of bits saved, we can subtract the number

Similar Computer Science Engineering (CSE) Doubts

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company