第六章 亲自尝试压缩数据

******** 文件是将数据存储在磁盘等存储媒介中的一种形式。程序文件中存储数据的单位是字节 。文件的大小之所以用x×KB、xxMB等来表示，就是因为文件是以字节（B=Byte）为单位来存储的。文件就是字节数据的集合。用1字节(=8位）表示的字节数据有256种，用二进制数来表示的话，其范围就是00000000~11111111。如果文件中存储的数据是文字，那么该文件就是文本文件。如果是图形，那么该文件就是图像文件。

RLE(Run Length Encoding，行程长度编码）算法 ：把文件内容用“数据x重复次数”的形式来表示的压缩方法。RLE算法是一种很好的压缩方法，经常被用于压缩传真的图像等①。因为图像文件本质上也是字节数据的集合体，所以可以用RLE算法来压缩。例如，This is a pen.中，is重复了两次。通过利用这个压缩技巧，压缩后的文件也能小一些。由此可见，压缩技巧的拙劣是由所花的功夫决定的。

哈夫曼算法的关键就在于“多次出现的数据用小于8位的字节数来表示，不常用的数据则可以用超过8位的字节数来表示”。 A和Q都用8位来表示时，原文件的大小就是100次×8位+3次×8位=824位，而假设A用2位、Q用10位来表示，压缩后的大小就是100次×2位+3次×10位=230位。而在哈夫曼算法中，通过借助哈夫曼树构造编码体系，即使在不使用字符区分符号的情况下，也可以构建能够明确进行区分的编码体系。也就是说，利用哈夫曼树后，就算表示各字符的数据位数不同，也能够做成可以明确区分的编码。因此，只要掌握了哈夫曼树的制作方法，并用程序将其完成，就可以借助哈夫曼算法实现文件压缩了。不过，与RLE算法相比，程序的内容要复杂很多。

图像文件还可以使用与前文介绍的RLE算法、哈夫曼算法不同的其他压缩算法。这是因为，多数情况下，并不要求压缩后的图像文件必须还原到与压缩前同等的质量。与之相比，程序的EXE文件以及每个字符、数值都有具体含义的文本文件则必须要还原到和压缩前同样的内容。而对于图像文件来说，即使有时无法还原到压缩前那样鲜明的图像状态，但只要肉眼看不出什么区别，有一些模糊也勉强可以接受。这里，我们把能还原到压缩前状态的压缩称为可逆压缩 ，无法还原到压缩前状态的压缩称为非可逆压缩 。