数据压缩/顺序/熵

熵

熵是不可预测性的度量。了解熵不仅有助于您了解数据压缩，还可以帮助您选择好的密码并避免容易被猜到的密码。

例如，1000 位数据代表 1000 次连续抛掷一枚公平硬币，其熵为 1000 位，因为无法预测接下来是“正面”还是“反面”。1000 位数据代表 1000 次连续抛掷一枚不公平的双面硬币，其熵为零 (0) 位，因为硬币总是会正面朝上。

信息的熵在某种意义上是其真正包含的信息量的度量。^[1]

通过去除存储元素中的一致性，例如冗余、类似组件、最常用词等，压缩会增加文件的熵，直到文件中包含的熵过多，无法进一步压缩。压缩在缩小文件大小时，会导致每个文件长度的熵密度更高。这使得经过适当压缩的文件在进行加密传递后，比未压缩的文件更难在仅密文攻击中被破解。参见

http://en.wikipedia.org/wiki/Unicity_distance

当然，如果攻击者可以选择您加密的明文，它对大多数明文攻击模式没有帮助。

同时，解压缩算法会向高熵文件添加越来越多的一致性和顺序，直到它有意义。压缩不是一种好的加密形式的原因之一是，文件中隐藏着信息，表明解压缩程序如何恢复它。事实上，在极端的压缩中，恢复压缩文本所需的数据量通常比尚未压缩的实际剩余数据所占的百分比更大。

“	熵总是相对于某个模型而言的。它不是您获得的特定位串的属性，而是您可能获得的位串集的属性。	”

熵总是相对于某个模型而言的。它不是您获得的特定位串的属性，而是您可能获得的位串集的属性。对于给定的位集，产生最低熵的模型是最佳预测这些位的模型，因此它以最小的方式压缩数据。大多数压缩文件格式存储 (a) 我们使用的模型，(b) 该模型的特定参数（如果有），以及 (c) 根据该模型压缩的数据。某些类型的模型有许多“参数”并且需要大量空间来存储，因此我们经常使用完全不切实际的模型，但这些模型需要非常少的空间来描述，以便减少最终压缩文件的大小（模型描述 + 压缩数据）。

最简单的模型之一是“文件的每个字节都是通过蒙着眼睛在墙上扔飞镖独立随机生成的。某些字母出现频率更高，因为它们在墙上的面积更大。”这是 0 阶马尔可夫模型，也称为每个字节都被认为是独立消息时的香农熵。使用该模型，任何特定字母 $F_{i}$ 在文件 F 中的熵 $H(F_{i})$ 为

$H(F_{i})=-log_{2}p(F_{i}),$

（这是使用熵编码来表示该字母所需的位数）

整个文件的熵 $H(F)$ 是文件中每个字母熵的总和（表示整个文件所需的位数是表示该文件中每个字母所需的位数的总和）

$H(F)=\sum _{i=1}^{N}{-\log _{2}p(F_{i})},$

在唯一的可能消息数 n 方面（文件中任何特定字母都是 n 个可能字母列表中的一个，从 $x_{1}..x_{n}$ 中，任何一个都可能出现 0、1 或 N 次）

$H(F)=\sum _{i=1}^{n}{-p(x_{i})\log _{2}p(x_{i})},$

其中

• $F_{i}$ 是一个唯一的字母，例如 'e'

* $f(x_{i})$ 是文件中的唯一字母 x_i 出现的次数

• $p(x_{i})$ 是符号 $x_{i}$（例如字符 'e'）在消息中的概率
• $f(F_{i})$ 是文件第 i 位置上的字母在文件中出现的次数（显然至少为 1）
• $N$ 是文件的长度（文件中消息的总数）
• $n$ 是可能的字符数量，通常 n=257
• $p(k)={\frac {f(k)}{N}}$ 是某个字母 k 出现的概率。

通常，字符集中的某个特定字母 x_i 在某个特定文件中不会出现 - 就像字母 'e' 从未出现在 Gadsby (1939) 中一样。可能存在任意数量的从未实际出现的字母。从未出现的字母不会影响实际出现的任何特定字母的熵，也不会影响它们的总和，即整个文件在 0 阶模型下的熵。当某个字母 x_i 存在于字符集中，但它在某个特定文件中从未实际使用时，该字母的频率为零，其概率为零，并且值 $0log_{2}(0)$ 实际上为零。

