1.前缀码
在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀，即前缀码。例如，有两个码字111与1111，那么这两个码字就不符合前缀码的规则，因为111是1111的前缀。放到二叉树里来讲，只用叶子节点编码的码字才是前缀码，如果同时使用中间节点和叶子节点编码，那结果就不是前缀码。因为压缩中经过编码的码字全部是前缀码，所以在对照码表解压的时候，碰到哪个码字就是哪个码字，不用担心出现某个字符的编码是另一个字符的编码的前缀的情况，该意识一定要具备。
 
关于前缀码，下面一段话摘自《算法导论》：“前缀码的作用是简化解码过程。由于没有码字是其他码字的前缀，编码文件的开始码字是无歧义的。我们可以简单的识别出开始码字，将其转换会原字符，然后对编码文件剩余部分重复这种解码过程。”
 
2.原始哈夫曼编码
哈夫曼设计了一个贪心算法来构造最优前缀码，被称为哈夫曼编码（Huffman code），其正确性证明依赖于贪心选择性质和最优子结构。哈夫曼编码可以很有效的压缩数据，具体压缩率依赖于数据本身的特性。这里我们先介绍几个概念：码字、码字长度、定长编码与变长编码。
 
每个字符可以用一个唯一的二进制串表示，这个二进制串称为这个字符的码字，这个二进制串的长度称为这个码字的码字长度。码字长度固定就是定长编码，码字长度不同则为变长编码。变长编码可以达到比定长编码好得多的压缩率，其思想是赋予高频字符（出现频率高的字符）短（码字长度较短）码字，赋予低频字符长码字。例如，我们用ASCII字符编辑一个文本文档，不论字符在整个文档中出现的频率，每个字符都要占用一个字节；如果我们使用变长编码的方式，每个字符因在整个文档中的出现频率不同导致码字长度不同，有的可能占用一个字节，而有的可能只占用一比特，这个时候，整个文档占用空间就会比较小了。当然，如果这个文本文档相当大，导致每个字符的出现频率基本相同，那么此时所谓变长编码在压缩方面的优势就基本不存在了（这点要十分明确，这是为什么压缩要分块的原因之一，后续源码分析会详细讲解）。
 
哈夫曼编码会自底向上构造出一棵对应最优编码的二叉树，我们使用下面这个例子来说明哈夫曼树的构造过程。首先，我们已知在某个文本中有如下字符及其出现频率，


字符


a


b


c


d


e


f


出现频率


45


13


12


16


 9


 5


构造过程如下图所示：

图1到图6列除了整个哈夫曼树构造过程中的每个步骤。在一开始，每个字符都已经按照出现频率大小排好顺序，在后续的步骤中，每次都将频率最低的两棵树合并，然后用合并后的结果再次排序（注意，排序不是目的，目的是找到这时出现频率最低的两项，以便下次合并。gzip源码中并没有专门去“排序”，而是使用专门的数据结构把频率最低的两项找到即可）。叶子节点用矩形表示，每个叶子节点包含一个字符及其频率。中间节点用圆圈表示，包含其孩子节点的频率之和。中间节点指向左孩子的边标记为0，指向右孩子的边标记为1。一个字符的码字对应从根到其叶节点的路径上的边的标签序列。图1为初始集合，有六个节点，每个节点对应一个字符；图2到图5为中间步骤，图6为最终哈夫曼树。此时每个字符的编码都是前缀码。
 
3.Deflate所用的哈夫曼编码的性质
哈夫曼编码使用的数据结构就是二叉树。这里介绍一些阅读gzip源码时需要使用的一些哈夫曼树的性质，注意，deflate算法使用的哈夫曼树在原始哈夫曼树的基础上增加了一些独特的性质，专门为压缩/解压缩服务。本章只要了解这些性质并记住这里提出的问题即可。上文所述是原始哈夫曼树，与压缩使用的哈夫曼树还有一些区别。这部分内容主要参考博客http://blog.csdn.net/imquestion/article/details/16439，还有一部分是我自己总结的。我们参看下图来验证这些性质，注意：码字长度就是树的深度，

