]>
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 <TMath.h> |
3ea47630 | 27 | #include "AliAltroBuffer.h" |
bea6b2a4 | 28 | #include "AliTPCHNode.h" |
29 | #include "AliTPCHTable.h" | |
2e9f335b | 30 | |
31 | ClassImp(AliTPCHTable) | |
32 | ||
33 | AliTPCHTable::AliTPCHTable(){ | |
a79660fb | 34 | //Constructor |
2e9f335b | 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){ | |
a79660fb | 46 | //Initialization |
2e9f335b | 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 | ||
b66321bb | 63 | AliTPCHTable::AliTPCHTable(const AliTPCHTable &source) |
64 | :TObject(source){ | |
a79660fb | 65 | //Copy Constructor |
2e9f335b | 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) { | |
a79660fb | 81 | //Assignment operator |
2e9f335b | 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(){ | |
a79660fb | 97 | //HTable destructor |
2e9f335b | 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){ | |
a79660fb | 111 | //Sets codelength of "val" to the variable "len" |
2e9f335b | 112 | fCodeLen[val]=len; |
113 | return; | |
114 | } | |
115 | ||
116 | ////////////////////////////////////////////////////////////////////////////// | |
117 | ||
118 | void AliTPCHTable::SetCode(Double_t code,Int_t val){ | |
a79660fb | 119 | //Sets the binary code of the variable "val" |
2e9f335b | 120 | fCode[val]=code; |
121 | return; | |
122 | } | |
123 | ||
124 | ////////////////////////////////////////////////////////////////////////////// | |
125 | ||
126 | void AliTPCHTable::PrintTable()const{ | |
a79660fb | 127 | //This method prints a table |
2e9f335b | 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<<"|"; | |
0b3c7dfc | 134 | cout.width(6);cout<<hex<<(UInt_t)fCode[i]<<dec; |
2e9f335b | 135 | cout.width(5);cout<<"|"; |
0b3c7dfc | 136 | cout.width(6);cout<<(UInt_t)fCodeLen[i]<<endl; |
2e9f335b | 137 | }//end if |
138 | }//end for | |
139 | } | |
140 | ||
141 | ////////////////////////////////////////////////////////////////////////////// | |
142 | ||
0b3c7dfc | 143 | Bool_t AliTPCHTable::SpanTree(AliTPCHNode *start, UInt_t code, UChar_t len){ |
a79660fb | 144 | //Hoffman codes are generated spanning the Huffman tree |
2e9f335b | 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(){ | |
a79660fb | 162 | //Reset number of HNodes and the HNodes array |
2e9f335b | 163 | if (fHNodes) fHNodes->Clear(); |
164 | if (fNnodes) fNnodes=0; | |
165 | } | |
166 | ||
167 | ////////////////////////////////////////////////////////////////////////////// | |
168 | ||
169 | void AliTPCHTable::ClearTable(){ | |
a79660fb | 170 | //Clear the table |
2e9f335b | 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){ | |
a79660fb | 178 | //It fills the "fCode" array with the frequencies of the symbols read from the file |
3ea47630 | 179 | AliAltroBuffer buff(fname,0); |
0b3c7dfc | 180 | UInt_t numberOfWords=0; |
a79660fb | 181 | Int_t val; |
182 | while((val=buff.GetNext())!=-1){ | |
183 | fCode[val]++; | |
2e9f335b | 184 | fNum++; |
a79660fb | 185 | numberOfWords++; |
2e9f335b | 186 | } |
a79660fb | 187 | cout<<"Total number of words: "<<numberOfWords<<endl; |
2e9f335b | 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 | ||
09f6432c | 198 | Int_t AliTPCHTable::SetValFrequency(Int_t Val,Double_t Value){ |
a79660fb | 199 | //This method sets to "Value" the frequency of the symbol "Val" |
2e9f335b | 200 | fCode[Val]=Value; |
201 | fNum=1; | |
202 | return 0; | |
203 | } | |
204 | ||
205 | ////////////////////////////////////////////////////////////////////////////// | |
206 | ||
09f6432c | 207 | Int_t AliTPCHTable::SetFrequency(Int_t Val){ |
a79660fb | 208 | //It increments by one the frequency of the symbol "Val" whose frequency is |
209 | //stored in the fCode array | |
2e9f335b | 210 | fCode[Val]++; |
211 | fNum++; | |
212 | return 0; | |
213 | } | |
214 | ||
215 | ////////////////////////////////////////////////////////////////////////////// | |
216 | ||
9f992f70 | 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 | ////////////////////////////////////////////////////////////////////////////// | |
a79660fb | 236 | Int_t AliTPCHTable::StoreFrequencies(const char *fname)const{ |
237 | //It stores the frequencies in a text file | |
2e9f335b | 238 | ofstream ftxt(fname); |
239 | for (Int_t i=0;i<fSize;i++){ | |
9f992f70 | 240 | ftxt<<fCode[i]<<endl; |
2e9f335b | 241 | } |
242 | ftxt.close(); | |
243 | return 0; | |
244 | } | |
245 | ||
246 | ////////////////////////////////////////////////////////////////////////////// | |
247 | ||
248 | void AliTPCHTable::CompleteTable(Int_t k){ | |
a79660fb | 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 | |
2e9f335b | 251 | Int_t max; |
0b3c7dfc | 252 | UInt_t val; |
2e9f335b | 253 | switch(k){ |
254 | case 0: | |
c9bd9d3d | 255 | max=fSize; |
2e9f335b | 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{ | |
a79660fb | 277 | //This method calculates the value of the entropy |
2e9f335b | 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(){ | |
a79660fb | 292 | //It builds a Huffman tree |
2e9f335b | 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 | } | |
2e9f335b | 326 | ////////////////////////////////////////////////////////////////////////////// |