Octane v1.01.20 - The Open Compression Toolkit for C++ http://octane.sourceforge.net/
Homepage | Main | Modules | Class Hierarchy | Compound List | File List | Compound Members | Related Pages

HuffmanCoder Class Reference
[Coders]

#include <huffmancoder.hpp>

Inheritance diagram for HuffmanCoder:

OctaneCoder OctaneClass List of all members.

Detailed Description

During compression, the job of the Coder class is use probability information from the modeler to figure out the optimal bitcodes to use when writing symbols into the output stream.

During decompression, the coder is responsible for reading bitcodes from the input and providing a stream of symbol numbers to the compressor.

The Huffman Coding algorithm was invented by David A. Huffman, http://www.wikipedia.org/wiki/Huffman_coding

The idea of using an STL priority queue to build the Huffman tree is from Mark Nelson, http://dogma.net/markn/articles/pq_stl/priority.htm.

Definition at line 49 of file huffmancoder.hpp.

Public Member Functions

 HuffmanCoder ()
 constructor

virtual ~HuffmanCoder ()
 destructor

virtual std::string GetName ()
 provide a unique name for the coder, used in some cases to automatically register the object with a manager

virtual std::string GetDescription ()
 optionally provide a longer (maybe 20-60 characters) description

virtual std::string GetHelpInformation ()
 optionally provide more information about the object on request for help

virtual void ShowDebuggingInfo ()
 show any debugging info on request (used by various derived classes) [optional]

virtual unsigned int GetMemoryUsed ()
 Report actual current memory usage (in bytes).

virtual bool WriteSymbolBits (int symbolnum, bitwriter &bw)
 write bits for symbol number

virtual bool DecodeSymbolFromInput (int &symbolnum, bitreader &br)
 Decode the next symbol from the input.

virtual void ResetState ()
virtual void SynchronizeStateForNewStream ()
 Synchronize state for a new stream - this *MUST* be called before beginning a new parsing stream.

virtual bool IsReadyToCode ()
 Are we ready to actually code and decode?

virtual void ReceiveNotification_ModelChange_AllSymbolWeights (OctaneModeler *modelerp)
 Notify coder that all probabilities are being updated.

virtual void ReceiveNotification_ModelChange_SingleSymbolWeight (OctaneModeler *modelerp, int symbolnum)
 notify that a single symbol probability has changed (by default just calls AllSymbolWeights change above)


Protected Member Functions

bool BuildUpdateHuffmanTreeAndBitcodes (OctaneModeler *modelerp)
 Using the current probability vector from the modeler, build a huffman tree and compute bitcodes for each symbol.

void TraverseHuffmanTreeBuildBitcodes ()
 Traverse built tree and assign bitcodes.

void FreeSymbols ()
 Free any current tree and symbols in preparation for rebuilding.

void ShowBitStrings ()
 Show bitcodes for each symbol - useful for debugging.


Protected Attributes

THuffmanNodePriorityQueue symbolsetpq
 Stl priority queue for Huffman tree, built from "huffman nodes".

vector< HuffNode_Leaf * > symbolvector
 vector of pointers to symbols, for fast lookup when it comes time to writing symbols by symbol#

vector< HuffNode_Leaf
* >::iterator 		symbolvector_pos
 vector iterator

Member Function Documentation

virtual std::string HuffmanCoder::GetName (   )  [inline, virtual]
 

provide a unique name for the coder, used in some cases to automatically register the object with a manager

Returns:
a short *unique* name

Reimplemented from OctaneCoder.

Definition at line 69 of file huffmancoder.hpp. 

00069 {return "HuffmanCoder";}

virtual std::string HuffmanCoder::GetDescription (   )  [inline, virtual]
 

optionally provide a longer (maybe 20-60 characters) description

Returns:
a one line description

Reimplemented from OctaneCoder.

Definition at line 70 of file huffmancoder.hpp. 

00070 {return "Huffman Coder";}

virtual std::string HuffmanCoder::GetHelpInformation (   )  [inline, virtual]
 

optionally provide more information about the object on request for help

Returns:
a long string (can be multiple
newlines)

Reimplemented from OctaneCoder.

Definition at line 71 of file huffmancoder.hpp. 

00071 { return ""; }

bool HuffmanCoder::WriteSymbolBits (  int  symbolnum,
bitwriter &  bw
)  [virtual]
 

write bits for symbol number

Returns:
true on success

Implements OctaneCoder.

Definition at line 54 of file huffmancoder.cpp.

References symbolvector. 

