数据压缩/编码
大多数人认为压缩主要与编码有关。好吧，曾经确实如此。在信息论出现之前，人们花费数年时间开发完美的代码以有效地存储数据。为了理解编码作为压缩机制的局限性，我们必须了解什么是编码。
计算机真正只理解一种类型的数据，即0和1的字符串。你知道0是关，1是开，以及所有这些废话。这些实际上与内存单元的状态有关，其中0是单元的低电压输出，而1是略高的电压。随着电路尺寸的减小以及跨并行电路间隙所需的电压减小，实际涉及的电压差也在减小。
硬件配置用于定义代码的大小，方法是限制可以一次移动的双状态内存元素（称为比特）的数量。例如，在微型计算机开发过程中发现的4位、8位、16位、32位、64位，以及现在的128位架构。
现在，计算机中的所有内容基本上都存储为比特序列。计算机的存储容量受浪费的比特数量的限制。理想情况下，我们不想浪费比特，因此我们倾向于使用能够最大程度地减少任何特定计算机架构上浪费的比特数量的代码。最终的代码是涵盖数据类型中所有可能变化的代码，并且浪费的比特最少。
有趣的是，这在人脑中并不是一个考虑因素，事实上，我们不得不定义一个术语来解释大脑代码中携带的冗余信息，这个术语是简并编码，一个贬义词，实际上只是意味着同一信息有多个代码。
考虑一个表示某些含义的数字字符串。它们是一串数字吗？如果是，我们希望对它们进行编码以最小化每个数字的存储。一个整数值？如果是，我们希望对它们进行编码以最小化任意大小整数的存储。一个浮点值？如果是，我们希望对它们进行编码以最小化任意大小尾数的存储，并包含有关数字提高到什么幂以及我们将存储小数点后多少位的信息。或者一个地址字符串？如果是，我们希望对它进行编码以最小化特定语言中字符所需的比特数。
对于人类来说，所有这些不同类型的存储在打印页面上看起来都一样。但是，在不同类型的存储之间进行转换需要时间，因此您可能不希望在使用它们时将其转换为最紧凑的编码。但是，稍后当您想将其存储起来以备后用时，将其压缩到尽可能小的尺寸似乎是一个好主意。这就是压缩的本质。
因此，编码密度的限制取决于您尝试编码的数据类型，以及从单独位置获得的信息量。
例如，军队有在战役期间限制无线电通信的惯例，这通常被认为是一件好事。甚至将其推到限制自己点击麦克风以触发攻击下一阶段的程度。对于完全了解情况的人来说，点击麦克风将足以发送有关行动状态的大量信息。这一事件对躲在战壕里的敌人来说毫无意义，因此他们第一次发现攻击的证据是枪声响起的时候。
理想情况下，所有存储都可以通过包含完整百科全书的单个比特文件来实现。实际上，这不太可能发生。编码仍然很重要，但它现在对压缩的贡献非常有限。新的压缩算法越来越难以获得，因此新的方法专注于源数据，真正的进步最近已减少到代码将运行的硬件。
| “ | 需要说明的是，真正的压缩算法是一项复杂的技术，几乎算得上是一种艺术形式。 | ” |
——Leo A. Notenboom，[1] | ||
在数据压缩领域，用数据的基本单位——比特来衡量数据“大小”很方便。
许多数据压缩算法生成一个压缩数据流，该数据流是比特流——与任何其他大小没有特定对齐方式。
有时根据“符号”来考虑输入数据很方便。一些算法根据输入中的符号压缩英文文本，并处理它们，将它们转换为压缩输出上的可逆表示。符号通常是比特集，但它们反过来可以表示任何类型的字符表示/编码，甚至像素或波形。
在压缩CD音质音频时，符号是2^16个可能的振幅级别——扬声器锥体的2^16个可能的物理位置。
一些文件压缩实用程序根据257个不同的符号来考虑未压缩的文件。在文件的任何位置，“下一个符号”都可以是257个符号中的任何一个：256个可能的字节之一——或者我们可能已经到达文件末尾，第257个符号表示“文件末尾”。
在比较图像压缩例程时，有时使用术语“bpp”（每像素比特数）。未压缩的彩色位图图像为24 bpp。未压缩的2色位图图像（仅包含黑色像素和白色像素）为1 bpp。一些图像压缩算法可以将某些图像压缩到远小于0.1 bpp。相同的图像压缩算法可能在将其他一些图像压缩到7.5 bpp方面做得非常好。
使用变长编码，我们可以使某些符号非常短——比这些符号的任何定长编码都短。这对于压缩数据非常有用。
然而，变长编码几乎总是会导致其他符号略长于这些符号的最佳定长编码。
一开始，使用更多比特来存储一个符号听起来很荒谬——为什么我们不简单地存储这些符号的较短的定长版本呢？
好的，是的，*其他*符号可以更短。所以……为什么我们不能在变长版本更短时使用它，而在定长版本更短时使用它呢？两全其美？也许使用“1”前缀来表示“接下来是定长表示”？
我们将在本书的熵编码部分更详细地讨论变长编码。
数字信息可以编码为一系列整数。使用现代数字电子设备，我们通常首先 (1) 将数据（等）以某种相对简单的（但冗长的）编码方式编码为一系列整数，然后 (2 & 3) 数据压缩算法获取该整数序列，并找到其他方法来用更少的比特表示整个序列。
例如，当我们将音乐存储在 MP3 文件中时，机器通常首先 (1) 使用麦克风和 ADC 将模拟声音数字化为 (相对简单但冗长的) 16 位 PCM 编码，采样率为每通道 44.1 kHz（CD 数字音频，未压缩的 WAV 音频等）。然后软件首先处理原始数据以 (2) 将其转换为需要更少整数的表示形式，然后 (3) 以某种方式表示每个整数的比特，以便整首歌曲可以用相对较少的比特存储。
（在计算机的早期，人们花费大量时间来弄清楚如何将音乐（等）编码成合理的按键数量，在将其输入计算机之前，使用人脑“手动”压缩和编码数据）。
人们发明了大量将整数表示为比特的方法。
…（在此处简要说明 32 位无符号整数）…
…（在此处简要说明 2 的补码有符号整数）…
浮点数通常存储为一对有符号整数——尾数（有效数字）和指数。
定长码是表示一系列整数的最简单方法。
...
逗号码是表示一系列任意长整数的一种方法。
每个整数都由一系列数字表示。
一个特殊的符号——称为逗号——用于每个码字之间，以标记一个整数的结束和下一个整数的开始。
SCDC 是表示一系列任意长整数的一种方法。
(s,c) 码，也称为 (s,c) 密集码 (SCDC)，其长度是 8 位字节的倍数。[1]
SCDC 只有一个参数 s，选择为 0 < s < 256。每个码字由一系列 8 位字节组成，其中码字中的最后一个字节的值小于 s，而其他字节（如果有）的值大于或等于 s。
结束标记密集码 (ETDC)，也称为变长量 (VLQ)，是 s=128 的 SCDC 特例。
由于每个 SCDC 码字都与字节边界对齐，因此 SCDC 解压缩比霍夫曼解压缩更简单、更快。[1]
SCDC 和斐波那契码都支持在压缩文件中直接搜索。[2][1]
Z 字形编码是表示有符号整数的一种方法。它将“小”有符号整数（接近零）映射到“小”无符号整数（最高有效位全部为零）。[3][4] 它旨在在 32 位 Z 字形编码的有符号整数和 32 位 2 的补码有符号整数之间进行一对一的映射。Z 字形编码（如增量编码）本身不会节省任何空间，但它通常以某种方式转换数据，使其他下游压缩算法能够更好地工作。（增量编码后跟 Z 字形编码通常会产生更好的结果——使用相同的下游压缩算法——而不是单独使用其中任何一个）。[5]
encoded integer 0000 0005 : -3 0000 0003 : -2 0000 0001 : -1 0000 0000 : 0 0000 0002 : +1 0000 0004 : +2 0000 0006 : +3
- ↑ a b c Shmuel T. Klein；和 Miri Kopel Ben-Nissan。[https://pdfs.semanticscholar.org/62de/373af61cc71854f86028554a988f8a4dbe36.pdf “关于斐波那契压缩码的有用性”]。2009 年。
- ↑ Shmuel T. Klein；和 Dana Shapira。“实用定长 Lempel Ziv 编码”。
- ↑ Google 开发者。“Protocol Buffers：编码”。
- ↑ “protobuf-c.c”
- ↑ “增量 Z 字形编码二进制打包”