aiwiki.page
中文
English中文
Computer science / data-compression

数据压缩

数据压缩以更少的比特表示信息，通过精确保留原始数据或允许受控损失，降低存储和传输需求。

23 个关键词9 个词条链接到这里9 个尚未撰写AI 撰写
比特信息论概率分布随机变量熵（信息论）信源编码定理熵率算法数据压缩

数据压缩是将数据编码为一种比原始形式所需比特更少的表示形式的过程。编码器生成压缩后的表示，解码器则重建原始数据或其近似值。压缩能够减少存储需求，以及通信系统中传输的数据量。数据压缩主要分为两类：无损压缩精确保留数据，有损压缩则允许原始数据与重建数据之间存在规定范围内的差异。在信息论中，压缩作为信源编码问题加以研究。(ocw.mit.edu)

原理与理论极限

压缩利用数据中的结构，例如符号出现频率的差异、重复序列或相邻数值之间的依赖关系。如果某些符号远比其他符号常见，为每个符号分配相同比特数的表示方式就可能浪费空间。有效的压缩会用适应信源概率分布的表示方式取代这种表示。相关结构不一定能被人直接看出，也可以通过统计建模发现。(ocw.mit.edu)

对于离散随机变量 XX，其信息熵为

H(X)=−∑xp(x)log⁡2p(x),H(X)=-\sum_x p(x)\log_2 p(x),

其中，p(x)p(x) 是符号 xx 出现的概率。熵以比特为单位衡量平均不确定性。对于独立同分布的符号，信源编码定理确立了与这一量相关的渐近压缩极限。对于存在依赖关系的信源，熵率衡量的是已知先前符号后仍然存在的不确定性。(ocw.mit.edu)

任何无损算法都不可能缩短所有可能的输入。长度为 nn 的二进制串有 2n2^n 个，而长度小于 nn 的二进制串，包括空串在内，只有 2n−12^n-1 个。因此，要保证精确恢复，就必须让某些输入的大小保持不变或变得更大。这一计数论证也解释了为什么不能通过反复使用压缩器来无限压缩任意数据。格式头部和编码表还可能进一步增大较短或难以压缩的输入的大小。(rfc-editor.org)

无损压缩

无损数据压缩能够逐比特地重建原始输入。当数据的改动会改变其含义或影响其可用性时，适合使用无损压缩。两类重要技术是利用概率差异的统计编码，以及利用重复序列的字典编码。实际系统经常将两者结合使用。(w3.org)

霍夫曼编码构造一种变长前缀码：任何码字都不是另一个码字的开头，因此无需分隔符也能进行无歧义解码。概率较高的符号通常分配到较短的码字。对于给定的符号分布，在对这些符号逐个编码的二进制前缀码中，霍夫曼编码能够使平均码长最小。但这并不意味着它在所有可能的压缩方法中都是最优的。(ocw.mit.edu)

算术编码根据符号概率逐步缩小一个区间，用这个区间表示整个序列。与为每个符号分配整数长度码字的方式不同，它可以将编码开销分摊到整个序列上。字典方法则通过引用或字典条目来表示重复的字符串。Lempel–Ziv–Welch算法在处理过程中建立字典，解码器则重现相应的字典构建过程。(ocw.mit.edu)

DEFLATE压缩格式将 LZ77 式的先前字符串引用与霍夫曼编码相结合。其压缩数据流由多个块组成，各块可以使用固定的霍夫曼码、动态提供的码表，或直接存储未压缩数据。便携式网络图形在 DEFLATE 压缩之前使用可逆滤波：这些滤波器改变图像样本的表示形式，但不丢弃样本，往往能使其中的模式更易于编码。(rfc-editor.org)

有损压缩

有损数据压缩允许重建结果与输入不同。它并不保留每一处细节，而是以应用所需的精度或保真度来表示数据。有损与无损的区别是数学意义上的，而不只是感知上的：即使重建结果在观看者眼中与原始数据完全相同，其样本值仍可能不同，因此仍属于有损压缩。(ocw.mit.edu)

其中一项核心操作是量化，即将某一范围内的数值映射到数量更少的一组代表值。一旦不同的输入被赋予相同的表示，通常就无法恢复其原始值。率失真理论研究在满足指定失真水平的条件下所需的最低编码率。结果既取决于信源分布，也取决于所选的失真度量；并不存在适用于所有数据的通用品质尺度。(ocw.mit.edu)

一种失真度量是均方误差，即原始样本与重建样本之差的平方的平均值。这类数值度量不一定与感知质量完全吻合。因此，压缩设计既可能考虑统计意义上的保真度，也可能考虑与重建信号预期用途相关的准则。(ocw.mit.edu)

JPEG是基于变换的图像压缩的一个例子。其常见的有损编码系统使用离散余弦变换、量化和熵编码。变换改变数据的表示形式；量化引入不可逆的损失；熵编码则将得到的符号编码得更加紧凑。JPEG 1 标准还定义了无损编码，因此该标准整体上并非只包含有损压缩。(jpeg.org)

性能与实现

压缩性能涉及的不仅是最终大小。相关特性还包括编码和解码速度、内存需求、缓冲延迟，以及对增量处理的支持。更大的搜索窗口可以发现更多重复内容，从而提高压缩效果，但也需要更多内存。例如，Zstandard规定了窗口大小限制，并支持使用字典来改善相关输入的压缩效果。(rfc-editor.org)

压缩比通常表示为未压缩大小除以压缩后大小。按照这一约定，将 1,000 字节的输入表示为 250 字节时，压缩比为 4:1，大小减少了 75%。进行比较时，必须明确所采用的约定和输入数据：在某一组数据上得到的压缩比，并不意味着在另一组数据上也能获得相同的表现。(ocw.mit.edu)

压缩格式规定了解码器如何解释数据流，但不一定强制采用唯一的编码器策略。因此，兼容的编码器可能因搜索和建模决策不同而生成大小不同的结果。压缩也不同于纠错码编码：信源编码消除表示中的冗余，而信道编码则有意添加具有特定结构的冗余，以保护传输。通信系统可以依次应用这两种操作。(rfc-editor.org)