信息论与编码论文
信息论与编码 论文
信息论与编码之数据压缩
关键词：简介 概要 原理 应用 理论 类型 流行算法 算法编码
简介
在计算机科学和信息论中，数据压缩或者源编码是按照特定的编码机制用比未经编码少的数据位元（或者其它信息相关的单位）表示信息的过程。例如，如果我们将“compression”编码为“comp”那么这篇文章可以用较少的数据位表示。一种流行的压缩实例是许多计算机都在使用的ZIP 文件格式，它不仅仅提供了压缩的功能，而且还作为归档工具（Archiver）使用，能够将许多文件存储到同一个文件中。
概要
对于任何形式的通信来说，只有当信息的发送方和接受方都能够理解编码机制的时候压缩数据通信才能够工作。例如，只有当接受方知道这篇文章需要用英语字符解释的时候这篇文章才有意义。同样，只有当接受方知道编码方法的时候他才能够理解压缩数据。一些压缩算法利用了这个特性，在压缩过程中对数据进行加密，例如利用密码加密，以保证只有得到授权的一方才能正确地得到数据。
一些机制是可逆的，这样就可以恢复原始的数据，这种机制称为无损数据压缩；另外一些机制为了实现更高的压缩率允许一定程度的数据损失，这种机制称为有损数据压缩。 然而，经常有一些文件不能被无损数据压缩算法压缩，实际上对于不含可以辨别样式的数据任何压缩算法都不能压缩。试图压缩已经经过压缩的数据通常得到的结果实际上是扩展数据，试图压缩经过加密的数据通常也会得到这种结果。
原理
事实上，多媒体信息存在许多数据冗余。例如，一幅图像中的静止建筑背景、蓝天和绿地，其中许多像素是相同的如果逐点存储，就会浪费许多空间，这称为空间冗余。又如，在电视和动画的相邻序列中，只有运动物体有少许变化，仅存储差异部分即可，这称为时间冗余。此外还有结构冗余、视觉冗余等，这就为数据压缩提供了条件。
应用
一种非常简单的压缩方法是行程长度编码，这种方法使用数据及数据长度这样简单的编码代替同样的连续数据，这是无损数据压缩的一个实例。这种方法经常用于办公计算机以更
好地利用磁盘空间、或者更好地利用计算机网络中的带宽。对于电子表格、文本、可执行文件等这样的符号数据来说，无损是一个非常关键的要求，因为除了一些有限的情况，大多数情况下即使是一个数据位的变化都是无法接受的。
在有损音频压缩中，心理声学的方法用来去除信号中听不见或者很难听见的成分。人类语音的压缩经常使用更加专业的技术，因此人们有时也将“语音压缩”或者“语音编码”作为一个独立的研究领域与“音频压缩”区分开来。不同的音频和语音压缩标准都属于音频编解码范畴。例如语音压缩用于因特网电话，而音频压缩被用于CD翻录并且使用 MP3 播放器解码。
理论
压缩的理论基础是信息论（它与算法信息论密切相关）以及率失真理论，这个领域的研究工作主要是由 Claude Shannon 奠定的，他在二十世纪四十年代末期及五十年代早期发表了这方面的基础性的论文。Doyle 和 Carlson 在2000年写道数据压缩“有所有的工程领域最简单、最优美的设计理论之一”。密码学与编码理论也是密切相关的学科，数据压缩的思想与统计推断也有很深的渊源。
信源编码中，有定长编码和变长编码。在定长编码中,K是定值。我们的目的是寻找最小K值。编码器输入X=(X1 X2…Xl …XL), Xl∈{a1,…an},
输入的消息总共有nL种可能的组合。输出的码字Y=(Y1 Y2 …Yk… YK ) , Yk∈{b1,…bm} 输出的码字总共有mK种可能的组合。若对信源进行定长编码,必须满足: nL≤mK。对于平均符号熵为HL(X)的离散平稳无记忆信源,必存在一种无失真编码方法,使平均信息率满足不等式HL(X)KHL(X) 其中ε为任意小正数。用变长编码来达到相当高的编码效率,一般所要求的符号长度L可以比定长编码小得多。编码效率的下界：HL(X)HL(X)KHL(X)L
类型
数据压缩可分成两种类型，一种叫做无损压缩，另一种叫做有损压缩。
无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/2～1/4。一些常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv & Welch)压缩算法。
有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。
流行算法
Lempel-Ziv（LZ）压缩方法是最流行的无损存储算法之一。DEFLATE是 LZ 的一个变体，它针对解压速度与压缩率进行了优化，虽然它的压缩速度可能非常缓慢，PKZIP、gzip 以
及 PNG 都在使用 DEFLATE。LZW （Lempel-Ziv-Welch）是 Unisys 的专利，直到2003年6月专利到期限，这种方法用于 GIF 图像。另外值得一提的是 LZR (LZ-Renau) 方法，它是 Zip 方法的基础。LZ 方法使用基于表格的压缩模型，其中表格中的条目用重复的数据串替换。
算法编码
算法编码简介
最好的压缩工具将概率模型预测结果用于算术编码。算术编码由 Jorma Rissanen 发明，并且由 Witten、Neal 以及 Cleary 将它转变成一个实用的方法。这种方法能够实现比众人皆知的哈夫曼算法更好的压缩，并且它本身非常适合于自适应数据压缩，自适应数据压缩的预测与上下文密切相关。算术编码已经用于二值图像压缩标准 JBIG、文档压缩标准 DejaVu。文本 输入 系统 Dasher 是一个逆算术编码器。
把信源输出序列的概率和实数段[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]
一般多元信源序列的累积概率递推公式为：
P(S,ar)P(S)p(S)Pr，A(S,ar)p(S,ar)p(S)p(ar)
序列的概率公式为：p(S,ar)p(S)pr
实际应用中,采用累积概率P(S)表示码字C(S),符号概率p(S)表示状态区间A(S),则有： C(S,r) = C(S)+A(S)Pr
A(S,r) = A(S) pr
实际编码时,只需两个存储器,起始时可令:
A(Φ) =1, C(Φ) = 0
每输入一个信源符号,存储器C和A 就按照上式更新一次,直至信源符号输入完毕,就可将存储器C的内容作为该序列的码字输出。
编码方法：
将符号序列的累积概率写成二进位的小数，取小数点后L位,若后面有尾数,就进位到第L位,这样得到的一个数C,并使L满足
1Llogp(S)，取整
我们学习了几种信源编码：香农编码、费诺编码、哈夫曼编码、游程编码、算术编码。有时为了得到较高的编码效率，先采用某种正交变换，解除或减弱信源符号间的相关性，然后再进行信源编码；有时则利用信源符号间的相关性直接编码。