任何任意文件，当使用 1 阶马尔可夫模型（“一阶模型”）分析时，都会得到一个熵值，该值小于或等于 0 阶熵。

我们将在本书后面详细讨论 1 阶马尔可夫模型和更高阶马尔可夫模型（马尔可夫模型）。

如何进一步压缩数据

压缩在某个点变得是如何进一步压缩已经具有熵的数据，这些数据主要由解压缩最小数据量的指令组成？

有两种方法可以尝试，第一种方法是在不增加文件长度的情况下注入顺序，以便你可以获得更多的压缩，而另一种方法则更有争议，因为它建议在不改变文件长度的情况下注入熵，以便你可以获得更多的压缩。

后一种方法基于一个鲜为人知的科学原理，该原理最早在“一种新型科学”中解释，该原理表明熵和顺序至少在增量或减量型 IV 细胞自动机中是循环的。这种方法可能解释了热力学第二定律下的自组织现象，这意味着有时当足够多的熵被注入数据场时，数据会再次自组织成有序状态。如果我们能跟踪它为达到自组织水平而经历过的熵状态，我们就可以压缩新的顺序，并有希望恢复原始状态。

熵编码

统计符号压缩

前缀编码

霍夫曼编码

对于压缩数据中的每个前缀代码，霍夫曼解压缩器会在表中查找压缩符号，并输出相应的明文符号。

在以下示例中，我们假设明文符号是某个 8 位字节。（大多数霍夫曼解压缩器在其字母表中包含 257 个符号：256 个可能的字节和一个表示“块结束”的特殊第 257 个代码。一些霍夫曼解压缩器具有额外的压缩符号，这些符号解压缩为常见的字节对或整个单词，这会导致更小的压缩文件大小）。

代码到字母的转换表从哪里来？所选的特定源可能是不同霍夫曼压缩文件格式之间最大的区别。

• 固定霍夫曼代码
• 静态霍夫曼代码（有时称为“半自适应霍夫曼”）（RFC 1951 对 DEFLATE 的定义称其为“动态霍夫曼代码”）
• 自适应霍夫曼代码

（是的，用“静态”作为“动态”的同义词很令人困惑。现在改变它还来得及吗？）

当解压缩器使用固定霍夫曼代码时，它使用硬编码到解压缩器中的转换表，该表永远不会改变。

当解压缩器使用静态霍夫曼代码时，它会在压缩块的开头读取转换表。然后它使用该数据来解码块的其余部分。大多数霍夫曼的“最优性证明”都假设这种静态代码。

通常，即使在同一个文件中，一段文本的字母频率也会略有不同。大多数静态霍夫曼解压缩器会观察一个特殊的第 257 个“块结束”符号，然后丢弃旧的霍夫曼表并读取新的静态压缩表。解压缩器使用该表来解码新的块。

DEFLATE 和一些其他解压缩器会在每个块的开头放置一些“模型选择器”元数据。这命令解压缩器要么

• (a) 在模型选择器之后立即获取静态霍夫曼表元数据；
• (b) 复制存储在解压缩器内的默认固定霍夫曼表；
• (c) 复制原始数据，而不尝试解压缩它——这对“不可压缩”的数据很有用；或者
• (d) 使用完全不同的其他压缩算法。

当解压缩器使用自适应霍夫曼代码时，它会从一些默认的转换表开始。但是，它会使用通过的每个符号来更新该表。

让压缩器和解压缩器使用相同的代码字

为了实现无损压缩，当压缩器用比特串“010”表示字节“e”时，解压缩器必须以某种方式知道比特串“010”必须被解码为字节“e”。

霍夫曼解压缩器有几种方法可以“知道”相应霍夫曼压缩器使用的符号到比特串映射（有时称为“频率表”）

