无损数据压缩 · aiwiki.page

无损数据压缩是一种数据压缩方式，解码后可精确还原原始数据。它利用数据中的重复、符号出现频率的差异或可预测的关系来进行压缩，而不丢弃信息。与有损压缩不同，无损压缩不允许用近似结果代替编码时的输入。无损压缩方法既包括面向字节流的通用技术，也包括专门用于图像和音频的格式。能够精确还原是编码与解码过程的性质，并不意味着每个输入经过压缩后都会变小。(web.mit.edu)

可逆性与基本限制

编码器 $E$ 和解码器 $D$ 必须对每个支持的输入 $x$ 满足

D(E(x))=x

因此，编码器必须是单射函数：两个不同的输入不能具有相同的完整编码表示。还原数据所需的任何字典、模型或其他信息，都必须能由解码器获得，无论这些信息是随数据传输、由解码器重建，还是事先约定的。(web.mit.edu)

没有任何无损压缩算法能够缩短所有可能的输入。长度为 $n$ 的二进制串有 $2^n$ 个，而长度小于 $n$ 的二进制串，包括空串在内，只有 $2^n-1$ 个。因此，通过计数可知，彼此不同的编码不可能全部比原始输入更短。有些输入的长度必然保持不变，或有所增加。对于较小的输入，头部和编码表所占的空间也可能超过压缩节省的空间；DEFLATE 等格式提供了未压缩块，以应对压缩无益的情况。(rfc-editor.org)

信息论通过信源的概率分布来描述压缩的极限。对于离散随机变量 $X$ ，其信息熵为

H(X)=-\sum_x p(x)\log_2 p(x).

对于可唯一解码的符号编码，码长的期望值不能低于 $H(X)$ ，其单位是每个符号的比特数。信源编码定理说明，对于独立同分布信源，如何通过对越来越大的数据块进行编码来逼近熵界。这些限制针对的是平均值，而不是每条消息各自的最小长度。对于存在依赖关系的信源，熵率描述了考虑上下文后，每个符号仍包含的信息量。(ocw.mit.edu)

主要技术

**游程编码**用一个符号及其重复次数来表示连续重复的符号。例如，连续出现二十次的同一字符，无须将该字符写出二十遍即可表示。这种方法适合较长的连续重复段，但对于主要由较短重复段组成的数据，记录次数和标记所需的空间可能反而使数据变大。(jshun.csail.mit.edu)

**霍夫曼编码**根据符号的概率，为其分配变长的二进制码字。这些码字构成前缀码，也就是说，任何一个完整码字都不是另一个码字的前缀。因此，解码时无须分隔符即可识别符号边界。对于给定的符号分布，霍夫曼编码的构造方法能使二进制前缀码的期望码长达到最小；不过，由于码字长度只能取整数，期望码长与熵之间仍可能存在差距。将多个符号分组编码，可以缩小按每个原始符号计算的差距。(web.mit.edu)

**算术编码**通过不断细分数值区间来表示一个序列，并根据符号概率确定各子区间的大小。它不必为每个符号单独分配整数比特长度，因此能够逼近模型所预测的信息量。其效果既取决于编码机制，也取决于概率估计的准确性。(ocw.mit.edu)

字典方法用紧凑的引用替换反复出现的字符串。LZ77使用对先前已解码数据的引用，通常以距离和长度来表示。伦佩尔–齐夫–韦尔奇算法（LZW）则建立字符串表，并输出表中的索引。解码器会重建同样动态变化的表，因此无须单独传输整个字典。这类方法利用的是重复出现的序列，而不仅仅是单个符号的频率。(rfc-editor.org)

建模与可逆预处理

压缩通常将模型或可逆变换与熵编码器结合使用。模型估计哪些符号更可能出现，也可能将前面的符号作为上下文。自适应方法在处理数据流的过程中更新自身状态；编码器与解码器必须遵循一致的规则，才能保证还原结果没有歧义。即使能准确统计单个符号的出现次数，忽略依赖关系的模型仍可能无法利用大量冗余。(web.mit.edu)

可逆预处理改变的是数据的表示方式，而不是删除信息。预测编码存储实际值与预测值之间的差，预测值由先前已知的数值推算得出。数值较小、分布较集中的残差，可能比原始值更容易编码。还原时，将每个残差加到相同的预测值上即可。PNG 滤波和 FLAC 音频编码都采用了这一基本原理。(w3.org)

格式与应用

RFC 1951 规定的 DEFLATE 将 LZ77 式匹配与霍夫曼编码相结合。其数据流由多个块组成，各块可以采用固定的霍夫曼码、随数据传输的编码表，或不经压缩直接存储。它支持顺序处理，且所需的中间存储空间有明确上限，但该格式本身并不支持随机访问原始数据中的任意位置。(rfc-editor.org)

便携式网络图形（PNG）在压缩前对扫描行进行可逆滤波。解码时，先解压经过滤波的字节，再执行滤波的逆操作，以还原图像样本值。无损性针对的是所编码的这些样本值：它无法恢复编码前已经丢弃的信息，也不意味着不同的 PNG 编码器会生成字节完全相同的文件。PNG 还提供数据块级别的冗余校验，用于检测传输过程中发生的数据损坏。(w3.org)

自由无损音频编解码器（FLAC）利用相邻样本之间的关系、预测和残差编码来压缩脉冲编码调制音频，并精确还原所编码的样本值。其规范要求在编码和解码样本值时使用整数运算，以避免舍入误差，但允许在选择编码参数时进行浮点分析。FLAC 还定义了一个适合流式处理的子集，通过限制参数，使解码器的资源需求更易于预测。(rfc-editor.org)