ITS/UPGRADE/compression/Huffman.C

   1 #include "TMath.h"
   2 #include "TH1.h"
   3 #include "TArrayI.h"
   4 #include "TArrayF.h"
   5
   6 #define MAX_TREE_HT 100
   7
   8 struct MH_Node
   9 {
  10   int character;
  11   float frequency;
  12   struct MH_Node *l, *r;
  13 };
  14
  15
  16 struct M_Heap
  17 {
  18   unsigned size;
  19   unsigned space;
  20   struct MH_Node **array;
  21 };
  22
  23 struct MH_Node* newNode(int character, float frequency)
  24 {
  25   struct MH_Node* temp = (struct MH_Node*) malloc(sizeof(struct MH_Node));
  26   temp->l = temp->r = NULL;
  27   temp->character = character;
  28   temp->frequency = frequency;
  29   return temp;
  30 }
  31
  32
  33 struct M_Heap* createM_Heap(unsigned space)
  34 {
  35   struct M_Heap* M_Heap = (struct M_Heap*) malloc(sizeof(struct M_Heap));
  36   M_Heap->size = 0;
  37   M_Heap->space = space;
  38   M_Heap->array = (struct MH_Node**)malloc(M_Heap->space * sizeof(struct MH_Node*));
  39   return M_Heap;
  40 }
  41
  42
  43 void swapMH_Node(struct MH_Node** a, struct MH_Node** b)
  44 {
  45   struct MH_Node* t = *a;
  46   *a = *b;
  47   *b = t;
  48 }
  49
  50
  51 void M_Heapify(struct M_Heap* M_Heap, int idx)
  52 {
  53   // arrange in increasing frequency order
  54   for (int i=idx;i<M_Heap->size;i++) {
  55     for (int j=i+1;j<M_Heap->size;j++) {
  56       if (M_Heap->array[i]->frequency > M_Heap->array[j]->frequency)
  57         swapMH_Node(&M_Heap->array[i], &M_Heap->array[j]);
  58     }
  59   }
  60 }
  61
  62 int isSizeOne(struct M_Heap* M_Heap)
  63 {
  64   return (M_Heap->size == 1);
  65 }
  66
  67
  68 struct MH_Node* extractMin(struct M_Heap* M_Heap)
  69 {
  70   struct MH_Node* temp = M_Heap->array[0];
  71   M_Heap->array[0] = M_Heap->array[M_Heap->size - 1];
  72   --M_Heap->size;
  73   M_Heapify(M_Heap, 0);
  74   return temp;
  75 }
  76
  77
  78 void insertM_Heap(struct M_Heap* M_Heap, struct MH_Node* MH_Node)
  79 {
  80   //  printf("Insert %f\n",MH_Node->frequency);
  81   int i = M_Heap->size - 1;
  82   if (i<0) {
  83     M_Heap->array[M_Heap->size++] = MH_Node;
  84     return;
  85   }
  86   M_Heap->array[M_Heap->size] = MH_Node;
  87   ++M_Heap->size;
  88   M_Heapify(M_Heap, 0);
  89 }
  90
  91
  92 void buildM_Heap(struct M_Heap* M_Heap)
  93 {
  94   M_Heapify(M_Heap, 0);
  95 }
  96
  97
  98 void printArr(int arr[], int n)
  99 {
 100   int i;
 101   for (i = 0; i < n; ++i) printf("%d", arr[i]);
 102   printf("\n");
 103 }
 104
 105
 106 int isLeaf(struct MH_Node* root)
 107 {
 108   return !(root->l) && !(root->r) ;
 109 }
 110
 111
 112 struct M_Heap* createAndBuildM_Heap(int character[], float frequency[], int size)
 113 {
 114   int i;
 115   struct M_Heap* M_Heap = createM_Heap(size);
 116   for (i = 0; i < size; ++i) M_Heap->array[i] = newNode(character[i], frequency[i]);
 117   M_Heap->size = size;
 118   buildM_Heap(M_Heap);
 119   return M_Heap;
 120 }
 121
 122 struct MH_Node* buildHuffmanTree(int character[], float frequency[], int size)
 123 {
 124   struct MH_Node *l, *r, *top;
 125   struct M_Heap* M_Heap = createAndBuildM_Heap(character, frequency, size);
 126   while (!isSizeOne(M_Heap)) {
 127     l = extractMin(M_Heap);
 128     r = extractMin(M_Heap);
 129     top = newNode('$', l->frequency + r->frequency);
 130     top->l = l;
 131     top->r = r;
 132     insertM_Heap(M_Heap, top);
 133   }
 134   return extractMin(M_Heap);
 135 }
 136
 137 float printCodes(struct MH_Node* root, int arr[], int top)
 138 {
 139   float totsiz = 0;
 140   if (root->l)
 141     {
 142       arr[top] = 0;
 143       totsiz += printCodes(root->l, arr, top + 1);
 144     }
 145   if (root->r)
 146     {
 147       arr[top] = 1;
 148       totsiz += printCodes(root->r, arr, top + 1);
 149     }
 150   if (isLeaf(root))
 151     {
 152       printf("%d: (%f) ", root->character, root->frequency);
 153       totsiz += top*root->frequency;
 154       printArr(arr, top);
 155     }
 156   return totsiz;
 157 }
 158
 159 void HuffmanCodes(int character[], float frequency[], int size)
 160 {
 161   struct MH_Node* root = buildHuffmanTree(character, frequency, size);
 162   int arr[MAX_TREE_HT], top = 0;
 163   int defNbits = 1 + TMath::Log2(size);
 164   double freqNorm = 0;
 165   for (int i=0;i<size;i++) {
 166     freqNorm += frequency[i];
 167   }
 168   float packSize = printCodes(root, arr, top);
 169   //
 170   printf("Brute force: %d vs %f coded\n",defNbits,packSize/freqNorm);
 171
 172 }
 173
 174 void HuffmanCodes(TH1* histo, int maxBin=-1)
 175 {
 176   int nb = histo->GetNbinsX();
 177   if (maxBin>1 && nb>maxBin) nb = maxBin;
 178   TArrayI dat(nb);
 179   TArrayF frq(nb);
 180   for (int i=0;i<nb;i++) {
 181     dat[i] = i;
 182     frq[i] = histo->GetBinContent(i+1);
 183   }
 184   HuffmanCodes(dat.GetArray(),frq.GetArray(),nb);
 185   //
 186 }