如何压缩数据与图像？

文件以字节为单位保存

文件是将数据存储在磁盘等存储媒介中的一种形式。程序文件中存储数据的单位是字节。文件的大小之所以用××KB、××MB等来表示，就是因为文件是以字节（B = Byte）为单位来存储的。

文件就是字节数据的集合。用1 字节（= 8 位）表示的字节数据有256 种，用二进制数来表示的话，其范围就是00000000～11111111。如果文件中存储的数据是文字，那么该文件就是文本文件。如果是图形，那么该文件就是图像文件。在任何情况下，文件中的字节数据都是连续存储的。

LZH 是用LHA 等工具压缩过的文件的扩展名。该压缩格式有时也称为LZH 格式。
ZIP 是用PKZIP 等工具压缩过的文件的扩展名。该压缩格式有时也称为ZIP 格式。
从物理上对磁盘进行读写时是以扇区（512 字节）为单位的。但另一方面，程序则可以在逻辑上以字节为单位对文件的内容进行读写。

半角和全角的区别

一、性质不同
1、全角：一个字符占用两个标准字符位置的状态。
2、半角：一个字符占用一个标准字符的位置。
二、使用不同
1、全角：字母和数字等与汉字占等宽位置的字。
2、半角：ASCII方式的字符，在没有汉字输入法起作用的时候输入的字母数字和字符都是半角的。
三、代表符号不同
1、全角：中GB2312-80（《信息交换用汉字编码字符集·基本集》）中的各种符号，如A、B、C、1、2、3等，应将这些符号理解为汉字。
2、半角：英文件ASCII码中的各种符号，如A、B、C、1、2、3、等。

RLE 算法的机制

接下来就让我们正式看一下文件的压缩机制。首先让我们来尝试一下对存储着AAAAAABBCDDEEEEEF 这17 个半角字符的文件（文本文件）进行压缩。虽然这些文字没有什么实际意义，但是很适合用来解说RLE 算法的压缩机制。

压缩后同压缩前文件大小的比率，称为压缩比率或压缩比。

由于半角字母中，1 个字符是作为1 个字节的数据被保存在文件中
的。因此上述文件的大小就是17 个字节。那么如何才能压缩该文件呢？大家也不妨考虑一下。只要能使文件小于17 字节，我们可以使用任何压缩方法。

这时，大家是不是会采取将文件的内容用“字符× 重复次数”这样的表现方式来压缩呢。确实，在观察AAAAAABBCDDEEEEEF 这个数据后，不难看出有不少字符是重复出现的。在字符后面加上重复出现次数，AAAAAABBCDDEEEEEF 就可以用A6B2C1D2E5F1 来表示。

A6B2C1D2E5F1 是12 个字符也就是12 字节，因此结果就将原
文件压缩了12 字节÷17 字节≒ 70%。恭喜你，压缩成功了！
像这样，把文件内容用“数据× 重复次数”的形式来表示的压缩方
法称为RLE（Run Length Encoding，行程长度编码）算法。

RLE算法是一种很好的压缩方法，经常被用于压缩传真的图像等。因为图像文件本质上也是字节数据的集合体，所以可以用RLE 算法来压缩。

RLE 算法经常被用于传真FAX 等。G3 类传真机是把文字和图形都作为黑白图像来发送的。由于黑白图像的数据中，白或黑通常是部分连续的，因此就没有必要再发送这部分数据的值（白或者黑），而只需附带上重复次数即可，这样压缩效率就得到了大幅提升。

RLE算法的缺点

然而，在实际的文本文件中，同样字符多次重复出现的情况并不
多见。虽然针对相同数据经常连续出现的图像、文件等，RLE 算法可以发挥不错的效果，但它并不适合文本文件的压缩。不过，因为该压缩机制非常简单，因此使用RLE 算法的程序也相对更容易编写。

通过表6-1 可以看出，使用RLE 算法对文本文件进行压缩后，文件却增大了，而且几乎是压缩前的2 倍。这是因为文本文件中同样字符连续出现的部分并不多。以存储着“This is a pen.”这14 个字符的文本文件为例，使用RLE 算法对其进行压缩后，就变成了“T1h1i1s1 1i1s11a1 1p1e1n1.1”这样的28 个字符，是压缩前的2 倍。

