压缩就是预测

最近，我在阅读有关压缩的文章时，偶然发现了一些疯狂的事情：压缩器和法学硕士的核心是试图解决完全相同的问题。在这篇文章中，我将引导我们了解压缩的基础知识，以了解它与语言建模的深层关系。这可能会让你大吃一惊。将本节添加为书签 压缩的工作原理 压缩数据的方法有很多种。以缩小为例：它的工作原理是将代码精简到机器需要解析的最低限度。人类可读的变量被简化为单个字母；空格和注释被删除。单击“Minify”查看实际效果： sum-numbers.js // 对列表中的每个数字求和 function sumNumbers (numbers) { let total = 0 ; for ( const 数字个数 ) { 总数 += 数字 ;返回总计； } 原始来源，156 个字符： // 对列表中的每个数字求和 function sumNumbers(numbers) { let total = 0; for (const 数字数量) { 总数 += 数字;返回总计；通过删除注释、将变量名称缩短为单个字母以及去除空格、大括号和分号，将其缩小到 62 个字符（缩小了 60%）。缩小重新开始生成的文件要小得多，但您几乎从未听说过数据压缩领域中提到的缩小。这是为什么？缩小相当简单：它只是丢弃机器不需要的任何语法。但“真正的”压缩依赖于冗余来压缩数据。考虑字符串“AAAAAAAAABBBBCCDAAADDDDDDDDDD”，其中有 9 个 A、4 个 B、2 个 C、1 个 D、3 个 A，然后是 9 个 D：这里有很多冗余。我们可以通过按顺序记录每个字符的总运行次数来将其编码为较短的字符串：原始字符串：9 个 A、4 个 B、2 个 C、1 个 D、3 个 A、9 个 D — 28 个字符，224 位。将每次运行替换为其字符以及重复次数，得到 A9B4C2D1A3D9 — 12 个字符，96 位，小 57%。使用标准 8 位 ASCII 编码，我们的原始字符串需要 224 位，而我们的压缩字符串（“A9B4C2D1A3D9”）只需要 96 位。不错！上述技术只是一种压缩方法（称为游程编码），但我们可以做得更好。实际的压缩器（例如 gzip、Brotli 等）依赖于多种方法来压缩数据。我们来看一下。为本节添加书签 压缩器的剖析 现代压缩工具大致分为三个“器官”：变换、模型和熵编码器。我在谈论这些术语时就好像它们是清晰明确的事物一样，但界限可能会有点模糊，而且它们很少单独使用。转换 Model Entropy Coder 100101110 转换是使我们的数据更容易压缩的预处理步骤。我们之前看到的方法（行程编码）是变换的一个示例，但值得注意的是，变换并不总是会缩小数据。有时它们可​​以用来创建更多的冗余，冗余越多，我们以后可以压缩的就越多。我们不会在本文中重点讨论转换，但它们仍然是任何压缩工具的重要组成部分。模型根据每个符号的频率来描述数据的形状（无论我们使用什么单位来查找冗余：字母、数字、标记，甚至二进制代码）。现在，您可以将模型视为将每个符号映射到其概率的表格，但正如我们稍后将看到的，它们可以变得更加复杂。这是一个基于我们之前的字符串的示例： 原始字符串：9 个 A、4 个 B、2 个 C、1 个 D、3 个 A、9 个 D — 28 个字符。按符号计算：12 个 A、10 个 D、4 个 B、2 个 C。 A A A A A A A A B B B B B C C D A A A D D D D D D D D 熵编码器几乎总是任何压缩算法的最后一步，并且产生最终的压缩工件：原始比特流，它只是一个裸露的比特序列，没有任何文件格式将其包裹的结构。我想重点关注最后两个步骤，因为这很重要。我们的数据模型为熵编码器提供一组概率，以尽可能有效地对数据进行编码。输入概率，压缩比特流出来： Model Symbol Probability A 0.429 D 0.357 B 0.143 C 0.071 Entropy Coder 100101110 现在，说实话：这一切仍然有点手动。熵编码器对于所有这些概率能做什么？这如何帮助它进行挤压？将本节添加为书签 用概率压缩数据 每个熵编码器都是独特的雪花，他们使用概率压缩数据的方式差异很大。为了简单起见，我们现在只关注一个：算术编码。我选择它是因为它最好地说明了更好的概率如何带来更好的压缩。它也非常整洁。将此部分添加为书签 算术编码 如果我告诉您可以用单个数字表示整个数据集怎么办？这听起来很疯狂吗？我也是这么想的，不过算术确实是这样