It is an application of Greedy’s Algorithm. It can be explained as transmission of data in minimum number of binary bits.
Let us consider an example,
Suppose if we need to transmit a string “ttpl oks lssao ahi h”
We have - 2 t’s, 2 h’s, 1 i’s, 3 s’s, 2 o’s, 2 a’s, 2 l’s, 1 p’s
Writing in ascending order (we can write in descending order also…)
Character Frequency
- i 1
- p 1
- k 1
- t 2
- h 2
- o 2
- a 2
- l 2
- s 3
- sp(“ ”) 4
There are 10 different characters so nearest 2 power greater than 10 is 16. Therefore, each character can have 4 bits minimum to have unique code.(24=16)
Then total no of bits transmitted = 4*(1+1+1+2+2+2+2+2+3+4) = 88 bits.
Now, let’s use huffman code tree
Constructing huffman code tree:
i p k t h o a l s sp
1 1 1 2 2 2 2 2 3 4
Combining two nodes of minimum frequency (take maximum frequencies if you considered in descending order..)
![](https://codelido.com/assets/files/2022-08-24/1661368192-759251-image.png)
Continuing the same process until the no of nodes is one
![](https://codelido.com/assets/files/2022-08-24/1661368253-270184-image.png)
![](https://codelido.com/assets/files/2022-08-24/1661368264-120275-image.png)
Consider left edge of node is 0 and right edge of node is 1 after tree construction
![](https://codelido.com/assets/files/2022-08-24/1661368298-251981-image.png)
Traversing from root for every character we get,
Character Frequency Obtained Code No of bits allocated(Each x frequency)
- i 1 1000 4*1=4
- p 1 1001 4*1=4
- k 1 1100 4*1=4
- t 2 1101 4*2=8
- h 2 000 3*2=6
- o 2 001 3*2=6
- a 2 010 3*2=6
- l 2 011 3*2=6
- s 3 101 3*3=9
- sp(“ ”) 4 111 3*4=12
—————————————————–
Total bits: 65
Therefore, instead of sending 88 bits we can send only 65 bits using huffman coding.
Obtained code - 11011101100101111100111001011110011011010100011110100001000111000
When the receiver gets this huffman code tree, he can decode the obtained binary format into normal format.