• 固定霍夫曼代码，硬编码到解压缩器中。避免发送频率表，但如果实际概率分布与假设概率分布有很大差异，则可能会导致压缩效果很差——甚至可能会扩展文件。估计的概率分布仅在压缩器软件更改时更改。这具有最低的延迟——前几个符号可以立即编码和传输。
• 一个动态霍夫曼代码，在文件之前发送一个频率表。这要求压缩器在生成和发送第一个压缩代码字之前存储整个文件，该文件可能任意长，同时计算符号频率——这具有最差的延迟。估计的概率分布每个文件更改一次。
• 几个动态霍夫曼代码，文件被分成几个块，每个块之前发送一个频率表。这比每个文件一个表具有更低的延迟。在概率分布从一个块到另一个块发生显著变化的情况下，存储所有代码字所需的总位数可能少得多——但发送表的位数开销可能多得多。此外，压缩器可能花费大量时间试图通过“优化”文件分割的确切位置来挤出更多位。估计的概率分布每个块更改一次。
  • 一些文件格式（如 bzip2）不是总是发送一个完整的频率表来指示下一个块的确切频率，而是有时发送一个对先前发送的频率表的简短引用，该频率表（希望）足够接近下一个块的频率，以至于该块中代码字的扩展（如果有）可以通过不必发送完整的频率表来弥补。
• 自适应霍夫曼压缩：估计的概率分布每个符号更改（略微）。经过的字母的概率分布用于估计未来的概率分布。这具有第二低的延迟——前几个符号可以或多或少立即传输——但解压缩器在每个符号上会做更多工作来更新表。

每个文件和每个块的动态霍夫曼代码可以保证某些符号永远不会出现在一个块中，因此有些人编写代码完全从树中消除这些从未出现的符号，从而减少至少一个出现在压缩文本中的代码字的位数。

许多压缩算法（包括固定霍夫曼代码和自适应霍夫曼压缩）以一种无法保证某些符号永远不会出现的方式估计概率。特别是，如果某个符号非常罕见，以至于它尚未出现在训练文本中——它迄今为止的频率为零——那么将估计的零概率分配给该符号就很诱人。这会导致零频率问题。

规范霍夫曼代码

规范霍夫曼代码是一种霍夫曼代码，它可以非常简洁地描述。这使得它非常适合静态霍夫曼压缩。一个大型文本文件可能包含数千个部分，每个部分的字母频率略有不同。如果我们假装霍夫曼表开销不重要，那么为每个部分提供一个优化的霍夫曼表将最大限度地减少存储该部分所需的位数。唉，霍夫曼表开销通常很重要。许多压缩器会花费大量时间来考虑，如果我们 (a) 为几个连续部分中的每一个使用单独的霍夫曼表或 (b) 将连续部分合并到一个块中并为整个块使用一个折衷的霍夫曼表，那么总文件是否会更短。

例如，关于 x 射线的文章中字母 x 的频率远高于之前关于黄腹啄木鸟的文章。如果我们假装霍夫曼表开销不重要，那么为每个部分提供一个优化的霍夫曼表将最大限度地减少存储该部分所需的位数。唉，霍夫曼表开销通常很重要。许多压缩器会花费大量时间来考虑，如果我们 (a) 为几个连续部分中的每一个使用单独的霍夫曼表或 (b) 将连续部分合并到一个块中并为整个块使用一个折衷的霍夫曼表，那么总文件是否会更短。

“删除一些尾随的 1，然后递增”

解压缩器需要两件事来重新生成一段明文：压缩器使用的确切霍夫曼代码和一系列压缩代码字。

给定任何一个霍夫曼代码，就可以构造许多其他等效代码，所有这些代码对于任何特定明文符号都具有完全相同的代码字长度，但分配给每个明文符号的确切位模式不同。由于任何特定明文符号都被分配了一个特定长度的代码字，这个长度对于任何等效代码都是相同的，无论你选择哪个特定代码，任何明文符号序列都将被压缩成一系列具有完全相同总长度的代码字。如果前缀代码描述的开销微不足道，那么使用这些众多等效代码中的哪一个并不重要——随机选择一个即可。所有等效代码都将该数据压缩到相同数量的位。

但是，与其随机选择一个并将其发送到解压缩器，不如通过选择一个特定的规范霍夫曼代码来节省前缀代码描述中的位数。

仅给定任何前缀代码中每个符号的代码字的长度（以位为单位），就可以构造规范霍夫曼代码，该代码使每个符号都具有与该原始前缀代码相同的长度。 使代码成为规范霍夫曼 (CH) 代码的是，代码字按其代码长度进行字典排序； 给定的一组概率不会导致唯一的 CH 代码；可以自由地重新排序具有相同代码长度的符号。

