数据压缩

计算机功能
收藏
0有用+1
0
数据压缩(英文:Data Compression [2]),是用更少的空间对原有数据进行编码的过程 [2],指在不丢失有用信息的前提下,缩减数据量以减少存储空间,提高其传输、存储和处理效率,或按照一定的算法对数据进行重新组织,减少数据的冗余和存储的空间的一种技术方法。数据压缩包括有损压缩和无损压缩
计算机科学信息论中,数据压缩或者源编码是按照特定的编码机制用比未经编码少的数据位元(或者其它信息相关的单位)表示信息的过程。例如,如果我们将“compression”编码为“comp”那么这篇文章可以用较少的数据位表示。一种流行的压缩实例是许多计算机都在使用的ZIP 文件格式,它不仅仅提供了压缩的功能,而且还作为归档工具(Archiver)使用,能够将许多文件存储到同一个文件中。
中文名
数据压缩
外文名
Data Compression
包    括
有损压缩无损压缩
学    科
计算机科学技术_数据库_数据库新技术

概要

播报
编辑
对于任何形式的通信来说,只有当信息的发送方和接受方都能够理解编码机制的时候压缩数据通信才能够工作。例如,只有当接受方知道这篇文章需要用英语字符解释的时候这篇文章才有意义。同样,只有当接受方知道编码方法的时候他才能够理解压缩数据。一些压缩算法利用了这个特性,在压缩过程中对数据进行加密,例如利用密码加密,以保证只有得到授权的一方才能正确地得到数据。
数据压缩能够实现是因为多数现实世界的数据都有统计冗余。例如,字母“e”在英语中比字母“z”更加常用,字母“q”后面是“z”的可能性非常小。无损压缩算法通常利用了统计冗余,这样就能更加简练地、但仍然是完整地表示发送方的数据。
如果允许一定程度的保真度损失,那么还可以实现进一步的压缩。例如,人们看图画或者电视画面的时候可能并不会注意到一些细节并不完善。同样,两个音频录音采样序列可能听起来一样,但实际上并不完全一样。有损压缩算法在带来微小差别的情况下使用较少的位数表示图像、视频或者音频。
由于可以帮助减少如硬盘空间与连接带宽这样的昂贵资源的消耗,所以压缩非常重要,然而压缩需要消耗信息处理资源,这也可能是费用昂贵的。所以数据压缩机制的设计需要在压缩能力、失真度、所需计算资源以及其它需要考虑的不同因素之间进行折衷。
一些机制是可逆的,这样就可以恢复原始的数据,这种机制称为无损数据压缩;另外一些机制为了实现更高的压缩率允许一定程度的数据损失,这种机制称为有损数据压缩
然而,经常有一些文件不能被无损数据压缩算法压缩,实际上对于不含可以辨别样式的数据任何压缩算法都不能压缩。试图压缩已经经过压缩的数据通常得到的结果实际上是扩展数据,试图压缩经过加密的数据通常也会得到这种结果。
实际上,有损数据压缩也会最终达到不能工作的地步。我们来举一个极端的例子,压缩算法每次去掉文件最后一个字节,那么经过这个算法不断的压缩直至文件变空,压缩算法将不能继续工作。

分类

播报
编辑
数据压缩的方式非常多,不同特点的数据有不同的数据压缩方式(也就是编码方式),下面从几个方面对其进行分类。 [1]
(1)即时压缩和非即时压缩
比如打IP电话,就是将语音信号转化为数字信号,同时进行压缩,然后通过Internet传送出去,这个数据压缩的过程是即时进行的。即时压缩一般应用在影像、声音数据的传送中。即时压缩常用到专门的硬件设备,如压缩卡等。
非即时压缩是计算机用户经常用到的,这种压缩在需要的情况下才进行,没有即时性。例如压缩一张图片、一篇文章、一段音乐等。非即时压缩一般不需要专门的设备,直接在计算机中安装并使用相应的压缩软件就可以了。
(2)数据压缩和文件压缩
其实数据压缩包含了文件压缩,数据本来是泛指任何数字化的信息,包括计算机中用到的各种文件,但有时,数据是专指一些具有时间性的数据,这些数据常常是即时采集、即时处理或传输的。而文件压缩就是专指对将要保存在磁盘等物理介质的数据进行压缩,如一篇文章数据、一段音乐数据、一段程序编码数据等的压缩。
(3)无损压缩与有损压缩
无损压缩利用数据的统计冗余进行压缩。数据统计冗余度的理论限制为2:1到5:1,所以无损压缩的压缩比一般比较低。这类方法广泛应用于文本数据、程序和特殊应用场合的图像数据等需要精确存储数据的压缩。有损压缩方法利用了人类视觉、听觉对图像、声音中的某些频率成分不敏感的特性,允许压缩的过程中损失一定的信息。虽然不能完全恢复原始数据,但是所损失的部分对理解原始图像的影响较小,却换来了比较大的压缩比。有损压缩广泛应用于语音、图像和视频数据的压缩。

原理

