1,399
次編輯
變更
创建页面，内容为“{{noteTA |G1=IT |T=zh-hans:数据压缩; zh-hant:资料压缩; |1=zh-hans:数据; zh-hant:资料; |2=zh-hans:信息; zh-hant:资讯; |3=zh-hans:无损; zh-hant:非…”
{{noteTA
|G1=IT
|T=zh-hans:数据压缩; zh-hant:资料压缩;
|1=zh-hans:数据; zh-hant:资料;
|2=zh-hans:信息; zh-hant:资讯;
|3=zh-hans:无损; zh-hant:非破坏性;
|4=zh-hans:有损; zh-hant:破坏性;
|5=zh-hans:可执行文件; zh-hant:执行档;
|6=zh-hans:质量; zh-hant:品质;
}}
在[[计算机科学]]和[[信息论]]中，'''数据压缩'''或者'''源编码'''是按照特定的编码机制用比未经编码少的数据[[位元]]（或者其它信息相关的单位）表示信息的过程。例如，如果我们将「compression」编码为「comp」那么这篇文章可以用较少的数据位表示。常见的例子是[[ZIP (算法)|ZIP文件格式]]，此格式不仅仅提供压缩功能，还可作为[[归档工具]]（Archiver），能够将许多文件存储到同一个文件中。
== 概要 ==
对于任何形式的通信来说，只有当[[信息]]的[[发送方]]和接受方都能够理解编码机制的时候压缩数据通信才能够工作。例如，只有当接受方知道这篇文章需要用汉语字符解释的时候这篇文章才有意义。同样，只有当接受方知道编码方法的时候他才能够理解压缩数据。
数据压缩能够实现是因为多数现实世界的数据都有[[统计冗余]]。例如，字母「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 (algorithm)|LZX]]，它用于微软公司的[[CAB]]格式。
最好的压缩工具将概率模型预测结果用于[[算术编码]]。算术编码由芬兰信息理论学家Jorma Rissanen发明，并且由Witten、Neal以及Cleary将它转变成一个实用的方法。这种方法能够实现比众人皆知的哈夫曼算法更好的压缩，并且它本身非常适合于自适应数据压缩，自适应数据压缩的预测与上下文密切相关。算术编码已经用于[[二值图像]]压缩标淮[[JBIG]]、文档压缩标淮[[DjVu|DejaVu]]。文本输入系统[[Dasher]]是一个逆算术编码器。
== 参见 ==
=== 数据压缩专题 ===
* [[柯氏复杂性]]
* [[信息熵]]
* [[自解压缩档]]
* [[图像压缩]]
* [[语音压缩]]
* [[视频压缩]]
* [[多媒体压缩]]
* [[最小描述长度]]
* [[最小消息长度]]（two-part lossless compression designed for inference）
=== 压缩算法 ===
==== [[无损数据压缩]] ====
* [[行程长度编码]]
* [[字典编码]]
** [[LZ77与LZ78]]
** [[LZW]]
* [[局部匹配预测]]（也称为PPM）
* [[熵编码]]
** [[哈夫曼编码]]：简单的熵编码，通常用于压缩的最后一步
** [[自适应哈夫曼编码]]
** [[算术编码]]
*** [[区间编码]]：与算术编码一样，但是用一种少许不同的方法工作
** [[T-code]]：哈夫曼编码的变体
** [[Golomb coding]]：用于[[几何分布]]的无限输入数据的简单熵编码
* [[Slepian-Wolf编码]]：无损的[[分布式信源编码]]
==== [[有损数据压缩]] ====
* [[离散余弦变换]]
* [[分形压缩]]（fractal compression）
** [[分形变换]]（fractal transform）
* [[小波压缩]]
* [[向量量化]]（vector quantization）
* [[线性预测编码]]
* [[Wyner-Ziv编码]]（有损的[[分布式信源编码]]）
==== 实现实例 ====
* [[DEFLATE]]（LZ77与哈夫曼编码的组合）——爲ZIP、gzip、zlib与PN文件所使用
* [[LZMA]]：[[7-Zip]]与{{tsl|en|StuffitX|StuffiX}}使用
* [[LZO]]（非常快速的LZ变体，针对速度要求）
* [[Unix]] compress工具（.Z文件格式）、以及GIF使用LZW
* [[bzip2]]（Burrows-Wheeler变换与哈夫曼编码的组合）
* {{tsl|en|PAQ|PAQ}}（一种基于{{tsl|en|context mixing|上下文混合}}的超高压缩率的算法，但是极度缓慢，是最高压缩比竞争中的佼佼者。）
* [[JPEG]]（使用离散余弦变换、量化、哈夫曼编码的[[图像压缩技术|图像压缩]]）
* [[MPEG]]（广泛使用的音频及视频压缩标淮族，视频压缩使用[[离散余弦变换]]以及运动补偿预测）
* [[MP3]]（[[MPEG-1]]标淮中用于声音及音乐压缩的部分，使用子带、[[MDCT]]、感知模型、量化以及哈夫曼编码）
* [[Windows Media Audio|WMA]]（[[WMV]]音频编码规范中的一部分，使用[[MDCT]]、感知模型、低位元率量化、量化以及哈夫曼编码）
* [[Vorbis]]（类似于AAC的基于DCT的音频编解码，为了避免专利问题而设计）
* [[JPEG 2000]]（使用小波、量化、熵编码的图像压缩）
* [[TTA]]（使用[[线性预测编码]]，用于无损音频压缩）
* [[FLAC]]（用于无损音频压缩的[[线性预测编码]]）
== 外部链接 ==
* [http://www.maximumcompression.com/ Data Compression Benchmarks and Tests]
* [http://www-nt.e-technik.uni-rostock.de/~ts/Datacompression/compression.html Data Compression - Systematisation by T.Strutz]
* [http://www.vectorsite.net/ttdcmp1.html Public domain article on data compression]
* [http://computer.howstuffworks.com/file-compression.htm/printable How Compression Works]
* [http://uclc.info/ Ultimate Command Line Compressors]
* [http://www.compression-links.info/ Compression Resources catalog]（currently the biggest）
* [http://www.c10n.info/ The Data Compression News Blog]
* [http://www.elis.ugent.be/~wheirman/compression/ Practical Compressor Test]（Compares speed and efficiency for commonly used compression programs）
* [http://www.c10n.info/newsletter/ The Monthly Data Compression Newsletter]
* [http://dotwhat.net/type/compressed-files/ Compressed File Types and File Extensions]
* [http://www.fileinfo.net/filetypes/compressed Compressed File Types and File Extensions]
{{压缩方法}}
{{Authority control}}
[[Category:数据压缩]]
|G1=IT
|T=zh-hans:数据压缩; zh-hant:资料压缩;
|1=zh-hans:数据; zh-hant:资料;
|2=zh-hans:信息; zh-hant:资讯;
|3=zh-hans:无损; zh-hant:非破坏性;
|4=zh-hans:有损; zh-hant:破坏性;
|5=zh-hans:可执行文件; zh-hant:执行档;
|6=zh-hans:质量; zh-hant:品质;
}}
在[[计算机科学]]和[[信息论]]中，'''数据压缩'''或者'''源编码'''是按照特定的编码机制用比未经编码少的数据[[位元]]（或者其它信息相关的单位）表示信息的过程。例如，如果我们将「compression」编码为「comp」那么这篇文章可以用较少的数据位表示。常见的例子是[[ZIP (算法)|ZIP文件格式]]，此格式不仅仅提供压缩功能，还可作为[[归档工具]]（Archiver），能够将许多文件存储到同一个文件中。
== 概要 ==
对于任何形式的通信来说，只有当[[信息]]的[[发送方]]和接受方都能够理解编码机制的时候压缩数据通信才能够工作。例如，只有当接受方知道这篇文章需要用汉语字符解释的时候这篇文章才有意义。同样，只有当接受方知道编码方法的时候他才能够理解压缩数据。
数据压缩能够实现是因为多数现实世界的数据都有[[统计冗余]]。例如，字母「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 (algorithm)|LZX]]，它用于微软公司的[[CAB]]格式。
最好的压缩工具将概率模型预测结果用于[[算术编码]]。算术编码由芬兰信息理论学家Jorma Rissanen发明，并且由Witten、Neal以及Cleary将它转变成一个实用的方法。这种方法能够实现比众人皆知的哈夫曼算法更好的压缩，并且它本身非常适合于自适应数据压缩，自适应数据压缩的预测与上下文密切相关。算术编码已经用于[[二值图像]]压缩标淮[[JBIG]]、文档压缩标淮[[DjVu|DejaVu]]。文本输入系统[[Dasher]]是一个逆算术编码器。
== 参见 ==
=== 数据压缩专题 ===
* [[柯氏复杂性]]
* [[信息熵]]
* [[自解压缩档]]
* [[图像压缩]]
* [[语音压缩]]
* [[视频压缩]]
* [[多媒体压缩]]
* [[最小描述长度]]
* [[最小消息长度]]（two-part lossless compression designed for inference）
=== 压缩算法 ===
==== [[无损数据压缩]] ====
* [[行程长度编码]]
* [[字典编码]]
** [[LZ77与LZ78]]
** [[LZW]]
* [[局部匹配预测]]（也称为PPM）
* [[熵编码]]
** [[哈夫曼编码]]：简单的熵编码，通常用于压缩的最后一步
** [[自适应哈夫曼编码]]
** [[算术编码]]
*** [[区间编码]]：与算术编码一样，但是用一种少许不同的方法工作
** [[T-code]]：哈夫曼编码的变体
** [[Golomb coding]]：用于[[几何分布]]的无限输入数据的简单熵编码
* [[Slepian-Wolf编码]]：无损的[[分布式信源编码]]
==== [[有损数据压缩]] ====
* [[离散余弦变换]]
* [[分形压缩]]（fractal compression）
** [[分形变换]]（fractal transform）
* [[小波压缩]]
* [[向量量化]]（vector quantization）
* [[线性预测编码]]
* [[Wyner-Ziv编码]]（有损的[[分布式信源编码]]）
==== 实现实例 ====
* [[DEFLATE]]（LZ77与哈夫曼编码的组合）——爲ZIP、gzip、zlib与PN文件所使用
* [[LZMA]]：[[7-Zip]]与{{tsl|en|StuffitX|StuffiX}}使用
* [[LZO]]（非常快速的LZ变体，针对速度要求）
* [[Unix]] compress工具（.Z文件格式）、以及GIF使用LZW
* [[bzip2]]（Burrows-Wheeler变换与哈夫曼编码的组合）
* {{tsl|en|PAQ|PAQ}}（一种基于{{tsl|en|context mixing|上下文混合}}的超高压缩率的算法，但是极度缓慢，是最高压缩比竞争中的佼佼者。）
* [[JPEG]]（使用离散余弦变换、量化、哈夫曼编码的[[图像压缩技术|图像压缩]]）
* [[MPEG]]（广泛使用的音频及视频压缩标淮族，视频压缩使用[[离散余弦变换]]以及运动补偿预测）
* [[MP3]]（[[MPEG-1]]标淮中用于声音及音乐压缩的部分，使用子带、[[MDCT]]、感知模型、量化以及哈夫曼编码）
* [[Windows Media Audio|WMA]]（[[WMV]]音频编码规范中的一部分，使用[[MDCT]]、感知模型、低位元率量化、量化以及哈夫曼编码）
* [[Vorbis]]（类似于AAC的基于DCT的音频编解码，为了避免专利问题而设计）
* [[JPEG 2000]]（使用小波、量化、熵编码的图像压缩）
* [[TTA]]（使用[[线性预测编码]]，用于无损音频压缩）
* [[FLAC]]（用于无损音频压缩的[[线性预测编码]]）
== 外部链接 ==
* [http://www.maximumcompression.com/ Data Compression Benchmarks and Tests]
* [http://www-nt.e-technik.uni-rostock.de/~ts/Datacompression/compression.html Data Compression - Systematisation by T.Strutz]
* [http://www.vectorsite.net/ttdcmp1.html Public domain article on data compression]
* [http://computer.howstuffworks.com/file-compression.htm/printable How Compression Works]
* [http://uclc.info/ Ultimate Command Line Compressors]
* [http://www.compression-links.info/ Compression Resources catalog]（currently the biggest）
* [http://www.c10n.info/ The Data Compression News Blog]
* [http://www.elis.ugent.be/~wheirman/compression/ Practical Compressor Test]（Compares speed and efficiency for commonly used compression programs）
* [http://www.c10n.info/newsletter/ The Monthly Data Compression Newsletter]
* [http://dotwhat.net/type/compressed-files/ Compressed File Types and File Extensions]
* [http://www.fileinfo.net/filetypes/compressed Compressed File Types and File Extensions]
{{压缩方法}}
{{Authority control}}
[[Category:数据压缩]]