huffman.h

游戏开发数据结构Data Structures for Game Programmers

// ============================================================================
// Data Structures For Game Programmers
// Ron Penton
// Huffman.h
// This file holds the Huffman Tree compression class
// ============================================================================
#ifndef HUFFMAN_H
#define HUFFMAN_H


#include "Array.h"
#include "Bitvector.h"
#include "BinaryTree.h"
#include "Heap.h"


// ----------------------------------------------------------------
//  Name:           HuffmanNode
//  Description:    This is the node class that is stored in
//                  the huffman tree.
// ----------------------------------------------------------------
template<class DataType>
class HuffmanNode
{
public:

// ----------------------------------------------------------------
//  Name:           m_data
//  Description:    The data to store in the node
// ----------------------------------------------------------------
    DataType m_data;

// ----------------------------------------------------------------
//  Name:           m_code
//  Description:    The huffman code that represents this data.
// ----------------------------------------------------------------
    unsigned long int m_code;

// ----------------------------------------------------------------
//  Name:           m_codeLength
//  Description:    The length of the code, in bits
// ----------------------------------------------------------------
    int m_codeLength;
};


// ----------------------------------------------------------------
//  Name:           HuffmanFrequency
//  Description:    This class stores frequency information
//                  about a piece of data.
// ----------------------------------------------------------------
template<class DataType>
class HuffmanFrequency
{
public:
    DataType m_data;
    int m_frequency;
};


// ----------------------------------------------------------------
//  Name:           CompareNodes
//  Description:    This is a comparison function, for use in the
//                  tree creation algorithm. Nodes with a higher
//                  frequency are "lower", becaue items with the
//                  lowest frequencies need to be used first.
//  Arguments:      left, right: the nodes
//  Return Value:   the comparison value.
// ----------------------------------------------------------------
template<class DataType>
int CompareNodes( BinaryTree< HuffmanFrequency<DataType> >* left,
                  BinaryTree< HuffmanFrequency<DataType> >* right )
{
    // return right-left; smaller frequencies are "Higher"
    return right->m_data.m_frequency - left->m_data.m_frequency;
}



// ----------------------------------------------------------------
//  Name:           Huffman
//  Description:    The huffman encoding/decoding class.
// ----------------------------------------------------------------
template<class DataType, unsigned long int MaxValue>
class Huffman
{
public:

    // typedef the classes to make them easier to use.
    typedef HuffmanNode<DataType> Node;
    typedef HuffmanFrequency<DataType> Frequency;
    typedef BinaryTree<Frequency> TreeNode;


// ----------------------------------------------------------------
//  Name:           m_compressedData
//  Description:    This is the compressed data.
// ----------------------------------------------------------------
    Bitvector m_compressedData;

// ----------------------------------------------------------------
//  Name:           m_dataLength
//  Description:    The length of the data stored.
// ----------------------------------------------------------------
    int m_dataLength;

// ----------------------------------------------------------------
//  Name:           m_compressedLength
//  Description:    the length, in bits, of the compressed data
// ----------------------------------------------------------------
    int m_compressedLength;

// ----------------------------------------------------------------
//  Name:           m_huffmanTree
//  Description:    The huffman tree
// ----------------------------------------------------------------
    Array<Node> m_huffmanTree;

// ----------------------------------------------------------------
//  Name:           m_maxEntry
//  Description:    This is the maximum entry in the arrayed
//                  representation of the huffman tree.
// ----------------------------------------------------------------
    int m_maxEntry;

// ----------------------------------------------------------------
//  Name:           m_lookupTable
//  Description:    This is the lookup table of nodes
// ----------------------------------------------------------------
    Array<Node> m_lookupTable;


// ----------------------------------------------------------------
//  Name:           Huffman
//  Description:    Constructor, creates an empty huffman tree.
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    Huffman()
        :   m_compressedData( 1 ),
            m_huffmanTree( 1 ),
            m_lookupTable( MaxValue + 1 )
    {
        m_dataLength = 0;
        m_compressedLength = 0;
        m_maxEntry = 0;
    }



// ----------------------------------------------------------------
//  Name:           CalculateTree
//  Description:    this calculates a huffman tree for a given
//                  array of data
//  Arguments:      p_array: the array of data.
//  Return Value:   None
// ----------------------------------------------------------------
    void CalculateTree( Array<DataType>& p_array )
    {
        // create an array to hold the frequency table.
        Array<int> frequencyTable( MaxValue + 1 );

        int index;

        // clear the frequency table
        for( index = 0; index <= MaxValue; index++ )
        {
            frequencyTable[index] = 0;
        }

        // calculate the frequency table
        for( index = 0; index < p_array.Size(); index++ )
        {
            frequencyTable[ p_array[index] ]++;
        }

        // create a heap that can hold every entry in the table
        Heap<TreeNode*> heap( frequencyTable.Size(), CompareNodes );

        TreeNode* parent;
        TreeNode* left;
        TreeNode* right;

        // first go though the freqency table and create a node for them,
        // and add them into the heap.
        for( index = 0; index <= MaxValue; index++ )
        {
            // only add the item if it has a freqency
            if( frequencyTable[index] != 0 )
            {
                parent = new TreeNode;
                parent->m_data.m_data = index; 
                parent->m_data.m_frequency = frequencyTable[index];
                heap.Enqueue( parent );
            }
        }


        // now that all of the nodes are in the queue,
        // perform the huffman tree creation.
        while( heap.m_count > 1 )
        {
            // remove the first two items from the heap
            left = heap.Item();
            heap.Dequeue();
            right = heap.Item();
            heap.Dequeue();

            // create the new parent node
            parent = new TreeNode;
            parent->m_left = left;
            parent->m_right = right;
            parent->m_data.m_frequency = left->m_data.m_frequency + 
                                         right->m_data.m_frequency;

            // add the new node into the queue again.
            heap.Enqueue( parent );
        }


        // calculation of the tree is complete, now convert the tree into the
        // binary tree array.
        ConvertTreeToArray( heap.m_array[1] );

        // create the lookup table now
        CreateLookupTable();


        // delete the tree once you are done with it.
        delete heap.m_array[1];
    }


// ----------------------------------------------------------------
//  Name:           Compress
//  Description:    Compresses an array of data into the
//                  m_compressedData bitvector
//  Arguments:      p_array: the array to compress.
//  Return Value:   None
// ----------------------------------------------------------------
    void Compress( Array<DataType>& p_array )
    {
        int index;
        int vectorindex = 0;
        int codeindex;
        int codelength;
        unsigned long int code;
        bool value;

        // this routine goes through the entire array.
        //  - looks up each item in the huffman tree to find out its code
        //  - adds the code to the bitvector.

        for( index = 0; index < p_array.Size(); index++ )
        {
            // look up the code and its length
            code = m_lookupTable[ p_array[index] ].m_code;
            codelength = m_lookupTable[ p_array[index] ].m_codeLength;

            // resize vector if needed.
            if( m_compressedData.Size() < vectorindex + codelength )
                m_compressedData.Resize( m_compressedData.Size() * 2 );

            for( codeindex = 0; codeindex < codelength; codeindex++ )