HUFFMAN ENCODING

Huffman encoding is a Greedy Technique, It is used to encode and compress the data.

So, what is compression? and why we use Huffman encoding…

I will explain with a simple example.

Here let’s take,

M = 100 Characters

a = 50

b = 10

c = 30

d = 5

e = 3

f = 2

the given alphabets represent the frequencies.

Now we have to encode the data, which means converting it into ‘1’s and ‘0’s .

The basic encoding technique used is ASCII encoding.

The range in ASCII encoding is 0–127

We represent 127 characters by 7 bits.

127 characters = 7 bits is obtained from, the max range is 127 and this 127 in binary form is represented by ‘1111111’ seven 1’s.

Now each character is represented by 7 bits. And to represent 100 characters it takes 7 × 100 = 700 bits.

We need to encode this message into digital form.

In general, to encode the above message it takes 700 bits.

Here we use Huffman encoding to compress the data size to encode the message.

First in the above message take the two smallest digits, and the smaller number should be placed in the left side and larger number should be placed on the right side.

In this, for left tree assign it as ‘0’ and for right tree assign it with ‘1’.

Now, let’s see the path

Path for each alphabet is taken from edge of root node to the alphabet.

a = 0 1 bit

b = 1 0 0 3 bits

c = 1 1 2 bits

d = 1 0 1 0 4 bits

e = 1 0 1 1 0 5 bits

f = 1 0 1 1 0 5 bits

Here, we found the answers for 2 questions.

The code used to represent each alphabet and number of bits used for each alphabet.

a => 50 × 1 = 50bits

b => 10 × 3 = 30bits

c = > 30 × 2 = 60 bits

d = > 5 × 4 = 20 bits

e = > 3 × 5 = 15 bits

f = > 2 × 5 = 10 bits

Total bits = 185 bits

This the total number of bits used to encode the message using Huffman encoding.

The logic in Huffmann encoding is higher frequency is represented in less bits and for lower frequency it is represented in large bits.

Here another question can be asked, which is average bits required to represent each character

So, it is Total Bits / Total Characters

= > 185/100 = 1.85 bits/characters

So here the benefit is when we compress the data it takes less number of bits to represent the data and the storage is used efficiently.

And if you are transmitting the data then TT = Message / Bandwidth

Here Transmission Time is directly proportional to the Message.

Which means lower the message lower is the transmission time.

By this example Huffmann Encoding is explained.

,