资源描述：
《哈夫曼编码以及哈夫曼压缩》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、编程独白给你40分钟的时间，你可以思考十分钟，然后用三十分钟的时间来写代码，最后浪费在无谓的调试上；你也可以思考半个小时，彻底弄清问题的本质与程序的脉络，然后用十分钟的时间来编写代码，体会代码如行云流水而出的感觉。在编程过程当中，相信大家都深有体会，在调试上浪费时间，问题出现在下笔之前没有一个系统结构。 关于哈夫曼哈夫曼在通信领域有很多的用途，将需要传输的数据转换01串，相比直接传输，极大提高了传输的速率，同时还在数据压缩的重要方法。而本篇主要介绍的是哈夫曼压缩算法。 哈夫曼树创建哈夫曼树创建用了两种的方法，一种是基于顺序表，另一种是基于最小堆。关于这两种方法可以参考：·基于顺序表哈夫曼树
2、·（堆的应用）Huffman赫夫曼树的建立（推荐）建立Huffman树的基本思路：给定有权重的一系列数据（带权重），从中挑选最小权重的两个数据，组成一棵树，得到的父节点再插入到数据系列当中。 哈夫曼压缩思路假设一字符串是，“abcabcabcabcabcabcddddddddd”，统计各字符出现的次数如下表。字符出现次数a6b6c6d9按照一搬的存储方法，一个字符占用一个字节，那么共花费(6+6+6+9)*sizeof(char)=27字节，27字节确实不算什么，但是如果是海量数据的时候，就可能要考虑存储空间的问题了。来看看哈夫曼压缩算法是怎么做的，同样是上面的例子，我们试着建立哈夫曼树，
3、出现的次数就当做是权重，出现的次数越多的话，越靠近根节点，那么编码越短，如下图： 于是上面的“abcabcabcabcabcabcddddddddd”，就可以转化为“0001,1000,0110,0001,1000,0110,0001,1000,0110,1111,1111,1111,1111,11”，注意这里采用的按位存储的，也就是说0和1都是位，而非char型。那么之前的27字节就被我们转换成了7个字节（7字节不足，不足的话就补零），而这就达到了压缩的效果。所以总结一下：利用哈夫曼树编码的特点，权重越大越靠近根节点，得到的编码就越短的原理，而如果把字符出现次数作为权重的话，文本当中出现
4、次数最多的字符就被压缩成了很短的编码。 哈夫曼压缩详解·压缩过程主要步骤如下：1.统计：读入源文件，统计字符出现的次数（即统计权重），顺便根据权重进行从大到小的排序（主要的话之后的操作会简单一些）；2.建树：以字符的权重（权重为0的字符除外）为依据建立哈夫曼树；3.编码：依据2中的哈夫曼树，得到每一个字符的编码；4.写入：新建压缩文件，写入压缩数据。其中最为复杂的是步骤4，因为它涉及到了位的操作，待我细细道来。 假设一字符串是，“acbcbacddaddaddccd”，统计各字符出现的次数如下表。字符出现次数a4b2c5d7 哈夫曼树 步骤123统计，建树，编码都已经完成了，剩下写入压缩
5、文件。将字符串一步一步翻译成01串， ·a:111·ac:11110·acb:11110110·acbc:11110110 10·acbcb:1111011010110… 似乎都很顺利，但是位操作有点麻烦。首先申请足够大的内存，比如已知文本字符个数是1000个字符（字节），可以申请1000*4，即一个字节平均4字节（32位）的压缩编码空间（已经足够大了），别把这些看成是char型了，当作位来看。声明nCodeIndex作为已编码的位数，相当于counter。刚申请的足够大的内存以8位划分，那么可以发现：·nCodeIndex/8可以标明第一个未存满的字节，相当于nCodeIndex>>3；
6、·nCodeIndex%8可以标明第一个未存满的字节当中有几位已经完成了存储，相当于nCodeIndex&7。可能说的不够清楚，所以画了图: *(long*)(pDest+(nCodeIndex>>3))
7、=(p->code)<<(nCodeIndex&7);（其中p为哈夫曼节点） 如此一来，我们就可以很理直气壮的将*(long*)(pDest+(nCodeIndex>>3))赋值为*(long*)(pDest+(nCodeIndex>>3))
8、(p->code)<<(nCodeIndex&7)（0
9、X=X），而不用担心到底*(long*)(pDest+(nCodeIndex>>3))里
10、面到底有多少位已经是存储了的。给出压缩主要代码：void CompressHuffman(char *filename){ //·统计权重 int count=Statistics(filename); Huffmanhf; hf.CreateHuffmanTree(acsii,count); //·测试 //hf.Print(); //根据生成的哈夫曼树，为每个字符生成编