播报
编辑
事实上,多媒体信息存在许多数据冗余。例如,一幅图像中的静止建筑背景、蓝天和绿地,其中许多像素是相同的如果逐点存储,就会浪费许多空间,这称为空间冗余。又如,在电视和动画的相邻序列中,只有运动物体有少许变化,仅存储差异部分即可,这称为时间冗余。此外还有结构冗余、视觉冗余等,这就为数据压缩提供了条件。
总之,压缩的理论基础是信息论。从信息的角度来看,压缩就是去除掉信息中的冗余,即去除掉确定的或可推知的信息,而保留不确定的信息,也就是用一种更接近信息本质的描述来代替原有的冗余的描述,这个本质的东西就是信息量。

应用

播报
编辑
一种非常简单的压缩方法是行程长度编码,这种方法使用数据及数据长度这样简单的编码代替同样的连续数据,这是无损数据压缩的一个实例。这种方法经常用于办公计算机以更好地利用磁盘空间、或者更好地利用计算机网络中的带宽。对于电子表格文本可执行文件等这样的符号数据来说,无损是一个非常关键的要求,因为除了一些有限的情况,大多数情况下即使是一个数据位的变化都是无法接受的。
对于视频和音频数据,只要不损失数据的重要部分一定程度的质量下降是可以接受的。通过利用人类感知系统的局限,能够大幅度得节约存储空间并且得到的结果质量与原始数据质量相比并没有明显的差别。这些有损数据压缩方法通常需要在压缩速度、压缩数据大小以及质量损失这三者之间进行折衷。
有损图像压缩用于数码相机中,大幅度地提高了存储能力,同时图像质量几乎没有降低。用于DVD的有损MPEG-2编解码视频压缩也实现了类似的功能。
在有损音频压缩中,心理声学的方法用来去除信号中听不见或者很难听见的成分。人类语音的压缩经常使用更加专业的技术,因此人们有时也将“语音压缩”或者“语音编码”作为一个独立的研究领域与“音频压缩”区分开来。不同的音频和语音压缩标准都属于音频编解码范畴。例如语音压缩用于因特网电话,而音频压缩被用于CD翻录并且使用 MP3 播放器解码。

理论

播报
编辑
压缩的理论基础是信息论(它与算法信息论密切相关)以及率失真理论,这个领域的研究工作主要是由 Claude 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 是一个逆算术编码器。

类型

播报
编辑
数据压缩可分成两种类型,一种叫做无损压缩,另一种叫做有损压缩
无损压缩是指使用压缩后的数据进行重构(或者叫做还原,解压缩),重构后的数据与原来的数据完全相同;无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。无损压缩算法一般可以把普通文件的数据压缩到原来的1/2~1/4。一些常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv & Welch)压缩算法。
有损压缩是指使用压缩后的数据进行重构,重构后的数据与原来的数据有所不同,但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如,图像和声音的压缩就可以采用有损压缩,因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息,丢掉一些数据而不至于对声音或者图像所表达的意思产生误解,但可大大提高压缩比

延伸阅读

播报
编辑
在网上,我们之所以能够轻松地发送图像和音频数据,方便地分享视频,不仅得益于互联网的带宽变大、速度变快,也得益于数据压缩技术的进步。可以不夸张地说,我们常用的各种数据都使用了数据压缩。
数据压缩可以粗略分为两种:一种是可以把数据完全恢复到原始状态的无损数据压缩,另一种是无法将数据完全恢复到原始状态的有损数据压缩。
无损数据压缩中,最简单的方法就是行程长度压缩。假设某字符串中有相同字符连续排列的部分,就可以将连续重复的字符换成数字,达到缩短数据的目的。例如aaaabbbcccccc这个字符串,是由4个a、3个b和6个c连续构成的,所以可以用“4a3b6c”来表示,将原本有13个字符的数据压缩为6个字符。这个方法还可以应用到图像上,例如,如果图像数据里有12个像素连续为红色、10个像素连续为黄色,就可以用“12红10黄”来表示。但是在实际数据中,大量字符相同或者颜色连续的情况很少。
无损数据压缩中,另有一个著名的算法是哈夫曼编码,这是一个应用范围更广的压缩技术。在计算机里,对每一个字符(例如英文字母)都采用8比特(bit)来表示。在哈夫曼编码里,会暂时取消原本分配给各个字符的8比特数,将数据中出现次数很多的字符用短比特数来表示,而出现次数不多的字符则用长比特数来表示。通过这样的变换,就能更有效率地表示数据了。哈夫曼编码压缩率比较高而且不存在专利问题,所以被用于zip等压缩算法中。
有损数据压缩常被使用到图像、音频和视频等数据中。实际上,压缩之前的这类数据里,包含了很多人的知觉无法感知到的信息。只要删除这些信息,就能让数据变小。不过,消除的数据是无法恢复的。例如,图像数据中包含了亮度和色相(颜色的成分)。人的视觉对亮度的变化很敏感,而在分辨色相方面却不太灵敏。因此,可以巧妙地缩小表示色相的数据。此时用到的是称为傅里叶变换的数学方法。
一些数码相机可以同时存储未压缩的原始数据(raw data)和压缩之后的JPEG数据。对同一个物体拍摄的图像,原始数据可达数十兆字节(MB),JPEG数据则可压缩到其十分之一左右 [2]