Friday, 23 May 2014

Huffman Compression and Huffman Tree



Hi folks
We used ASCII code for represent character inside of computer. there are two types of ASCII 7 bit and 8bit.8bit ASCII is known as extended ASCII.
In 7 bit ASCII if represent text  following manner 

ABCDACDCAB     (Each character takes 7 bit)

Total Bit   = No. of character * 7
Total Bit   =  10*7
Total Bit   = 70

If consider frequency of character then we’ll find

Frequency of A = 3
Frequency of B = 2
Frequency of C = 3
Frequency of D = 2

In 7 bit ASCII we can represent 127 characters but it’s not always necessary that each character appeared in string as in our example string. There is only four characters which are repeated  so if we used 3 bit for code then we’ll save some bit
i.e. A=000
      B=001
      C=100
      D=101
Now total bit required 10*3 which is 30 instead of 70.



So far Huffman compression technique follows same approach for compression we first find the repeated character then assign bit stream.

It’s not necessary always to make equal bit stream for each character we can also use variable length

i.e    A=0
        B=01
        C=11
        D=111
To minimize the complexity of identified character stream. We use prefix and if any character has assign a code then no one will get the same.