一霎微雨洒庭轩

2007-08-22

优先队列示例: 哈夫曼编码 - [Algorithms]

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://conoon.blogbus.com/logs/7856751.html

//优先队列示例: 哈夫曼编码
//Modified By Veiz
//Huffman.h
#ifndef HUFFMAN_H_
#define HUFFMAN_H_

#include <queue>
#include <vector>
#include <string>
#include <istream>
#include <ostream>
#include <fstream>
#include <iostream>

using namespace std;

struct huffmanNode;
typedef huffmanNode* nodePtr;
struct huffmanNode
{   //霍夫曼树结点
    unsigned int freq;   //频率
  
    string code;  //编码
    nodePtr left; 
    nodePtr right;
    nodePtr parent;
};

class Compare
{   //比较类
public:
    bool operator() (const nodePtr& c1, const nodePtr& c2) const
    {
        return  ((*c1).freq > (*c2).freq);
    }
};

class Huffman
{
private:
    static const int MAX_SIZE = 256;
    nodePtr nodePtrArray[MAX_SIZE];
    priority_queue<nodePtr, vector<nodePtr>, Compare> priorityQueue;  //一个优先队列，函数Compare指定了优先准则
    fstream inFile;
    string inFilename;
    string outFilename;
    void CreatePriorityQueue();
    void CreateNodePtrArray();
    void CreateHuffmanTree();
    void CalculateHuffmanCodes();
    void SaveToFile();
public:
    void CreateHuffmanCodes(string inFilename, string outFilename);   
};

#endif /* HUFFMAN_H_ */

//  Huffman.cpp

#include "Huffman.h"

void Huffman::CreatePriorityQueue()
{ 
    for(int i = 0; i < MAX_SIZE; ++i)
    {
        nodePtrArray[i] = new huffmanNode;
        nodePtrArray[i]->freq = 0;
    }

    CreateNodePtrArray();

    nodePtr entry;
    for(int i = 0; i < MAX_SIZE; ++i)
    {
        entry = nodePtrArray[i];
        if(entry->freq > 0)
        {
            priorityQueue.push(entry);
        } 
    }
}

void Huffman::CreateNodePtrArray()
{
    nodePtr entry;
    inFile.seekg(0, ios::end);
 unsigned int posEnd = inFile.tellg();
 inFile.seekg(0, ios::beg);
    char ch[1];
    for(unsigned int i = 0 ; i < posEnd; ++i)
    {       
        inFile.read(ch, 1);
        entry = nodePtrArray[(unsigned char)(ch[0])];
        ++entry->freq;
        if(entry->freq == 1)
        {   //字符第一次出现
            entry->left = 0;
            entry->right = 0;
            entry->parent = 0;
        }        
    }
}

void Huffman::CreateHuffmanTree()
{
    nodePtr left;  
    nodePtr right; 
    nodePtr sum;

    while(priorityQueue.size() > 1)
    {
        left = priorityQueue.top(); //从优先队列中取出一个子树
        priorityQueue.pop();    //从优先队列中移除一个子树
        left->code = string("0");   //左子树用0表示

        right = priorityQueue.top();    //从优先队列中取出一个子树
        priorityQueue.pop();    //从优先队列中移除一个子树
        right->code = string("1");   //右子树用1表示

        sum = new huffmanNode;
        sum->parent = 0;
        sum->freq = left->freq + right->freq;   //子树根的节点标记等于它两个后代的频率计数之和
        sum->left = left;
        sum->right = right;
        left->parent = sum;
        right->parent = sum;   
        priorityQueue.push(sum);    //把新子树置入优先队列
    }
}

void Huffman::CalculateHuffmanCodes()
{
    string code;
    nodePtr entry;

    for(int i = 0; i < MAX_SIZE; ++i)
    {
        code = "";
        entry = nodePtrArray[i];
        if(entry->freq > 0)
        {
            do
            {
                code = entry->code + code;
                entry = entry->parent;
            }while(entry->parent != 0);
            nodePtrArray[i]->code = code;
        }
    }
}

void Huffman::SaveToFile()
{
    nodePtr entry;
    string line;
    inFile.close();
    ifstream inFile;
    inFile.open(inFilename.c_str(), ios::in | ios::binary);
    ofstream outFile;
    outFile.open(outFilename.c_str(), ios::out | ios::binary);
    if(!outFile)
    {
        cerr << "OutputFileNotFoundException";
    }
    inFile.seekg(0, ios::end);
 unsigned int posEnd = inFile.tellg();
 inFile.seekg(0, ios::beg);
    char ch[1];
    for(unsigned int i = 0 ; i < posEnd; ++i)
    {       
        inFile.read(ch, 1);
        entry = nodePtrArray[(unsigned char)(ch[0])];
        outFile.write(entry->code.c_str(), (streamsize)entry->code.length());
    }
    outFile.close();
}

void Huffman::CreateHuffmanCodes(string inFilename, string outFilename)
{
    this->inFilename = inFilename;
    inFile.open(inFilename.c_str(), ios::in | ios::binary);
    if(!inFile)
    {
        cerr << "InputFileNotFoundException";
    }
    this->outFilename = outFilename;

    CreatePriorityQueue();
    CreateHuffmanTree();   
    CalculateHuffmanCodes();
    SaveToFile();
}

//  main.cpp

#include <string>
#include <iostream>
#include "Huffman.h"
using namespace std;

int main(int argc, char* argv[])
{
    const string USAGE_MESSAGE = "Usage: HUFFMAN [[drive:][path]inputfilename] [[drive:][path]outputfilename]";
    const string CONTINUE_MESSAGE = "Press any key to continue...";
    if(argc != 3)
    {
        cout << USAGE_MESSAGE << endl;       
    }       
    else
    {
        string inputFilename(argv[1]);
        string outputFilename(argv[2]);
        Huffman huffman;
        huffman.CreateHuffmanCodes(inputFilename, outputFilename);
    }
    cout << CONTINUE_MESSAGE << endl;
    cin.get();
    return 0;
}