What is Huffman Code in DAA | Algorithm

 What is Huffman Code in DAA | Algorithm....

What is Huffman Code in DAA?

----> Huffman Code is the technique in which it is use for calculating variable length or Code for given s             strings

----->Normally there are two types of coding skills                                                                                                                        1. Fixed length coding skill                                                                                                                                2. Variable length coding skill

-----> In Fixed Length encoding the variable are encoded accordingly to linear skill with 0 and 1 prefix                for example,  0 → 0 ,  4 → 100,  5 → 101, etc....

-----> For calculating the exact appearance of actual frequency of variable length coding is used it                        actually calculating the appearance of 0 and 1 with minimum time. 

Algorithm:

-----> HUFFMAN(C)

          n ← |C|

          Q ← C

          for i ← 1 to n-1

             do allocate a new node Z

                     x ← left[Z] ← EXTRACT - min(Q)

                     y ← right[Z] ← EXTRACT - min(Q)

             

             f[x] ← f[x] + f[y]

             Insert (Q,Z)

             return EXTRACT - min(Q)

Steps in Huffman code

Example:  a: 45,  b: 13,  c: 12,  d: 16,  e: 9,  f: 5

Solution: 

Step 1: Arrange the node in increasing order of frequency 

             

                       
Step 2: Add the two minimum numbers from the items 

                                          

Step 3:  Arrange the step 2 in increasing order in items

                
Step 4: Repeat Step 2and 3 until tree done

         

                              

             

            

                


                         

Step 5: In this step we allot the 0's and 1's in the path as 

                               left → 0

                               right → 1

                          

The solution is as:  a: 45 → 0

                               b: 13 → 101

                               c: 12 → 100

                               d: 16 → 111

                               e: 9 →  1101

                               f: 5 → 1100

Example 1:  a: 50,  b: 25,  c: 15,  d: 40,  e: 75