Line data Source code
1 : //-*- Mode: C++ -*-
2 : // $Id$
3 : #ifndef ALIHLTHUFFMAN_H
4 : #define ALIHLTHUFFMAN_H
5 : //* This file is property of and copyright by the ALICE HLT Project *
6 : //* ALICE Experiment at CERN, All rights reserved. *
7 : //* See cxx source for full Copyright notice *
8 :
9 : /// @file AliHLTHuffman.h
10 : /// @author Thorsten Kollegger, Matthias Richter
11 : /// @date 2011-08-14
12 : /// @brief Huffman code generator/encoder/decode
13 :
14 : #include "AliHLTLogging.h"
15 :
16 : #include "TNamed.h"
17 :
18 : #include <vector>
19 : #include <bitset>
20 : #include <string>
21 :
22 : /**
23 : * @class AliHLTHuffmanNode
24 : * Huffman code nodes. This is the base class for two types of nodes,
25 : * AliHLTHuffmanTreeNode and AliHLTHuffmanLeaveNode. The latter nodes
26 : * represent the index array of values to huffman codes. The former are
27 : * used in a tree reaching from the value of highest occuremce to all
28 : * leaves. The two node types are defined in order to optimize the storage
29 : * format for the huffman table. Leave nodes don't need persistent pointers
30 : * to childs, tree nodes don't need persistent binary code values.
31 : *
32 : * 2015-09-09 It turned out a while ago that float precission for the weight
33 : * can lead to a non-optimal huffman table if a large sample is used and float
34 : * precision is not enough to represent small differences in large occurrences
35 : * of values. Precision has been changed to double internally. The new double
36 : * precision weight member is however defined transient and the float
37 : * precision is kept for storage in order to avoid increase of the (already
38 : * big) huffman table. The float precision is approached by scaling weights of
39 : * all nodes by the exponent of the least non-zero weight. This is not
40 : * entirely accurate but given the informative character of the weight member
41 : * after the generation of the huffman codes, this is accepted.
42 : *
43 : * @ingroup alihlt_base
44 : */
45 : class AliHLTHuffmanNode: public TObject {
46 : public:
47 : /// default constructor
48 : AliHLTHuffmanNode();
49 : /// copy constructor
50 : AliHLTHuffmanNode(const AliHLTHuffmanNode& other);
51 : /// assignment operator
52 : AliHLTHuffmanNode& operator=(const AliHLTHuffmanNode& other);
53 : /// destructor
54 : virtual ~AliHLTHuffmanNode();
55 :
56 : /// set symbol value of node
57 : void SetValue(AliHLTInt64_t v) {
58 0 : fValue = v;
59 0 : }
60 : /// add weight to node
61 : void AddWeight(Double_t w) {
62 0 : fWeightDouble += w;
63 0 : fWeight = static_cast<float>(fWeightDouble);
64 0 : }
65 : /// set weight of node
66 : void SetWeight(Double_t w) {
67 0 : fWeightDouble = w;
68 0 : fWeight = static_cast<float>(fWeightDouble);
69 0 : }
70 : /// return symbol value of node
71 : AliHLTInt64_t GetValue() const {
72 0 : return fValue;
73 : }
74 : /// return weight of node
75 : Double_t GetWeight() const {
76 0 : return fWeightDouble;
77 : }
78 : /// scale weight of node
79 : void ScaleWeight(Double_t scale) {
80 : // see note above on the two weight members
81 0 : if (scale > 0.) fWeightDouble /= scale;
82 0 : fWeight = static_cast<Float_t>(fWeightDouble);
83 0 : }
84 :
85 : /// assign huffman code to this node and its children
86 : /// bReverse = true the bit corresponding to the parent is shifted and
87 : /// decoding needs to start from the MSB of the code
88 : void AssignCode(bool bReverse=false);
89 : /// set binary huffman code and length of node
90 : virtual void SetBinaryCode(AliHLTUInt64_t length, std::bitset<64> code) = 0;
91 : /// set pointer to left child
92 : virtual void SetLeftChild(AliHLTHuffmanNode* n) = 0;
93 : /// set pointer to right child
94 : virtual void SetRightChild(AliHLTHuffmanNode* n) = 0;
95 : /// Return length of huffman code
96 : virtual AliHLTUInt64_t GetBinaryCodeLength() const = 0;
97 : /// Return binary huffman code
98 : virtual const std::bitset<64>& GetBinaryCode() const = 0;
99 : /// Return pointer to left Child
100 : virtual AliHLTHuffmanNode* GetLeftChild() const = 0;
101 : /// Return pointer to right Child
102 : virtual AliHLTHuffmanNode* GetRightChild() const = 0;
103 :
104 : /// Print information about node
105 : void Print(Option_t* option = "") const;
106 : /// Overload less operator, based on node weights
107 : Bool_t operator <(const AliHLTHuffmanNode& other) const {
108 0 : return (this->GetWeight() < other.GetWeight());
109 : }
110 : class less {
111 : public:
112 : bool operator()(const AliHLTHuffmanNode* i1,
113 : const AliHLTHuffmanNode* i2) const {
114 : //reverse sort, less likely to most likely
115 0 : return ((*i1) < (*i2));
116 : }
117 : };
118 :
119 : private:
120 : AliHLTInt64_t fValue; // value
121 : Float_t fWeight; // weight
122 : // see note above on the two weight members
123 : Double_t fWeightDouble; //! double precision weight
124 :
125 138 : ClassDef(AliHLTHuffmanNode, 2)
126 : };
127 :
128 : /**
129 : * @class AliHLTHuffmanTreeNode
130 : * Tree nodes store the childs persistently. The binary code is
131 : * a transient member.
132 : */
133 : class AliHLTHuffmanTreeNode: public AliHLTHuffmanNode {
134 : public:
135 : /// default constructor
136 : AliHLTHuffmanTreeNode();
137 : /// copy constructor
138 : AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other);
139 : /// assignment operator
140 : AliHLTHuffmanTreeNode& operator=(const AliHLTHuffmanTreeNode& other);
141 : /// constructor for internal nodes, based on two input nodes (leaves or internal nodes)
142 : AliHLTHuffmanTreeNode(AliHLTHuffmanNode* l, AliHLTHuffmanNode* r);
143 : /// desstructor
144 : ~AliHLTHuffmanTreeNode();
145 :
146 : /// set binary huffman code and length of node
147 : void SetBinaryCode(AliHLTUInt64_t length, std::bitset<64> code) {
148 0 : fBinaryCodeLength = length;
149 0 : fBinaryCode = code;
150 0 : }
151 :
152 : /// set pointer to left child
153 : void SetLeftChild(AliHLTHuffmanNode* n) {
154 0 : fLeft = n;
155 0 : }
156 : /// set pointer to right child
157 : void SetRightChild(AliHLTHuffmanNode* n) {
158 0 : fRight = n;
159 0 : }
160 : /// Return length of huffman code
161 : AliHLTUInt64_t GetBinaryCodeLength() const {
162 0 : return fBinaryCodeLength;
163 : }
164 : /// Return binary huffman code
165 : const std::bitset<64>& GetBinaryCode() const {
166 0 : return fBinaryCode;
167 : }
168 : /// Return pointer to left Child
169 : AliHLTHuffmanNode* GetLeftChild() const {
170 0 : return fLeft;
171 : }
172 : /// Return pointer to right Child
173 : AliHLTHuffmanNode* GetRightChild() const {
174 0 : return fRight;
175 : }
176 :
177 : private:
178 : AliHLTUInt8_t fBinaryCodeLength; //! code length
179 : std::bitset<64> fBinaryCode; //! WARNING: this fixed the maximum code length to 128
180 : AliHLTHuffmanNode* fLeft; // left neighbor
181 : AliHLTHuffmanNode* fRight; // right neighbor
182 :
183 468570 : ClassDef(AliHLTHuffmanTreeNode, 2)
184 : };
185 :
186 : /**
187 : * @class AliHLTHuffmanLeaveNode
188 : * Leave nodes store the binary code persistently, while the childs are transient
189 : */
190 : class AliHLTHuffmanLeaveNode: public AliHLTHuffmanNode {
191 : public:
192 : /// default constructor
193 : AliHLTHuffmanLeaveNode();
194 : /// copy constructor
195 : AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other);
196 : /// assignment operator
197 : AliHLTHuffmanLeaveNode& operator=(const AliHLTHuffmanLeaveNode& other);
198 : /// destructor
199 : ~AliHLTHuffmanLeaveNode();
200 :
201 : /// set binary huffman code and length of node
202 : void SetBinaryCode(AliHLTUInt64_t length, std::bitset<64> code) {
203 0 : fBinaryCodeLength = length;
204 0 : fBinaryCode = code;
205 0 : }
206 : /// set pointer to left child
207 : void SetLeftChild(AliHLTHuffmanNode* n) {
208 0 : fLeft = n;
209 0 : }
210 : /// set pointer to right child
211 : void SetRightChild(AliHLTHuffmanNode* n) {
212 0 : fRight = n;
213 0 : }
214 : /// Return length of huffman code
215 : AliHLTUInt64_t GetBinaryCodeLength() const {
216 0 : return fBinaryCodeLength;
217 : }
218 : /// Return binary huffman code
219 : const std::bitset<64>& GetBinaryCode() const {
220 0 : return fBinaryCode;
221 : }
222 : /// Return pointer to left Child
223 : AliHLTHuffmanNode* GetLeftChild() const {
224 0 : return fLeft;
225 : }
226 : /// Return pointer to right Child
227 : AliHLTHuffmanNode* GetRightChild() const {
228 0 : return fRight;
229 : }
230 :
231 : private:
232 : AliHLTUInt8_t fBinaryCodeLength; // code length
233 : std::bitset<64> fBinaryCode; // WARNING: this fixed the maximum code length to 128
234 : AliHLTHuffmanNode* fLeft; //! left neighbor
235 : AliHLTHuffmanNode* fRight; //! right neighbor
236 :
237 937094 : ClassDef(AliHLTHuffmanLeaveNode, 2)
238 : };
239 :
240 : /**
241 : * @class AliHLTHuffman
242 : * Huffman code generator/encoder/decoder
243 : *
244 : * @ingroup alihlt_base
245 : */
246 : class AliHLTHuffman: public TNamed, public AliHLTLogging {
247 : public:
248 : AliHLTHuffman();
249 : AliHLTHuffman(const AliHLTHuffman& other);
250 : AliHLTHuffman(const char* name, UInt_t maxBits);
251 : ~AliHLTHuffman();
252 :
253 : UInt_t InitMaxCodeLength();
254 :
255 0 : UInt_t GetMaxBits() const {return fMaxBits;}
256 0 : UInt_t GetMaxValue() const {return fMaxValue;}
257 0 : UInt_t GetMaxCodeLength() const {return fMaxCodeLength;}
258 :
259 : /// Return huffman code for a value
260 : const std::bitset<64>& Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const;
261 :
262 : /// Return value for bit pattern, LSB first
263 : Bool_t DecodeLSB(std::bitset<64> /*bits*/, AliHLTUInt64_t& /*value*/, AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
264 : /// Return value for bit pattern, MSB first
265 : Bool_t DecodeMSB(std::bitset<64> /*bits*/, AliHLTUInt64_t& /*value*/, AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
266 : /// Return value for bit pattern using decoder node array, MSB first
267 : Bool_t FastDecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
268 : AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
269 :
270 : /// Add a new training value (with optional weight) to the training sample
271 : Bool_t AddTrainingValue(const AliHLTUInt64_t value,
272 : const Float_t weight = 1.);
273 : /// Generate huffman tree from training sample
274 : Bool_t GenerateHuffmanTree();
275 : /// Print info about huffman en-/decoder
276 : void Print(Option_t* option = "short") const;
277 : /// Overload assignment operator
278 : AliHLTHuffman& operator =(const AliHLTHuffman& other);
279 :
280 : bool CheckConsistency() const;
281 :
282 : /**
283 : * Binary structure for fast access of node information
284 : * in the decoding
285 : */
286 : struct AliHuffmanDecodingNode {
287 : AliHLTHuffmanNode* fParent; // parent
288 : AliHLTInt64_t fValue; // value
289 : AliHuffmanDecodingNode* fLeft; // left neighbor
290 : AliHuffmanDecodingNode* fRight; // right neighbor
291 : AliHLTUInt8_t fBinaryCodeLength; // code length
292 : };
293 :
294 : int EnableDecodingMap();
295 :
296 : private:
297 : AliHuffmanDecodingNode* BuildDecodingNode(AliHLTHuffmanNode* node, vector<AliHuffmanDecodingNode>& decodingnodes) const;
298 :
299 : UInt_t fMaxBits; // bit lenght
300 : UInt_t fMaxValue; // maximum value
301 : std::vector<AliHLTHuffmanLeaveNode> fNodes; // array of nodes
302 : AliHLTHuffmanNode* fHuffTopNode; // top node
303 : bool fReverseCode; // indicate the type of the binary code
304 : UInt_t fMaxCodeLength; //! maximum code length
305 : std::vector<AliHuffmanDecodingNode> fDecodingNodes; //! array of reduced nodes
306 : AliHuffmanDecodingNode* fDecodingTopNode; //! top node of reduced nodes
307 :
308 170 : ClassDef(AliHLTHuffman, 4)
309 : };
310 :
311 : #endif
|
