CS61B 课程笔记（Lecture 38 Compression)

---

压缩技术概述

1. 压缩的定义与过程 压缩是减少文件大小的一种技术。通过压缩算法将文件内容缩减，之后通过解压缩算法可以恢复到原始文件。例如，将 mobydick.txt 文件压缩为 mobydick.zip 后，文件大小显著减小，但解压后，原始内容保持不变。这种过程体现了无损压缩，即信息无丢失。

2. 压缩模型 1：基于位的算法 压缩可以理解为对一串二进制位应用压缩算法，解压缩则是应用逆压缩算法恢复数据。以 example.txt 压缩成 example.zip 为例，压缩后文件的位数减少，解压后文件恢复为原始数据。

无前缀编码

1. 前缀编码的基础概念 在编码中，若一个编码是另一编码的前缀，可能会导致歧义。例如，摩尔斯电码中 "-- -- •" 可以代表多个不同字符组合。为避免这种歧义，可以使用无前缀编码，即任何编码都不会是另一个编码的前缀。

2. Shannon-Fano 编码 Shannon-Fano 编码通过统计符号的出现频率，将频率较高的符号分配较短的编码，频率较低的符号分配较长的编码。虽然该方法可以生成无前缀编码，但并非最优算法，实际使用较少。

3. Huffman 编码 Huffman 编码通过自底向上的方法生成最优的无前缀编码。其核心思想是：

   • 统计符号的相对频率；
   • 将最小频率的两个符号合并为一个超级节点，重复该过程，直到生成完整的编码树。

数据结构与实践

1. 编码与解码的实现
   • 编码：可以使用 HashMap/TreeMap 来将字符映射到对应的位序列，或者使用数组存储字符与位序列的关系。数组操作速度更快，但可能占用更多内存。
   • 解码：使用二进制前缀树 (Trie) 来存储编码。当接收到位流时，可以通过前缀树快速查找对应的字符。
2. 实践问题
   • 语料库压缩：根据大量输入样本创建标准的压缩编码，但此方法可能无法适用于特定的输入文件。
   • 唯一编码：为每个输入文件生成唯一的编码，并在解码时发送编码表。虽然这种方法需要额外空间，但通常比语料库压缩更有效。

压缩理论

1. 压缩比 压缩比是衡量压缩效率的指标。常用的压缩算法包括 Huffman 编码、游程编码（替换重复字符）和 LZW（利用输入模式的重复性）。这些算法的核心思想是利用数据中的冗余或规律性来减少数据大小。

2. 自解压位流 自解压位流技术将压缩数据和解压算法打包在一起，形成一个可以自行解压的可执行文件。这种方法简化了压缩与解压的过程。

3. LZW 压缩 LZW 压缩基于发现输入数据中的模式，允许一个编码词表示多个符号。其核心算法是：

   • 初始时，每个符号都有对应的编码；
   • 当某个编码词被使用时，创建一个新的编码词代表该编码词与下一个符号的组合；
   • 该算法可以从压缩位流中自行重建编码表，无需额外发送编码表。

总结

• 压缩模型：压缩算法通过对位流进行处理，生成更小的位流。
• 变长编码：常见符号使用较短的编码，稀有符号使用较长的编码，例如摩尔斯电码。
• 无前缀编码：确保没有编码是其他编码的前缀，以避免歧义。
• Shannon-Fano 编码：基于频率分割的无前缀编码，但非最优。
• Huffman 编码：一种自底向上生成最优无前缀编码的算法。