数据压缩

在计算机科学和信息论中，数据压缩或者源编码是按照特定的编码机制用比未经编码少的数据比特（或者其它信息相关的单位）表示信息的过程。例如，若将“compression”编码为“comp”，则这篇文章可以用较少的数据比特表示。常见的例子是ZIP文件格式，此格式不仅仅提供压缩功能，还可作为归档工具（Archiver），能够将许多文件存储到同一个文件中。

可利用资料的一致性（可用信息熵，entropy来表示），规则性，与可预测性去实现数据压缩。人类最先发展的压缩技术实为自然语言，一般来说，若可以用比较精简的自然语言来描述一样事物，那么也就越能够对这样事物做压缩。资料越一致，亦代表其统计特性越集中。以影像压缩为例，其集中代表有傅立叶变换的时域及频域，直方图，特征值。

概要

数据压缩能够实现是因为多数现实世界的数据都有统计冗余。例如，字母“e”在英语中比字母“z”更加常用，字母“q”后面是“z”的可能性非常小。无损数据压缩通常利用了统计冗余，这样就能更加简练地、但仍然是完整地表示发送方的数据。

无损数据压缩的压缩率不足以处理庞大体积的音视频数据，但如果允许一定程度的保真度损失，那么还可以实现进一步的压缩。例如，人们看图画或者电视画面的时候可能并不会注意到一些细节并不完善。同样，两个音频录音采样序列可能听起来一样，但实际上并不完全一样。有损数据压缩在可以接受或无法察觉的情况下使用较少的位数表示图像、视频或者音频。

然而，经常有一些文件不能被有损数据压缩压缩，实际上对于不含可以辨别样式的数据任何压缩算法都不能压缩。另外，试图压缩已经经过压缩的数据通常得到的结果实际上是增加数据。

实际上，有损数据压缩也会最终达到不能工作的地步。例如一个极端的例子：压缩算法每次去掉文件最后一个字节，那么经过这个算法不断的压缩直至文件变空，压缩算法将不能继续工作。

由于可以帮助减少如硬盘空间与连接带宽这样的昂贵资源的消耗，所以压缩非常重要，然而压缩需要消耗信息处理资源，这也可能是费用昂贵的。所以数据压缩机制的设计需要在压缩能力、失真度、所需计算资源以及其它需要考虑的不同因素之间进行折衷。

对于任何形式的通信来说，只有当信息的发送方和接受方都能够理解编码机制的时候压缩数据通信才能够工作。例如，只有当接受方知道这篇文章需要用汉语字符解释的时候这篇文章才有意义。同样，只有当接受方知道编码方法的时候他才能够理解压缩数据。

应用

一种非常简单的压缩方法是行程长度编码，这种方法使用数据及数据长度这样简单的编码代替同样的连续数据，这是无损数据压缩的一个实例。这种方法经常用于办公计算机以更好地利用磁盘空间、或者更好地利用计算机网络中的带宽。对于电子表格、文本、可执行文件等这样的符号数据来说，无损是一个非常关键的要求，因为除了一些有限的情况，大多数情况下即使是一个数据位的变化都是无法接受的。

对于视频和音频数据，只要不损失数据的重要部分一定程度的质量下降是可以接受的。通过利用人类感知系统的局限，能够大幅度的节约存储空间并且得到的结果质量与原始数据质量相比并没有明显的差别。这些有损数据压缩方法通常需要在压缩速度、压缩数据大小以及质量损失这三者之间进行折衷。

有损图像压缩用于数字相机中，大幅度地提高了存储能力，同时图像质量几乎没有降低。用于DVD的有损MPEG-2编解码视频压缩也实现了类似的功能。

在有损音频压缩中，心理声学的方法用来去除信号中听不见或者很难听见的成分。人类语音的压缩经常使用更加专业的技术，因此人们有时也将“语音压缩”或者“语音编码”作为一个独立的研究领域与“音频压缩”区分开来。不同的音频和语音压缩标准都属于音频编解码范畴。例如语音压缩用于因特网电话，而音频压缩被用于CD翻录并且使用MP3播放器解码。

理论

压缩的理论（它与算法信息论密切相关）以及率失真理论，这个领域的研究工作主要是由美国学者克劳德·香农（Claude Elwood Shannon）奠定的，他在二十世纪四十年代末期及五十年代早期发表了这方面的基础性的论文。Doyle和Carlson在2000年写到数据压缩“是所有的工程领域最简单、最优美的设计理论之一”。密码学与编码理论也是密切相关的学科，数据压缩的思想与统计推断也有很深的渊源。

