数据压缩简介
你有没有试过发送高画质视频给朋友，却发现上传速度慢得惊人？又或者手机提示你存储空间不足？这时候数据压缩（Data Compression）就能派上用场了！在这一章中，我们将学习电脑如何将文件“缩小”，让它们占用更少的空间，并在网络上传输得更快。别担心，这听起来可能很技术性，但核心概念其实很简单：压缩就是寻找聪明的方法，更有效率地包装信息。
什么是数据压缩？
数据压缩是指减少文件大小的过程。通过将文件变小，我们可以在硬盘中存储更多内容，并让文件在网络（如互联网）上的传输速度大幅提升。
为什么我们需要它？
在计算机科学中，压缩主要有两个关键原因：
1. 存储空间：文件越小，你的设备就能容纳更多照片、音乐和应用程序。
2. 传输速度：文件越小，下载或上传所需的时间就越短。这对于 Netflix 或 YouTube 等流媒体服务至关重要，能确保视频不会一直“缓冲（buffering）”。
快速复习：压缩 = 更小的文件 = 更多的空间 + 更快的分享速度！
赫夫曼编码 (Huffman Coding)
赫夫曼编码是一种压缩文字或数据的聪明方法，它通过分析特定字符出现的频率来运作。在标准的 ASCII 编码中，每个字符（例如 'A'、'e' 或 '!'）都占用相同数量的位元（通常是 7 或 8 个 bits）。赫夫曼编码则发现这样其实有点浪费。为什么要给像 'Z' 这样罕见的字母，分配与 'E' 这样常见字母一样多的空间呢？
核心概念
想象你在收拾行李。你会把最常用的物品（如手机）放在容易拿取的口袋里，而很少使用的东西（如雨伞）则放在行李箱的最底层。赫夫曼编码对位元（bits）的操作原理相同：
- 高频字符获得较短的二进制编码。
- 低频字符获得较长的二进制编码。
解读赫夫曼树 (Huffman Tree)
要找到某个字符的二进制编码，我们需要从赫夫曼树的顶端（根节点，root）向下移动到目标字符：
- 每往左走一步，就加上一个 0。
- 每往右走一步，就加上一个 1。
例子： 如果你为了找到字母 'A'，路径是先向左、再向右、最后向左，那么它的赫夫曼编码就是 010。
计算节省的位元空间
你可能会被要求计算与 ASCII 相比，使用赫夫曼编码能节省多少位元。以下是计算步骤：
1. 计算未压缩大小：算出字符串中的总字符数，然后乘以每个字符的位元数（通常为 7 或 8）。
2. 计算压缩后大小：算出每个字符出现的次数，乘以该字符对应的赫夫曼编码长度，然后将所有数值相加。
3. 计算差值：用未压缩的大小减去压缩后的大小。
你知道吗？赫夫曼编码被广泛应用于你日常使用的许多常见文件格式中，包括 ZIP 压缩档和 JPEG 图片！
重点总结：赫夫曼编码通过为常见数据分配较短的编码、为罕见数据分配较长的编码来节省空间。
行程长度编码 (Run Length Encoding, RLE)
行程长度编码 (RLE) 是一种简单的压缩形式，最适合处理包含大量重复数值的数据。它在简单的点阵图 (bitmap images) 中非常常见，因为这类图像往往有大面积的相同颜色。
RLE 如何运作
RLE 不会单独记录每一笔数据，而是记录数据值以及它连续重复的次数（频率）。我们称之为“频率/数据对 (frequency/data pairs)”。
类比： 如果你要教朋友怎么画墙壁，你不会说“画一个蓝色像素，再画一个蓝色像素，再画一个蓝色像素……”，你会直接说“画 10 个蓝色像素”。
以 RLE 表示数据
让我们看看一串二进制数据：
00000 111 000000 11
在 RLE 中，我们计算相同位元的“连续长度（runs）”：
- 有五个 0
- 有三个 1
- 有六个 0
- 有两个 1
其 RLE 的表示方式为：5 0 3 1 6 0 2 1
要避免的常见错误！
在编写 RLE 数值对时，一定要确保自己清楚哪个数字是次数 (count)，哪个是数据 (data)。通常，第一个数字是频率（有多少个），第二个是数值（是什么）。
重点总结：RLE 通过将重复的数据序列替换为“计数”与“单一数值”来缩减文件大小。
压缩方法总结
赫夫曼编码：最适合某些项目出现频率远高于其他项目的数据（例如英文文本中的字母 'e'）。
行程长度编码 (RLE)：最适合具有长串重复数值的数据（例如拥有纯色背景的简单图示）。
如果刚开始觉得有点复杂，别担心！ 只要记住目标永远是一样的：找出用更少的 1 和 0 来描述相同信息的方法。多练习几个树状图追踪和 RLE 转换，很快你就会成为这方面的高手！
快速复习栏
- 数据压缩：为了存储和传输速度而将文件缩小。
- 赫夫曼编码：使用树状图；常见字符 = 短编码；罕见字符 = 长编码。
- RLE：使用频率/数据对；最适合重复出现的数据。
- 数学小撇步：计算 ASCII 的位元数，使用 \( \text{字符总数} \times 7 \) (或 8)。计算赫夫曼编码的位元数，则将每个独立字符所使用的位元相加即可。