搜索
信息论信息论与编码之数据压缩摘要:在计算机科学和信息论中，数据压缩或者源编码是按照特定的编码机制用比未经编码少的数据位元（或者其它信息相关的单位）表示信息的过程。例如，如果我们将“compression”编码为“comp”那么这篇文章可以用较少的数据位表示。一种流行的压缩实例是许多计算机都在使用的ZIP文件格式，它不仅仅提供了压缩的功能，而且还作为归档工具（Archiver）使用，能够将许多文件存储到同一个文件中。关键词：概述原理应用理论类型流行算法算法编码1.概述对于任何形式的通信来说，只有当信息的发送方和接受方都能够理解编码机制的时候压缩数据通信才能够工作。例如，只有当接受方知道这篇文章需要用英语字符解释的时候这篇文章才有意义。同样，只有当接受方知道编码方法的时候他才能够理解压缩数据。一些压缩算法利用了这个特性，在压缩过程中对数据进行加密，例如利用密码加密，以保证只有得到授权的一方才能正确地得到数据。数据压缩能够实现是因为多数现实世界的数据都有统计冗余。例如，字母“e”在英语中比字母“z”更加常用，字母“q”后面是“z”的可能性非常小。无损压缩算法通常利用了统计冗余，这样就能更加简练地、但仍然是完整地表示发送方的数据。如果允许一定程度的保真度损失，那么还可以实现进一步的压缩。例如，人们看图画或者电视画面的时候可能并不会注意到一些细节并不完善。同样，两个音频录音采样序列可能听起来一样，但实际上并不完全一样。有损压缩算法在带来微小差别的情况下使用较少的位数表示图像、视频或者音频。由于可以帮助减少如硬盘空间与连接带宽这样的昂贵资源的消耗，所以压缩非常重要，然而压缩需要消耗信息处理资源，这也可能是费用昂贵的。所以数据压缩机制的设计需要在压缩能力、失真度、所需计算资源以及其它需要考虑的不同因素之间进行折衷。一些机制是可逆的，这样就可以恢复原始的数据，这种机制称为无损数据压缩；另外一些机制为了实现更高的压缩率允许一定程度的数据损失，这种机制称为有损数据压缩。然而，经常有一些文件不能被无损数据压缩算法压缩，实际上对于不含可以辨别样式的数据任何压缩算法都不能压缩。试图压缩已经经过压缩的数据通常得到的结果实际上是扩展数据，试图压缩经过加密的数据通常也会得到这种结果。实际上，有损数据压缩也会最终达到不能工作的地步。我们来举一个极端的例子，压缩算法每次去掉文件最后一个字节，那么经过这个算法不断的压缩直至文件变空，压缩算法将不能继续工作。信息论2.原理事实上，多媒体信息存在许多数据冗余。例如，一幅图像中的静止建筑背景、蓝天和绿地，其中许多像素是相同的如果逐点存储，就会浪费许多空间，这称为空间冗余。又如，在电视和动画的相邻序列中，只有运动物体有少许变化，仅存储差异部分即可，这称为时间冗余。此外还有结构冗余、视觉冗余等，这就为数据压缩提供了条件。总之，压缩的理论基础是信息论。从信息的角度来看，压缩就是去除掉信息中的冗余，即去除掉确定的或可推知的信息，而保留不确定的信息，也就是用一种更接近信息本质的描述来代替原有的冗余的描述，这个本质的东西就是信息量。3.应用一种非常简单的压缩方法是行程长度编码，这种方法使用数据及数据长度这样简单的编码代替同样的连续数据，这是无损数据压缩的一个实例。这种方法经常用于办公计算机以更好地利用磁盘空间、或者更好地利用计算机网络中的带宽。对于电子表格、文本、可执行文件等这样的符号数据来说，无损是一个非常关键的要求，因为除了一些有限的情况，大多数情况下即使是一个数据位的变化都是无法接受的。对于视频和音频数据，只要不损失数据的重要部分一定程度的质量下降是可以接受的。通过利用人类感知系统的局限，能够大幅度得节约存储空间并且得到的结果质量与原始数据质量相比并没有明显的差别。这些有损数据压缩方法通常需要在压缩速度、压缩数据大小以及质量损失这三者之间进行折衷。有损图像压缩用于数码相机中，大幅度地提高了存储能力，同时图像质量几乎没有降低。用于DVD的有损MPEG-2编解码视频压缩也实现了类似的功能。在有损音频压缩中，心理声学的方法用来去除信号中听不见或者很难听见的成分。人类语音的压缩经常使用更加专业的技术，因此人们有时也将“语音压缩”或者“语音编码”作为一个独立的研究领域与“音频压缩”区分开来。不同的音频和语音压缩标准都属于音频编解码范畴。例如语音压缩用于因特网电话，而音频压缩被用于CD翻录并且使用MP3播放器解码。4.理论压缩的理论基础是信息论（它与算法信息论密切相关）以及率失真理论，这个领域的研究工作主要是由ClaudeShannon奠定的，他在二十世纪四十年代末期及五十年代早期发表了这方面的基础性的论文。Doyle和Carlson在2000年写道数据压缩“有所有的工程领域最简单、最优美的设计理论之一”。密码学与编码理论也是密切相关的学科，数据压缩的思想与统计推断也有很深的渊源。许多无损数据压缩系统都可以看作是四步模型，有损数据压缩系统通常包含更多的步骤，例如它包括预测、频率变换以及量化。信源编码中，有定长编码和变长编码。在定长编码中,K是定值。我们的目的是寻找最小K值。编码器输入X=(X1X2…Xl…XL),Xl∈{a1,…an},输入的消息总共有nL种可能的组合。输出的码字Y=(Y1Y2…Yk…YK),Yk∈{b1,…bm}输出的码字总共有mK种可能的组合。若对信源进行定长编码,信息论必须满足:nL≤mK。实际英文电报符号信源,在考虑了符号出现的概率以及符号之间的依赖性后,平均每个英文电报符号所提供的信息量约等于1.4比特,大大小于5比特。编码后5个二元符号只携带约1.4比特信息量。所以说，定长编码的信息传输效率极低。所以选用变长编码。对于平均符号熵为HL(X)的离散平稳无记忆信源,必存在一种无失真编码方法,使平均信息率满足不等式)X()(LLHKXH其中ε为任意小正数。用变长编码来达到相当高的编码效率,一般所要求的符号长度L可以比定长编码小得多。编码效率的下界：LmXHXHKXHLLLlog)()()(5.类型数据压缩可分成两种类型，一种叫做无损压缩，另一种叫做有损压缩。无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/2～1/4。一些常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv&Welch)压缩算法。有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。6.流行算法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格式。7.算法编码7.1算法编码简介最好的压缩工具将概率模型预测结果用于算术编码。算术编码由JormaRissanen发明，并且由Witten、Neal以及Cleary将它转变成一个实用的方法。这种方法能够实现比众人皆知的哈夫曼算法更好的压缩，并且它本身非常适合于信息论自适应数据压缩，自适应数据压缩的预测与上下文密切相关。算术编码已经用于二值图像压缩标准JBIG、文档压缩标准DejaVu。文本输入系统Dasher是一个逆算术编码器。算术编码是近十多年来发展迅速的一种无失真信源编码,它与最佳的哈夫曼码相比,理论性能稍加逊色,而实际压缩率和编码效率却往往还优于哈夫曼码,且实现简单,故很受工程上的重视。算术编码不同于哈夫曼码,它是非分组(非块)码。它从全序列出发,考虑符号之间的关系来进行编码。算术编码利用了累积概率的概念。算术码主要的编码方法是计算输入信源符号序列所对应的区间。7.2算术编码的主要概念把信源输出序列的概率和实数段[0,1]中的一个数C联系起来。设信源字母表为{a1,a2},其概率p(a1)=0.6,p(a2)=0.4，将[0,1]分成与概率比例相应的区间,[0,0.6][0.6,l]设信源输出序列S=S1S2S3…Sn。当信源输出的第一个符号S1=a1时,数C的值处在[0,0.6]，当信源输出的第一个符号S1=a2时,数C的值处在[0.6,l]一般多元信源序列的累积概率递推公式为：rrPSpSPaSP)()(),(，)()(),(),(rrrapSpaSpaSA序列的概率公式为：rrpSpaSp)(),(实际应用中,采用累积概率P(S)表示码字C(S),符号概率p(S)表示状态区间A(S),则有：C(S,r)=C(S)+A(S)PrA(S,r)=A(S)pr实际编码时,只需两个存储器,起始时可令:A(Φ)=1,C(Φ)=0每输入一个信源符号,存储器C和A就按照上式更新一次,直至信源符号输入完毕,就可将存储器C的内容作为该序列的码字输出。7.3编码方法将符号序列的累积概率写成二进位的小数，取小数点后L位,若后面有尾数,就进位到第L位,这样得到的一个数C,并使L满足)S(1logpL，取整8.结论信息论我们学习中学了，几种信源编码：香农编码、费诺编码、哈夫曼编码、游程编码、算术编码。游程编码和算术编码是非分组编码；游程编码是限失真信源编码。优点：提高编码效率；缺点：需要大量缓冲设备来存储这些变长码,然后再以恒定的码率进行传送；在传输的过程中如果出现了误码,容易引起错误扩散,所以要求有优质的信道。有时为了得到较高的编码效率，先采用某种正交变换，解除或减弱信源符号间的相关性，然后再进行信源编码；有时则利用信源符号间的相关性直接编码。参考文献:[1]多媒体数据压缩标准化的现状与发展丁贵广郭宝龙《计算机工程与应用》2002第1期-万方数据[2]WebGIS矢量空间数据压缩方法探讨李青元刘晓东曹代勇《中国图象图形学报A辑》2001第12期-万方数据[3]褚振勇,翁木云.FPGA设计及应用[M].西安:西安电子科技大学出版社,2002.[4]楼顺天,陈生潭,雷虎民.Matlab51x程序设计语言[M].西安:西安电子科技大学出版社,2000.[5]BernardSklar,徐平平,宋铁成,等.数字通信基础与应用[M].北京:电子工业出版社,2000.[6]梁华国,基于交替与连续长度码的有效测试数据压缩和解压.科学出版社,2002