Octane v1.01.20 - The Open Compression Toolkit for C++

http://octane.sourceforge.net/

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