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

格式：doc
大小：688.50 KB
文档页数：13

这个是代码是昨天写完的，一开始的时候还出了点小bug，这个bug在晚上去吃饭的路上想明白的，回来更改之后运行立刻完成最后一步，大获成功。

简单说下huffman编码和文件压缩主要的技术。

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

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

1I 首先，如何创建Huffman树？在这个我在前天的那篇文章中简单的提了一下，现在好好说一下。

如果你不知道什么是Huffman树，请google之~对于获取到的文件，首先要做的就是，建立一个长度为256的int数组，全部置零，然后以字节流的形式读取文件，并对字节流中的字节出现次数进行统计，方法就是以字节数值为数组偏移地址，对应的数组元素进行+1操作。

另外这里需要提一下的就是，用于存储文件字节流的缓冲区最好是unsigned char类型，因为这样能直接使用，如果是char的，在转化为int类型的时候，一旦数值大于127，因为补码问题，你就直接乘上了通往未知数值的高铁~完成统计之后，将这个数组中出现次数不为0的元素添加对应大小的二叉树节点数组中，然后以出现次数为Key值，进行排序。

在排序完成之后，就能开始构建Huffman树了。

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

（其实就是将前两个元素添加到一个临时节点的左右根节点，然后在原数组中删除这两个元素，，接着再将这个临时节点插入到数组头部，充当新的节点。

上面的那段描述我觉得说的不是很清楚，但是那个是我在代码中发现的一个可以优化的地方，减少了一个元素的删除操作）2 此时数组依据key值的排序很有可能已经不再有序，而又因为仅有一个乱序元素，所以专门设计了一个函数，一次完成排序，效率，应该是最高的了。

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

这样，Huffman树的构造就完成了。

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