创建规范霍夫曼 (CH) 代码的步骤如下

1. 构造一个霍夫曼树，并丢弃除符号和代码字长度之外的所有信息。
2. 按代码长度递增对符号进行排序。
3. 将具有每个代码长度的符号数量以及排序后的符号本身存储起来。

关于树的一些内容

每个前缀代码都可以被认为类似于一棵树。

树上的每个叶子都标记着明文字母或其他符号。

每个代码字的长度（以位为单位）有时被称为该符号的路径长度。

动态霍夫曼：存储频率表

（这是对“让压缩器和解压缩器使用相同的代码字”的延续，用于动态霍夫曼的常见情况）。

在一个典型的压缩文件中，每个压缩数据块之前都有一个头部。对于使用动态霍夫曼压缩的块，该块的头部会告诉解压缩器该块中使用的代码字集以及代码字到明文符号的映射。

通常，压缩器和解压缩器会有一些硬编码的 S 个明文符号的字母表，它们需要处理。通常 S=258 个符号，即 256 个可能的字节和一些其他特殊符号，例如块结束符号。字母表中的每个符号在压缩数据中都由一个代码字表示，其长度为 1 到 MAX_CODEWORD_LENGTH 位。

许多简单的霍夫曼文件格式只是将这 258 个位长度的列表存储为 258 个字节的块。每个位置代表一个明文符号——即使那些从未在明文中使用过的符号——通常位置 0 代表 0 字节，位置 32 (0x20) 代表空格字符，位置 __ (0x65) 代表字母 'e'，位置 255 代表 255 字节，位置 256 代表一些特殊命令，位置 257 代表块结束指示符。

每个位置的数字代表与该明文符号对应的代码字的长度，以位为单位。(由于我们使用规范霍夫曼代码，与每个明文符号对应的代码字的长度是解压缩器重新生成该块中使用的实际代码字集所需的一切)。通常，"0 位"的特殊"长度"被保留用于指示该块中从未出现过的字母，因此不应包含在霍夫曼树中。

这个 S 个数字的列表通常被称为"频率表"。有时这个 S 个数字的列表被称为"克拉夫特向量"，因为它必须满足w:克拉夫特不等式。

头部中的这 258 个字节的块代表了大量的开销，尤其是如果压缩文件包含许多独立的块，每个块都有自己的头部。一些霍夫曼压缩器，例如面向英文单词的霍夫曼压缩器，使用大量的符号(英文词典中每个单词一个)，需要更长的克拉夫特向量。可以通过设计文件格式来减少此块的大小，从而以多种方式获得更小的压缩文件大小，包括

• 使用完全相同的代码字到明文符号动态霍夫曼映射，但以更紧凑的形式存储该映射
  • 使用某种长度限制的霍夫曼压缩。如果没有比 15 位更长的代码字，那么我们可以将每个长度存储在 4 位中，而不是完整的 8 位字节。
  • 单独压缩频率表，可能使用 RLE 或一些变长代码，例如固定霍夫曼压缩，甚至另一个动态霍夫曼"预表"。
  • 当数据文件在两种数据之间交替出现时——例如，英文文本和长数字表——使用简单的差分压缩来紧凑地表示后面的表作为对前面某个表的引用，就像 bzip2 中一样。
  • 当一个数据块的频率略微不同于前一个块时——例如，一篇关于 X 光的文章的字母频率大致相同，但比一篇关于黄腹吸汁鸟的文章的 'X' 多得多，而 'y' 则少一些——使用差分压缩来紧凑地表示新表，方法是给出与前一个表的(希望相对较小的)变化，就像 LZX 中一样。我们在后面的章节数据差异中讨论其他类型的差分压缩。
  • 或以上几种方法的组合。
• 使用除动态霍夫曼映射以外的其他代码字到明文符号映射
  • 自适应霍夫曼：根据已在明文中解码的字母，动态地估计未来的字母频率
  • 通用代码：...

实现技巧

人们花了很多时间来找出使霍夫曼压缩和霍夫曼解压缩真正快速的方法。这些只是用来使解压缩器(或压缩器，或两者)能够给出与非优化程序相同输出的相同位，同时运行得更快的一些技术。

