用Huffman树实现文件的压缩与解压
我们先来了解一下什么是Huffman树？
我们平常所使用的Zip等压缩工具都是借助Huffman树实现的，Huffman是一种特殊的二叉树，它是一种加权路径最短的二叉树，
因此也称为最优二叉树。
（下面用一幅图来说明） 
它们的带权路径长度分别为：
图1： WPL=3*2+4*2+2*2+10*2=48
图2： WPL=3*3+2*3+4*2+10*1=33
我们很容易可以看出图2的带权路径长度较小，证明图b就是哈夫曼树(也称为最优二叉树)。
如何构建一个Huffman树？
一般我们可以按下面步骤构建：
1）将所有左，右子树都为空的作为根节点。
2）在森林中选出两棵根节点的权值最小的树作为一棵新树的左，右子树，且置新树的附加根节点的权值为其左，右子树上根节点的权值之和。注意，左子树的权值应小于右子树的权值。
3）从森林中删除这两棵树，同时把新树加入到森林中。
4）重复2，3步骤，直到森林中只有一棵树为止，最终生成的树便是哈夫曼树
（Huffman的构建图解如下）： 
Huffman有什么特点呢？
我们构建的Huffman树，保证了所有的成员数据都在叶子节点上，最底层的是最小的两个节点数据，向顶端求和，然后再依次增加一个次小的
节点数据再求和，知道数据被全部插入Huffman树中，这样一来这个树中的节点就有了一个特点，离根节点越近的节点数据越大，
离根节点越远的节点数据越小。
用Huffman树实现文件压缩流程：
1.构造一个存放该文件中字符出现的信息的结构体，该结构体的成员分别有字符、字符出现的次数，对该字符的编码。
2.创建一个字符信息的结构体数组，读要压缩的文件，统计给文件的字符信息写入该数组中。
3.根据该字符数组，按照字符出现的次数构造一个Huffman，由于Huffman树的构建每次取最小数据的特点，所以我们借助构建一个小顶堆来实现。
4.根据该Huffman对每个字符进行编码，将每个字符的编码写入字符结构体数组中。（这里我们用图示具体说明一下） 
5.对该文件进行压缩，读取文件信息，根据读取到的字符压缩为该字符对应的编码，编码够8位写入压缩文件，读完文件中的所有内容，压缩完成。
需要注意的是什么时候就完成了对整个文件的压缩呢？这个问题其实我们可以有多种方法，我们在第一次读取源文件的时候就可以增加一个
计数器来记录当前文件的字符总数，另外其实如果我们足够熟悉Huffman树，很容易就可以看出来，Huffman数的根节点有什么意义？
没有错，根节点的值是从底端到顶端一层层累加上去的，因此根节点的数据就保存着文件的总字符数。
压缩源码：
string Compress(const char* filename)
{
// 1.统计字符出现的次数
assert(filename);
FILE* fout = fopen(filename, "rb"); //以只读方式打开文件
assert(fout);
//读取文件中的字符
int ch = fgetc(fout);
while (ch != EOF)
{
_Infos[ch]._count++;
ch = fgetc(fout);
}
//fclose(fout);
// 2.生成huffman tree
CharInfo invaild;
HuffmanTree<CharInfo> Tree(_Infos, 256,invaild);
// 3.生成huffmn code
string code;
_GenerateHuffmanCode(Tree.ReturnRoot(), code);
Node* Root = Tree.ReturnRoot();
cout <<"压缩"<< Root->_Weight._count <<"字符"<<endl;
//4.压缩
string CompressFilename = filename;
CompressFilename.append(".Compress");
FILE* fin = fopen(CompressFilename.c_str(), "wb");
fseek(fout, 0, SEEK_SET); //将文件偏移量设置为0
ch = fgetc(fout);
unsigned char value = 0;
int pos = 0;
while (ch != EOF)
{
code = _Infos[ch]._code;
for (size_t i = 0; i < code.size(); i++)
{
//value &= (code[i]&1);
//value <<= 1;
if (code[i] == '1')
{
value <<= 1;
value |= 1;
}
else
{
value <<= 1;
value |= 0;
}
pos++;
if (pos == 8)
{
pos = 0;
fputc(value, fin);
value = 0;
}
}
ch = fgetc(fout);
}
if (pos != 0)
{
value <<= (8 - pos);
fputc(value, fin);
}
cout << "文件压缩:" << filename<<endl;
/*cout << "一共压缩：" <<Tree.ReturnRoot()._Weight._count << "字符" << endl;*/
fclose(fin);
fclose(fout);
//创建配置文件,配置文件存储源文件中字符和字符所出现的次数
string ConfigFilename = filename;
ConfigFilename += ".config";
FILE* finConfig = fopen(ConfigFilename.c_str(), "wb");
string Line;
char Buff[128];
for (int i = 0; i < 256; i++)
{
if (_Infos[i]._count != 0)
{
/*Line += _Infos[i]._ch;*/
fputc(_Infos[i]._ch, finConfig);
/*Line += ',';*/
Line = Line + ',';
//Line += itoa(_Infos[i]._count, Buff, 10);
_itoa((int)_Infos[i]._count, Buff, 10);
Line += Buff;
Line += '\n';
fputs(Line.c_str(), finConfig);
Line.clear();
}
}
fclose(finConfig);
return CompressFilename;
}这个时候我们就可以来实现解压缩部分了，那么如何对压缩文件进行解压缩呢？
6.首先解压缩时需要一个配置文件，该文件是源文件的字符信息，需要造次构建一个Huffman，来对应完成文件解压，为什么需要这个配置文件？
原因很简单，我们压缩的时候构建了一个Huffman树并对每个字符进行了编码，我们是按照这种规则去压缩的，因此在解压缩的时候我们同样
需要这样Huffman树来帮助我们完成解压缩，正因为这样的压缩与解压缩的对应关系，我们实现了对源文件准确无误的还原。
7.读取压缩文件，当我们读取到码’1’时指向Huffman树的指针向右移动，当我们读取到码’0’时指针向左移动，由于每个字符对应的都是叶子结点，因此
我们只需要判断当前指针的Left和Right是否为空，为空则将该段码字译为对应的字符即可。循环读取解压，直到文件结尾即实现了对整个文件的解压缩。
解压缩源码：
string UnCompress(const char* filename) //解压缩
{
assert(filename);
//打开配置文件
string name= filename;
size_t Config_index = name.rfind('.');
string ConfigFileName = name.substr(0, Config_index);
ConfigFileName += ".config";
FILE* foConfigFilename = fopen(ConfigFileName.c_str(),"rb");
cout << "解压缩文件：" << name << endl;
//重新构建_Infos 哈希表
string Line;
while (ReadLine(foConfigFilename, Line))
{
unsigned char ch = Line[0];
_Infos[ch]._ch = Line[0];
LongType count = atoi(Line.substr(2).c_str());
_Infos[ch]._count = count;
Line.clear();
}
//消除压缩文件的后缀（.Compress）
string CompressFilename = filename;
size_t index=CompressFilename.rfind('.');
string UnCompressFilename = CompressFilename.substr(0, index);
UnCompressFilename.append(".UnCompress");
// 生成huffman tree
CharInfo invaild;
HuffmanTree<CharInfo> Tree(_Infos, 256, invaild);
//打开要被解压缩的文件
FILE* fout = fopen(filename, "rb");
//创建解压缩文件,并写入
FILE* fin = fopen(UnCompressFilename.c_str(), "wb");
Node* root = Tree.ReturnRoot();
Node* cur = root;
LongType count = root->_Weight._count;
cout << "解压缩" << count << "字符" << endl;
unsigned char ReadCh = fgetc(fout);
int pos = 7;
while (ReadCh != EOF)
{
if (pos >= 0)
{
if (((ReadCh >> pos) & 1) == 1)
{
cur = cur->_Right;
}
else
{
cur = cur->_Left;
}
--pos;
if (cur->_Weight == NULL && cur->_Right == NULL&& count > 0)
{
fputc(cur->_Weight._ch, fin);
cur = root;
--count;
}
if (count <= 0)
{
break;
}
}
else
{
ReadCh = fgetc(fout);
pos = 7;
}
}
return UnCompressFilename;
}下面我们来看一下压缩和解压缩的结果如何？ 
上图中名为src_file的是我们解压的源文件。
后缀为.Compress的是生成的压缩文件，我们对比一下源文件可以看到文件大小明显从4KB缩小到了3KB因为我的测试源文件里面写了一小部分内容，文件大小不是足够的大，所以解压效果不是很明显，大家可以尝试解压一个相对较大的文件，对比一下结果。
第三个后缀为.txt的为为解压专门生成的配置文件。
最后一个后缀为.UnCompress的文件是完成的解压缩文件。打开该文件内容和源文件完全相同。
到这我们就顺利地完成了基于Huffman树的文件压缩与解压缩，在实现该功能过程中我遇到了一些问题和大家分享一下：
（1）、读写文件的打开方式，我们打开文件时一定要使用二进制形式”wb”,”rb”打开需要读写的文件。文本形式打开会对文件中的一些字符做特殊处理，这样会导致不能正确无误地解压文件。
（2）、本次Huffman树实现文件的压缩与解压程序用C++模板编程，由于模板不能分离编译，因此跨文件应用程序时需要将头文件写为.hpp后缀方可通过编译。