【技术白皮书】外功心法 | 第五部分 | 亲身体验数据压缩之旅

热身问题

1. 文件储存的基本单位是什么？
2. DOC、LZH和TXT这些扩展名中，哪一个是压缩文件的扩
   展名？
3. 文件内容用“数据的值×循环次数”来表示的压缩方法是
   RLE 算法还是哈夫曼算法？
4. 在 Windows 计算机经常使用的 SHIFT JIS 字符编码中，1
   个半角英数是用几个字节的数据来表示的？
5. BMP（BITMAP）格式的图像文件，是压缩过的吗？

你是不是发现有些问题并不像表面看起来那样简单？最后，笔者的答案和解析或许能为你提供一些参考。

前提介绍

要理解文件压缩的原理，首先需要知道文件中存在着大量的“冗余信息”。简单来说，就是文件里有很多重复出现的数据或者可以用更简洁方式表示的信息。比如，一篇文章里可能多次出现“的”“是”“在”这样的常用字，或者一张图片中某一区域的像素颜色完全相同。这些重复或可简化的信息，就是压缩的对象。

压缩技术的基本原理

压缩技术的核心就是通过特定的算法，将这些冗余信息进行“精简”或“替代”，从而减少文件所占用的存储空间。

行程长度编码Run-Length Encoding (RLE)

一种简单的压缩思路，即“行程长度编码”（RLE）。当然，实际的压缩算法要复杂得多，但基本逻辑都是通过识别和消除数据中的冗余来实现体积的减小。

文本文件为例，假设一段文字是“ABABABABAB”，这里“AB”重复了5次。如果直接存储，需要10个字符的空间。但如果我们用一种算法记录为“AB 5”，意思是“AB”这个组合重复了5次，那么只需要很少的空间就能表示同样的内容。

有损压缩和无损压缩

图像、音频、视频等多媒体文件，冗余信息的表现形式更加多样。比如BMP格式的位图图像，每个像素的颜色信息都是独立存储的，即使相邻像素颜色相同也不例外，这就存在大量空间冗余。

• 有损压缩：JPEG格式则会通过离散余弦变换等方法，将图像从空间域转换到频率域，然后对高频部分（人眼不太敏感的细节）进行量化和丢弃，从而实现高效压缩。这种压缩会损失一部分数据，因此被称为“有损压缩”；
• 无损压缩：像ZIP格式对文本文件的压缩，通常能精确还原原始数据，属于“无损压缩”。

无论是哪种方式，都是利用数据本身的特性，通过数学和逻辑的方法去除冗余，让文件“变瘦”。

文件以字节为单位保存

在探讨文件压缩机制的细节之前，让我们首先剖析数据在文件中的存储形式。文件作为数据在磁盘等存储介质中的组织形式，其基本存储单元是字节。程序文件中的信息正是以字节为单位进行存储的，这正是文件大小通常以KB、MB等计量单位表示的原因，其中B代表Byte（字节）。

文件是字节数据的集合体

文件是字节数据的集合。1字节等于8位，可表示256种数据，用二进制表示范围为00000000～11111111。

{{{width=“auto” height=“auto”}}}

存储文字的文件是文本文件，存储图形的文件是图像文件。无论何种文件，字节数据都是连续存储的，需注意这一点。

行程长度编码算法

在上一节中，我们已经对行程长度编码算法（RLE）有了基本的了解。现在，让我们更深入地分析这一算法，并探讨它是如何应用于文件压缩的。为了更好地理解这一点，我们将以一个包含17个半角字符的文件（文本文件）为例进行压缩演示，尽管这些字符本身没有实际意义，但它们非常适合用来解释RLE算法的压缩机制。这个文件的内容是：AAAAAABBCDDEEEEEF。

由于在半角字母中，每个字符均以1个字节的形式保存在文件中，因此上述文件的大小即为17个字节。那么，我们该如何压缩这个文件呢？这确实值得大家思考一番。只要最终能使文件大小小于17字节，任何压缩方法都是可以尝试的。

计算RLE压缩比

在此时，人们或许会采用一种将文件内容压缩的策略，即以“字符乘以重复次数”的形式来表示。

当观察诸如AAAAAABBCDDEEEEEF这样的数据时，不难发现其中存在大量重复的字符。在每个字符后标注其重复出现的次数，AAAAAABBCDDEEEEEF便可简洁地表示为A6B2C1D2E5F1。如此一来，原本的数据便被转换为仅有12个字符，即12字节，从而实现了对原文件的压缩，相较于原本的17字节，减少了70%。恭喜你，成功地完成了数据压缩！

RLE的算法逻辑

将文件内容以“数据 × 重复次数”的形式进行表示的压缩方法被称为RLE（Run Length Encoding，行程长度编码）算法。

{{{width=“auto” height=“auto”}}}