实现霍夫曼解压缩器的软件通常包含 2 个部分

• 设置部分会提取一个紧凑的"频率表"头部，并将其扩展成某种类型的查找表，以便使下一部分真正快速
• 将代码字转换为明文符号的内部循环。

霍夫曼解压缩器的内部循环会找到与压缩文本的下一部分匹配的代码字，并发出相应的明文符号。即使压缩 7 位 ASCII 文本，代码字也可能超过 32 位长，对齐位并比较如此长的字可能有点麻烦。有三种方法可以避免如此长的比较：(a) 长度限制的霍夫曼代码。通常"自然"文件从未使用过如此长的代码字，只有专门设计的，旨在作为最坏情况文件的代码字。一些压缩器选择故意将霍夫曼代码字的长度限制为某个最大长度。这使得这些最坏情况文件在压缩后，比没有限制时略微长一些；它对压缩"自然"文件的长度没有影响。大多数旨在在硬件中解压缩的文件格式(使用 FPGA 解压缩的视频等)会限制长度，以降低硬件成本。(b) 一个用于处理短代码字的短而快的表，并具有一个"长代码字"标志，以及其他用于处理长代码字的表。由于最频繁的霍夫曼代码很短，因此解码器通常可以使用一次对完全适合缓存的短而快的表的查找来快速解码代码字；偶尔解码器会命中一个带标记的条目，并且需要花更多时间在其他表中查找长代码。(c) 而不是直接与代码字位串进行比较，首先进行一个零计数(到下一个 1 位，或到文件末尾，以先到者为准)，找到 Z 个零，丢弃这个 1 位，然后是接下来的 n 位。

前缀代码解压缩器实现可以通过它们从压缩流中读取的位数以及它们如何使用这些位来决定下一步来区分。人们已经通过多种方式实现了"快速"解压缩器，包括

• 一次一位：一个"简单"的前缀解码器通常从压缩流中逐位读取，一次一位。这可能是最慢的方式。
• 始终一次 max_codelength 位：一个大型查找表，直接由从压缩流中读取的多个位索引
• 一次一个字节(8 位)：一个大型查找表，直接由"树位置"状态和从压缩流中读取的字节索引
• X 个初始位，然后是 Y 个后续位，每个符号(其中 X 是一个常数，通常选择为 max_codelength 的一半位数，而 Y 通常根据在最初 X 位中读取的特定值而变化；X+Y 最多为 max_codelength)
  • 一个由从压缩流中读取的某些位索引的第一个查找表，它会选择一个由从压缩流中读取的更多位索引的第二个索引表
• 任意数量的零位，然后是 F 个尾随位：(这对规范霍夫曼代码有效，但可能对其他前缀代码没有用)。
  • 一个大型查找表，由从压缩流中读取的零计数和位索引
  • 一个由压缩流中的位零计数索引的第一个查找表，它会选择一个由从压缩流中读取的更多位索引的第二个索引表。

在概念上，最简单的一个是"一个大型查找表"方法

• 一个大型查找表

如果您的最大代码长度相对较短，这可能是最快的方法。

一个快速前缀代码解码器的快速内部循环会一次读取压缩数据一个字节(而不是"简单"前缀解码器的逐位读取)。"当前树位置"和压缩字节被用作一个大型表的索引，该表保存生成的"新树位置"以及最多 8 个解压缩的明文符号。

• (new_tree_position, [解压缩的符号列表]) := lookup_table( current_tree_position, compressed_byte )

任何代码字都可以用两个数字(Z 个初始零的计数，F 个尾随位的数值)表示。例如，代码字"000101"可以用两个值(3,5)表示。代码字"11"可以用两个值(0,3)表示。

规范霍夫曼代码的一个特点是，如果所有明文符号都适合 n 位固定长度代码，那么 Z 可以用 n 位表示，F 也可以用 n 位存储。(这*不适用于*所有前缀代码)。(当解压缩器在压缩文本中实际进行零计数时，连续的全零代码字会导致无限数量的连续零——我在这里试图指出的是，任何一个特定代码字中初始零的数量可以用 n 位表示)。这允许几个不同的时间/速度权衡，它们都给出完全相同的输出文件。可能最快的内部循环类似于以下操作：对于每个符号