由于文章中字符大量连续出现的情况并不多见，因此，使用RLE 算法后，大部分字符后面都会加上1，这样一来，压缩后的文件自然变成了之前的2 倍。与文本文件不同，图像文件的压缩比率A 达到了40%。程序的EXE文件的压缩比率也达到了60%，这是因为EXE 文件中连续的数据部分，其初始值为0 的情况很多。

此外，我们也可以在RLE 算法的基础上再下点功夫，不以1 个字符为单位，而以字符串为单位来查找重复次数。例如，This is a pen.中，is 重复了两次。通过利用这个压缩技巧，压缩后的文件也能小一些。由此可见，压缩技巧的拙劣是由所花的功夫决定的。

通过莫尔斯编码来看哈夫曼算法的基础

压缩技巧实际上有很多种。接下来，我们就来看一下本章要介绍
的第二个压缩技巧， 即哈夫曼算法。

哈夫曼算法是哈夫曼（D. A. Huffman）于1952 年提出来的压缩算法。

为了更好地理解哈夫曼算法，首先大家要抛弃掉“半角英文数字的1 个字符是1 个字节（8 位）的数据”这一概念。

文本文件是由不同类型的字符组合而成的，而且不同的字符出现的次数也是不同的。例如，在某一个文本文件中，A 出现了100 次左右，Q 仅用到了3 次，类似这样的情况是很常见的。而哈夫曼算法的关键就在于“多次出现的数据用小于8 位的字节数来表示，不常用的数据则可以用超过8 位的字节数来表示”。

A 和Q 都用8 位来表示时，原文件的大小就是100 次× 8 位 ＋ 3 次× 8 位 = 824 位，而假设A 用2 位、Q 用10 位来表示，压缩后的大小就是100 次×2 位＋3 次×10 位 = 230 位。不过有一点需要注意，不管是不满8 位的数据，还是超过8 位的数据，最终都要以8 位为单位保存到文件中。这是因为磁盘是以字节（8 位）为单位来保存数据的（图6-3）。为了实现这一处理，压缩程序的内容会复杂很多，不过作为回报，最终得到的压缩率也是相当高的。

下面让我们把当前的话题暂时放下，为了更好地理解哈夫曼算法，先来看一下莫尔斯编码。莫尔斯编码是1837 年莫尔斯（Samuel F. B.Morse）提出的。莫尔斯编码不是通过语言，而是通过“嗒 嘀 嗒 嘀”这些长点和短点的组合来传递文本信息的。想必大家在电影中也都看到过发送莫尔斯电码的设备。

接下来我们就来仔细讲解一下莫尔斯编码。对数字领域比较熟悉的读者可能会认为“莫尔斯编码的短点是0，长点是1，其中 1 个字符用8 位来表示”，但实际上，根据字符种类的不同，莫尔斯电码符号的长度也是不同的。表6-2 是莫尔斯编码的示例。大家把1 看作是短点
（嘀），把11 看作是长点（嗒）即可。

莫尔斯编码把一般文本中出现频率高的字符用短编码来表示。这图里所说的出现频率，不是通过对出版物等文章进行统计调查得来的，而是根据印刷行业的印刷活字数目而确定的。如表6-2 所示，假设表示短点的位是1，表示长点的位是11 的话，那么E（嘀）这一字符的数据就可以用1 位的１来表示，C（嗒 嘀 嗒 嘀）这一字符的数据就可以用9 位的110101101 来表示。在实际的莫尔斯编码中，如果短点的长度是1，长点的长度就是3，短点和长点的间隔就是1。这里的长度指的是声音的长度。

接下来，就让我们尝试一下用莫尔斯编码来表示前面提到的AAAAAABBCDDEEEEEF 这个17 个字符的文本。在莫尔斯编码中，各个字符之间需要加入表示间隔的符号。这里我们用00 来进行区分。因此，AAAAAABBCDDEEEEEF 这个文本，就变成了A× 6 次＋ B× 2 次＋C× 1 次＋D× 2 次＋ E × 5 次＋F × 1 次 ＋字符间隔× 16 =4 位× 6 次＋ 8 位× 2 次＋9 位× 1 次＋6 位× 2 次＋1 位× 5 次＋8 位× 1 次＋ 2 位× 16 次 = 106 位 ≒ 14 字节。