许多无损数据压缩系统都可以看作是四步模型，有损数据压缩系统通常包含更多的步骤，例如它包括预测、频率变换以及量化。

Lempel-Ziv（LZ）压缩方法是流行的无损存储算法之一。DEFLATE是LZ的一个变体，它针对解压速度与压缩率进行了优化，虽然它的压缩速度可能非常缓慢，PKZIP、gzip以及PNG都在使用DEFLATE。LZW（Lempel-Ziv-Welch）是Unisys的专利，直到2003年6月专利到期限，这种方法用于GIF图像。另外值得一提的是LZR （LZ-Renau） 方法，它是Zip方法的基础。LZ方法使用基于表格的压缩模型，其中表格中的条目用重复的数据串替换。对于大多数的LZ方法来说，这个表格是从最初的输入数据动态生成的。这个表格经常采用霍夫曼编码维护（例如SHRI、LZX）。 目前一个性能良好基于LZ的编码机制是LZX，它用于微软公司的CAB格式。

最好的压缩工具将概率模型预测结果用于算术编码。算术编码由芬兰信息理论学家Jorma Rissanen发明，并且由Witten、Neal以及Cleary将它转变成一个实用的方法。这种方法能够实现比众人皆知的哈夫曼算法更好的压缩，并且它本身非常适合于自适应数据压缩，自适应数据压缩的预测与上下文密切相关。算术编码已经用于二值图像压缩标准JBIG、文档压缩标准DejaVu。文本输入系统Dasher是一个逆算术编码器。

参见

数据压缩专题

• 柯氏复杂性
• 信息熵
• 自解压缩包
• 图像压缩
• 语音压缩
• 视频压缩
• 多媒体压缩
• 最小描述长度
• 最小消息长度（two-part lossless compression designed for inference）
• 史路特数字编码系统

压缩算法

无损数据压缩

• 行程长度编码
• 字典编码
  • LZ77与LZ78
  • LZW
• 局部匹配预测（也称为PPM）
• 熵编码
  • 哈夫曼编码：简单的熵编码，通常用于压缩的最后一步
  • 自适应哈夫曼编码
  • 算术编码
    • 区间编码：与算术编码一样，但是用一种少许不同的方法工作
  • T-code：哈夫曼编码的变体
  • 格伦布编码：用于几何分布的无限输入数据的简单熵编码
• Slepian-Wolf编码：无损的分布式信源编码

有损数据压缩

• 离散余弦变换
• 分形压缩（fractal compression）
  • 分形变换（fractal transform）
• 小波压缩
• 向量量化（vector quantization）
• 线性预测编码
• Wyner-Ziv编码（有损的分布式信源编码）

实现实例

• DEFLATE（LZ77与哈夫曼编码的组合）——为ZIP、gzip、zlib与PN文件所使用
• LZMA：7-Zip与StuffiX使用
• LZO（非常快速的LZ变体，针对速度要求）
• Unix compress工具（.Z文件格式）、以及GIF使用LZW
• bzip2（Burrows-Wheeler变换与哈夫曼编码的组合）
• PAQ（一种基于上下文混合的超高压缩率的算法，但是极度缓慢，是最高压缩比竞争中的佼佼者。）

• JPEG（使用离散余弦变换、量化、哈夫曼编码的图像压缩）
• MPEG（广泛使用的音频及视频压缩标准族，视频压缩使用离散余弦变换以及运动补偿预测）
• MP3（MPEG-1标准中用于声音及音乐压缩的部分，使用子带、MDCT、感知模型、量化以及哈夫曼编码）
• WMA（WMV音频编码规范中的一部分，使用MDCT、感知模型、低比特率量化、量化以及哈夫曼编码）
• Vorbis（类似于AAC的基于DCT的音频编解码，为了避免专利问题而设计）
• JPEG 2000（使用小波、量化、熵编码的图像压缩）
• TTA（使用线性预测编码，用于无损音频压缩）
• FLAC（用于无损音频压缩的线性预测编码）
• ATRAC（Adaptive Transform Acoustic Coding，自适应听觉转换编码）为SONY公司于1992年所开发之音频有损数据压缩技术，也是相关技术名词之总称。

外部链接

• Data Compression - Systematisation by T.Strutz （页面存档备份，存于互联网档案馆）
• How Compression Works （页面存档备份，存于互联网档案馆）
• Practical Compressor Test （页面存档备份，存于互联网档案馆）（Compares speed and efficiency for commonly used compression programs）