• 将零计数到 Z
• 丢弃接下来的 1 位，使"下一个要读取的位"指针指向*接下来的*位，但提前查看接下来的 n-1 位并将它们放入 F 中。
• 将 Z 的最低有效 n 位和 F 的 n-1 位打包到 2n-1 位索引中。
• (plaintext_symbol, useful_bits) := lookup_table[index]
• 将"下一个要读取的位"指针移动 useful_bits 位——对于只有代码字中零之后的 1 位的代码字(1, 01, 001, 0001 等)可以是 0 位，对于代码字中零后的第一个 1 位后面的完整 n-1 位的代码字可以是 n-1 位。
• 发出明文符号。

重复此过程，直到我们遇到文件末尾。

这忽略了全零码字的特殊情况处理。许多哈夫曼编码器，例如 DEFLATE，设计了一个具有“伪”条目的哈夫曼表，这样压缩后的文本永远不会使用全零码字；因此解压缩器永远不必处理这种复杂情况。这还忽略了对映射到某些特殊命令而不是映射到文字明文符号的码字的特殊处理。这需要一个大小为 2^(2n-1) 的查找表。对于一个典型的哈夫曼代码，其中 n=9 位，能够处理所有 2^8 字节和一些其他特殊符号，使用这种实现类型的规范哈夫曼代码需要一个大小为 2^(17) = 131 072 个条目的查找表。如果一个明文符号被映射到一个比最大码长更小的码长，那么该表中的多个条目会映射到同一个符号。还有其他实现方式，它们使用的 RAM 少得多。其他实现甚至可能更快，因为它们允许更多的工作内存适合缓存。

通常，对于alphabet_size个明文符号，最坏情况下的最大“压缩”哈夫曼码长度为alphabet_size - 1位。

对于 257 个明文符号，最坏（不太可能）的情况是最大位长为 2 个字符，它们被“压缩”为 256 位，因此最大零计数（除了当我们有 1 个或多个连续的全零代码时）为 255。

处理文本结束通常很麻烦，因为压缩的位字符串通常存储在某个整数个字节中，即使压缩的位字符串通常*不*是 8 位的倍数。大多数哈夫曼解压缩器使用以下两种技术之一来处理文本结束

• 压缩器和解压缩器都在树中包含一个特殊的文本结束符号（在进行二进制字节定向压缩时为第 257 个符号，或者在压缩以 null 结尾的 C 字符串时为 null 字节）。由于它只出现一次，它的频率为 1，因此表示它的代码在长度上与一个或多个最长可能的长度符号绑定在一起。
  • 解压缩器在看到文本结束符号时立即返回，并忽略该符号之后的任何填充位，这些位填充了最后一个存储字节。或者，
  • 压缩器告诉解压缩器使用多少个有效输入字节来保存压缩的位字符串。解压缩器强制表示文本结束符号的代码为全零符号。解压缩器模拟在最后一个有效输入字节之后读取零位——可能在某些其他有效符号的末尾读取一些零位——最终读取全零文本结束符号。
• 一些解压缩器没有特殊的文本结束符号。
  • 压缩器告诉解压缩器输入压缩位字符串表示多少个输出符号，并且解压缩器在发出正好那么多符号后立即返回。或者，
  • 压缩器告诉解压缩器使用多少个有效输入字节来保存输入压缩位字符串。有时最后一个有效符号在最后一个字节的末尾干净地结束，并且解压缩器返回。其他时候，有一些剩余位不够长，无法构成完整的有效码字——所有具有该前缀的码字都更长。当剩余位全部为零时，丢弃这些剩余的零位并返回。（这种技术*假设*全零代码至少有 8 位长——当树中至少有 2^7+1 = 129 个符号并且使用规范哈夫曼代码时，这总是正确的。如果您少于 129 个符号，您必须使用其他技术来处理文本结束）。

改进哈夫曼

原始的哈夫曼算法对于对具有已知概率分布的无关符号流进行符号级编码是最佳的。

但是，可以使用几种算法来压缩比哈夫曼算法更小的某些类型的文件。这些算法利用哈夫曼最优性证明中的一种或多种注意事项