a.  如果有n个叶子节点，那么整棵树的总节点个数为2n-1。以上图为例，有6个叶子节点，而总节点共有11个。注意，这个地方与gzip源码中几个数组的定义不同，源码中是2n+1，原因后续分析，这里提一下，后续分析时要留心；
b.  整棵树最左边叶子节点的码字为0（码字长度视情况而定）；
c.   码字长度相同（即树深相同）的叶子节点，它们的码字是连续的，而且右面的总比左面的大1。从上图中可以看出，c、b、d节点在同一层，c的码字为100，b的码字为101，符合该性质，但是d的码字为111，不符合该性质。如果能将d节点与14节点交换，那就符合该性质了。实际上，这就是deflate中所用哈夫曼编码与原始哈夫曼编码不同的地方，前者构建哈夫曼树的过程在后者的构建上增加了一些条件。这个地方留作一个问题，我们后续分析源码时详细讨论，这里要留心。
 
此时我们已经初步看到deflate中所用哈夫曼编码与原始哈夫曼编码的不同，现在我们使用一棵deflate中所用的标准的哈夫曼树来分析以下的性质，如下图所示

d.  树深为（n+1）时，该层最左面的叶子节点（即本层码字值最小的那个叶子节点）的值为，树深为n时，n层最右面的叶子节点（即这一层码字值最大的叶子节点）的值+1，并且要变长一位（即左移一位）。以上图为例，i的码字是01，f的码字是100，符合该性质；a的码字是11100，但是a的上一层没有叶子节点，不能用该性质？我们先接着看下面的性质；
e.  树深为n这层，最右面的叶子节点（即该层码字值最大的叶子节点）的值为最左面的叶子节点的值（即该层码字值最小的叶子节点）加上该层所含叶子节点的个数减一。以上图为例，f的码字是100，e的码字是110，该层共有叶子节点三个，符合该性质；a的码字为11100，d的码字为11111，该层共有叶子节点四个，符合该性质；
f.  前两条性质可以合成本条性质，即，树深为（n+1）时，该层最左面的叶子节点的值为，树深为n的这一层最左面的叶子节点的值加上该层所有叶子节点的个数，然后变长一位（即左移一位）。以上图为例，h的码字为00，改层有叶子节点两个，f的码字为100，所以00+10（2的二进制表示）=10，将10左移一位就是100，即f，符合该性质。实际上，该性质在源码中对应的代码就是code
 = (code + bl_count[bits-1])<< 1，后面我们详细分析这句话。看到这里，上面第四条性质的问题就可以解决了，f的码字是100，f所在的这层有三个叶子节点，那么再往下一层，这层没有叶子节点，但是我们可以假设一个不存在的叶子节点，这个不存在的叶子节点的编码要用f去计算，即，code = (100+11)<<1，11就是二进制的3，所以code就是1110，即这个不存在的叶子节点的编码就是1110，用它去计算a，继续套用这个公式，code = (1110+0)<<1，所以code就是11100，与性质是符合的！！！
g. 节点n的左子节点是2n，右子节点是2n+1；
 
其实deflate中使用的哈夫曼编码就是“范式哈夫曼编码”，范式哈夫曼编码的相关介绍如下：“范式哈夫曼编码最早由Schwartz提出，它是哈夫曼编码的一个子集。其中心思想是使用某些强制的约定，仅通过很少的数据便能重构出哈夫曼编码树的结构。其中一种很重要的约定是数字序列属性(numerical
 sequence property)，它要求相同长度的码字是连续整数的二进制描述。例如，假设码字长度为4的最小值为0010，那么其它长度为4的码字必为0011, 0100, 0101, ...；另一个约定：为了尽可能的利用编码空间，长度为i第一个码字f(i)能从长度为i-1的最后一个码字得出, 即：f(i) = 2(f(i-1)+1)。假定长度为4的最后一个码字为1001，那么长度为5的第一个码字便为10100。最后一个约定：码字长度最小的第一个编码从0开始。通过上述约定，解码器能根据每个码字的长度恢复出整棵哈夫曼编码树的结构。”从上面的性质可以看出，我们这里使用的就是范式哈夫曼编码。
 

Huffman 算法原理

前缀码

在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀，即前缀码。 例如，有两个码字 111 与 1111，那么这两个码字就不符合前缀码的规则，因为 111 是

1111 的前缀。放到二叉树里来讲，只用叶子节点编码的码字才是前缀码，如果同时使用 中间节点和叶子节点编码，那结果就不是前缀码。因为压缩中经过编码的码字全部是前 缀码，所以在对照码表解压的时候，碰到哪个码字就是哪个码字，不用担心出现某个字 符的编码是另一个字符的编码的前缀的情况，该意识一定要具备。

