RAW/AliTPCHuffman.cxx

   1 /**************************************************************************
   2  * Copyright(c) 1998-2003, ALICE Experiment at CERN, All rights reserved. *
   3  *                                                                        *
   4  * Author: The ALICE Off-line Project.                                    *
   5  * Contributors are mentioned in the code where appropriate.              *
   6  *                                                                        *
   7  * Permission to use, copy, modify and distribute this software and its   *
   8  * documentation strictly for non-commercial purposes is hereby granted   *
   9  * without fee, provided that the above copyright notice appears in all   *
  10  * copies and that both the copyright notice and this permission notice   *
  11  * appear in the supporting documentation. The authors make no claims     *
  12  * about the suitability of this software for any purpose. It is          *
  13  * provided "as is" without express or implied warranty.                  *
  14  **************************************************************************/
  15 /* $Id:*/
  16 ////////////////////////////////////////////////
  17 //  Huffman classes for set:TPC               //
  18 ////////////////////////////////////////////////
  19 //This file contains two classes and it implements
  20 //the Huffman algorithm for creating tables
  21 //used in the compression phase.
  22 //The class AliTPCHNode represents a node of the Huffman tree, while
  23 //the class AliTPCHTable represents a compression table
  24
  25 #include <TObjArray.h>
  26 #include <Riostream.h>
  27 #include <TMath.h>
  28 #include "AliTPCBuffer160.h"
  29 #include "AliTPCHuffman.h"
  30
  31 ClassImp(AliTPCHNode)
  32
  33 AliTPCHNode::AliTPCHNode(){
  34   //Constructor
  35   fLeft=0;
  36   fRight=0;
  37 }
  38
  39 //////////////////////////////////////////////////////////////////////////////
  40
  41 AliTPCHNode::AliTPCHNode(Int_t sym, Double_t freq){
  42   //Standard constructor
  43   fSymbol=sym;
  44   fFrequency=freq;
  45   fLeft=0;
  46   fRight=0;
  47 }
  48
  49 //////////////////////////////////////////////////////////////////////////////
  50
  51 AliTPCHNode::AliTPCHNode(const AliTPCHNode &source){
  52   //Copy Constructor
  53   if(&source == this) return;
  54   this->fSymbol = source.fSymbol;
  55   this->fFrequency = source.fFrequency;
  56   this->fLeft = source.fLeft;
  57   this->fRight = source.fRight;
  58   return;
  59 }
  60
  61 //////////////////////////////////////////////////////////////////////////////
  62
  63 AliTPCHNode& AliTPCHNode::operator=(const AliTPCHNode &source){
  64   //Assignment operator
  65   if(&source == this) return *this;
  66   this->fSymbol = source.fSymbol;
  67   this->fFrequency = source.fFrequency;
  68   this->fLeft = source.fLeft;
  69   this->fRight = source.fRight;
  70   return *this;
  71 }
  72
  73 //////////////////////////////////////////////////////////////////////////////
  74
  75 Int_t AliTPCHNode::Compare(const TObject *obj)const{
  76   //Function called by Sort method of TObjArray
  77   AliTPCHNode *node=(AliTPCHNode *)obj;
  78   Double_t f=fFrequency;
  79   Double_t fo=node->fFrequency;
  80   if (f<fo) return 1;
  81   else if (f>fo) return -1;
  82   else return 0;
  83 }
  84
  85 //////////////////////////////////////////////////////////////////////////////
  86 //////////////////////////////////////////////////////////////////////////////
  87 //////////////////////////////////////////////////////////////////////////////
  88
  89 ClassImp(AliTPCHTable)
  90
  91 AliTPCHTable::AliTPCHTable(){
  92   //Constructor
  93   fCodeLen=0;
  94   fCode=0;
  95   fHNodes=0;
  96   fNnodes=0;
  97   fNum=0;
  98   fVerbose=0;
  99 }
 100
 101 //////////////////////////////////////////////////////////////////////////////
 102
 103 AliTPCHTable::AliTPCHTable(Int_t size){
 104   //Initialization
 105   fSize=size;
 106   fCodeLen = new UChar_t[fSize];
 107   fCode = new Double_t[fSize];
 108   fHNodes = new TObjArray;
 109   fNnodes=0;
 110   fNum=0;
 111   fVerbose=0;
 112   fSym= new Short_t[fSize];
 113   for (Short_t i=0;i<fSize;i++) {
 114     fSym[i]=i;
 115   }//end for
 116   ClearTable();
 117 }
 118
 119 //////////////////////////////////////////////////////////////////////////////
 120
 121 AliTPCHTable::AliTPCHTable(const AliTPCHTable &source){
 122   //Copy Constructor
 123   if(&source == this) return;
 124   this->fSize = source.fSize;
 125   this->fCodeLen = source.fCodeLen;
 126   this->fCode = source.fCode;
 127   this->fSym = source.fSym;
 128   this->fHNodes = source.fHNodes;
 129   this->fNnodes = source.fNnodes;
 130   this->fNum=source.fNum;
 131   this->fVerbose=source.fVerbose;
 132   return;
 133 }
 134
 135 //////////////////////////////////////////////////////////////////////////////
 136
 137 AliTPCHTable& AliTPCHTable::operator=(const AliTPCHTable &source) {
 138   //Assignment operator
 139   if(&source == this) return *this;
 140   this->fSize = source.fSize;
 141   this->fCodeLen = source.fCodeLen;
 142   this->fCode = source.fCode;
 143   this->fSym = source.fSym;
 144   this->fHNodes = source.fHNodes;
 145   this->fNnodes = source.fNnodes;
 146   this->fNum=source.fNum;
 147   this->fVerbose=source.fVerbose;
 148   return *this;
 149 }
 150
 151 //////////////////////////////////////////////////////////////////////////////
 152
 153 AliTPCHTable::~AliTPCHTable(){
 154   //HTable destructor
 155   if(fVerbose)
 156     cout<<"HTable destructor !\n";
 157   if (fCodeLen) delete[] fCodeLen;
 158   if (fCode) delete [] fCode;
 159   if (fHNodes) {
 160     fHNodes->Delete(); //Clear out the collection and deletes the removed objects
 161     delete fHNodes;
 162   }//end if
 163 }
 164
 165 //////////////////////////////////////////////////////////////////////////////
 166
 167 void AliTPCHTable::SetCodeLen(UChar_t len,Int_t val){
 168   //Sets codelength of "val" to the variable "len"
 169   fCodeLen[val]=len;
 170   return;
 171 }
 172
 173 //////////////////////////////////////////////////////////////////////////////
 174
 175 void AliTPCHTable::SetCode(Double_t code,Int_t val){
 176   //Sets the binary code of the variable "val"
 177   fCode[val]=code;
 178   return;
 179 }
 180
 181 //////////////////////////////////////////////////////////////////////////////
 182
 183 void AliTPCHTable::PrintTable()const{
 184   //This method prints a table
 185   cout<<"Table for Huffman coding\n";
 186   cout<<"  Symbol|   Code   |   Length \n";
 187   for (Int_t i=0;i<fSize;i++){
 188     if (fCodeLen[i]){
 189       cout.width(6);cout<<fSym[i];
 190       cout.width(3);cout<<"|";
 191       cout.width(6);cout<<hex<<(ULong_t)fCode[i]<<dec;
 192       cout.width(5);cout<<"|";
 193       cout.width(6);cout<<(ULong_t)fCodeLen[i]<<endl;
 194     }//end if
 195   }//end for
 196 }
 197
 198 //////////////////////////////////////////////////////////////////////////////
 199
 200 Bool_t AliTPCHTable::SpanTree(AliTPCHNode *start, ULong_t code, UChar_t len){
 201   //Hoffman codes are generated spanning the Huffman tree
 202   //In an Huffman tree any internal node has always two children
 203   AliTPCHNode * visited;
 204   visited = start;
 205   Int_t idx=visited->GetSymbol();
 206   if (!visited->GetLeft()) {
 207     fCode[idx] = code;
 208     fCodeLen[idx] = len;
 209     return kTRUE;
 210   }//end if
 211   SpanTree(visited->GetLeft(), code << 1, len + 1);
 212   SpanTree(visited->GetRight(), code << 1 | 0x0001, len + 1);
 213   return kTRUE;
 214 }
 215
 216 //////////////////////////////////////////////////////////////////////////////
 217
 218 void AliTPCHTable::ResetHNodes(){
 219   //Reset number of HNodes and the HNodes array
 220   if (fHNodes)  fHNodes->Clear();
 221   if (fNnodes)  fNnodes=0;
 222 }
 223
 224 //////////////////////////////////////////////////////////////////////////////
 225
 226 void AliTPCHTable::ClearTable(){
 227   //Clear the table
 228   memset(fCodeLen,0,sizeof(UChar_t)*fSize);
 229   memset(fCode,0,sizeof(Double_t)*fSize);
 230 }
 231
 232 //////////////////////////////////////////////////////////////////////////////
 233
 234 Int_t  AliTPCHTable::GetFrequencies(const char *fname){
 235   //It fills the "fCode" array with the frequencies of the symbols read from the file
 236   AliTPCBuffer160 buff(fname,0);
 237   ULong_t numberOfWords=0;
 238   Int_t val;
 239   while((val=buff.GetNext())!=-1){
 240     fCode[val]++;
 241     fNum++;
 242     numberOfWords++;
 243   }
 244   cout<<"Total number of words: "<<numberOfWords<<endl;
 245   //Print out the frequencies
 246   /*
 247     for (Int_t i=0;i<fSize;i++){
 248     if (fCode[i])cout<<"Symbol: "<<i<<" Freq: "<<fCode[i]<<endl;
 249     }
 250     cout<<endl;
 251   */
 252   return 0;
 253 }
 254
 255 Int_t AliTPCHTable::SetValFrequency(const Int_t Val,Double_t Value){
 256   //This method sets to "Value" the frequency of the symbol "Val"
 257   fCode[Val]=Value;
 258   fNum=1;
 259   return 0;
 260 }
 261
 262 //////////////////////////////////////////////////////////////////////////////
 263
 264 Int_t AliTPCHTable::SetFrequency(const Int_t Val){
 265   //It increments by one the frequency of the symbol "Val" whose frequency is
 266   //stored in the fCode array
 267   fCode[Val]++;
 268   fNum++;
 269   return 0;
 270 }
 271
 272 //////////////////////////////////////////////////////////////////////////////
 273
 274 Int_t AliTPCHTable::NormalizeFrequencies(){
 275   //This method normalized the frequencies
 276   //Frequencies normalization
 277   Double_t sum=0.;
 278   for (Int_t i=0; i< fSize; i++) {
 279     sum+=fCode[i];
 280   }//end for
 281   if (fVerbose){
 282     cout<<"Frequency sum: "<<sum<<endl;
 283   }//end if
 284   if(sum!=0.){
 285     for (Int_t i=0; i< fSize; i++) {
 286       fCode[i]/=sum;
 287       if ((fCode[i]!=0.) && (fCode[i]<10e-20))cout<<"Frequency value very small !!! "<<fCode[i]<<endl;
 288     }//end for
 289   }
 290   return 0;
 291 }
 292 //////////////////////////////////////////////////////////////////////////////
 293 Int_t AliTPCHTable::StoreFrequencies(const char *fname)const{
 294   //It stores the frequencies in a text file
 295   ofstream ftxt(fname);
 296   for (Int_t i=0;i<fSize;i++){
 297     ftxt<<fCode[i]<<endl;
 298   }
 299   ftxt.close();
 300   return 0;
 301 }
 302
 303 //////////////////////////////////////////////////////////////////////////////
 304
 305 void AliTPCHTable::CompleteTable(Int_t k){
 306   //According to the kind of table (0..4) it associates a dummy frequency (1) to
 307   //every symbols whose real frequency is zero, in a given range 0..max
 308   Int_t max;
 309   ULong_t val;
 310   switch(k){
 311   case 0:
 312     max=fSize;
 313     val=1;
 314     break;
 315   case 1:
 316     max=445;
 317     val=1;
 318     break;
 319   default:
 320     max=fSize;
 321     val=1;
 322     break;
 323   }//end switch
 324
 325   for(Int_t i=0;i<max;i++){
 326     if(fCode[i]==0.0)fCode[i]=val;
 327   }
 328   return;
 329 }
 330
 331 //////////////////////////////////////////////////////////////////////////////
 332
 333 Double_t  AliTPCHTable::GetEntropy()const{
 334   //This method calculates the value of the entropy
 335   Double_t entropy=0;
 336   Double_t prob=0;
 337   for (Int_t i=0;i<fSize;i++){
 338     if (fCode[i]){
 339       prob=fCode[i]/(Double_t)fNum;
 340       entropy+=prob*(TMath::Log2(prob));
 341     }
 342   }
 343   return -entropy;
 344 }
 345
 346 //////////////////////////////////////////////////////////////////////////////
 347
 348 Int_t AliTPCHTable::BuildHTable(){
 349   //It builds a Huffman tree
 350   if(GetWordsNumber()){
 351     for (Int_t i=0; i< fSize; i++) {
 352       if (fCode[i] > 0.){
 353         fNnodes++;
 354         //cout<< "Symbol:"<<i<<" Freq:"<<fCode[i]<<endl;
 355         fHNodes->Add(new AliTPCHNode(i,fCode[i]));
 356       }//end if
 357     }//end for
 358     Int_t nentries=fHNodes->GetEntriesFast();
 359     //cout<<"Number of symbols: "<<nentries<<endl;
 360     Int_t nindex=nentries-1;
 361     while (nindex > 0){
 362       fHNodes->Sort(nindex+1);
 363       AliTPCHNode *aux = new AliTPCHNode(0,0);
 364       AliTPCHNode *node= (AliTPCHNode*)fHNodes->UncheckedAt(nindex-1);
 365       AliTPCHNode *node1= (AliTPCHNode*)fHNodes->UncheckedAt(nindex);
 366
 367       aux->SetLeft(node);
 368       aux->SetRight(node1);
 369       aux->SetFrequency(node->GetFrequency() + node1->GetFrequency());
 370       fHNodes->RemoveAt(nindex-1);
 371       fHNodes->AddAt(aux,nindex-1);
 372       nindex--;
 373     }//end while
 374     ClearTable();
 375     AliTPCHNode *start= (AliTPCHNode*)fHNodes->UncheckedAt(0);
 376     SpanTree(start,0,0);
 377   }//end if
 378   else{
 379     cout<<"Table contains 0 elements\n";
 380   }//end else
 381   return 0;
 382 }
 383 //////////////////////////////////////////////////////////////////////////////