Practice Questions On Huffman Encoding

Practice Questions on Huffman Encoding
Difficulty Level : Medium ● Last Updated : 06 Feb, 2018
Huffman Encoding is an impor tant topic from GATE point of view and different types of
questions are asked from this topic. Before understanding this ar ticle, you should have
basic idea about Huffman encoding.
These are the types of questions asked in GATE based on Huffman Encoding.
Type 1. Conceptual questions based on Huffman Encoding –
Here are the few key points based on Huffman Encoding:
It is a lossless data compressing technique generating variable length codes for
different symbols.
It is based on greedy approach which considers frequency/probability of alphabets
for generating codes.
It has complexity of nlogn where n is the number of unique characters.
The length of the code for a character is inversely propor tional to frequency of its
occurrence.
No code is prefix of another code due to which a sequence of code can be
unambiguously decoded to characters.
Que – 1. Which of the following is true about Huffman Coding?
(A) Huffman coding may become lossy in some cases
(B) Huffman Codes may not be optimal lossless codes in some cases
(C) In Huffman coding, no code is prefix of any other code.
(D) All of the above
Solution: A s discussed, Huffman encoding is a lossless compression technique.
We use cookies to ensure you have the best browsing experience on our website. By using
Got It !
Therefore, option (A) and (B) are false. Option (C) is true as this is the basis of decoding
our site, you acknowledge that you have read and understood our Cookie Policy & Privacy
of message from given code.
Policy ▲
Type 2. To find number of bits for encoding a given message –
To solve this type of questions:
First calculate frequency of characters if not given
Generate Huffman Tree
Calculate number of bits using frequency of characters and number of bits required
to represent those characters.
Que – 2. How many bits may be required for encoding the message ‘mississippi’?
Solution: Following is the frequency table of characters in ‘mississippi’ in non-
decreasing order of frequency:
our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Got It !
Policy ▲
The generated Huffman tree is:
Following are the codes:
Total number of bits
= freq(m) * codelength(m) + freq(p) * code_length(p) + freq(s) * code_length(s) +
freq(i) * code length(i)
= 1*3 + 2*3 + 4*2 + 4*1 = 21
Also, average bits per character can be found as:
Total number of bits required / total number of characters = 21/11 = 1.909
Type 3. Decoding from code to message –

oursolve
To site, youthis
acknowledge
type of that you have read and understood our Cookie Policy & Privacy
question:
Got It !
Policy ▲
Generate codes for each character using Huffman tree (if not given)
Using prefix matching, replace the codes with characters.
Que – 3. The characters a to h have the set of frequencies based on the first 8 Fibonacci
numbers as follows:
a : 1, b : 1, c : 2, d : 3, e : 5, f : 8, g : 13, h : 21
A Huffman code is used to represent the characters. What is the sequence of characters
Related Articles
corresponding to the following code?
110111100111010
(A) fdheg
(B) ecgdf
(C) dchfg
(D) fehdg
Solution: Using frequencies given in the question, huffman tree can be generated as:
Policy ▲
Following are the codes:
Using prefix matching, given string can be decomposed as
110 11110 0 1110 10

f d h e g
Type 4. Number of bits saved using Huffman encoding –
Que – 4. 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:
Note that each character in input message takes 1 byte.
Policy ▲
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
Solutions : Finding number of bits without using Huffman,
Total number of characters = sum of frequencies = 100
size of 1 character = 1byte = 8 bits
Total number of bits = 8*100 = 800
Using Huffman Encoding, Total number of bits needed can be calculated as:
5*4 + 9*4 + 12*3 + 13*3 + 16*3 + 45* 1 = 224
Bits saved = 800-224 = 576.
Attention reader! Don’t stop learning now. Get hold of all the impor tant DS A concepts
with the DSA Self Paced Course at a student-friendly price and become industr y ready.
 Like 0
Policy ▲

Practice Questions On Huffman Encoding - GeeksforGeeks

Uploaded by

Copyright:

Available Formats

Practice Questions On Huffman Encoding - GeeksforGeeks

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Practice Questions On Huffman Encoding - GeeksforGeeks

Uploaded by

Copyright:

Available Formats

Difficulty Level : Medium ● Last Updated : 06 Feb, 2018

basic idea about Huffman encoding.

Type 1. Conceptual questions based on Huffman Encoding –

Here are the few key points based on Huffman Encoding:

It is a lossless data compressing technique generating variable length codes for

It is based on greedy approach which considers frequency/probability of alphabets

for generating codes.

It has complexity of nlogn where n is the number of unique characters.

No code is prefix of another code due to which a sequence of code can be

unambiguously decoded to characters.

Que – 1. Which of the following is true about Huffman Coding?

(A) Huffman coding may become lossy in some cases

(C) In Huffman coding, no code is prefix of any other code.

(D) All of the above

Solution: A s discussed, Huffman encoding is a lossless compression technique.

To solve this type of questions:

First calculate frequency of characters if not given

Generate Huffman Tree

to represent those characters.

Solution: Following is the frequency table of characters in ‘mississippi’ in non-

decreasing order of frequency:

Following are the codes:

Total number of bits

= freq(m) * codelength(m) + freq(p) * code_length(p) + freq(s) * code_length(s) +

freq(i) * code length(i)

= 1*3 + 2*3 + 4*2 + 4*1 = 21

Also, average bits per character can be found as:

Total number of bits required / total number of characters = 21/11 = 1.909

Type 3. Decoding from code to message –

Using prefix matching, replace the codes with characters.

Using prefix matching, given string can be decomposed as

110 11110 0 1110 10

Type 4. Number of bits saved using Huffman encoding –

Que – 4. A networking company uses a compression technique to encode the message

characters with their frequency:

Solutions : Finding number of bits without using Huffman,

Total number of characters = sum of frequencies = 100

size of 1 character = 1byte = 8 bits

Total number of bits = 8*100 = 800

5*4 + 9*4 + 12*3 + 13*3 + 16*3 + 45* 1 = 224

Bits saved = 800-224 = 576.

You might also like

= 13 + 23 + 42 + 41 = 21

54 + 94 + 123 + 133 + 163 + 45 1 = 224