因为文件只能以字节为单位来存储数据，因此不满1 字节的部分就要圆整成1 个字节。如果所有字符占用的空间都是1 个字节（8 位），这样文本中列出来的17 个字符 = 17 字节，那么摩尔斯电码的压缩比率就是14÷17 ≒ 82%，并不太突出。

用二叉树实现哈夫曼编码

刚才已经提到，莫尔斯编码是根据日常文本中各字符的出现频率来决定表示各字符的编码的数据长度的。不过，该编码体系，对AAAAAABBCDDEEEEEF 这样的特殊文本并不是最适合的。

在莫尔斯编码中，E 的数据长度最短，而在AAAAAABBCDDEEEEEF 这个文本中，出现最频繁的是字符A。因此，应该给A 分配数据长度最短的编码。这样做才会使压缩率更高。

下面我们来看一下哈夫曼算法。哈夫曼算法是指，为各压缩对象文件分别构造最佳的编码体系，并以该编码体系为基础来进行压缩。因此，用什么样式的编码（哈夫曼编码）对数据进行分割，就要由各个文件而定。用哈夫曼算法压缩过的文件中，存储着哈夫曼编码信息和压缩过的数据（图6-4）。

接下来，我们尝试一下把AAAAAABBCDDEEEEEF 中的A～F 这
些字符，按照“出现频率高的字符用尽量少的位数编码来表示”这一原则进行整理。按照出现频率从高到低的顺序整理后，结果就如表6-3 所示。该表中同时也列出了编码的方案。

在表6-3 的编码( 方案) 中，随着出现频率的降低，字符编码信息的数据位数也在逐渐增加，从开始的1 位、2 位，依次增加到3 位。

不过，这个编码体系是存在问题的。该问题就是，例如100 这个3 位的编码，它的意思是用1、0、0 这3 个编码来表示E、A、A 呢？还是用10、0 这两个编码来表示B 、A 呢？亦或是用100 来表示C 呢？这些都无法进行区分。因此，如果不加入用来区分字符的符号，这个编码（方案）就无法使用。

而在哈夫曼算法中，通过借助 哈夫曼树构造编码体系，即使在不使用字符区分符号的情况下，也可以构建能够明确进行区分的编码体系。也就是说，利用哈夫曼树后，就算表示各字符的数据位数不同，也能够做成可以明确区分的编码。

因此，只要掌握了哈夫曼树的制作方法，并用程序将其完成，就可以借助哈夫曼算法实现文件压缩了。

不过，与RLE 算法相比，程序的内容要复杂很多。

接下来我们就来看一下如何制作哈夫曼树。自然界的树是从根开始生枝长叶的。而哈夫曼树则是从叶生枝，然后再生根。

图6-5 展示了对AAAAAABBCDDEEEEEF 进行编码的哈夫曼树的制作过程。

哈夫曼算法能够大幅提升压缩比率

使用哈夫曼树后，出现频率越高的数据所占用的数据位数就越少，而且数据的区分也可以很清晰地实现。但哈夫曼算法为什么达到这么好的效果呢，大家都了解吗？

通过图6-5 的步骤2 可以发现，在用枝条连接数据时，我们是从出
现频率较低的数据开始的，这就意味着出现频率越低的数据到达根部的枝条数就越多。而枝条数越多，编码的位数也就随之增多了。

而从用哈夫曼算法压缩过的文件中读取数据后，就会以位为单位对该数据进行排查，并与哈夫曼树进行比较看是否到达了目标编码，这就是为什么哈夫曼算法可以对数据进行区分的原因。

例如，10001 这个使用图6-5 所示的哈夫曼编码作成的5 位数据，到达100 时，对照哈夫曼树的数据，该数据表示的是B 这个字符。至此就找到了1 个字符。然后再顺着哈夫曼树寻找剩下的01，会发现它表示的是E 这个字符。接下来，让我们来看一下哈夫曼算法的压缩比率。用图6-5 得到的哈夫曼编码表示AAAAAABBCDDEEEEEF，结果为00000000000010010
01101011010101010101111，40 位= 5 字节（这里为不包含哈夫曼编码信息的情况）。

压缩前的数据是17 字符= 17 字节，也就是说，我们惊奇地得到了 5 字节÷ 17 字节 ≒ 29% 这样高的压缩率。表6-4 是将表6-1中的文件应用哈夫曼算法的LHA 进行压缩后的结果，大家可以参考一下。可以看出，不管是哪种类型的文件，都得到了很高的压缩比率。

