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