关于此实验
每个 ZIP 文件、PNG 图像和 MP3 音轨都比原始数据小，因为它们会去除重复内容。用你自己的消息试试两种经典的无损压缩方法。游程编码会将一串相同的符号替换为其数量，这种方法非常适合简单图像，却不适用于普通文本。霍夫曼编码为常见符号分配较短的编码，为罕见符号分配较长的编码，并通过逐步构建一棵树来生成编码，其效率与克劳德·香农于 1948 年发现的理论极限相差不到每个符号 1 比特。
学习目标
- 解释无损压缩与有损压缩的区别
- 使用游程编码对消息进行编码和解码，并说明它在什么情况下有用
- 反复合并出现频率最低的两个符号，构建霍夫曼树
- 从树中读取码字，并解释为什么没有任何编码是另一个编码的前缀
- 将压缩后的大小与熵极限进行比较，并计算压缩率
使用方法
- 1选择 Pixel 行并选择游程编码。编码前后，这一行分别需要多少位？为什么它的效果这么好？
- 2选择游程编码，然后切换到 Hamlet。为什么消息变大了？
- 3选择 Mississippi，然后按“构建树”。每一步中，哪两棵树会合并？为什么？
- 4树构建完成后，找出出现频率最高和最低的字母对应的码字，并数一数它们各有多少位。
- 5从根节点开始沿树向下走，手动解码编码消息的前几位。
- 6输入一条只使用同一个字母的消息，再输入一条每个字母都不同的消息。在这两种情况下，比较霍夫曼编码与熵极限。
模型
假设
- 原始消息每个字符使用 8 位，与 ASCII 一样。
- 每个游程对都存储为一个 8 位计数和一个 8 位字符，因此长度超过 255 的游程会被拆分。
- 霍夫曼编码的大小只计算编码后的消息。实际文件还需要存储码表或各字符的计数，这对较短的消息很重要。
- 如果两棵树的权重相同，则先创建的树先被选中，较轻的树成为 0 分支。采用其他的平局处理规则，会得到总长度相同但内容不同的编码。
在课堂上试试这个实验
- Q1使用游程编码对 BBBBBWWWBBBBBBBB 进行编码。需要多少字节？
- Q2根据计数 A 5、B 2、R 2、C 1、D 1 构建霍夫曼树，并求出编码 ABRACADABRA 所需的总位数。
- Q3为什么霍夫曼编码必须是前缀码？如果 A 编为 0、B 编为 01，会有什么问题？
- Q4一段文本中有 8 个不同的字母，且出现频率相同。它的熵是多少？霍夫曼编码能压缩它吗？
- Q5JPEG 和 MP3 的压缩率远高于霍夫曼编码。它们为此牺牲了什么？
常见问题
如今霍夫曼编码用在什么地方？
它应用于许多日常格式：ZIP 和 gzip（DEFLATE 方法）、PNG 图像、有损压缩步骤之后的 JPEG 图像，以及 MP3 音频。通常，这是在另一种方法将重复内容转换为数字之后进行的最后一个阶段。
任何文件都能压缩吗？
不能。如果存在一种能让每个文件都变小的无损压缩方法，就可以不断地再次压缩压缩后的结果。但短文件的数量少于长文件，因此这不可能实现。随机数据和已经压缩过的文件通常不会变得更小。
哈夫曼树是唯一的吗？
不一定。计数相同时，不同的选择会产生不同的树和码字，但对于相同的计数，任何哈夫曼树所需的总比特数都相同。