Huffman Coding

• Proposed by Dr. David A. Huffman in 1952

–        “A Method for the Construction of Minimum Redundancy Codes”

• Applicable to many forms of data transmission

               

Algorithm for Huffman Tree

1. Construct a set of trees with root nodes that contain each of the individual symbols and their weights.
2. Place the set of trees into a priority queue.
3. while the priority queue has more than one item
4. Remove the two trees with the smallest weights.
5. Combine them into a new binary tree in which the weight of the tree root is the sum of the weights of its children.
6. Insert the newly created tree back into the priority queue.

• Huffman coding is a technique used to compress files for transmission
• Uses statistical coding

–        more frequently used symbols have shorter code words

• Works well for text and fax transmissions
• An application that uses several data structures 

#include<iostream>
#include<string>
#include<iomanip>
#define MAX 26

using namespace std;

typedef struct HuffTree
{
 char sym;
 int weight;
 struct HuffTree *left;
 struct HuffTree *right;
}Node;

void Min_Heap(HuffTree *Heap[],int Index, HuffTree *p)
{
 int par;  

 Index = Index+1;
 while(Index > 0)
 { par = int((Index-1)/2); // Parent
  if(p->weight >= Heap[par]->weight)
  {
   Heap[Index] = p;
   return;
  }
  Heap[Index] = Heap[par];
  Index = par;
 }
 Heap[0] = p;

}

Node* Delete_Heap(Node *hp[],int *n)
{
 Node *ptr = hp[0];
 Node *last = hp[*n];
 hp[*n] = NULL;
 *n = *n-1;
 int k = 0, left = 1, right = 2;
 while(right <= *n)
 {
  if((last->weight <= hp[left]->weight) && (last->weight <= hp[right]->weight))
  {
   hp[k] = last;
   return(ptr);
  }
  if(hp[left]->weight <= hp[right]->weight)
  {
   hp[k] = hp[left];
   k = left;
  }
  else
  { hp[k] = hp[right];
   k = right;
  }
  left = 2*k+1;
  right = left+1;
 }
 if((left == *n) && (last->weight > hp[left]->weight))
 {
  hp[k] = hp[left];
  k = left;
 }
 hp[k] = last;

 return(ptr);
}

Node* HuffmanTree(Node *hp[],int n)
{
 n--;
 while(n)
 {
  Node *p1 = Delete_Heap(hp,&n);
  Node *p2 = Delete_Heap(hp,&n);
  Node *p = new Node;

  p->sym = '*';
  p->weight = p1->weight + p2->weight;
  p->left = p1;
  p->right = p2;

  Min_Heap(hp,n++,p);
 }
 return(hp[0]);
}

void Genetarte_Codes(HuffTree *root,int i)
{
 static char s[MAX];

 if(root->left)
 {
  s[i] = '0';
  Genetarte_Codes(root->left,i+1);
 }
 if(root->right)
 {
  s[i] = '1';
  Genetarte_Codes(root->right,i+1);
 }
 if(root->left==NULL && root->right==NULL)
 {
  cout<<" "<<root->sym<<"->";
  for(int j=0;j<i;j++)
   cout<<" "<<s[j];

   cout<<endl;
 }
}


void main()
{
 Node* HuffmanTree(Node *heap[],int n);
 
 char symb[MAX+1] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','\0'};
 int freq[MAX] = {200,106,170,64,63,57,57,51,48,47,32,32,23,22,21,20,18,16,15,15,13,8,5,1,1,1};

 //char symb[MAX+1] = {'E','e','r','i','y','s','n','a','l','k','.','\0'};
 //int freq[MAX] = {1,8,2,1,1,2,2,2,1,1,1};

 Node *heap[MAX];

 for(int i=0;i<MAX;i++)
 {
  Node *p = new Node;
  p->sym = symb[i];
  p->weight = freq[i];
  p->left = p->right = NULL;

  Min_Heap(heap,i-1,p);
 }

 Node *root = HuffmanTree(heap,MAX);
  
 Genetarte_Codes(root,0);
}