关于前缀码，下面一段话摘自《算法导论》：“前缀码的作用是简化解码过程。由于 没有码字是其他码字的前缀，编码文件的开始码字是无歧义的。我们可以简单的识别出 开始码字，将其转换会原字符，然后对编码文件剩余部分重复这种解码过程。

1111111     ? 111 1111 ? 1111 111

 

哈夫曼编码

 

哈夫曼设计了一个贪心算法来构造最优前缀码，被称为哈夫曼编码（Huffman code）， 其正确性证明依赖于贪心选择性质和最优子结构。哈夫曼编码可以很有效的压缩数据，


 


具体压缩率依赖于数据本身的特性。这里我们先介绍几个概念：码字、码字长度、定长 编码与变长编码。

每个字符可以用一个唯一的二进制串表示，这个二进制串称为这个字符的码字，这 个二进制串的长度称为这个码字的码字长度。码字长度固定就是定长编码，码字长度不 同则为变长编码。变长编码可以达到比定长编码好得多的压缩率，其思想是赋予高频字 符（出现频率高的字符）短（码字长度较短）码字，赋予低频字符长码字。例如，我们 用 ASCII 字符编辑一个文本文档，不论字符在整个文档中出现的频率，每个字符都要占 用一个字节；如果我们使用变长编码的方式，每个字符因在整个文档中的出现频率不同 导致码字长度不同，有的可能占用一个字节，而有的可能只占用一比特，这个时候，整 个文档占用空间就会比较小了。当然，如果这个文本文档相当大，导致每个字符的出现 频率基本相同，那么此时所谓变长编码在压缩方面的优势就基本不存在了（这点要十分 明确，这是为什么压缩要分块的原因之一，后续源码分析会详细讲解）。

哈夫曼编码会自底向上构造出一棵对应最优编码的二叉树，我们使用下面这个例子 来说明哈夫曼树的构造过程。首先，我们已知在某个文本中有如下字符及其出现频率，

 


			
字符
			
			

			
a
			
			

			
b
			
			

			
c
			
			

			
d
			
			

			
e
			
			

			
f
			
		

			
出现频率
			
			

			
45
			
			

			
13
			
			

			
12
			
			

			
16
			
			

			
9
			
			

			
5
			
		
构造过程如下图所示：


 


 

 

 

图 1 到图 6 列除了整个哈夫曼树构造过程中的每个步骤。在一开始，每个字符都已 经按照出现频率大小排好顺序，在后续的步骤中，每次都将频率最低的两棵树合并，然 后用合并后的结果再次排序（注意，排序不是目的，目的是找到这时出现频率最低的两 项，以便下次合并。gzip 源码中并没有专门去“排序”，而是使用专门的数据结构把频率 最低的两项找到即可）。叶子节点用矩形表示，每个叶子节点包含一个字符及其频率。中 间节点用圆圈表示，包含其孩子节点的频率之和。中间节点指向左孩子的边标记为 0， 指向右孩子的边标记为 1。一个字符的码字对应从根到其叶节点的路径上的边的标签序 列。图 1 为初始集合，有六个节点，每个节点对应一个字符；图 2 到图 5 为中间步骤，

图 6 为最终哈夫曼树。此时每个字符的编码都是前缀码。


 



 

哈夫曼压缩和解压文件

利用库中的优先级队列实现哈夫曼树，最后基于哈夫曼树最终实现文件压缩。

1.统计文件中字符出现的次数，利用优先级队列构建 Haffman 树，生成 Huffman 编 码。构造过程可以使用 priority_queue 辅助，每次 pq.top()都可以取出权值（频数）最小 的节点。每取出两个最小权值的节点，就 new 出一个新的节点，左右孩子分别指向它 们。然后把这个新节点 push 进优先队列。

2.压缩：利用 Haffman 编码对文件进行压缩，即在压缩文件中按顺序存入每个字符 的 Haffman 编码。 码表（实际存储是对应数值的概率，然后调用程序生成码表） + 编码

 

 



3.将文件中出现的字符以及它们出现的次数写入配置文件中，以便后续压缩使用。

4.解压缩：利用配置文件重构 Haffman 树，对文件进行减压缩。

HuffmanTree.hpp

#ifndef _HUFFMAN_TREE_H_ 
#define _HUFFMAN_TREE_H_
#include <iostream>
#include <queue>
#include <vector>
#include <unistd.h>
using namespace std;