Huffman树节点，一开始就是一个Struct，但是因为涉及到了STL，所以添加了方法1struct HaffmanStruct2{3//a small structure4HaffmanStruct():val(0),ncounts(0),lNext(NULL),rNext(NULL){}5bool operator< (HaffmanStruct &);6bool operator> (HaffmanStruct &);7void Reset();8unsigned char val;9unsigned int ncounts;10char HuffmanCode[254];11//used for tree12HaffmanStruct * lNext;13HaffmanStruct * rNext;14};给他一个数组，他给你一颗Huffman树1void HuffManEncode(vector<HaffmanStruct> & vecValidNumberArray)2{3HaffmanStruct ValidStruct;//temporary struct4//Analysis5while(vecValidNumberArray.size() != 1)6{7ValidStruct.Reset();8ValidStruct.ncounts = vecValidNumberArray[0].ncounts + vecValid NumberArray[1].ncounts;9ValidStruct.lNext = new HaffmanStruct;10*ValidStruct.lNext = vecValidNumberArray[0];11ValidStruct.rNext = new HaffmanStruct;12*ValidStruct.rNext = vecValidNumberArray[1];13vecValidNumberArray.erase(vecValidNumberArray.begin());14vecValidNumberArray[0] = ValidStruct;15SingleSort(&vecValidNumberArray[0], vecValidNumberArray.size(), 0);16}17}以上就是Huffman树构造的全部过程。

II 根据Huffman树获取Huffman编码对树最有效的访问方式就是遍历，而遍历有两种方式：深度优先遍历和广度优先遍历。

不过学过Huffman编码的人都知道，Huffman的编码，必须使用深度优先遍历，你懂得~我在此默认的模式是，左树为0，右树为1.而这个遍历函数需要使用一个编码缓冲区和输出目标，以及深度探测。

于是乎，一个参数好多的递归函数新鲜出炉了，昨天才被我正式造出来。

1template <class T>2void ErgodicTree(T & Root, char* szStr, int nDeep, string pStrArray[])3{4if(Root.lNext == NULL && Root.rNext == NULL)5pStrArray[Root.val] = szStr;6szStr[nDeep] = '0';7if(Root.lNext != NULL)8ErgodicTree(*Root.lNext, szStr, nDeep + 1, pStrArray);9szStr[nDeep] = '1';10if(Root.rNext != NULL)11ErgodicTree(*Root.rNext, szStr, nDeep + 1, pStrArray);12szStr[nDeep] = 0;13}需要注意的是，编码和解码的递归函数是不一样的，在这专门提一下，因为编码是一次性遍历完成全部的节点，而解码是每次只遍历到叶子节点。

可以看到，每次向下传递参数的时候，左树就置'0'，右树就置'1'，返回的时候必须清零。

这样下一级函数会获取的结果，并且根据Deep的值对应置位，上级函数函数的乞讨递归也不会受到影响。

代码写的很简单，但是其实很细致。

一旦访问到了叶子节点，就直接输出，这里写的也很巧妙，也就是在这里，获取到了Huffman编码，输出到对应的string数组中。

这样，就完成了Huffman编码。

III Huffman解码用Huffman解码之前，你获取到的是一个很长的，内容是'0'和'1'的字符串。

在我的代码中，这个字符串的长度是1024.其实Huffman的解码实现起来也很简单，但是，存在细节性问题。

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

这些都是相当细节性的问题，另外文件中一般有n多个1024长度的以上的字节数，如何承上启下也是问题。

这一切，都在下面这段代码中解决：1char Buffer[128];2char DecodeBuffer[1056];//增加了八个缓冲字节3DWORD dwReadByte;4DWORD dwFlag = 1;5DWORD dwDeep = 0;6char tmpchar;7int EffectiveBufferSize = 0;8int nLeftNumberInBuffer = 0;9char szSmallBuffer[2] = {0};1011//创建解压文件12HANDLE hDeCompressionFile = QuickCreateFile("C:\\DCRecord.txt"); 13assert(hDeCompressionFile != INVALID_HANDLE_VALUE);1415while(1)16{17int i = 0;18dwReadByte = ReadHuffCodeFromFile(hHuffFile, Buffer, 128);19if(dwReadByte == 0)20break;21EffectiveBufferSize = ReadBitToBuffer(Buffer, (int)dwReadByte, De codeBuffer + nLeftNumberInBuffer, 1024);22EffectiveBufferSize += nLeftNumberInBuffer;23//TextFileFunction(DecodeBuffer, 1024);24for(i = 0;(i + dwDeep) < EffectiveBufferSize;i += dwDeep)25{26dwDeep = 0;27tmpchar = DecodeHuffman(&vecHuffmanArray[0], DecodeBuff er + i, EffectiveBufferSize - i, dwDeep, dwFlag);28if(dwFlag == 1)29{30szSmallBuffer[0] = tmpchar;31WriteBufferIntoFileNormally(hDeCompressionFile, szSmall Buffer, 1);32}33else34{35dwFlag = 1;36break;37}38}39nLeftNumberInBuffer = EffectiveBufferSize - i;40memcpy(DecodeBuffer, DecodeBuffer + i, nLeftNumberInBuffer); 41}这段代码中对于这种问题完成的很好，我上面说的在晚上去吃饭的路上就是想明白了实现承上启下那个问题的。

大致步骤如下：要注意到参数Deep是引用值，是会修改原值的。

Huffman编码与解码

(*ht)[i].data = ' ';
}
/*---------初始化Huffman树完毕---------*/
for(i=n+1;i<=2*n-1;i++)//在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回
(*ht)[i].data = ' ';
}
}
/*打印Huffman树*/
void outputHuffman(HuffmanTree **ht, int m)
{
if(m!=0)
{
cout<<m<<"\t"<<(*ht)[m].weight<<"\t"<<(*ht)[m].parent<<"\t"<<(*ht)[m].LChild<<"\t"<<(*ht)[m].RChild<<endl;
p=(*ht)[p].RChild;
}
}
printf("%c",(*ht)[p].data);
}
cout<<endl;
}
void main()
{
int n,m,longsize,longup,i;
int *w;
w=(int *)malloc((27)*sizeof(int));
for(i=0;i<=26;i++)
{w[i]=0;}

c语言实现霍夫曼编码概述及解释说明

c语言实现霍夫曼编码概述及解释说明1. 引言1.1 概述本篇长文主要介绍了C语言如何实现霍夫曼编码。

霍夫曼编码是一种广泛应用于信息压缩领域的算法，通过利用字符出现频率的统计信息，能够将常见字符用较短的二进制串来表示，从而实现数据的高效压缩和传输。

文章将详细说明霍夫曼编码的基本原理，以及在C语言中实施该算法所需的步骤和思路。

1.2 文章结构本文按照以下结构来组织内容：第一部分为引言部分，对文章进行概述并介绍文章结构；第二部分将介绍霍夫曼编码的基本原理，包括信息压缩与编码的关系、霍夫曼编码的定义以及构建霍夫曼树的过程；第三部分详细说明了在C语言中实现霍夫曼编码所需的算法思路和步骤，包括文本文件的读取与处理、统计字符频率并构造优先队列、构建霍夫曼树及生成编码表等；第四部分给出了示例代码演示，在这一部分中我们提供了完整的C语言实现代码示例，并解释了样例文件的压缩与解压缩过程；最后一部分是结论与讨论，我们将探讨霍夫曼编码在信息压缩中的应用价值，并对C语言实现霍夫曼编码的工作进行总结和展望。

1.3 目的本文的目的是帮助读者理解霍夫曼编码算法及其在C语言中的实现。

通过阅读本文，读者将能够掌握如何使用C语言来处理文本文件、统计字符频率并构建优先队列、构建霍夫曼树以及生成对应的编码表。

同时，本文还将探讨霍夫曼编码在信息压缩中的应用价值，并对C语言实现霍夫曼编码进行总结和展望。

2. 霍夫曼编码的基本原理2.1 信息压缩与编码霍夫曼编码是一种常用的无损数据压缩算法，通过对不同字符赋予不同的可变长度编码来达到有效压缩数据的目的。

在信息压缩中，我们希望用更少的位数来表示出现频率较高的字符，而用更多的位数来表示出现频率较低的字符，从而减小整个消息占用的存储空间。

2.2 霍夫曼编码的定义霍夫曼编码是一种前缀编码，即没有一个字符是另一个字符编码序列的前缀。

这确保了在解析编码时不会存在歧义。

根据霍夫曼编码规则，出现频率较低的字符使用比较长的二进制串来表示，而出现频率较高的字符则使用较短的二进制串进行表示。