00055 {
00056         // write bits for symbol number - this is easy because we've precomputed the bitvectors for every symbol
00057         assert(symbolnum<(int)(symbolvector.size()));
00058         return symbolvector[symbolnum]->AddBitsToBitWriter(bw);
00059 }

bool HuffmanCoder::DecodeSymbolFromInput (  int &  symbolnum,
bitreader &  br
)  [virtual]
 

Decode the next symbol from the input.

Returns:
true on success, false when there are no more symbols to read.

Implements OctaneCoder.

Definition at line 61 of file huffmancoder.cpp.

References bitreader::empty(), bitreader::get_bit(), HuffNode::get_child0(), HuffNode::get_child1(), HuffNode::isleaf(), and symbolsetpq. 

00062 {
00063         // decode a symbol from the input, and set symbolnum to symbol number
00064         // return false on no symbols left in stream
00065         HuffNode* nodep;
00066         bool bitvalue;
00067         
00068         // now walk through the input bits      
00069         nodep = symbolsetpq.top();
00070         while (!br.empty())
00071                 {
00072                 // grab a bit
00073                 bitvalue = br.get_bit();
00074 
00075                 // traverse down tree
00076                 if (bitvalue==false)
00077                         nodep=nodep->get_child0();
00078                 else
00079                         nodep=nodep->get_child1();
00080                 if (nodep==NULL)
00081                         {
00082                         cerr << "ERROR: Internal error traversing huffman tree in huffmancoder.cpp, in HuffmanCoder::DecodeSymbolFromInput()." << endl;
00083                         break;
00084                         }
00085 
00086                 // if its leaf we got our symbol
00087                 if (nodep->isleaf())
00088                         {
00089                         // we hit a leaf, so this is our decoded symbol - return its number
00090                         symbolnum=((HuffNode_Leaf*)nodep)->get_symbolid();
00091                         return true;
00092                         }
00093                 else
00094                         {
00095                         // just a middle node, so keep traversing
00096                         }
00097                 }
00098         
00099         // no symbols to read
00100         return false;
00101 }

virtual bool HuffmanCoder::IsReadyToCode (   )  [inline, virtual]
 

Are we ready to actually code and decode?

Returns:
true on success

Reimplemented from OctaneCoder.

Definition at line 90 of file huffmancoder.hpp.

References symbolvector. 

00090 {if (symbolvector.size()>0) return true; else return false;};

virtual void HuffmanCoder::ReceiveNotification_ModelChange_AllSymbolWeights (  OctaneModeler *  modelerp  )  [inline, virtual]
 

Notify coder that all probabilities are being updated.

We can be informed by a model when the underlying probabilities are changing this part of the API exists so that we can flexibly and efficiently handle different kinds of situations where the coder needs to be synchronized with the model probabilities. in some cases, a coder may ignore these messages and simply rebuild its internal datastructure on each coding event in other cases, it will want to incrementally update as model changes. Two kinds of notifications are supported, depending on how the model updates itself during processing, whether it updates one symbol per iteration, or modifies all symbols at once.

See also:
OctaneCoder::ReceiveNotification_ModelChange_SingleSymbolWeight

Reimplemented from OctaneCoder.

Definition at line 95 of file huffmancoder.hpp.

References BuildUpdateHuffmanTreeAndBitcodes(). 

00095 {BuildUpdateHuffmanTreeAndBitcodes(modelerp);};

virtual void HuffmanCoder::ReceiveNotification_ModelChange_SingleSymbolWeight (  OctaneModeler *  modelerp,
int  symbolnum
)  [inline, virtual]
 

notify that a single symbol probability has changed (by default just calls AllSymbolWeights change above)

Note:
the SingleSymbolWeight() call will NOT be made when all weights change; see ReceiveNotification_ModelChange_AllSymbolWeights instead.
See also:
OctaneCoder::ReceiveNotification_ModelChange_AllSymbolWeights

Reimplemented from OctaneCoder.

Definition at line 96 of file huffmancoder.hpp.

References BuildUpdateHuffmanTreeAndBitcodes(). 

00096 {BuildUpdateHuffmanTreeAndBitcodes(modelerp);};

Member Data Documentation

THuffmanNodePriorityQueue HuffmanCoder::symbolsetpq [protected]
 

Stl priority queue for Huffman tree, built from "huffman nodes".

See also:
huffmannodes.hpp

Definition at line 54 of file huffmancoder.hpp.

Referenced by BuildUpdateHuffmanTreeAndBitcodes(), DecodeSymbolFromInput(), FreeSymbols(), GetMemoryUsed(), ShowBitStrings(), and TraverseHuffmanTreeBuildBitcodes().

The documentation for this class was generated from the following files:  
Generated on 20 May 2004 by doxygen 1.3.3