template<class W>
struct HuffmanTreeNode
{
    HuffmanTreeNode(const W &weight)
    : _pLeft(NULL)
    , _pRight(NULL)
    , _pParent(NULL)
    , _weight(weight)
    {}
    HuffmanTreeNode<W>*_pLeft;
    HuffmanTreeNode<W>*_pRight;
    HuffmanTreeNode<W>*_pParent;
    W _weight;
};

template<class W>
class HuffmanTree
{
    typedef HuffmanTreeNode<W>*PNode;
public:
        HuffmanTree()
        : _pRoot(NULL)
    {}
    HuffmanTree(W*array, size_t size, const W&invalid)
    {
        _CreateHuffmantree(array,  size, invalid);

    }
    void _Destroy(PNode&pRoot)
    {
        //后序
        if (pRoot)
        {
            _Destroy(pRoot->_pLeft);
            _Destroy(pRoot->_pRight);
            delete pRoot;
            pRoot = NULL;
        }
    }
    ~HuffmanTree()
    {
        _Destroy(_pRoot);
    }
    PNode GetRoot()
    {
        return  _pRoot;
    }
private:    
    //构建哈夫曼树
    void _CreateHuffmantree(W*array, size_t size, const W&invalid)
    {

        struct PtrNodeCompare
        {
            bool operator()(PNode n1, PNode n2)//重载“（）”
            {
                return n1->_weight <  n2->_weight;
            }
        };
        priority_queue<PNode, vector<PNode>, PtrNodeCompare>hp; // 最大堆

        for (size_t i = 0; i < size; ++i)
        {
            if (array[i] != invalid)
            {
                hp.push(new HuffmanTreeNode<W>(array[i]));      // 数据入堆
            }
        }
        //空堆
        if (hp.empty())
            _pRoot = NULL;
        
        while (hp.size()>1)
        {
            PNode pLeft = hp.top();
            hp.pop();
            PNode pRight = hp.top();
            hp.pop();
            PNode pParent = new HuffmanTreeNode<W>(pLeft->_weight + pRight->_weight);//左加右的权值，作为新节点
            pParent->_pLeft = pLeft;
            pLeft->_pParent = pParent;

            pParent->_pRight = pRight;
            pRight->_pParent = pParent;
            hp.push(pParent);
        }
        _pRoot = hp.top();          // 节点在堆
    }

public:
    PNode _pRoot;
};
#endif

 FileCompress.hpp

/*利用库中的优先级队列实现哈夫曼树，最后基于哈夫曼树最终实现文件压缩。 
描述： 
    1.统计文件中字符出现的次数，利用优先级队列构建Haffman树，生成Huffman编码。 
    构造过程可以使用priority_queue辅助，每次pq.top()都可以取出权值（频数）最小的节点。每取出两个最小权值的节点，就new出一个新的节点，左右孩子分别指向它们。然后把这个新节点push进优先队列。  
    2.压缩：利用Haffman编码对文件进行压缩，即在压缩文件中按顺序存入每个字符的Haffman编码。 
    3.将文件中出现的字符以及它们出现的次数写入配置文件中，以便后续压缩使用。 
    4.解压缩：利用配置文件重构Haffman树，对文件进行减压缩。
*/
#ifndef _FILE_COMPRESS_H_
#define _FILE_COMPRESS_H_
#include "HuffmanTree.hpp"
#include <iostream>
#include <vector>
#include <assert.h>
#include <unistd.h>
using namespace std;


unsigned long getFileSize(const char *path)
{
	unsigned long filesize = -1;
	FILE *fp;
	fp = fopen(path, "r");
	if(fp == NULL)
		return filesize;
	fseek(fp, 0L, SEEK_END);
	filesize = ftell(fp);
	fclose(fp);
	return filesize;
}


typedef unsigned int CountType;
typedef unsigned char CharType;
struct CharInfo
{
    CharType _ch;//字符
    CountType _count;//次数
    string  _code;//编码

    bool operator!=(const CharInfo &info)
    {
        return _count != info._count;
    }
    CharInfo operator+(const CharInfo &info)
    {
        CharInfo ret;
        ret._count = _count + info._count;
        return ret;
    }
    bool operator<(const CharInfo &info)
    {
        return _count > info._count;
    }
};

