]>
Commit | Line | Data |
---|---|---|
6a1b3945 | 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 AliHLTDataHuffman.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 | * @ingroup alihlt_base | |
33 | */ | |
34 | class AliHLTHuffmanNode: public TObject { | |
35 | public: | |
36 | /// default constructor | |
37 | AliHLTHuffmanNode(); | |
38 | /// copy constructor | |
39 | AliHLTHuffmanNode(const AliHLTHuffmanNode& other); | |
40 | /// assignment operator | |
41 | AliHLTHuffmanNode& operator=(const AliHLTHuffmanNode& other); | |
42 | /// destructor | |
43 | virtual ~AliHLTHuffmanNode(); | |
44 | ||
45 | /// set symbol value of node | |
46 | void SetValue(AliHLTInt64_t v) { | |
47 | fValue = v; | |
48 | } | |
49 | /// add weight to node | |
50 | void AddWeight(Float_t w) { | |
51 | fWeight += w; | |
52 | } | |
53 | /// set weight of node | |
54 | void SetWeight(Float_t w) { | |
55 | fWeight = w; | |
56 | } | |
57 | /// return symbol value of node | |
58 | AliHLTInt64_t GetValue() const { | |
59 | return fValue; | |
60 | } | |
61 | /// return weight of node | |
62 | Float_t GetWeight() const { | |
63 | return fWeight; | |
64 | } | |
65 | ||
9409b4b1 | 66 | /// assign huffman code to this node and its children |
67 | /// bReverse = true the bit corresponding to the parent is shifted and | |
68 | /// decoding needs to start from the MSB of the code | |
69 | void AssignCode(bool bReverse=false); | |
6a1b3945 | 70 | /// set binary huffman code and length of node |
71 | virtual void SetBinaryCode(AliHLTUInt64_t length, std::bitset<64> code) = 0; | |
72 | /// set pointer to left child | |
73 | virtual void SetLeftChild(AliHLTHuffmanNode* n) = 0; | |
74 | /// set pointer to right child | |
75 | virtual void SetRightChild(AliHLTHuffmanNode* n) = 0; | |
76 | /// Return length of huffman code | |
77 | virtual AliHLTUInt64_t GetBinaryCodeLength() const = 0; | |
78 | /// Return binary huffman code | |
79 | virtual const std::bitset<64>& GetBinaryCode() const = 0; | |
80 | /// Return pointer to left Child | |
81 | virtual AliHLTHuffmanNode* GetLeftChild() const = 0; | |
82 | /// Return pointer to right Child | |
83 | virtual AliHLTHuffmanNode* GetRightChild() const = 0; | |
84 | ||
85 | /// Print information about node | |
86 | void Print(Option_t* option = "") const; | |
87 | /// Overload less operator, based on node weights | |
88 | Bool_t operator <(const AliHLTHuffmanNode& other) const { | |
89 | return (this->GetWeight() < other.GetWeight()); | |
90 | } | |
91 | class less { | |
92 | public: | |
93 | bool operator()(const AliHLTHuffmanNode* i1, | |
94 | const AliHLTHuffmanNode* i2) const { | |
95 | //reverse sort, less likely to most likely | |
96 | return ((*i1) < (*i2)); | |
97 | } | |
98 | }; | |
99 | ||
100 | private: | |
101 | AliHLTInt64_t fValue; // value | |
102 | Float_t fWeight; // weight | |
103 | ||
104 | ClassDef(AliHLTHuffmanNode, 1) | |
105 | }; | |
106 | ||
107 | /** | |
108 | * @class AliHLTHuffmanTreeNode | |
109 | * Tree nodes store the childs persistently. The binary code is | |
110 | * a transient member. | |
111 | */ | |
112 | class AliHLTHuffmanTreeNode: public AliHLTHuffmanNode { | |
113 | public: | |
114 | /// default constructor | |
115 | AliHLTHuffmanTreeNode(); | |
116 | /// copy constructor | |
117 | AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other); | |
118 | /// assignment operator | |
119 | AliHLTHuffmanTreeNode& operator=(const AliHLTHuffmanTreeNode& other); | |
120 | /// constructor for internal nodes, based on two input nodes (leaves or internal nodes) | |
121 | AliHLTHuffmanTreeNode(AliHLTHuffmanNode* l, AliHLTHuffmanNode* r); | |
122 | /// desstructor | |
123 | ~AliHLTHuffmanTreeNode(); | |
124 | ||
125 | /// set binary huffman code and length of node | |
126 | void SetBinaryCode(AliHLTUInt64_t length, std::bitset<64> code) { | |
127 | fBinaryCodeLength = length; | |
128 | fBinaryCode = code; | |
129 | } | |
130 | ||
131 | /// set pointer to left child | |
132 | void SetLeftChild(AliHLTHuffmanNode* n) { | |
133 | fLeft = n; | |
134 | } | |
135 | /// set pointer to right child | |
136 | void SetRightChild(AliHLTHuffmanNode* n) { | |
137 | fRight = n; | |
138 | } | |
139 | /// Return length of huffman code | |
140 | AliHLTUInt64_t GetBinaryCodeLength() const { | |
141 | return fBinaryCodeLength; | |
142 | } | |
143 | /// Return binary huffman code | |
144 | const std::bitset<64>& GetBinaryCode() const { | |
145 | return fBinaryCode; | |
146 | } | |
147 | /// Return pointer to left Child | |
148 | AliHLTHuffmanNode* GetLeftChild() const { | |
149 | return fLeft; | |
150 | } | |
151 | /// Return pointer to right Child | |
152 | AliHLTHuffmanNode* GetRightChild() const { | |
153 | return fRight; | |
154 | } | |
155 | ||
156 | private: | |
157 | AliHLTUInt8_t fBinaryCodeLength; //! code length | |
158 | std::bitset<64> fBinaryCode; //! WARNING: this fixed the maximum code length to 128 | |
159 | AliHLTHuffmanNode* fLeft; // left neighbor | |
160 | AliHLTHuffmanNode* fRight; // right neighbor | |
161 | ||
162 | ClassDef(AliHLTHuffmanTreeNode, 1) | |
163 | }; | |
164 | ||
165 | /** | |
166 | * @class AliHLTHuffmanLeaveNode | |
167 | * Leave nodes store the binary code persistently, while the childs are transient | |
168 | */ | |
169 | class AliHLTHuffmanLeaveNode: public AliHLTHuffmanNode { | |
170 | public: | |
171 | /// default constructor | |
172 | AliHLTHuffmanLeaveNode(); | |
173 | /// copy constructor | |
174 | AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other); | |
175 | /// assignment operator | |
176 | AliHLTHuffmanLeaveNode& operator=(const AliHLTHuffmanLeaveNode& other); | |
177 | /// destructor | |
178 | ~AliHLTHuffmanLeaveNode(); | |
179 | ||
180 | /// set binary huffman code and length of node | |
181 | void SetBinaryCode(AliHLTUInt64_t length, std::bitset<64> code) { | |
182 | fBinaryCodeLength = length; | |
183 | fBinaryCode = code; | |
184 | } | |
185 | /// set pointer to left child | |
186 | void SetLeftChild(AliHLTHuffmanNode* n) { | |
187 | fLeft = n; | |
188 | } | |
189 | /// set pointer to right child | |
190 | void SetRightChild(AliHLTHuffmanNode* n) { | |
191 | fRight = n; | |
192 | } | |
193 | /// Return length of huffman code | |
194 | AliHLTUInt64_t GetBinaryCodeLength() const { | |
195 | return fBinaryCodeLength; | |
196 | } | |
197 | /// Return binary huffman code | |
198 | const std::bitset<64>& GetBinaryCode() const { | |
199 | return fBinaryCode; | |
200 | } | |
201 | /// Return pointer to left Child | |
202 | AliHLTHuffmanNode* GetLeftChild() const { | |
203 | return fLeft; | |
204 | } | |
205 | /// Return pointer to right Child | |
206 | AliHLTHuffmanNode* GetRightChild() const { | |
207 | return fRight; | |
208 | } | |
209 | ||
210 | private: | |
211 | AliHLTUInt8_t fBinaryCodeLength; // code length | |
212 | std::bitset<64> fBinaryCode; // WARNING: this fixed the maximum code length to 128 | |
213 | AliHLTHuffmanNode* fLeft; //! left neighbor | |
214 | AliHLTHuffmanNode* fRight; //! right neighbor | |
215 | ||
216 | ClassDef(AliHLTHuffmanLeaveNode, 1) | |
217 | }; | |
218 | ||
219 | /** | |
220 | * @class AliHLTHuffman | |
221 | * Huffman code generator/encoder/decoder | |
222 | * | |
223 | * @ingroup alihlt_base | |
224 | */ | |
225 | class AliHLTHuffman: public TNamed, public AliHLTLogging { | |
226 | public: | |
227 | AliHLTHuffman(); | |
228 | AliHLTHuffman(const AliHLTHuffman& other); | |
229 | AliHLTHuffman(const char* name, UInt_t maxBits); | |
230 | ~AliHLTHuffman(); | |
231 | ||
232 | UInt_t GetMaxBits() const {return fMaxBits;} | |
233 | UInt_t GetMaxValue() const {return fMaxValue;} | |
234 | ||
235 | /// Return huffman code for a value | |
236 | const std::bitset<64>& Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const; | |
237 | ||
238 | /// Return value for bit pattern | |
9409b4b1 | 239 | Bool_t Decode(std::bitset<64> /*bits*/, AliHLTUInt64_t& /*value*/, AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const; |
6a1b3945 | 240 | /// Add a new training value (with optional weight) to the training sample |
241 | Bool_t AddTrainingValue(const AliHLTUInt64_t value, | |
242 | const Float_t weight = 1.); | |
243 | /// Generate huffman tree from training sample | |
244 | Bool_t GenerateHuffmanTree(); | |
245 | /// Print info about huffman en-/decoder | |
246 | void Print(Option_t* option = "short") const; | |
247 | /// Overload assignment operator | |
248 | AliHLTHuffman& operator =(const AliHLTHuffman& other); | |
249 | ||
9409b4b1 | 250 | bool CheckConsistency() const; |
251 | ||
6a1b3945 | 252 | private: |
253 | UInt_t fMaxBits; // bit lenght | |
254 | UInt_t fMaxValue; // maximum value | |
255 | std::vector<AliHLTHuffmanLeaveNode> fNodes; // array of nodes | |
256 | AliHLTHuffmanNode* fHuffTopNode; // top node | |
9409b4b1 | 257 | bool fReverseCode; // indicate the type of the binary code |
6a1b3945 | 258 | |
9409b4b1 | 259 | ClassDef(AliHLTHuffman, 2) |
6a1b3945 | 260 | }; |
261 | ||
262 | #endif |