What is Hufffman Algorithm?

 Huffman Algorithm is an encoding technique for symbols where most frequently occurring symbols are represented with short length bit strings and least frequently occurring symbols are represented with long bit strings.


Algorithm
 Huffman(c: symbols a[i] with frequencies w[i]=1,2,3.......n)

F: forest of n rooted trees,each consisting of the single vertex a[i] and assigned weight w[i] in ascending order of w[i] while F is not a tree.

i)Start
  Replace the rooted trees T and T ' of least weight from F with w(T ) >= w(T ') with a tree hvaing a new root that has T as its left sub tree and T ' as its right sub tree label new edge to T with 0 and new edge to T ' with 1
Assign w(T) + w(T ') as weight of new tree.



ii)End


Example
   Use Huffman algorithm to encode the following symbols with frequencies listed as A : 0.5 , B : 0.2 ,C : 0.2
   and D : 0.1.And also calculate average number of bits used to encode the symbols.
 Sol-
        Symbols                      Frequency
          A                                  0.5
          B                                  0.2
          C                                  0.2
          D                                  0.1

       Symbols                     Assigned Bit
          A                                1
          B                                000
          C                                01
          D                                001

Average number of bit =1*0.5+3*0.2+2*0.2+3*0.1
                                  =1.8       ans    


USES
  1>It is fundamental algorithm in data compression.
 2> It lowers the transmittal time and also reduces memory uses.