第13章 项目设计 文件压缩与解压缩

《第13章 项目设计 文件压缩与解压缩》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第12章项目实践文件压缩与解压缩在计算机中，文件是储存信息的重要手段。在不丢失信息的前提下，文件越小，越便于存储和传输；而文件压缩可以有效地减少文件长度。12.1预备知识——数据压缩的原理通常计算机储存文本文件时，是将文件内容的ASCII码存储在计算机中，每个字符需要一个字节的存储空间。但就某个具体的文件来说，文件中使用到的字符不太可能是整个字符集，也就是说有些字符在文件中没有使用，这样就造成了编码的浪费。例如：某个文件只使用了’a’,’b’,’c’,’d’,’e’,’f’六个字符，其出现的次数如下：表12.1字符abcdef频次（单位：千次）4516131295如果使用ASCII码存储这个文

2、件需要8×100×103bit的存储的空间，假如改变它的编码长度，就会大大缩小文件的长度。例将编码改为三位，如下表：表12.2字符Abcdef编码000001010011100101就当前文件来说这种编码完全可以使用，并不会使文件的信息丢失。但使用这种编码存储这个文件只要3×100×103bit的存储的空间。所以我们说：数据压缩过程就是编码，就是将文件中的每个字符均转换成一个唯一的二进制位串。反之，数据解压过程就是解码，也就是将二进制位串转换成对应的字符。1、编码方案介绍（1）等长编码方案对于一个确定的文件，将其中出现的的字符的集合称为字符集，记为C(n)，其中n为字符集C中所包含字符的个数。

3、如表12.1所示该文件的字符集C(6)={a,b,c,d,e,f}。等长编码方案是将一个文件的给定字符集C(n)中每个字符码长定为N=lgn向上取整，记为N=[lgn]。对于C(6)字符集编码的长度为N=[lg6]=3，从表12.2可以看出，这种编码不会产生重码；即编码和字符有一一对应的关系。所以编码和解码都不会产生二义性。也就不会产生信息的丢失。（2）变长编码方案变长编码方案是将字符集中出现频次高的字符编码设置的短，而将出现频次低的字符编码设置较长。例如对于C(6)={a,b,c,d,e,f}进行编码时，根据字符出现的频次，将字符’a’的编码长度定为1，’b’字符的编码长度定为2，其余字符的

4、编码长度定为3。具体编码如表12.3。我们可以算出(45×1+16×2+13×3+12×3+9×3+5×3)×103=194×103bit。约为定长编码8×100×103bit的65%。表12.3字符abcdef频度（单位：千次）4516131295等长编码000001010011100101变长编码001001011101111 值得注意的是：变长编码可能使解码产生二义性。产生该问题的原因是某些字符的编码可能与其他字符的编码开始部分(称为前缀)相同。 例如：’a’、’b’、’c’的编码分别为0、01、010，则解码时无法确定信息串010是’c’还是’b’、’a’。这就造成信息的丢失。所以这种

5、编码不能使用。2、前缀码方案                                     对字符集进行编码时，要求字符集中任一字符的编码都不能是其它字符编码的前缀，这种编码称为前缀(编)码。例如：等长编码就是前缀码。但在实际应用中，为了减少存储的空间，总是希望获得较高的。能不能设计一种变长前缀编码，来提高文件压缩比呢？下面介绍一种高效的编码方案。3、哈夫曼最优前缀码 编码后，平均码长或文件总长最小的前缀编码称为最优前缀码。最优前缀码对文件的压缩效果也是最好的。      其中：   pi为第i个字符出现的概率，   li为字符编码码长若将表12.3所示的文件作为统计的样本，则a至f

6、六个字符的概率分别为0.45，0.16，0.13，0.12，0.09，0.05，对变长编码求得的平均码长为2.24，优于等长编码(平均码长为3)。根据最优二叉树构造哈夫曼编码利用哈夫曼树很容易求出给定字符集按其概率(或频度)分布的最优前缀码。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可以将数据文件压缩掉20％至90％，其压缩效率取决于被压缩文件的特征（字符集和字符的频次）。具体做法如下：（1）用字符集中的字符ci作为叶子，pi（为字符出现的概率）或fi（为字符出现的频次）作为叶子ci的权，构造一棵哈夫曼树，其构造过程见图12.1和12.2。并将树中左分支和右分支分别标记为0

7、和1；（2）将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码就是最优前缀码（也称哈夫曼编码）。【例12．1】对表12.1的统计构造一棵哈夫曼树。步骤：将所有元素看成是只有一个节点的树，所有树组成森林，将森林中根节点权最小的两棵树合并组成一棵新树，这棵新树根的权值为两棵树权的和。将新树放回森林中。重新合并树，直到森林合并成一棵树。图12.24、求哈夫曼编码的算法给定字符集的哈夫