RLE算法是一种颇为有效的压缩手段，经常被应用于压缩传真图像等文件。由于图像文件在本质上也是字节数据的集合，因此可以利用 RLE 算法进行压缩处理。

RLE算法在传真中的应用

RLE算法在传真（FAX）等领域的应用十分广泛。以G3类传真机为例，其在发送文字和图形时，均将其视为黑白图像进行处理。由于在黑白图像的数据中，白色或黑色像素往往会出现连续的情况，因此无需逐一发送每个像素的值，而是通过记录连续相同颜色的像素数量来实现数据的压缩，从而显著提高了压缩效率。

例如，对于一幅图像，其中白色像素连续出现5次，接着是黑色像素连续出现7次，再然后是白色像素连续出现4次，最后是黑色像素连续出现6次，那么我们可以将这段图像数据压缩为表示重复次数的字符串“5746”。通过这种方式，RLE算法有效地减少了数据的存储空间和传输带宽。

RLE的算法的缺点

然而，在实际的文本文件中，相同字符频繁重复出现的情况并不多见。尽管RLE算法在处理图像、文件等时常有相同数据连续出现的情形时表现良好，但它并不适用于文本文件的压缩。不过，由于这种压缩机制极为简单，采用RLE算法的程序也相对易于编写。

应用 RLE 算法对文本文件进行压缩后，文件大小反而增加了，几乎是压缩前的两倍。这是因为在文本文件中，连续出现相同字符的情况并不多见。例如，对于存储了 “This is a pen.” 这 14 个字符的文本文件，使用 RLE 算法压缩后，变成了 “T1h1i1s1 1i1s1 1a1 1p1e1n1.1”，总共 28 个字符，是压缩前的两倍。由于文章中字符大量连续出现的情况并不多见，因此使用 RLE 算法后，大部分字符后面都会加上 1，这样压缩后的文件自然就变成了之前的的两倍。

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

文件类型分析

相较于文本文件，图像文件的压缩比率A成功达到了40%。而程序的EXE文件压缩比率更是高达60%，这是由于在EXE文件中，连续的数据部分初始值为0的情况十分常见。此外，我们还可以在RLE算法的基础上进行进一步优化，不再以单个字符为单位，而是以字符串为单位来检测重复次数。

例如，在句子This is a pen.中，is重复出现了两次。通过运用这一压缩技巧，压缩后的文件体积能进一步减小。由此可见，压缩效率的高低往往取决于所投入的努力和方法的巧妙程度。

哈夫曼编码算法

接下来，我们探讨第二种值得关注的压缩技巧——哈夫曼法。这种由D. A. Huffman在1952年提出的压缩算法，在数据压缩领域占据了举足轻重的地位。值得注意的是，哈夫曼算法被广泛应用于日本人日常使用的压缩软件LHA中。

LHA 是吉崎荣泰开发的一款免费压缩软件。

为了更深入地理解哈夫曼算法，我们首先需要摒弃一个固有观念，即“半角英文数字的一个字符占用一个字节（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位），如下图所示。为实现这一操作，压缩程序的内部逻辑将变得更为复杂，但作为补偿，其最终实现的压缩效率也将显著提高。

{{{width=“auto” height=“auto”}}}

接下来，我们暂时将当前话题搁置一旁，以便更深入地探讨哈夫曼算法。在此之前，让我们先了解一下莫尔斯编码。莫尔斯编码，由塞缪尔·芬利·布里斯·莫尔斯于1837年首次提出，它并不是依靠语言进行信息传递，而是通过巧妙地组合长点和短点，即‘嗒’和‘嘀’的声音，来实现文本信息的交流。

莫尔斯编码

莫尔斯编码的基本规则，即短点表示0，长点表示1，每个字符通常由8位组成。然而，实际上莫尔斯电码的符号长度会根据不同字符而变化。在这些编码中，我们可以将“1”视为短点（嘀），而“11”则视为长点（嗒）。这种编码方式通过不同的信号长度和间隔，有效地传递了各种字符信息。

1 ：短点、 11 ：长点、 0：短点和长点的分隔符

莫尔斯编码的分析

莫尔斯编码用短编码表示高频字符，这里的频率基于印刷活字的数量而非实际文章统计。例如，E（嘀）编码为1，C（嗒 嘀 嗒 嘀）编码为110101101。实际编码中，短点为1，长点为3，间隔为1，长度指声音长度。

对于AAAAAABBCDDEEEEEF这17个字符，用莫尔斯编码表示为A×6 + B×2 + C×1 + D×2 + E×5 + F×1 + 字符间隔×16 = 106位 ≈ 14字节。文件以字节存储，不满1字节需圆整。因此，若所有字符占1字节（8位），这17个字符应为17字节，莫尔斯电码的压缩比率为14÷17 ≈ 82%，效果不突出。

