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

coders/coder_huffman/huffmannodes.hpp File Reference


Detailed Description

Huffman node classes.

Remarks:
The HuffNode_Leaf is the base class for all symbols, and is (despite the elaborate interface), a very lightweight data structure, containing only a symbol id and a numeric weight.
The techinique to use a priority queue to generate the huffman tree is described in [nelson].

Author:
mouser
Date:
2003.07.29

Definition in file huffmannodes.hpp.

#include "../../bitio/bitio.hpp"
#include <string>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <bitset>

Go to the source code of this file.

Compounds

class  HuffNode
 The base HuffNode class is used to represent both leaf and internal HuffNodes. More...

class  HuffNode_Middle
 A derived huffman node for a node in the middle of the tree. More...

class  HuffNode_Leaf
 The leaves of the huffman tree contains actual symbol information. More...

class  PQWeightGreater
 We need to make a special Greater<> classes used during sorting, since our collection stl elements are built from pointers, and the default sort will be done on pointer addresses instead of weights if we don't. More...


Defines

#define OCTANE_USEJIBZHUFFMANPQGREATER
#define THuffmanNodeWeight   float
 Precision for representing a huffman weight.

#define THuffmanNodeWeight_MAX   FLOATMAX
 Largest value a weight can hold.

#define DEF_HUFFMANPQ_MAXIMUM_CODEBITDEPTH   160
 Maximum depth that will be seen in the priority queue (huffman tree).

#define DEF_HUFFMANPQ_MAXFUNCBITS   200
 simple define which should represent more bits than we could ever see in a symbol (depth of tree) note that this size does not effect the per-symbol memory used, its just a one time thing, so we can make it as large as we want.


Typedefs

typedef std::priority_queue<
HuffNode *, std::vector<
HuffNode * >, PQWeightGreater<
HuffNode * > > 
THuffmanNodePriorityQueue


Define Documentation

#define DEF_HUFFMANPQ_MAXIMUM_CODEBITDEPTH   160
 

Maximum depth that will be seen in the priority queue (huffman tree).

Which is equivalent to the maximum bitlength for any code. Setting this is a little tricky because it directly affects the memory used by every dictionary entry. an entry needs to reserver a number of bits equal to the maximum depth of any node in the huffman tree. so this value should be a multiple of 8, and can be estimated from the number of dictionary entries that will be in the final huffman tree. The code will detect if it is not large enough and tell you during building of the codebook. A reasonable value for a dictionary of several thousand symbols would be something like 104.

Definition at line 91 of file huffmannodes.hpp.

Referenced by HuffNode_Leaf::AddBitsToBitWriter(), HuffNode_Leaf::get_bitcode_string(), HuffNode_Leaf::traverse_buildbitcodes(), and HuffNode_Middle::traverse_buildbitcodes().

 

Generated on 20 May 2004 by doxygen 1.3.3