用C++实现Huffman文件编码和解码

这个是代码是昨天写完的，一开始的时候还出了点小bug，这个bug在晚上去吃饭的路上想明白的，回来更改之后运行立刻完成最后一步，大获成功。 简单说下huffman编码和文件压缩主要的技术。

Huffman编码，解码：

I 创建Huffman树

II 根据Huffman树实现编码，并将编码结果和要编码的数据建立映射关系。

III Huffman解码，也就是根据获取的Huffman码来逆向获取解码信息，而且你从解压文件中一次性获取的数据是一个很长的字符串，没有预处理好的成段字符串式Huffman码。1

I 首先，如何创建Huffman树？

在这个我在前天的那篇文章中简单的提了一下，现在好好说一下。如果你不知道什么是Huffman树，请google之~

对于获取到的文件，首先要做的就是，建立一个长度为256的int数组，全部置零，然后以字节流的形式读取文件，并对字节流中的字节出现次数进行统计，方法就是以字节数值为数组偏移地址，对应的数组元素进行+1操作。另外这里需要提一下的就是，用于存储文件字节流的缓冲区最好是unsigned char类型，因为这样能直接使用，如果是char的，在转化为int类型的时候，一旦数值大于127，因为补码问题，你就直接乘上了通往未知数值的高铁~

完成统计之后，将这个数组中出现次数不为0的元素添加对应大小的二叉树节点数组中，然后以出现次数为Key值，进行排序。

在排序完成之后，就能开始构建Huffman树了。操作如下：

1 如果数组中元素个数不为1，将前两个元素构造为一个临时节点的子树，此时临时节点的Key值为两个元素Key值之和，然后删除数组中的第一个元素（从数组中删除），再将临时节点赋值给当前数组的第一个元素。

（其实就是将前两个元素添加到一个临时节点的左右根节点，然后在原数组中删除这两个元素，http://mz.qqtop1.com，接着再将这个临时节点插入到数组头部，充当新的节点。上面的那段描述我觉得说的不是很清楚，但是那个是我在代码中发现的一个可以优化的地方，减少了一个元素的删除操作）

2 此时数组依据key值的排序很有可能已经不再有序，而又因为仅有一个乱序元素，所以专门设计了一个函数，一次完成排序，效率，应该是最高的了。重复1

这样当数组中只有1个元素的时候，就是Huffman树的根节点了。

这样，Huffman树的构造就完成了。我上面说的可能不是很清楚，你看了之后可能会有疑问，所以我在这贴下部分代码，你可以看一下，就是这么简单，而且很巧妙。

Huffman树节点，一开始就是一个Struct，但是因为涉及到了STL，所以添加了方法

1 struct HaffmanStruct 2 {

3 //a small structure

4 HaffmanStruct():val(0),ncounts(0),lNext(NULL),rNext(NULL){} 5 bool operator < (HaffmanStruct &); 6 bool operator > (HaffmanStruct &); 7 void Reset();

8 unsigned char val; 9 unsigned int ncounts; 10 char HuffmanCode[254]; 11 //used for tree

12 HaffmanStruct * lNext; 13 HaffmanStruct * rNext; 14 };

给他一个数组，他给你一颗Huffman树

1 void HuffManEncode(vector & vecValidNumberArray) 2 {

3 HaffmanStruct ValidStruct;//temporary struct 4 //Analysis

5 while(vecValidNumberArray.size() != 1) 6 {

7 ValidStruct.Reset();

8 ValidStruct.ncounts = vecValidNumberArray[0].ncounts + vecValidNumberArray[1].ncounts;

9 ValidStruct.lNext = new HaffmanStruct;

10 *ValidStruct.lNext = vecValidNumberArray[0]; 11 ValidStruct.rNext = new HaffmanStruct;

12 *ValidStruct.rNext = vecValidNumberArray[1];

13 vecValidNumberArray.erase(vecValidNumberArray.begin()); 14 vecValidNumberArray[0] = ValidStruct;

15 SingleSort(&vecValidNumberArray[0], vecValidNumberArray.size(), 0);

16 } 17 }

以上就是Huffman树构造的全部过程。

http://www.78name.com

II 根据Huffman树获取Huffman编码

对树最有效的访问方式就是遍历，而遍历有两种方式：深度优先遍历和广度优先遍历。不过学过Huffman编码的人都知道，Huffman的编码，必须使用深度优先遍历，你懂得~

我在此默认的模式是，左树为0，右树为1.而这个遍历函数需要使用一个编码缓冲区和输出目标，以及深度探测。于是乎，一个参数好多的递归函数新鲜出炉了，昨天才被我正式造出来。

1 template

2 void ErgodicTree(T & Root, char * szStr, int nDeep, string pStrArray[]) 3 {

4 if(Root.lNext == NULL && Root.rNext == NULL) 5 pStrArray[Root.val] = szStr; 6 szStr[nDeep] = '0';

7 if(Root.lNext != NULL)

8 ErgodicTree(*Root.lNext, szStr, nDeep + 1, pStrArray); 9 szStr[nDeep] = '1';

10 if(Root.rNext != NULL)

11 ErgodicTree(*Root.rNext, szStr, nDeep + 1, pStrArray); 12 szStr[nDeep] = 0; 13 }

需要注意的是，编码和解码的递归函数是不一样的，在这专门提一下，因为编码是一次性遍历完成全部的节点，而解码是每次只遍历到叶子节点。

可以看到，每次向下传递参数的时候，左树就置'0'，右树就置'1'，返回的时候必须清零。这样下一级函数会获取的结果，并且根据Deep的值对应置位，上级函数函数的乞讨递归也不会受到影响。代码写的很简单，但是其实很细致。 一旦访问到了叶子节点，就直接输出，这里写的也很巧妙，也就是在这里，获取到了Huffman编码，输出到对应的string数组中。 这样，就完成了Huffman编码。 III Huffman解码

用Huffman解码之前，你获取到的是一个很长的，内容是'0'和'1'的字符串。在我的代码中，这个字符串的长度是1024.

其实Huffman的解码实现起来也很简单，但是，存在细节性问题。

比如：从递归函数中获取返回值、下次解码的偏移地址、字符串访问已经到头了，但是解码失败（你想想这个问题出现的圆心），此时字符串中还剩下几个未解码的字符。