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 *
9 /// @file AliHLTHuffman.h
10 /// @author Thorsten Kollegger, Matthias Richter
12 /// @brief Huffman code generator/encoder/decode
14 #include "AliHLTLogging.h"
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.
32 * @ingroup alihlt_base
34 class AliHLTHuffmanNode: public TObject {
36 /// default constructor
39 AliHLTHuffmanNode(const AliHLTHuffmanNode& other);
40 /// assignment operator
41 AliHLTHuffmanNode& operator=(const AliHLTHuffmanNode& other);
43 virtual ~AliHLTHuffmanNode();
45 /// set symbol value of node
46 void SetValue(AliHLTInt64_t v) {
49 /// add weight to node
50 void AddWeight(Float_t w) {
53 /// set weight of node
54 void SetWeight(Float_t w) {
57 /// return symbol value of node
58 AliHLTInt64_t GetValue() const {
61 /// return weight of node
62 Float_t GetWeight() const {
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);
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;
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());
93 bool operator()(const AliHLTHuffmanNode* i1,
94 const AliHLTHuffmanNode* i2) const {
95 //reverse sort, less likely to most likely
96 return ((*i1) < (*i2));
101 AliHLTInt64_t fValue; // value
102 Float_t fWeight; // weight
104 ClassDef(AliHLTHuffmanNode, 1)
108 * @class AliHLTHuffmanTreeNode
109 * Tree nodes store the childs persistently. The binary code is
110 * a transient member.
112 class AliHLTHuffmanTreeNode: public AliHLTHuffmanNode {
114 /// default constructor
115 AliHLTHuffmanTreeNode();
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);
123 ~AliHLTHuffmanTreeNode();
125 /// set binary huffman code and length of node
126 void SetBinaryCode(AliHLTUInt64_t length, std::bitset<64> code) {
127 fBinaryCodeLength = length;
131 /// set pointer to left child
132 void SetLeftChild(AliHLTHuffmanNode* n) {
135 /// set pointer to right child
136 void SetRightChild(AliHLTHuffmanNode* n) {
139 /// Return length of huffman code
140 AliHLTUInt64_t GetBinaryCodeLength() const {
141 return fBinaryCodeLength;
143 /// Return binary huffman code
144 const std::bitset<64>& GetBinaryCode() const {
147 /// Return pointer to left Child
148 AliHLTHuffmanNode* GetLeftChild() const {
151 /// Return pointer to right Child
152 AliHLTHuffmanNode* GetRightChild() const {
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
162 ClassDef(AliHLTHuffmanTreeNode, 1)
166 * @class AliHLTHuffmanLeaveNode
167 * Leave nodes store the binary code persistently, while the childs are transient
169 class AliHLTHuffmanLeaveNode: public AliHLTHuffmanNode {
171 /// default constructor
172 AliHLTHuffmanLeaveNode();
174 AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other);
175 /// assignment operator
176 AliHLTHuffmanLeaveNode& operator=(const AliHLTHuffmanLeaveNode& other);
178 ~AliHLTHuffmanLeaveNode();
180 /// set binary huffman code and length of node
181 void SetBinaryCode(AliHLTUInt64_t length, std::bitset<64> code) {
182 fBinaryCodeLength = length;
185 /// set pointer to left child
186 void SetLeftChild(AliHLTHuffmanNode* n) {
189 /// set pointer to right child
190 void SetRightChild(AliHLTHuffmanNode* n) {
193 /// Return length of huffman code
194 AliHLTUInt64_t GetBinaryCodeLength() const {
195 return fBinaryCodeLength;
197 /// Return binary huffman code
198 const std::bitset<64>& GetBinaryCode() const {
201 /// Return pointer to left Child
202 AliHLTHuffmanNode* GetLeftChild() const {
205 /// Return pointer to right Child
206 AliHLTHuffmanNode* GetRightChild() const {
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
216 ClassDef(AliHLTHuffmanLeaveNode, 1)
220 * @class AliHLTHuffman
221 * Huffman code generator/encoder/decoder
223 * @ingroup alihlt_base
225 class AliHLTHuffman: public TNamed, public AliHLTLogging {
228 AliHLTHuffman(const AliHLTHuffman& other);
229 AliHLTHuffman(const char* name, UInt_t maxBits);
232 UInt_t InitMaxCodeLength();
234 UInt_t GetMaxBits() const {return fMaxBits;}
235 UInt_t GetMaxValue() const {return fMaxValue;}
236 UInt_t GetMaxCodeLength() const {return fMaxCodeLength;}
238 /// Return huffman code for a value
239 const std::bitset<64>& Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const;
241 /// Return value for bit pattern, LSB first
242 Bool_t DecodeLSB(std::bitset<64> /*bits*/, AliHLTUInt64_t& /*value*/, AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
243 /// Return value for bit pattern, MSB first
244 Bool_t DecodeMSB(std::bitset<64> /*bits*/, AliHLTUInt64_t& /*value*/, AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
245 /// Return value for bit pattern using decoder node array, MSB first
246 Bool_t FastDecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
247 AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
249 /// Add a new training value (with optional weight) to the training sample
250 Bool_t AddTrainingValue(const AliHLTUInt64_t value,
251 const Float_t weight = 1.);
252 /// Generate huffman tree from training sample
253 Bool_t GenerateHuffmanTree();
254 /// Print info about huffman en-/decoder
255 void Print(Option_t* option = "short") const;
256 /// Overload assignment operator
257 AliHLTHuffman& operator =(const AliHLTHuffman& other);
259 bool CheckConsistency() const;
262 * Binary structure for fast access of node information
265 struct AliHuffmanDecodingNode {
266 AliHLTHuffmanNode* fParent; // parent
267 AliHLTInt64_t fValue; // value
268 AliHuffmanDecodingNode* fLeft; // left neighbor
269 AliHuffmanDecodingNode* fRight; // right neighbor
270 AliHLTUInt8_t fBinaryCodeLength; // code length
273 int EnableDecodingMap();
276 AliHuffmanDecodingNode* BuildDecodingNode(AliHLTHuffmanNode* node, vector<AliHuffmanDecodingNode>& decodingnodes) const;
278 UInt_t fMaxBits; // bit lenght
279 UInt_t fMaxValue; // maximum value
280 std::vector<AliHLTHuffmanLeaveNode> fNodes; // array of nodes
281 AliHLTHuffmanNode* fHuffTopNode; // top node
282 bool fReverseCode; // indicate the type of the binary code
283 UInt_t fMaxCodeLength; //! maximum code length
284 std::vector<AliHuffmanDecodingNode> fDecodingNodes; //! array of reduced nodes
285 AliHuffmanDecodingNode* fDecodingTopNode; //! top node of reduced nodes
287 ClassDef(AliHLTHuffman, 4)