无损数据压缩的工作原理 | 广达杂志

每天有超过 9 亿千兆字节的信息在互联网上传播，研究人员一直在寻找新的方法将数据压缩成更小的包。 尖端技术专注于有损方法，它通过故意“丢失”传输中的信息来实现压缩。 例如，谷歌最近公布了一种有损策略，即发送计算机从图像中删除细节，而接收计算机使用人工智能来猜测缺失的部分。 甚至 Netflix 也使用有损方法，只要公司检测到用户正在低分辨率设备上观看，就会降低视频质量。

相比之下，目前很少有关于无损策略的研究，在这种策略中，传输变得更小，但没有牺牲任何物质。 原因？ 无损方法已经非常有效。 它们支持从 JPEG 图像标准到无处不在的软件实用程序 PKZip 的一切。 而这一切都是因为一个研究生，他只是想从一场艰难的期末考试中解脱出来。

七十年前，麻省理工学院教授罗伯特·法诺 (Robert Fano) 在他的信息论课上为学生提供了一个选择：参加传统的期末考试，或者改进领先的数据压缩算法。 Fano 可能会也可能不会告诉他的学生他是现有算法的作者，或者他多年来一直在寻求改进。 我们所知道的是，法诺向他的学生提出了以下挑战。

考虑一条由字母、数字和标点符号组成的消息。 对此类消息进行编码的一种直接方法是为每个字符分配一个唯一的二进制数。 例如，计算机可能将字母 A 表示为 01000001，将感叹号表示为 00100001。这导致代码易于解析——每八位数字或位对应一个唯一字符——但效率极低，因为相同的数字二进制数字用于常见和不常见的条目。 更好的方法是类似于摩尔斯电码，其中常用字母 E 仅由一个点表示，而不太常见的 Q 需要更长且更费力的破折号-破折号-点-破折号。

然而，摩尔斯电码也很低效。 当然，有些代码很短，有些代码很长。 但是由于代码长度不同，摩尔斯电码中的消息无法被理解，除非它们在每个字符传输之间包含短暂的静默期。 事实上，如果没有这些代价高昂的停顿，接收者将无法区分莫尔斯电文的破折号点破折号点破折号（“trite”）和破折号破折号-破折号-点破折号-破折号-破折号点（“真”） ).

法诺解决了这部分问题。 他意识到他可以使用不同长度的代码而不需要昂贵的空间，只要他从不使用相同的数字模式作为完整代码和另一个代码的开头。 例如，如果字母 S 在特定消息中如此常见，以至于 Fano 为其分配了非常短的代码 01，那么该消息中的其他字母将不会以 01 开头的任何内容进行编码； 诸如 010、011 或 0101 之类的代码都将被禁止。 结果，编码信息可以从左到右阅读，没有任何歧义。 例如，字母S赋值01，字母A赋值000，字母M赋值001，字母L赋值1，突然0100100011这个消息可以立即翻译成“small”这个词，尽管L用XNUMX表示数字，S 两位数，其他字母各三位。

为了实际确定代码，法诺构建了二叉树，将每个必要的字母放在视觉分支的末尾。 然后每个字母的代码由从上到下的路径定义。 如果路径向左分支，法诺加一个0； 正确的分支得到 1。树结构使 Fano 很容易避免那些不需要的重叠：一旦 Fano 在树中放置一个字母，该分支就会结束，这意味着未来的代码不能以相同的方式开始。

为了决定哪些字母应该放在哪里，法诺本可以详尽地测试每一种可能的模式以获得最大效率，但那是不切实际的。 因此，他开发了一个近似值：对于每条消息，他会按频率组织相关字母，然后将字母分配给分支，以便任何给定分支对中左侧的字母在消息中使用的次数与消息中使用的次数大致相同右边的字母。 这样，经常使用的字符就会出现在更短、密度更低的分支上。 少量的高频字母总是会平衡大量的低频字母。

结果是非常有效的压缩。 但这只是一个近似值； 必须存在更好的压缩策略。 因此，法诺要求他的学生找到它。

法诺从上到下建造了他的树，在成对的树枝之间尽可能保持对称。 他的学生戴维·霍夫曼 (David Huffman) 颠覆了这个过程，从头开始构建相同类型的树。 霍夫曼的见解是，无论发生什么情况，在一个有效的代码中，两个最不常见的字符应该有两个最长的代码。 因此霍夫曼确定了两个最不常见的字符，将它们组合在一起作为一个分支对，然后重复该过程，这次从剩余字符和他刚刚构建的字符对中寻找两个最不常见的条目。

考虑一条消息，其中 Fano 方法步履蹒跚。 在“schoolroom”中，O出现了四次，S/C/H/L/R/M各出现一次。 Fano 的平衡方法首先将 O 和另一个字母分配给左侧分支，这些字母的五次总使用量平衡了其余字母的五次出现。 生成的消息需要 27 位。

相比之下，霍夫曼从两个不常见的字母开始——比如 R 和 M——并将它们组合在一起，将这对字母视为一个字母。

然后，他更新的频率图表为他提供了四个选择：出现四次的 O，功能上使用了两次的新组合 RM 节点，以及单个字母 S、C、H 和 L。Huffman 再次选择了两个最不常见的选项，匹配（比如说）H 和 L。

图表再次更新：O 的权重仍然为 4，RM 和 HL 现在的权重均为 2，字母 S 和 C 独立。 霍夫曼从那里继续，在每个步骤中将两个最不频繁的选项分组，然后更新树和频率图。

最终，“schoolroom”变成了 11101111110000110110000101，比 Fano 自上而下的方法少了一点。

XNUMX 位听起来可能并不多，但当扩展到数十亿字节时，即使是很小的节省也会产生巨大的增长。

事实上，霍夫曼的方法已经证明非常强大，以至于今天几乎所有无损压缩策略都全部或部分地使用了霍夫曼的见解。 需要 PKZip 来压缩 Word 文档吗？ 第一步涉及另一个聪明的策略，用于识别重复并从而压缩消息大小，但第二步是获取生成的压缩消息并通过霍夫曼过程运行它。 将图像存储为 JPEG？ 您的计算机首先将图像转换为基于文本的表示形式，然后再次使用霍夫曼编码来压缩该文本。

对于一个最初由研究生跳过期末考试的愿望所激发的项目来说，这还不错。