二叉树实现哈夫曼编码

莫尔斯编码通过日常文本中各个字符的出现频率来决定其编码长度。然而，这种编码方式在处理AAAAAABBCDDEEEEEF这样特殊的文本时，却显得不那么适用。在莫尔斯编码体系中，字母E的编码长度最短。但是，在AAAAAABBCDDEEEEEF这个文本中，字母A的出现频率却是最高的。因此，如果给字母A分配最短的编码数据长度，压缩效果将会更加显著。这样的调整能够更有效地提升压缩率。

二叉树哈夫曼算法的实现

具体采用何种形式的编码（即哈夫曼编码）来对数据进行分割，完全取决于各个文件自身的特性。经过哈夫曼算法压缩处理后的文件，不仅包含了至关重要的哈夫曼编码信息，还存储了经过压缩处理的数据。这种算法巧妙地利用编码体系来提升压缩效率，从而在数据存储和传输中发挥着重要作用。

{{{width=“auto” height=“auto”}}}

接下来，让我们尝试对字符串AAAAAABBCDDEEEEEF中的字符A至F，依据“高频字符使用短编码”的原则进行编码整理。按照字符出现频率从高到低的顺序整理，结果如下表所示。该表同时列出了所提出的编码方案。

出现频率和编码

字符编码的数据位数随出现频率降低而增加，从1位、2位到3位。但此编码体系存在问题，如100三位编码，无法区分是表示E、A、A，还是B、A，或C。因此，无区分符号的编码方案不可用。

哈夫曼算法通过构建哈夫曼树来创造编码体系，无需字符区分符号即可实现明确区分的编码。尽管各字符的数据位数不同，也能制成可区分的编码。掌握哈夫曼树的制作方法并通过程序实现，即可利用哈夫曼算法压缩文件。但与RLE算法相比，程序更为复杂。

构建哈夫曼树

如何构建哈夫曼树。在自然界中，树是从根部开始生长分枝和树叶的，而哈夫曼树的构建过程则恰恰相反，它从叶子节点开始，逐渐形成树枝，最后生成根部。

下图展示了对于字符串“AAAAAABBCDDEEEEEF”进行编码时，哈夫曼树的构建过程。建议大家也亲自尝试绘制一下，通过一次实践，你将能够更清晰地理解哈夫曼树的构建顺序和原理。

步骤一

以下是整理后的数据及其出现频率，按降序排列：

步骤二

从给出的数字中，挑选出出现频率最小的两个数字，并分别引出两条直线。在这两条直线的交叉点上，标注出这两个数字之和。如果存在多种选择，可以任意选取其中的一组进行标注。

{{{width=“auto” height=“auto”}}}

通过重复执行步骤二，你能够连接位于任何位置的数值。

{{{width=“auto” height=“auto”}}}

步骤三

最终，这些数值将汇聚于一点，这一关键点便是树的根部，至此，哈夫曼树便完整构建而成。遵循从树根至叶子的顺序，我们将在左侧的树枝上标记0，右侧的树枝上标记1。随后，从根部出发，顺着树枝抵达目标字符，依据所经过树枝上的标记依次记录下0或1，便生成了哈夫曼编码。

{{{width=“auto” height=“auto”}}}

压缩算法的总结说明

压缩算法的种类繁多，大约有一二十种之多。之所以存在如此众多的压缩算法，是因为压缩比率、所需的处理时间（程序的复杂程度）以及各种文件的需求皆有所不同。因此，迄今为止，学界尚未能提出一种普遍适用的万能压缩算法。这无疑为各位读者展示才华提供了一个绝佳的机会。大家不妨尝试亲手设计一个独特的压缩算法。不过，需要注意的是，文本文件不宜进行非可逆压缩。原因想必大家都已心知肚明，无需赘述。

热身问题的答案解析

• 文件储存的基本单位是什么？

  • 答案：1 字节（= 8 位 ），文件是字节数据的集合体。

• DOC、LZH和TXT这些扩展名中，哪一个是压缩文件的扩
  展名？

  • 答案：LZH， 它是用 LHA 等工具压缩过的文件的扩展名。

• 文件内容用“数据的值×循环次数”来表示的压缩方法是
  RLE算法还是哈夫曼算法？

  • 答案：RLE算法,例如，AAABB 这个数据压缩后就是 A3B2

• 在 Windows 计算机经常使用的 SHIFT JIS 字符编码中，1
  个半角英数是用几个字节的数据来表示的？

  • 答案：1 字节（= 8 位），半角英文数字是用 1 个字节来表示的，汉字等全角字符是用两个字节来表示的。

• BMP（BITMAP）格式的图像文件，是压缩过的吗？

  • 没有压缩过，因为BMP格式的图像文件是没有被压缩的，因此要比JPEG格式等压缩过的图像文件大不少。