• 无关符号：大多数真实数据文件在符号之间存在一些互信息。可以通过“去相关”符号，然后对这些去相关符号使用哈夫曼算法，从而比纯哈夫曼做得更好。
• 符号级：一些压缩算法，例如范围编码，通过放宽二进制哈夫曼的限制，即每个输入符号必须编码为整数个位，从而比二进制哈夫曼提供更好的压缩。
• 已知概率分布：通常接收器不知道确切的概率分布。因此，典型的哈夫曼压缩算法首先发送频率表，然后发送压缩数据。一些“自适应”压缩算法，例如极性树编码，可以比哈夫曼获得更好的压缩，因为它们收敛到概率分布，或者适应不断变化的概率分布，而无需明确发送频率表。

这让人想起许多算法压缩比“最佳”固定位长编码码字长度 更小的文件的方式，方法是利用固定位长编码最优性证明中的注意事项

固定位长编码对于将具有已知有限字母大小 A 的符号流符号级编码到固定长度的码字中是最佳的。固定位长编码的最佳码字长度为 $L=\left\lceil log_{2}A\right\rceil$.

• 有限字母：固定位长编码对于无限字母是无用的；“通用代码”（如下所述）可以轻松地处理此类字母。
• 符号级：一些压缩算法，例如 LZW，具有比固定位长编码更好的压缩效果的固定长度码字，方法是使用一些码字来表示符号对或更长的符号字符串。
• 固定长度码字：可变长度代码通常提供更好的压缩效果。

前缀码

哈夫曼编码、香农-范诺编码和极性树编码都将一些相对较小的已知符号字母映射到前缀码。

“通用代码”将无限大的已知字母——通常是所有正整数的集合，或所有整数的集合——映射到前缀代码。

通用代码

存在许多“通用代码”，它们是一种前缀代码。

任何特定的前缀代码（包括任何通用代码）都可以看作是针对特定对应频率分布的某种哈夫曼代码。

典型的音频数据和典型的音频数据预测残差大约具有拉普拉斯分布。图像压缩和几何压缩的预测误差编码通常会产生近似于拉普拉斯分布的结果。 使用一般哈夫曼代码对拉普拉斯分布进行编码会得到一个前缀代码，该代码等效于使用戈伦布代码。戈伦布代码比一般哈夫曼代码更简单、更快地进行压缩和解压缩。如果音频数据“足够接近”拉普拉斯分布，则戈伦布代码可能会提供比一般哈夫曼代码更好的网络压缩效果，因为戈伦布解码器只需要 1 个参数的开销，而一般哈夫曼解码器则需要一个概率哈夫曼表的开销。

莱斯编码是戈伦布编码的一个子集，它在压缩和解压缩方面速度更快。由于莱斯代码非常接近拉普拉斯分布的哈夫曼代码，因此它们的压缩效果几乎与一般哈夫曼代码一样好。

待办事项：添加一些关于斐波那契代码（一种“通用代码”）的文字。

音频压缩

傅里叶变换

感知编码

“Gerzon/Craven 定理表明，最优去相关信号的电平由原始信号谱的平均值给出，当以 dB 对线性频率作图时。... 此 dB 平均值可能比原始信号具有明显更小的功率，因此数据速率降低。... 在实践中，任何一段音乐数据可以“白化”的程度取决于内容和预测滤波器中允许的复杂性。”

典型的音频数据和典型的音频数据预测残差（去相关后）大约具有拉普拉斯分布，因此它们通常使用戈伦布解码器或莱斯解码器而不是一般哈夫曼解码器进行解码。

一些音频解码器可以被告知在使用它们压缩效果良好的音乐段落中使用莱斯解码器，并在稍后被告知在使用莱斯解码器压缩效果不佳的音乐段落（例如纯正弦波音调或所有值等概率的白噪声）中切换到其他解码器。

在一些音频应用中，特别是双向电话通信，端到端延迟至关重要。电话服务的推荐最大时延为 150 毫秒(Wikipedia:1 E-1 s)。这排除了许多流行的压缩算法。我们将在本书的 Data_Compression/Evaluating_Compression_Effectiveness#latency 部分更详细地讨论延迟。

算术编码

算术编码

上下文自适应二进制算术编码

...

组合

参见 数据压缩/多重变换