可逆压缩和非可逆压缩

最后，让我们来看一下图像文件的数据形式。图像文件的使用目的通常是把图像数据输出到显示器、打印机等设备上。Windows 的标准图像数据形式为BMPA，是完全未压缩的。由于显示器及打印机输出的bit（点）是可以直接映射（mapping）的，因此便有了BMP = bitmap 这一名称。

除BMP 格式以外，还有其他各种格式的图像数据形式。比如JPEGB 格式、TIFFC 格式、GIFD 格式等。与BMP 格式不同的是，这些图像数据都会用一些技法来对数据进行压缩。

图像文件还可以使用与前文介绍的RLE 算法、哈夫曼算法不同的
其他压缩算法。这是因为，多数情况下，并不要求压缩后的图像文件必须还原到与压缩前同等的质量。与之相比，程序的EXE 文件以及每个字符、数值都有具体含义的文本文件则必须要还原到和压缩前同样的内容。

而对于图像文件来说，即使有时无法还原到压缩前那样鲜明的图像状态，但只要肉眼看不出什么区别，有一些模糊也勉强可以接受。

这里，我们把能还原到压缩前状态的压缩称为 可逆压缩，无法还原到压缩前状态的压缩称为 非可逆压缩，这一点希望大家记住（图6-6）。

图6-7 中列出了各种格式的图像文件。其中，原始的图像文件是BMP 格式。通过此图可以看出，JPEG 格式和GIF 格式的图像文件有一些模糊。

这是因为JPEG 格式 的文件是非可逆压缩，因此还原后的图像信息有一部分是模糊的。

而GIF 格式的文件虽然是可逆压缩，但因为有色数不能超过256 色的限制，所以还原后颜色信息会有一些缺失，进而导致了图像模糊。

TIFF 格式的图像文件虽然不模糊，但却比原始的BMP 格式的文件还要大，这是为什么呢？我们知道，TIFF 格式的文件中带有各种标签信息，是可以选择压缩格式的，而这里选择的是与BMP 同样的无压缩方式。但由于与原始的图像数据相比，TIFF格式的文件中附加了标签信息，所以结果就比BMP 格式的文件更大了。

压缩算法的种类大概有一二十种。之所以会存在如此多的压缩算法，是因为压缩比率、压缩需要的处理时间（程序的复杂程度）以及各种文件的需求等是不一样的。

数码相机中经常用到的JPEG 格式文件，有3 种压缩方式。
（1）把构成图像的点阵的颜色信息由RGB（红色、绿色、蓝色）形式转化成YCbCr（亮度、蓝色色度、红色色度）形式。我们知道，人眼对亮度很敏感，但对颜色的变化却有些迟钝。因此，人眼比较敏感的亮度Y 就是一个很重要的参数，而表示颜色的Cb、Cr 则没有那么重要。于是我们就可以通过减少Cb 和Cr 的信息间距来缩小图像数据的大小。

（2）将每个点的色素变化看作是波形的信号变化，进行傅里叶变换。傅里叶变换是指将波形按照频率分量进行分解。照片等图像文件的特点是低频率（柔和的颜色变化）的部分较多，高频率（强烈的的颜色变化）的部分较少。因此，这里我们就可以把高频率的部分剪切掉。这样一来，图像数据也就会缩小。虽然剪切掉了高频率部分，但人眼分辨不出什么差别。不过，如果是用Windows画笔描绘的简单图形，其中颜色变化强烈的部分就会出现模糊现象。大家不妨使用Windows 画笔做一个圆形或者四方形的图形，并将其保存成JPEG 格式。然后再打开这个JPEG 文件，你就会发现颜色变化强烈的部分变模糊了。

（3）最后，将已经瘦身的图像数据通过哈夫曼算法进行压缩。这样可以使图像数据进一步缩小。

不同格式的图像

BMP（Bitmap）是使用Windows 自带的画笔来做成的一种图像数据形式。
JPEG（Joint Photographic Experts Group）是数码相机等常用的一种图像数据形式。
TIFF（Tag Image File Format）是一种通过在文件头中包含“标签”就能够显示出数据性质的图像数据形式。
GIF（Graphics Interchange Format）是由美国CompuServe 开发的一种数据格式。这种格式要求色数不超过256 色。

参考资料

https://zhidao.baidu.com/question/655618266888873685.html
《程序是怎样跑起来的》