Huffman Coding

Step 1) Create a symbol and probability table for each character
like for ‘C’ it comes once in total 14 characters(including space)
therefore it’s probability is 1/14.

Similarly for ‘M’ it appears 3 times in the message so its probability is

3/14

after finding probability of each character sort it according to probability as shown in above figure.

Step 2)

i) Now arrange the characters in their order of probabilty
as you can see in left part all characters are sorted according to decreasing order of it’s probability
ii) Now after writing each character and it’s probability in descending order

follow steps till the table size reduces to 2(step a and step b)

a) Merge 2 smallest probabilites into one and then again sort the values and write to the right of it as shown in diagram
like for example
e.g [4/14 , 3/14, 3/14, 1/14,1/14, 1/14 ,1/14]

now 1st iteration take last 2 elements merget them(i.e add) and then put in the array and sort again
1) [4/14, 3/14, 3/14, 2/14, 1/14, 1/14 ( merged 1/14+1/14= 2/14)

2) 4/14 , 3/14, 3/14, 2/14, 2/14 ( merged 1/14+1/14= 2/14)

3) 4/14, 4/14 , 3/14, 3/14] (merged 2/14+ 2/14=4/14)

4) 6/14, 4/14, 4/14 (merged 3/14 +3/14 = 6/14)

5) 8/14 , 6/14 (merged 4/14+4/14= 8/14)
now as array contains only 2 elements stop
YOU CAN SEE THE SAME IN DIAGRAM GIVEN BELOW WHERE ARROW DENOTES THE MERGE OF ELEMENTS

STEP 3) Now starting from last elements give them label as ‘0’ and ‘1’

Now similarly just look at the arrow we draw when merging the elements
They will help you label the each number

label 0 given to 8/14 and 6/14 to 1

whenever there is division of the arrow you again label 0 and 1 as shown above

STEP 4)

Get Sumit Patel’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

After starting from each character following till the last element to right
you encounter 0 or 1 you will store it a string and at last reverse the string
It will be code-word for the symbol.

For Example -> for E from starting from E and following
E from table it will follow the arrow and reach 1 at last 2nd column and then 0 at last column . Hence string will have “10” reversing it
we will have “01” i.e codeword for ‘E’

Similarly for BLANK it will encounter ‘1’ in first column then ‘1’ in 3rd column
‘0’ in last second column hence sting will be “1100” reversing it we get
“0011” you can check for all the Symbols and get the final codeword table provided below

STEP 5)

Simply substitute the keyword for each Symbol(character) .

Step 6) Finding the evaluation metrices:

original size would be
The original message had 14 characters each of 1 byte

so Original size= 14*8 =112 bits

size of compressed image= 36 bits
hence compression ratio = ((112–36)/36) *100 %=67.85714

So in Conclusion in 6 easy steps you can compress using huffman coding

and decompress it too.

Now for practice you can solve below question provided Thanks
Homework question :

try to solve it solution provided below

Author: Sumit Patel
Acknowledgments:
I would like to thank Dr Kiran Talele Sir for assigning this topic and for the valuable lecture materials that helped shape this blog. The concepts and visuals presented here were greatly inspired by their teaching.