1 /**************************************************************************
2 * Copyright(c) 1998-2003, ALICE Experiment at CERN, All rights reserved. *
4 * Author: The ALICE Off-line Project. *
5 * Contributors are mentioned in the code where appropriate. *
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 **************************************************************************/
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
25 #include <TObjArray.h>
27 #include "AliAltroBuffer.h"
28 #include "AliTPCHNode.h"
29 #include "AliTPCHTable.h"
31 ClassImp(AliTPCHTable)
33 AliTPCHTable::AliTPCHTable(){
43 //////////////////////////////////////////////////////////////////////////////
45 AliTPCHTable::AliTPCHTable(Int_t size){
48 fCodeLen = new UChar_t[fSize];
49 fCode = new Double_t[fSize];
50 fHNodes = new TObjArray;
54 fSym= new Short_t[fSize];
55 for (Short_t i=0;i<fSize;i++) {
61 //////////////////////////////////////////////////////////////////////////////
63 AliTPCHTable::AliTPCHTable(const AliTPCHTable &source)
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;
78 //////////////////////////////////////////////////////////////////////////////
80 AliTPCHTable& AliTPCHTable::operator=(const AliTPCHTable &source) {
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;
94 //////////////////////////////////////////////////////////////////////////////
96 AliTPCHTable::~AliTPCHTable(){
99 cout<<"HTable destructor !\n";
100 if (fCodeLen) delete[] fCodeLen;
101 if (fCode) delete [] fCode;
103 fHNodes->Delete(); //Clear out the collection and deletes the removed objects
108 //////////////////////////////////////////////////////////////////////////////
110 void AliTPCHTable::SetCodeLen(UChar_t len,Int_t val){
111 //Sets codelength of "val" to the variable "len"
116 //////////////////////////////////////////////////////////////////////////////
118 void AliTPCHTable::SetCode(Double_t code,Int_t val){
119 //Sets the binary code of the variable "val"
124 //////////////////////////////////////////////////////////////////////////////
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++){
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;
141 //////////////////////////////////////////////////////////////////////////////
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;
148 Int_t idx=visited->GetSymbol();
149 if (!visited->GetLeft()) {
154 SpanTree(visited->GetLeft(), code << 1, len + 1);
155 SpanTree(visited->GetRight(), code << 1 | 0x0001, len + 1);
159 //////////////////////////////////////////////////////////////////////////////
161 void AliTPCHTable::ResetHNodes(){
162 //Reset number of HNodes and the HNodes array
163 if (fHNodes) fHNodes->Clear();
164 if (fNnodes) fNnodes=0;
167 //////////////////////////////////////////////////////////////////////////////
169 void AliTPCHTable::ClearTable(){
171 memset(fCodeLen,0,sizeof(UChar_t)*fSize);
172 memset(fCode,0,sizeof(Double_t)*fSize);
175 //////////////////////////////////////////////////////////////////////////////
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;
182 while((val=buff.GetNext())!=-1){
187 cout<<"Total number of words: "<<numberOfWords<<endl;
188 //Print out the frequencies
190 for (Int_t i=0;i<fSize;i++){
191 if (fCode[i])cout<<"Symbol: "<<i<<" Freq: "<<fCode[i]<<endl;
198 Int_t AliTPCHTable::SetValFrequency(Int_t Val,Double_t Value){
199 //This method sets to "Value" the frequency of the symbol "Val"
205 //////////////////////////////////////////////////////////////////////////////
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
215 //////////////////////////////////////////////////////////////////////////////
217 Int_t AliTPCHTable::NormalizeFrequencies(){
218 //This method normalized the frequencies
219 //Frequencies normalization
221 for (Int_t i=0; i< fSize; i++) {
225 cout<<"Frequency sum: "<<sum<<endl;
228 for (Int_t i=0; i< fSize; i++) {
230 if ((fCode[i]!=0.) && (fCode[i]<10e-20))cout<<"Frequency value very small !!! "<<fCode[i]<<endl;
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;
246 //////////////////////////////////////////////////////////////////////////////
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
268 for(Int_t i=0;i<max;i++){
269 if(fCode[i]==0.0)fCode[i]=val;
274 //////////////////////////////////////////////////////////////////////////////
276 Double_t AliTPCHTable::GetEntropy()const{
277 //This method calculates the value of the entropy
280 for (Int_t i=0;i<fSize;i++){
282 prob=fCode[i]/(Double_t)fNum;
283 entropy+=prob*(TMath::Log2(prob));
289 //////////////////////////////////////////////////////////////////////////////
291 Int_t AliTPCHTable::BuildHTable(){
292 //It builds a Huffman tree
293 if(GetWordsNumber()){
294 for (Int_t i=0; i< fSize; i++) {
297 //cout<< "Symbol:"<<i<<" Freq:"<<fCode[i]<<endl;
298 fHNodes->Add(new AliTPCHNode(i,fCode[i]));
301 Int_t nentries=fHNodes->GetEntriesFast();
302 //cout<<"Number of symbols: "<<nentries<<endl;
303 Int_t nindex=nentries-1;
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);
311 aux->SetRight(node1);
312 aux->SetFrequency(node->GetFrequency() + node1->GetFrequency());
313 fHNodes->RemoveAt(nindex-1);
314 fHNodes->AddAt(aux,nindex-1);
318 AliTPCHNode *start= (AliTPCHNode*)fHNodes->UncheckedAt(0);
322 cout<<"Table contains 0 elements\n";
326 //////////////////////////////////////////////////////////////////////////////