]>
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 | |
26 | #include <TObjArray.h> | |
0f0615a3 | 27 | #include "Riostream.h" |
2e9f335b | 28 | #include "TMath.h" |
29 | #include "AliTPCHuffman.h" | |
30 | #include "AliTPCBuffer160.h" | |
31 | ||
32 | ClassImp(AliTPCHNode) | |
33 | ||
34 | AliTPCHNode::AliTPCHNode(){ | |
a79660fb | 35 | //Constructor |
2e9f335b | 36 | fLeft=0; |
37 | fRight=0; | |
38 | } | |
39 | ||
40 | ////////////////////////////////////////////////////////////////////////////// | |
41 | ||
42 | AliTPCHNode::AliTPCHNode(Int_t sym, Double_t freq){ | |
a79660fb | 43 | //Standard constructor |
2e9f335b | 44 | fSymbol=sym; |
45 | fFrequency=freq; | |
46 | fLeft=0; | |
47 | fRight=0; | |
48 | } | |
49 | ||
50 | ////////////////////////////////////////////////////////////////////////////// | |
51 | ||
52 | AliTPCHNode::AliTPCHNode(const AliTPCHNode &source){ | |
a79660fb | 53 | //Copy Constructor |
2e9f335b | 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){ | |
a79660fb | 65 | //Assignment operator |
2e9f335b | 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{ | |
a79660fb | 77 | //Function called by Sort method of TObjArray |
2e9f335b | 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(){ | |
a79660fb | 93 | //Constructor |
2e9f335b | 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){ | |
a79660fb | 105 | //Initialization |
2e9f335b | 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){ | |
a79660fb | 123 | //Copy Constructor |
2e9f335b | 124 | if(&source == this) return; |
125 | this->fSize = source.fSize; | |
126 | this->fCodeLen = source.fCodeLen; | |
127 | this->fCode = source.fCode; | |
128 | this->fSym = source.fSym; | |
129 | this->fHNodes = source.fHNodes; | |
130 | this->fNnodes = source.fNnodes; | |
131 | this->fNum=source.fNum; | |
132 | this->fVerbose=source.fVerbose; | |
133 | return; | |
134 | } | |
135 | ||
136 | ////////////////////////////////////////////////////////////////////////////// | |
137 | ||
138 | AliTPCHTable& AliTPCHTable::operator=(const AliTPCHTable &source) { | |
a79660fb | 139 | //Assignment operator |
2e9f335b | 140 | if(&source == this) return *this; |
141 | this->fSize = source.fSize; | |
142 | this->fCodeLen = source.fCodeLen; | |
143 | this->fCode = source.fCode; | |
144 | this->fSym = source.fSym; | |
145 | this->fHNodes = source.fHNodes; | |
146 | this->fNnodes = source.fNnodes; | |
147 | this->fNum=source.fNum; | |
148 | this->fVerbose=source.fVerbose; | |
149 | return *this; | |
150 | } | |
151 | ||
152 | ////////////////////////////////////////////////////////////////////////////// | |
153 | ||
154 | AliTPCHTable::~AliTPCHTable(){ | |
a79660fb | 155 | //HTable destructor |
2e9f335b | 156 | if(fVerbose) |
157 | cout<<"HTable destructor !\n"; | |
158 | if (fCodeLen) delete[] fCodeLen; | |
159 | if (fCode) delete [] fCode; | |
160 | if (fHNodes) { | |
161 | fHNodes->Delete(); //Clear out the collection and deletes the removed objects | |
162 | delete fHNodes; | |
163 | }//end if | |
164 | } | |
165 | ||
166 | ////////////////////////////////////////////////////////////////////////////// | |
167 | ||
168 | void AliTPCHTable::SetCodeLen(UChar_t len,Int_t val){ | |
a79660fb | 169 | //Sets codelength of "val" to the variable "len" |
2e9f335b | 170 | fCodeLen[val]=len; |
171 | return; | |
172 | } | |
173 | ||
174 | ////////////////////////////////////////////////////////////////////////////// | |
175 | ||
176 | void AliTPCHTable::SetCode(Double_t code,Int_t val){ | |
a79660fb | 177 | //Sets the binary code of the variable "val" |
2e9f335b | 178 | fCode[val]=code; |
179 | return; | |
180 | } | |
181 | ||
182 | ////////////////////////////////////////////////////////////////////////////// | |
183 | ||
184 | void AliTPCHTable::PrintTable()const{ | |
a79660fb | 185 | //This method prints a table |
2e9f335b | 186 | cout<<"Table for Huffman coding\n"; |
187 | cout<<" Symbol| Code | Length \n"; | |
188 | for (Int_t i=0;i<fSize;i++){ | |
189 | if (fCodeLen[i]){ | |
190 | cout.width(6);cout<<fSym[i]; | |
191 | cout.width(3);cout<<"|"; | |
192 | cout.width(6);cout<<hex<<(ULong_t)fCode[i]<<dec; | |
193 | cout.width(5);cout<<"|"; | |
194 | cout.width(6);cout<<(ULong_t)fCodeLen[i]<<endl; | |
195 | }//end if | |
196 | }//end for | |
197 | } | |
198 | ||
199 | ////////////////////////////////////////////////////////////////////////////// | |
200 | ||
201 | Bool_t AliTPCHTable::SpanTree(AliTPCHNode *start, ULong_t code, UChar_t len){ | |
a79660fb | 202 | //Hoffman codes are generated spanning the Huffman tree |
2e9f335b | 203 | //In an Huffman tree any internal node has always two children |
204 | AliTPCHNode * visited; | |
205 | visited = start; | |
206 | Int_t idx=visited->GetSymbol(); | |
207 | if (!visited->GetLeft()) { | |
208 | fCode[idx] = code; | |
209 | fCodeLen[idx] = len; | |
210 | return kTRUE; | |
211 | }//end if | |
212 | SpanTree(visited->GetLeft(), code << 1, len + 1); | |
213 | SpanTree(visited->GetRight(), code << 1 | 0x0001, len + 1); | |
214 | return kTRUE; | |
215 | } | |
216 | ||
217 | ////////////////////////////////////////////////////////////////////////////// | |
218 | ||
219 | void AliTPCHTable::ResetHNodes(){ | |
a79660fb | 220 | //Reset number of HNodes and the HNodes array |
2e9f335b | 221 | if (fHNodes) fHNodes->Clear(); |
222 | if (fNnodes) fNnodes=0; | |
223 | } | |
224 | ||
225 | ////////////////////////////////////////////////////////////////////////////// | |
226 | ||
227 | void AliTPCHTable::ClearTable(){ | |
a79660fb | 228 | //Clear the table |
2e9f335b | 229 | memset(fCodeLen,0,sizeof(UChar_t)*fSize); |
230 | memset(fCode,0,sizeof(Double_t)*fSize); | |
231 | } | |
232 | ||
233 | ////////////////////////////////////////////////////////////////////////////// | |
234 | ||
235 | Int_t AliTPCHTable::GetFrequencies(const char *fname){ | |
a79660fb | 236 | //It fills the "fCode" array with the frequencies of the symbols read from the file |
2e9f335b | 237 | AliTPCBuffer160 buff(fname,0); |
a79660fb | 238 | ULong_t numberOfWords=0; |
239 | Int_t val; | |
240 | while((val=buff.GetNext())!=-1){ | |
241 | fCode[val]++; | |
2e9f335b | 242 | fNum++; |
a79660fb | 243 | numberOfWords++; |
2e9f335b | 244 | } |
a79660fb | 245 | cout<<"Total number of words: "<<numberOfWords<<endl; |
2e9f335b | 246 | //Print out the frequencies |
247 | /* | |
248 | for (Int_t i=0;i<fSize;i++){ | |
249 | if (fCode[i])cout<<"Symbol: "<<i<<" Freq: "<<fCode[i]<<endl; | |
250 | } | |
251 | cout<<endl; | |
252 | */ | |
253 | return 0; | |
254 | } | |
255 | ||
256 | Int_t AliTPCHTable::SetValFrequency(const Int_t Val,Double_t Value){ | |
a79660fb | 257 | //This method sets to "Value" the frequency of the symbol "Val" |
2e9f335b | 258 | fCode[Val]=Value; |
259 | fNum=1; | |
260 | return 0; | |
261 | } | |
262 | ||
263 | ////////////////////////////////////////////////////////////////////////////// | |
264 | ||
265 | Int_t AliTPCHTable::SetFrequency(const Int_t Val){ | |
a79660fb | 266 | //It increments by one the frequency of the symbol "Val" whose frequency is |
267 | //stored in the fCode array | |
2e9f335b | 268 | fCode[Val]++; |
269 | fNum++; | |
270 | return 0; | |
271 | } | |
272 | ||
273 | ////////////////////////////////////////////////////////////////////////////// | |
274 | ||
a79660fb | 275 | Int_t AliTPCHTable::StoreFrequencies(const char *fname)const{ |
276 | //It stores the frequencies in a text file | |
2e9f335b | 277 | ofstream ftxt(fname); |
278 | for (Int_t i=0;i<fSize;i++){ | |
279 | ftxt<<(ULong_t)fCode[i]<<endl; | |
280 | } | |
281 | ftxt.close(); | |
282 | return 0; | |
283 | } | |
284 | ||
285 | ////////////////////////////////////////////////////////////////////////////// | |
286 | ||
287 | void AliTPCHTable::CompleteTable(Int_t k){ | |
a79660fb | 288 | //According to the kind of table (0..4) it associates a dummy frequency (1) to |
289 | //every symbols whose real frequency is zero, in a given range 0..max | |
2e9f335b | 290 | Int_t max; |
291 | ULong_t val; | |
292 | switch(k){ | |
293 | case 0: | |
294 | max=700; | |
295 | val=1; | |
296 | break; | |
297 | case 1: | |
298 | max=445; | |
299 | val=1; | |
300 | break; | |
301 | default: | |
302 | max=fSize; | |
303 | val=1; | |
304 | break; | |
305 | }//end switch | |
306 | ||
307 | for(Int_t i=0;i<max;i++){ | |
308 | if(fCode[i]==0.0)fCode[i]=val; | |
309 | } | |
310 | return; | |
311 | } | |
312 | ||
313 | ////////////////////////////////////////////////////////////////////////////// | |
314 | ||
315 | Double_t AliTPCHTable::GetEntropy()const{ | |
a79660fb | 316 | //This method calculates the value of the entropy |
2e9f335b | 317 | Double_t entropy=0; |
318 | Double_t prob=0; | |
319 | for (Int_t i=0;i<fSize;i++){ | |
320 | if (fCode[i]){ | |
321 | prob=fCode[i]/(Double_t)fNum; | |
322 | entropy+=prob*(TMath::Log2(prob)); | |
323 | } | |
324 | } | |
325 | return -entropy; | |
326 | } | |
327 | ||
328 | ////////////////////////////////////////////////////////////////////////////// | |
329 | ||
330 | Int_t AliTPCHTable::BuildHTable(){ | |
a79660fb | 331 | //It builds a Huffman tree |
2e9f335b | 332 | if(GetWordsNumber()){ |
333 | for (Int_t i=0; i< fSize; i++) { | |
334 | if (fCode[i] > 0.){ | |
335 | fNnodes++; | |
336 | //cout<< "Symbol:"<<i<<" Freq:"<<fCode[i]<<endl; | |
337 | fHNodes->Add(new AliTPCHNode(i,fCode[i])); | |
338 | }//end if | |
339 | }//end for | |
340 | Int_t nentries=fHNodes->GetEntriesFast(); | |
341 | //cout<<"Number of symbols: "<<nentries<<endl; | |
342 | Int_t nindex=nentries-1; | |
343 | while (nindex > 0){ | |
344 | fHNodes->Sort(nindex+1); | |
345 | AliTPCHNode *aux = new AliTPCHNode(0,0); | |
346 | AliTPCHNode *node= (AliTPCHNode*)fHNodes->UncheckedAt(nindex-1); | |
347 | AliTPCHNode *node1= (AliTPCHNode*)fHNodes->UncheckedAt(nindex); | |
348 | ||
349 | aux->SetLeft(node); | |
350 | aux->SetRight(node1); | |
351 | aux->SetFrequency(node->GetFrequency() + node1->GetFrequency()); | |
352 | fHNodes->RemoveAt(nindex-1); | |
353 | fHNodes->AddAt(aux,nindex-1); | |
354 | nindex--; | |
355 | }//end while | |
356 | ClearTable(); | |
357 | AliTPCHNode *start= (AliTPCHNode*)fHNodes->UncheckedAt(0); | |
358 | SpanTree(start,0,0); | |
359 | }//end if | |
360 | else{ | |
361 | cout<<"Table contains 0 elements\n"; | |
362 | }//end else | |
363 | return 0; | |
364 | } | |
2e9f335b | 365 | ////////////////////////////////////////////////////////////////////////////// |