Question

如何写压缩软件，运用哈夫曼算法实现

Answer 1

　　到文件压缩大家很容易想到的就是rar,zip等我们常见的压缩格式。然而，还有一种就是大家在学习数据结构最常见到的哈夫曼树的数据结构，以前还不知道他又什么用，其实他最大的用途就是用来做压缩，也是一些rar,zip压缩的祖先，称为哈弗曼压缩（什么你不知道谁是哈弗曼，也不知道哈弗曼压缩，不急等下介绍）。

　　随着网络与多媒体技术的兴起，人们需要存储和传输的数据越来越多，数据量越来越大，以前带宽有限的传输网络和容量有限的存储介质难以满足用户的需求。

　　特别是声音、图像和视频等媒体在人们的日常生活和工作中的地位日益突出，这个问题越发显得严重和迫切。如今，数据压缩技术早已是多媒体领域中的关键技术之一。

　　一、什么是哈弗曼压缩

　　Huffman(哈夫曼)算法在上世纪五十年代初提出来了，它是一种无损压缩方法，在压缩过程中不会丢失信息熵，而且可以证明Huffman算法在无损压缩算法中是最优的。Huffman原理简单，实现起来也不困难，在现在的主流压缩软件得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合，Huffman算法是非常好的选择。

　　二、怎么实现哈弗曼压缩

　　哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。

　　故我们得了解几个概念：

　　1、二叉树：在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。

　　

　　2、哈夫曼编码(Huffman Coding)：是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。

　　

　　三、哈夫曼编码生成步骤：

　　①扫描要压缩的文件，对字符出现的频率进行计算。

　　②把字符按出现的频率进行排序，组成一个队列。

　　③把出现频率最低（权值）的两个字符作为叶子节点，它们的权值之和为根节点组成一棵树。

　　④把上面叶子节点的两个字符从队列中移除，并把它们组成的根节点加入到队列。

　　⑤把队列重新进行排序。重复步骤③④⑤直到队列中只有一个节点为止。

　　⑥把这棵树上的根节点定义为0（可自行定义0或1）左边为0，右边为1。这样就可以得到每个叶子节点的哈夫曼编码了。

　　既如 (a)、(b)、(c)、(d)几个图，就可以将离散型的数据转化为树型的了。
　　
　　如果假设树的左边用0表示右边用1表示，则每一个数可以用一个01串表示出来。

　　则可以得到对应的编码如下：
　　1-->110
　　2-->111
　　3-->10
　　4-->0
　　每一个01串，既为每一个数字的哈弗曼编码。
　　为什么能压缩：
　　压缩的时候当我们遇到了文本中的1、2、3、4几个字符的时候，我们不用原来的存储，而是转化为用它们的01串来存储不久是能减小了空间占用了吗。（什么01串不是比原来的字符还多了吗？怎么减少？）大家应该知道的，计算机中我们存储一个int型数据的时候一般式占用了2^32-1个01位，因为计算机中所有的数据都是最后转化为二进制位去存储的。所以，想想我们的编码不就是只含有0和1嘛，因此我们就直接将编码按照计算机的存储规则用位的方法写入进去就能实现压缩了。
　　比如：
　　1这个数字，用整数写进计算机硬盘去存储，占用了2^32-1个二进制位
　　而如果用它的哈弗曼编码去存储，只有110三个二进制位。
　　效果显而易见。