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