class FileCompress
{
    typedef HuffmanTreeNode<CharInfo> Node;
    struct TmpInfo
    {
        CharType _ch;//字符
        CountType _count;//次数
    };

public:
    //构造函数
    FileCompress()
    {
        for (size_t i = 0; i < 256; ++i)
        {
            _infos[i]._ch = i;
            _infos[i]._count = 0;
        }
    }
    //获取哈夫曼编码
    void GenerateHuffmanCode(Node *root, string code) 
    {
        if (root == NULL)
            return;
        //前序遍历生成编码
        if (root->_pLeft == NULL && root->_pRight == NULL)
        {
            _infos[(unsigned char)root->_weight._ch]._code = code;
            return;
        }
        GenerateHuffmanCode(root->_pLeft, code + '0');
        GenerateHuffmanCode(root->_pRight, code + '1');
    }
    // 真正的压缩算法窗口是32k, 我们这里直接对所有数据进行编码 
    void Compress(const char *file) //file:源文件
    {
        unsigned long fileSize = getFileSize(file);
        //1.统计字符出现的次数
        FILE *fout = fopen(file, "rb");
        assert(fout);
        char ch = fgetc(fout);
        while (feof(fout) == 0) //如文件结束，则返回值为1，否则为0
        {
            _infos[(unsigned char)ch]._count++;     // 计算对应字符出现的频率
            ch = fgetc(fout);
        }
        //2.生成Huffmantree 及code
        CharInfo invalid;
        invalid._count = 0;
        // 2.1 生成Huffmantree， 构建哈夫曼树
        HuffmanTree<CharInfo> tree(_infos, 256, invalid); //参数：数组，256个，无效值（出现0次）

        string compressfile = file;                    //
        compressfile += ".huffman";                    //?
        FILE *fin = fopen(compressfile.c_str(), "wb"); //打开压缩文件
        assert(fin);

        string code;
        //  2.2 生成code
        GenerateHuffmanCode(tree.GetRoot(), code);
        //3.0 写入字符出现的信息
        int writeNum = 0;
        int objSize = sizeof(TmpInfo);
        for (size_t i = 0; i < 256; ++i)            // 这里实质是讲码表存储到文件的头部
        {
            if (_infos[i]._count > 0) 
            {
                TmpInfo info;
                info._ch = _infos[i]._ch;
                info._count = _infos[i]._count;
                printf("codec ch:%u, cout:%u\n", (unsigned char)info._ch, info._count);
                fwrite(&info, objSize, 1, fin);         // 将对应的码流信息写入
                writeNum++;
            }
        }
        TmpInfo info;
        info._count = -1;
        printf("code objSize:%d\n", objSize);
        fwrite(&info, objSize, 1, fin); //把info._count = -1写进去作为结束标志位
        

        //3.压缩
        int writeCount = 0;
        int readCount = 0;
        fseek(fout, 0, SEEK_SET); //文件指针、偏移量、参照位置
        ch = fgetc(fout);
        readCount++;
        unsigned char value = 0;
        size_t pos = 0;

        while (feof(fout) == 0)           // 一个个字符读取,效率虽然低一些，但不影响实验
        {
            // 读取数据，查找对应编码
            string &code = _infos[(unsigned char)ch]._code; // 查找对应的编码
            printf("code[%d]:%u:%s\n", readCount, (unsigned char)ch, code.c_str());
            // code 实际存储的是对应 某个字符的哈夫曼编码
            for (size_t i = 0; i < code.size(); ++i)
            {
                if (code[i] == '1')
                    value |= (1 << pos);
                else if (code[i] == '0')
                {
                    value &= ~(1 << pos);
                }
                else
                {
                    assert(false);
                    printf("assert(false); ??????????");
                }
                ++pos;
                if (pos == 8)
                {
                    writeCount++;
                    fputc(value, fin);      // 够8个bit存储
                    value = 0;
                    pos = 0;
                }
            }
            readCount++;
            ch = fgetc(fout);
        }

        if (pos > 0)
        {
            writeCount++;
            fputc(value, fin); //写入压缩文件（fin）
        }
        printf("huffman code table  size::%d\n", objSize * (writeNum + 1));
        printf("compress file data  size:%d\n", writeCount);
        unsigned long totalSize = writeCount + objSize *  (writeNum + 1);
        printf("compress file total size:%lu, orign file size:%lu, ratio:%0.2f\n",
             totalSize, fileSize,  (float)(totalSize*1.0/fileSize));
        fclose(fout);
        fclose(fin);
    }
    void Uncompress(const char *file)
    {
        string uncompressfile = file;           //file:Input.txt.huffman
        size_t pos = uncompressfile.rfind('.'); //找到倒数第一个'.'
        assert(pos != string::npos);
        uncompressfile.erase(pos);                       //删除掉'.'后面字符串
        uncompressfile += ".unhuffman";                  //Input.txt+'.unhuffman'
        FILE *fin = fopen(uncompressfile.c_str(), "wb"); //打开解压缩文件
        assert(fin);
        FILE *fout = fopen(file, "rb"); //打开压缩文件
        assert(fout);

        //3.0 读入字符出现的信息
        TmpInfo info;
        int cycleNum = 1;
        int objSize = sizeof(TmpInfo);
        fread(&info, objSize, 1, fout);

        while (info._count != -1)           //-1为结束标志 
        {
            //  printf("decodec ch:%u, cout:%u\n", (unsigned char)info._ch, info._count);
            _infos[(unsigned char)info._ch]._ch = info._ch;
            _infos[(unsigned char)info._ch]._count = info._count;

            fread(&info, objSize, 1, fout);
            cycleNum++;
        }

        int aaa = 0;
        //重建huaffman树
        CharInfo invalid;
        invalid._count = 0;
        HuffmanTree<CharInfo> tree(_infos, 256, invalid); //参数：数组，256个，无效值（出现0次）
        Node *root = tree.GetRoot();
        Node *cur = root;
        CountType n = root->_weight._count; //所有叶子节点的和（源文件字符的个数）
        char ch = fgetc(fout);             //从fout(压缩文件)读字符
        int readCount = 0;

        while (ch != EOF || n > 0)
        {
            for (size_t i = 0; i < 8; ++i)
            {
                if ((ch & (1 << i)) == 0)
                    cur = cur->_pLeft;   // 往左边找
                else
                    cur = cur->_pRight; // 往右边找
                if (cur->_pLeft == NULL && cur->_pRight == NULL)
                {
                    //cout << cur->_weight._ch;
                    readCount++;
                    if(readCount % 1024 == 0) 
                    {
                        // printf("uncompress %dk data\n", readCount/1024);
                    }
                    fputc(cur->_weight._ch, fin); //fin解压缩文件
                    cur = root;
                    if (--n == 0)
                        break;
                }
            }
            ch = fgetc(fout);
        }
        printf("uncompress end\n");
        fclose(fin);
        fclose(fout);
    }

protected:
    CharInfo _infos[256];
};


