HLT/BASE/AliHLTHuffman.cxx

   1 // $Id$
   2 //**************************************************************************
   3 //* This file is property of and copyright by the ALICE HLT Project        *
   4 //* ALICE Experiment at CERN, All rights reserved.                         *
   5 //*                                                                        *
   6 //* Primary Authors: Thorsten Kollegger <kollegge@ikf.uni-frankfurt.de>    *
   7 //*                  for The ALICE HLT Project.                            *
   8 //*                                                                        *
   9 //* Permission to use, copy, modify and distribute this software and its   *
  10 //* documentation strictly for non-commercial purposes is hereby granted   *
  11 //* without fee, provided that the above copyright notice appears in all   *
  12 //* copies and that both the copyright notice and this permission notice   *
  13 //* appear in the supporting documentation. The authors make no claims     *
  14 //* about the suitability of this software for any purpose. It is          *
  15 //* provided "as is" without express or implied warranty.                  *
  16 //**************************************************************************
  17
  18 /// @file   AliHLTHuffman.cxx
  19 /// @author Thorsten Kollegger, Matthias Richter
  20 /// @date   2011-08-14
  21 /// @brief  Huffman code generator/encoder/decoder
  22
  23 #include "AliHLTHuffman.h"
  24
  25 #include <iostream>
  26 #include <set>
  27 #include <bitset>
  28 #include <algorithm>
  29
  30 AliHLTHuffmanNode::AliHLTHuffmanNode()
  31         : TObject()
  32         , fValue(-1)
  33         , fWeight(0.)
  34 {
  35         // nop
  36 }
  37
  38 AliHLTHuffmanNode::AliHLTHuffmanNode(const AliHLTHuffmanNode& other)
  39         : TObject()
  40         , fValue(other.GetValue())
  41         , fWeight(other.GetWeight())
  42 {
  43 }
  44
  45 AliHLTHuffmanNode& AliHLTHuffmanNode::operator =(const AliHLTHuffmanNode& other) {
  46         /// assignment operator
  47         this->fValue = other.fValue;
  48         this->fWeight = other.fWeight;
  49         return *this;
  50 }
  51
  52 AliHLTHuffmanNode::~AliHLTHuffmanNode() {
  53 }
  54
  55 void AliHLTHuffmanNode::AssignCode() {
  56         /// assign code to this node loop to right and left nodes
  57         if (GetLeftChild()) {
  58                 // shift current bit pattern to left and add one
  59                 std::bitset < 64 > v = (this->GetBinaryCode() << 1);
  60                 v.set(0);
  61                 GetLeftChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
  62                 GetLeftChild()->AssignCode();
  63         }
  64         if (GetRightChild()) {
  65                 std::bitset < 64 > v = (this->GetBinaryCode() << 1);
  66                 v.reset(0);
  67                 GetRightChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
  68                 GetRightChild()->AssignCode();
  69         }
  70 }
  71
  72 void AliHLTHuffmanNode::Print(Option_t* /*option*/) const {
  73         /// print info
  74         std::cout << "value=" << GetValue() << ", weight=" << GetWeight() << ", length="
  75                         << GetBinaryCodeLength() << ", code=" << GetBinaryCode().to_string()
  76                         << std::endl;
  77         if (GetLeftChild()) {
  78                 GetLeftChild()->Print();
  79         }
  80         if (GetRightChild()) {
  81                 GetRightChild()->Print();
  82         }
  83 }
  84
  85 ClassImp(AliHLTHuffmanNode)
  86
  87 ///////////////////////////////////////////////////////////////////////////////////////////////
  88
  89 AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode()
  90         : AliHLTHuffmanNode()
  91         , fBinaryCodeLength(0)
  92         , fBinaryCode(0)
  93         , fLeft(NULL)
  94         , fRight(NULL)
  95 {
  96         // nop
  97 }
  98
  99 AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other)
 100         : AliHLTHuffmanNode()
 101         , fBinaryCodeLength(other.fBinaryCodeLength)
 102         , fBinaryCode(other.fBinaryCode)
 103         , fLeft(other.GetLeftChild())
 104         , fRight(other.GetRightChild())
 105 {
 106
 107 }
 108
 109 AliHLTHuffmanTreeNode& AliHLTHuffmanTreeNode::operator =(const AliHLTHuffmanTreeNode& other)
 110 {
 111         /// assignment operator
 112         if (&other==this) return *this;
 113         this->fBinaryCodeLength = other.GetBinaryCodeLength();
 114         this->fBinaryCode = other.GetBinaryCode();
 115         this->fLeft = other.GetLeftChild();
 116         this->fRight = other.GetRightChild();
 117         AliHLTHuffmanNode::operator=(other);
 118         return *this;
 119 }
 120
 121 AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(AliHLTHuffmanNode* l, AliHLTHuffmanNode* r)
 122         : AliHLTHuffmanNode()
 123         , fBinaryCodeLength(0)
 124         , fBinaryCode(0)
 125         , fLeft(l)
 126         , fRight(r) {
 127         if (l && r) {
 128                 SetWeight(l->GetWeight() + r->GetWeight());
 129         } else if (l && !r) {
 130                 SetWeight(l->GetWeight());
 131         } else if (!l && r) {
 132                 SetWeight(r->GetWeight());
 133         }
 134 }
 135
 136 AliHLTHuffmanTreeNode::~AliHLTHuffmanTreeNode()
 137 {
 138         // nop
 139 }
 140
 141 ClassImp(AliHLTHuffmanTreeNode)
 142
 143 ///////////////////////////////////////////////////////////////////////////////////////////////
 144
 145 AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode()
 146         : AliHLTHuffmanNode()
 147         , fBinaryCodeLength(0)
 148         , fBinaryCode(0)
 149         , fLeft(NULL)
 150         , fRight(NULL)
 151 {
 152         // nop
 153 }
 154
 155 AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other)
 156         : AliHLTHuffmanNode()
 157         , fBinaryCodeLength(other.fBinaryCodeLength)
 158         , fBinaryCode(other.fBinaryCode)
 159         , fLeft(other.GetLeftChild())
 160         , fRight(other.GetRightChild())
 161 {
 162
 163 }
 164
 165 AliHLTHuffmanLeaveNode& AliHLTHuffmanLeaveNode::operator =(const AliHLTHuffmanLeaveNode& other)
 166 {
 167         /// assignment operator
 168         if (&other==this) return *this;
 169         this->fBinaryCodeLength = other.GetBinaryCodeLength();
 170         this->fBinaryCode = other.GetBinaryCode();
 171         this->fLeft = other.GetLeftChild();
 172         this->fRight = other.GetRightChild();
 173         AliHLTHuffmanNode::operator=(other);
 174         return *this;
 175 }
 176
 177 AliHLTHuffmanLeaveNode::~AliHLTHuffmanLeaveNode()
 178 {
 179         // nop
 180 }
 181
 182 ClassImp(AliHLTHuffmanLeaveNode)
 183
 184 ///////////////////////////////////////////////////////////////////////////////////////////////
 185
 186 AliHLTHuffman::AliHLTHuffman()
 187         : TNamed()
 188         , fMaxBits(0)
 189         , fMaxValue(0)
 190         , fNodes(0)
 191         , fHuffTopNode(NULL)
 192 {
 193         /// nop
 194 }
 195
 196 AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
 197         : TNamed()
 198         , AliHLTLogging()
 199         , fMaxBits(other.fMaxBits)
 200         , fMaxValue(other.fMaxValue)
 201         , fNodes(other.fNodes)
 202         , fHuffTopNode(NULL) {
 203         /// nop
 204 }
 205
 206 AliHLTHuffman::AliHLTHuffman(const char* name, UInt_t maxBits)
 207         : TNamed(name, name)
 208         , fMaxBits(maxBits)
 209         , fMaxValue((((AliHLTUInt64_t) 1) << maxBits) - 1)
 210         , fNodes((((AliHLTUInt64_t) 1) << maxBits))
 211         , fHuffTopNode(NULL)
 212  {
 213         /// standard constructor
 214         for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
 215                 fNodes[i].SetValue(i);
 216         }
 217 }
 218
 219 AliHLTHuffman::~AliHLTHuffman() {
 220         /// destructor, nop
 221 }
 222
 223 const std::bitset<64>& AliHLTHuffman::Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const {
 224         /// encode a value
 225         codeLength = 0;
 226         if (v <= fMaxValue) {
 227                 // valid symbol/value
 228                 if (fHuffTopNode) {
 229                         // huffman code has been generated
 230                         codeLength = fNodes[v].GetBinaryCodeLength();
 231                         return fNodes[v].GetBinaryCode();
 232                 } else {
 233                   HLTError("encoder '%s' does not seem to be initialized", GetName());
 234                 }
 235         } else {
 236           HLTError("encoder %s: value %llu exceeds range of %d bits", GetName(), v, GetMaxBits());
 237         }
 238
 239         static const std::bitset<64> dummy;
 240         return dummy;
 241 }
 242
 243 Bool_t AliHLTHuffman::Decode(std::bitset<64> bits, AliHLTUInt64_t& value) const {
 244         // TODO: check decoding logic, righ now it is just as written
 245         AliHLTHuffmanNode* currNode = fHuffTopNode;
 246         if (currNode->GetValue() >= 0) {
 247                 // handle case with just one node - also quite unlikely
 248                 value = currNode->GetValue();
 249                 return kTRUE;
 250         }
 251         while (currNode) {
 252                 if (bits[0] && currNode->GetLeftChild()) {
 253                         // follow left branch
 254                         currNode = currNode->GetLeftChild();
 255                         bits >>= 1;
 256                         if (currNode->GetValue() >= 0) {
 257                                 value = currNode->GetValue();
 258                                 return kTRUE;
 259                         }
 260                 }
 261                 if (!bits[0] && currNode->GetRightChild()) {
 262                         currNode = currNode->GetRightChild();
 263                         bits >>= 1;
 264                         if (currNode->GetValue() >= 0) {
 265                                 value = currNode->GetValue();
 266                                 return kTRUE;
 267                         }
 268                 }
 269         }
 270         value = ((AliHLTUInt64_t)1) << 63;
 271         return kFALSE;
 272 }
 273
 274 Bool_t AliHLTHuffman::AddTrainingValue(const AliHLTUInt64_t value,
 275                 const float_t weight) {
 276         if (value > fMaxValue) {
 277                 /* TODO: ERROR message */
 278                 return kFALSE;
 279         }
 280         fNodes[value].AddWeight(weight);
 281         return kTRUE;
 282 }
 283
 284 Bool_t AliHLTHuffman::GenerateHuffmanTree() {
 285         // insert pointer to nodes into ordered structure to build tree
 286         std::multiset<AliHLTHuffmanNode*, AliHLTHuffmanNode::less> nodeCollection;
 287         //      std::copy(fNodes.begin(), fNodes.end(),
 288         //                      std::inserter(freq_coll, freq_coll.begin()));
 289         for (std::vector<AliHLTHuffmanLeaveNode>::iterator i = fNodes.begin(); i
 290                         != fNodes.end(); ++i) {
 291                 nodeCollection.insert(&(*i));
 292         }
 293         while (nodeCollection.size() > 1) {
 294                 // insert new node into structure, combining the two with lowest probability
 295                 nodeCollection.insert(
 296                                 new AliHLTHuffmanTreeNode(*nodeCollection.begin(),
 297                                                 *++nodeCollection.begin()));
 298                 nodeCollection.erase(nodeCollection.begin());
 299                 nodeCollection.erase(nodeCollection.begin());
 300         }
 301         //assign value
 302         fHuffTopNode = *nodeCollection.begin();
 303         fHuffTopNode->AssignCode();
 304         return kTRUE;
 305 }
 306
 307 void AliHLTHuffman::Print(Option_t* option) const {
 308         std::cout << GetName() << endl;
 309         bool bPrintShort=strcmp(option, "short")==0;
 310         if (fHuffTopNode && !bPrintShort) {
 311                 std::cout << "Huffman tree:" << endl;
 312                 fHuffTopNode->Print();
 313         }
 314         Double_t uncompressedSize = 0;
 315         Double_t compressedSize = 0;
 316         Double_t totalWeight = 0;
 317         if (!bPrintShort)
 318           std::cout << std::endl << "Huffman codes:" << std::endl;
 319         for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
 320           if (!bPrintShort) fNodes[i].Print();
 321                 totalWeight += fNodes[i].GetWeight();
 322                 uncompressedSize += fNodes[i].GetWeight() * fMaxBits;
 323                 compressedSize += fNodes[i].GetWeight()
 324                                 * fNodes[i].GetBinaryCodeLength();
 325         }
 326         if (uncompressedSize > 0) {
 327                 std::cout << "compression ratio: " << compressedSize
 328                                 / uncompressedSize << std::endl;
 329                 std::cout << "<bits> uncompressed: " << uncompressedSize / totalWeight
 330                                 << std::endl;
 331                 std::cout << "<bits> compressed:   " << compressedSize / totalWeight
 332                                 << std::endl;
 333         }
 334 }
 335
 336 AliHLTHuffman& AliHLTHuffman::operator =(const AliHLTHuffman& other) {
 337         fMaxValue = other.fMaxValue;
 338         fNodes = other.fNodes;
 339         fHuffTopNode = NULL;
 340         return *this;
 341 }
 342
 343 ClassImp(AliHLTHuffman)
 344