]>
Commit | Line | Data |
---|---|---|
2e9f335b | 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 | **************************************************************************/ | |
a79660fb | 15 | /* $Id:*/ |
2e9f335b | 16 | //////////////////////////////////////////////// |
17 | // Huffman classes for set:TPC // | |
18 | //////////////////////////////////////////////// | |
a79660fb | 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 | ||
2e9f335b | 25 | #include <TObjArray.h> |
b62e2a95 | 26 | #include <Riostream.h> |
27 | #include <TMath.h> | |
2e9f335b | 28 | #include "AliTPCBuffer160.h" |
b62e2a95 | 29 | #include "AliTPCHuffman.h" |
2e9f335b | 30 | |
31 | ClassImp(AliTPCHNode) | |
32 | ||
33 | AliTPCHNode::AliTPCHNode(){ | |
a79660fb | 34 | //Constructor |
2e9f335b | 35 | fLeft=0; |
36 | fRight=0; | |
37 | } | |
38 | ||
39 | ////////////////////////////////////////////////////////////////////////////// | |
40 | ||
41 | AliTPCHNode::AliTPCHNode(Int_t sym, Double_t freq){ | |
a79660fb | 42 | //Standard constructor |
2e9f335b | 43 | fSymbol=sym; |
44 | fFrequency=freq; | |
45 | fLeft=0; | |
46 | fRight=0; | |
47 | } | |
48 | ||
49 | ////////////////////////////////////////////////////////////////////////////// | |
50 | ||
51 | AliTPCHNode::AliTPCHNode(const AliTPCHNode &source){ | |
a79660fb | 52 | //Copy Constructor |
2e9f335b | 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){ | |
a79660fb | 64 | //Assignment operator |
2e9f335b | 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{ | |
a79660fb | 76 | //Function called by Sort method of TObjArray |
2e9f335b | 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(){ | |
a79660fb | 92 | //Constructor |
2e9f335b | 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){ | |
a79660fb | 104 | //Initialization |
2e9f335b | 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){ | |
a79660fb | 122 | //Copy Constructor |
2e9f335b | 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) { | |
a79660fb | 138 | //Assignment operator |
2e9f335b | 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(){ | |
a79660fb | 154 | //HTable destructor |
2e9f335b | 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){ | |
a79660fb | 168 | //Sets codelength of "val" to the variable "len" |
2e9f335b | 169 | fCodeLen[val]=len; |
170 | return; | |
171 | } | |
172 | ||
173 | ////////////////////////////////////////////////////////////////////////////// | |
174 | ||
175 | void AliTPCHTable::SetCode(Double_t code,Int_t val){ | |
a79660fb | 176 | //Sets the binary code of the variable "val" |
2e9f335b | 177 | fCode[val]=code; |
178 | return; | |
179 | } | |
180 | ||
181 | ////////////////////////////////////////////////////////////////////////////// | |
182 | ||
183 | void AliTPCHTable::PrintTable()const{ | |
a79660fb | 184 | //This method prints a table |
2e9f335b | 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){ | |
a79660fb | 201 | //Hoffman codes are generated spanning the Huffman tree |
2e9f335b | 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(){ | |
a79660fb | 219 | //Reset number of HNodes and the HNodes array |
2e9f335b | 220 | if (fHNodes) fHNodes->Clear(); |
221 | if (fNnodes) fNnodes=0; | |
222 | } | |
223 | ||
224 | ////////////////////////////////////////////////////////////////////////////// | |
225 | ||
226 | void AliTPCHTable::ClearTable(){ | |
a79660fb | 227 | //Clear the table |
2e9f335b | 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){ | |
a79660fb | 235 | //It fills the "fCode" array with the frequencies of the symbols read from the file |
2e9f335b | 236 | AliTPCBuffer160 buff(fname,0); |
a79660fb | 237 | ULong_t numberOfWords=0; |
238 | Int_t val; | |
239 | while((val=buff.GetNext())!=-1){ | |
240 | fCode[val]++; | |
2e9f335b | 241 | fNum++; |
a79660fb | 242 | numberOfWords++; |
2e9f335b | 243 | } |
a79660fb | 244 | cout<<"Total number of words: "<<numberOfWords<<endl; |
2e9f335b | 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){ | |
a79660fb | 256 | //This method sets to "Value" the frequency of the symbol "Val" |
2e9f335b | 257 | fCode[Val]=Value; |
258 | fNum=1; | |
259 | return 0; | |
260 | } | |
261 | ||
262 | ////////////////////////////////////////////////////////////////////////////// | |
263 | ||
264 | Int_t AliTPCHTable::SetFrequency(const Int_t Val){ | |
a79660fb | 265 | //It increments by one the frequency of the symbol "Val" whose frequency is |
266 | //stored in the fCode array | |
2e9f335b | 267 | fCode[Val]++; |
268 | fNum++; | |
269 | return 0; | |
270 | } | |
271 | ||
272 | ////////////////////////////////////////////////////////////////////////////// | |
273 | ||
9f992f70 | 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 | ////////////////////////////////////////////////////////////////////////////// | |
a79660fb | 293 | Int_t AliTPCHTable::StoreFrequencies(const char *fname)const{ |
294 | //It stores the frequencies in a text file | |
2e9f335b | 295 | ofstream ftxt(fname); |
296 | for (Int_t i=0;i<fSize;i++){ | |
9f992f70 | 297 | ftxt<<fCode[i]<<endl; |
2e9f335b | 298 | } |
299 | ftxt.close(); | |
300 | return 0; | |
301 | } | |
302 | ||
303 | ////////////////////////////////////////////////////////////////////////////// | |
304 | ||
305 | void AliTPCHTable::CompleteTable(Int_t k){ | |
a79660fb | 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 | |
2e9f335b | 308 | Int_t max; |
309 | ULong_t val; | |
310 | switch(k){ | |
311 | case 0: | |
c9bd9d3d | 312 | max=fSize; |
2e9f335b | 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{ | |
a79660fb | 334 | //This method calculates the value of the entropy |
2e9f335b | 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(){ | |
a79660fb | 349 | //It builds a Huffman tree |
2e9f335b | 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 | } | |
2e9f335b | 383 | ////////////////////////////////////////////////////////////////////////////// |