#endif

main.cpp

 

/*
 * @Author: your name
 * @Date: 2020-06-04 16:21:01
 * @LastEditTime: 2020-06-04 19:13:01
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \huffman\main.cpp
 */ 
/*利用库中的优先级队列实现哈夫曼树，最后基于哈夫曼树最终实现文件压缩。 
描述： 
    1.统计文件中字符出现的次数，利用优先级队列构建Haffman树，生成Huffman编码。 
    构造过程可以使用priority_queue辅助，每次pq.top()都可以取出权值（频数）最小的节点。每取出两个最小权值的节点，就new出一个新的节点，左右孩子分别指向它们。然后把这个新节点push进优先队列。  
    2.压缩：利用Haffman编码对文件进行压缩，即在压缩文件中按顺序存入每个字符的Haffman编码。 
    3.将文件中出现的字符以及它们出现的次数写入配置文件中，以便后续压缩使用。 
    4.解压缩：利用配置文件重构Haffman树，对文件进行减压缩。
*/

#include "FileCompress.hpp"
#include <iostream>
#include <vector>
#include <unistd.h>
#include <assert.h>

// 注意是用g++编译器
// 编译 g++ -o huffman main.cpp HuffmanTree.hpp FileCompress.hpp  -std=c++11
int main(int argc, char** argv)
{
    if (argc != 2)
	{
		std::cout << "usage: " << argv[0] << ": <input_file> " << std::endl;
		return 1;
	}


    FileCompress fc;
    FileCompress fc1;
    std::string fileName(argv[1]);

    fc.Compress(fileName.c_str());      // 压缩文件
    fileName += ".huffman";             // 压缩后的文件名
    fc1.Uncompress(fileName.c_str());   // 解压缩

    return 0;
}

g++ -o huffman main.cpp HuffmanTree.hpp FileCompress.hpp  -std=c++11