字典编码和游程编码这两种都是非常经典和常用的无损数据压缩技术。
1. 字典编码
核心思想
字典编码的基本思想是：用一种较短的“代码”来替换数据中频繁出现的、较长的“短语”。这些“短语”和其对应的“代码”被存储在一个“字典”中。
- 压缩时：扫描原始数据，识别出重复出现的字符串（短语），然后用字典中对应的更短的代码来代替它们。
- 解压时：根据同样的字典，将代码还原成原始的字符串。
这就像我们平时说话用的缩写，比如把“中华人民共和国”缩写为“中国”，双方都知道是什么意思，但传递的信息变短了。
工作原理
最常见的字典编码算法是 LZ77 和 LZ78，以及它们的大量变种（如 LZW）。
简单例子：
假设我们要压缩这段文本：“TOBEORNOTTOBEORTOBEORNOT”
我们开始扫描并构建字典：
- 遇到 “TOBEORNOT”， 这是一个新短语，给它代码
#1。 - 接下来是 “TOBEOR”， 这也是一个新短语，给它代码
#2。 - 但当我们继续扫描时，我们发现后面的 “TOBEORNOT” 和开头的短语一模一样。
- 遇到 “TOBEORNOT”， 这是一个新短语，给它代码
压缩过程：我们可以将原始文本表示为：
“TOBEORNOT#2#1”#2代表了 “TOBEOR”#1代表了 “TOBEORNOT”
这样，我们就用两个简短的代码替换了两个长长的字符串，实现了压缩。实际的算法（如LZ77）会更智能，它使用一个“滑动窗口”来动态地寻找并匹配当前数据与之前出现过的数据。
特点与应用
- 自适应：大多数现代字典编码算法是自适应的，字典在压缩过程中动态生成，无需预先传输字典。
- 通用性强：对任何存在重复模式的数据都有效，尤其适合文本文件、源代码等。
- 广泛应用：是众多压缩格式的核心，如 ZIP、GIF、PNG 图像格式，以及早期的 ZIP、ARJ 等压缩工具。
2. 游程编码
核心思想
游程编码的核心思想非常简单：将连续的、重复出现的数据序列用一个“数据值”加上一个“重复次数”来代替。
它非常适合压缩包含大量连续重复数据的文件。
工作原理
编码规则：[数据值] [重复次数]
经典例子：
假设有一张黑白图像的某一行数据（B代表黑色，W代表白色）：“WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW”
我们用游程编码来压缩它：
- 连续12个W ->
W12 - 接着1个B ->
B1 - 连续12个W ->
W12 - 连续3个B ->
B3 - 连续24个W ->
W24 - 连续1个B ->
B1 - 连续14个W ->
W14
- 连续12个W ->
压缩后的数据变为：
“W12B1W12B3W24B1W14”
可以看到，原始67个字符的数据被压缩成了只有20个字符左右（取决于数字的表示方式），压缩效果非常显著。
特点与应用
- 简单高效：算法实现非常简单，编解码速度极快。
- 适用场景特定：在特定类型的数据上效果极佳，例如：
- 二值图像：如传真机传输就使用了游程编码。
- 计算机生成的图像：如BMP、PCX等格式，常有大片纯色区域。
- 日志文件：其中可能包含大量连续的空格或零。
- 不适用场景：如果数据中几乎没有连续重复的序列，使用游程编码反而可能使数据变大。例如，压缩一张复杂的彩色照片，效果就很差。
总结与对比
| 特性 | 字典编码 | 游程编码 |
|---|---|---|
| 核心思想 | 用短代码替换重复出现的短语/序列 | 用（值+次数）替换连续重复的单个字符/符号 |
| 优势 | 通用性强，对多种类型数据有效 | 算法简单，对特定数据（连续重复）压缩比极高 |
| 典型应用 | ZIP压缩包，GIF/PNG图像，PDF文件 | 传真，BMP/PCX图像，简单图形文件 |
| 好比 | 使用成语或缩写（“卧薪尝胆”代替长篇故事） | 说“这个动作重复5次”而不是描述5遍 |
在现代复杂的压缩算法（如 Deflate，ZIP格式的基础）中，常常会结合使用多种技术。例如，先用游程编码进行初步处理，然后再使用字典编码（如LZ77）和熵编码（如霍夫曼编码）进行更深层次的压缩，以达到最佳的压缩效果。
