信息论基础-数据压缩.ppt

《信息论基础-数据压缩.ppt》由会员分享，可在线阅读，更多相关《信息论基础-数据压缩.ppt（99页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章章数据压缩和信源编码数据压缩和信源编码最优码的实际构造！最优码的实际构造！1数据压缩数据压缩“数据压缩数据压缩”在汉英词典中的解释：在汉英词典中的解释：datacompression(Amethodofreducingtheamountofmemoryrequiredtostoredatabyencodingitandminimizingredundancy.Compresseddatatakeslesstimetotransmit,butmorecomputationtimetorestoreittoitsoriginalformwhenneededforprocessing.)2数

2、据压缩数据压缩-作用作用通俗地说，就是用最少的数码来表示信号。通俗地说，就是用最少的数码来表示信号。其作用是：能较快地传输各种信号，如传真、其作用是：能较快地传输各种信号，如传真、Modem通信等；在现有的通信干线并行开通更多的多媒体业通信等；在现有的通信干线并行开通更多的多媒体业务，如各种增值业务；紧缩数据存储容量，如务，如各种增值业务；紧缩数据存储容量，如CDROM、VCD和和DVD等；降低发信机功率，这对于多等；降低发信机功率，这对于多媒体移动通信系统尤为重要。由此看来，通信时间、媒体移动通信系统尤为重要。由此看来，通信时间、传输带宽、存储空间甚至发射能量，都可能成为数据传输带宽、存储空

3、间甚至发射能量，都可能成为数据压缩的对象。压缩的对象。3数据压缩数据压缩-目的目的一、可以节省空间。一、可以节省空间。二、可以减少对带宽的占用。二、可以减少对带宽的占用。JPEG压缩编码技术的基本原理：JPEG专家组开发了两种基本的压缩算法，一种是采用以离散余弦变换（DCT-DiscreteCosineTransform）为基础的有损压缩算法，另一种是以空间线性预测技术（DPCM）为基础的无损压缩算法。现在应用得较多的是有损压缩算法。JPEG标准只处理单帧图像，而不必顾及到前后左右帧，将每帧图像作为基础进行处理，利用了空间压缩编码原理。4数据压缩数据压缩-目的目的一、可以节省空间。一、可以节省

4、空间。二、可以减少对带宽二、可以减少对带宽的占用。的占用。MPEG编码技术的基本原理：MPEG数字视频编码技术实质上是一种统计方法。在时间和空间方向上，视频列通常包含统计冗余度。MPEG压缩技术所依赖的基本统计特性为像素之间(interpel)的相关性，这里包含这样一个设想：即在各连续帧之间存在简单的相关性平移运动。5数据压缩数据压缩-类型类型有损压缩和无损压缩（有损压缩和无损压缩（图片格式图片格式）有损压缩有损压缩可以减少图像在内存和磁盘中占用的空间，在屏幕上观看图像时，不会发现它对图像的外观产生太大的不利影响。因为人的眼睛对光线比较敏感，光线对景物的作用比颜色的作用更为重要，这就是有损压缩

5、技术的基本依据。有损压缩的特点是保持颜色的逐渐变化，删除图像中颜色的突然变化。生物学中的大量实验证明，人类大脑会利用与附近最接近的颜色来填补所丢失的颜色。6数据压缩数据压缩-类型类型有损压缩和无损压缩（有损压缩和无损压缩（图片格式图片格式）有损压缩例如，对于蓝色天空背景上的一朵白云，有损压缩的方法就是删除图像中景物边缘的某些颜色部分。当在屏幕上看这幅图时，大脑会利用在景物上看到的颜色填补所丢失的颜色部分。利用有损压缩技术，某些数据被有意地删除了，而被取消的数据也不再恢复。无可否认，利用有损压缩技术可以大大地压缩文件的数据，但是会影响图像质量。如果使用了有损压缩的图像仅在屏幕上显示，可能对图像质

6、量影响不太大，至少对于人类眼睛的识别程度来说区别不大。可是，如果要把一幅经过有损压缩技术处理的图像用高分辨率打印机打印出来，那么图像质量就会有明显的受损痕迹。7数据压缩数据压缩-类型类型有损压缩和无损压缩（有损压缩和无损压缩（图片格式图片格式）无损压缩无损压缩的基本原理是相同的颜色信息只需保存一次。压缩图像的软件首先会确定图像中哪些区域是相同的，哪些是不同的。包括了重复数据的图像(如蓝天)就可以被压缩，只有蓝天的起始点和终结点需要被记录下来。但是蓝色可能还会有不同的深浅，天空有时也可能被树木、山峰或其他的对象掩盖，这些就需要另外记录。从本质上看，无损压缩的方法可以删除一些重复数据，大大减少要在

7、磁盘上保存的图像尺寸。8数据压缩数据压缩-类型类型有损压缩和无损压缩（有损压缩和无损压缩（图片格式图片格式）无损压缩但是，无损压缩的方法并不能减少图像的内存占用量，这是因为，当从磁盘上读取图像时，软件又会把丢失的像素用适当的颜色信息填充进来。如果要减少图像占用内存的容量，就必须使用有损压缩方法。无损压缩方法的优点是能够比较好地保存图像的质量，但是相对来说这种方法的压缩率比较低。但是，如果需要把图像用高分辨率的打印机打印出来，最好还是使用无损压缩几乎所有的图像文件都采用各自简化的格式名作为文件扩展名。从扩展名就可知道这幅图像是按什么格式存储的，应该用什么样的软件去读写等等。9数据压缩数据压缩-概

8、要概要在计算机科学和信息论中，数据压缩或者信源编码在计算机科学和信息论中，数据压缩或者信源编码是按照特定的编码机制用比未经编码少的数据位元是按照特定的编码机制用比未经编码少的数据位元（或者其它信息相关的单位）表示信息的过程。例（或者其它信息相关的单位）表示信息的过程。例如，如果我们将如，如果我们将“compression”编码为编码为“comp”那那么这么这篇文章可以用较少的数据位表示。一种流行的压缩篇文章可以用较少的数据位表示。一种流行的压缩实例是许多计算机都在使用的实例是许多计算机都在使用的ZIP文件格式，它不仅文件格式，它不仅仅提供了压缩的功能，而且还作为归档工具仅提供了压缩的功能，而且

9、还作为归档工具Archiver）使用，能够将许多文件存储到同一个文件中。使用，能够将许多文件存储到同一个文件中。10数据压缩数据压缩-概要概要对于任何形式的通信来说，只有当信息的发送对于任何形式的通信来说，只有当信息的发送方和接受方都能够理解编码机制的时候压缩数据通方和接受方都能够理解编码机制的时候压缩数据通信才能够工作。例如，只有当接受方知道这篇文章信才能够工作。例如，只有当接受方知道这篇文章需要用英语字符解释的时候这篇文章才有意义。同需要用英语字符解释的时候这篇文章才有意义。同样，只有当接受方知道编码方法的时候他才能够理样，只有当接受方知道编码方法的时候他才能够理解压缩数据。一些压缩算法利

10、用了这个特性，在压解压缩数据。一些压缩算法利用了这个特性，在压缩过程中对数据进行加密，例如利用密码加密，以缩过程中对数据进行加密，例如利用密码加密，以保证只有得到授权的一方才能正确地得到数据。保证只有得到授权的一方才能正确地得到数据。11数据压缩数据压缩-概要概要数据压缩能够实现是因为多数现实世界的数据都有统计数据压缩能够实现是因为多数现实世界的数据都有统计冗余。例如，字母冗余。例如，字母“e”在英语中比字母在英语中比字母“z”更加常用，字更加常用，字母母“q”后面是后面是“z”的可能性非常小。无损压缩算法通常利用利用了的可能性非常小。无损压缩算法通常利用利用了统统计冗余，这样就能更加简练地、

11、但仍然是完整地表示发送方计冗余，这样就能更加简练地、但仍然是完整地表示发送方的数据。的数据。如果允许一定程度的保真度损失，那么还可以实现进一如果允许一定程度的保真度损失，那么还可以实现进一步的压缩。例如，人们看图画或者电视画面的时候可能并不步的压缩。例如，人们看图画或者电视画面的时候可能并不会注意到一些细节并不完善。同样，两个音频录音采样序列会注意到一些细节并不完善。同样，两个音频录音采样序列可能听起来一样，但实际上并不完全一样。有损压缩算法在可能听起来一样，但实际上并不完全一样。有损压缩算法在带来微小差别的情况下使用较少的位数表示图像、视频或者带来微小差别的情况下使用较少的位数表示图像、视频

12、或者音频。音频。12数据压缩数据压缩-概要概要由于可以帮助减少如硬盘空间与连接带宽这样由于可以帮助减少如硬盘空间与连接带宽这样的昂贵资源的消耗，所以压缩非常重要，然而压缩的昂贵资源的消耗，所以压缩非常重要，然而压缩需要消耗信息处理资源，这也可能是费用昂贵的。需要消耗信息处理资源，这也可能是费用昂贵的。所以数据压缩机制的设计需要在压缩能力、失真度、所以数据压缩机制的设计需要在压缩能力、失真度、所需计算资源以及其它需要考虑的不同因素之间进所需计算资源以及其它需要考虑的不同因素之间进行折衷。行折衷。一些机制是可逆的，这样就可以恢复原始的数一些机制是可逆的，这样就可以恢复原始的数据，这种机制称为无损数

13、据压缩；另外一些机制为据，这种机制称为无损数据压缩；另外一些机制为了实现更高的压缩率允许一定程度的数据损失，这了实现更高的压缩率允许一定程度的数据损失，这种机制称为有损数据压缩。种机制称为有损数据压缩。13数据压缩数据压缩-概要概要然而，经常有一些文件不能被无损数据压缩算法然而，经常有一些文件不能被无损数据压缩算法压缩，实际上对于不含可以辨别样式的数据任何压压缩，实际上对于不含可以辨别样式的数据任何压缩算法都不能压缩。试图压缩已经经过压缩的数据缩算法都不能压缩。试图压缩已经经过压缩的数据通常得到的结果实际上是扩展数据，试图压缩经过通常得到的结果实际上是扩展数据，试图压缩经过加密的数据通常也会得

14、到这种结果。加密的数据通常也会得到这种结果。实际上，有损数据压缩也会最终达到不能工作的实际上，有损数据压缩也会最终达到不能工作的地步。我们来举一个极端的例子，压缩算法每次去地步。我们来举一个极端的例子，压缩算法每次去掉文件最后一个字节，那么经过这个算法不断的压掉文件最后一个字节，那么经过这个算法不断的压缩直至文件变空，压缩算法将不能继续工作。缩直至文件变空，压缩算法将不能继续工作。14数据压缩数据压缩-应用应用一种非常简单的压缩方法是行程长度编码，这种一种非常简单的压缩方法是行程长度编码，这种方法使用数据及数据长度这样简单的编码代替同样方法使用数据及数据长度这样简单的编码代替同样的连续数据，这

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

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

17、量几乎没有降低。用于存储能力，同时图像质量几乎没有降低。用于DVD的的有损有损MPEG-2编解码视频压缩也实现了类似的功能。编解码视频压缩也实现了类似的功能。16数据压缩数据压缩-应用应用在有损音频压缩中，心理声学的方法用来去除信号在有损音频压缩中，心理声学的方法用来去除信号中听不见或者很难听见的成分。人类语音的压缩经常中听不见或者很难听见的成分。人类语音的压缩经常使用更加专业的技术，因此人们有时也将使用更加专业的技术，因此人们有时也将“语音压缩语音压缩”或者或者“语音编码语音编码”作为一个独立的研究领域与作为一个独立的研究领域与“音频音频压压缩缩”区分开来。不同的音频和语音压缩标准都属于音区

18、分开来。不同的音频和语音压缩标准都属于音频编解码范畴。例如语音压缩用于因特网电话，而音频编解码范畴。例如语音压缩用于因特网电话，而音频压缩被用于频压缩被用于CD翻录并且使用翻录并且使用MP3播放器解码。播放器解码。17数据压缩数据压缩-理论理论压缩的理论基础是信息论（它与算法信息论密切相压缩的理论基础是信息论（它与算法信息论密切相关）以及率失真理论，这个领域的研究工作主要是由关）以及率失真理论，这个领域的研究工作主要是由ClaudeShannon奠定的，他在二十世纪四十年代末奠定的，他在二十世纪四十年代末期及五十年代早期发表了这方面的基础性的论文。期及五十年代早期发表了这方面的基础性的论文。D

19、oyle和和Carlson在在2000年写道数据压缩年写道数据压缩“是所有是所有的的工程领域最简单、最优美的设计理论之一工程领域最简单、最优美的设计理论之一”。密码学。密码学与编码理论也是密切相关的学科，数据压缩的思想与与编码理论也是密切相关的学科，数据压缩的思想与统计推断也有很深的渊源。统计推断也有很深的渊源。18数据压缩数据压缩-理论理论许多无损数据压缩系统都可以看作是四步模型，有许多无损数据压缩系统都可以看作是四步模型，有损数据压缩系统通常包含更多的步骤，例如它包括预损数据压缩系统通常包含更多的步骤，例如它包括预测、频率变换以及量化。测、频率变换以及量化。Lempel-Ziv（LZ）压缩

20、方法是最流行的无损存储算）压缩方法是最流行的无损存储算法之一。法之一。DEFLATE是是LZ的一个变体，它针对解压的一个变体，它针对解压速度与压缩率进行了优化，虽然它的压缩速度可能非速度与压缩率进行了优化，虽然它的压缩速度可能非常缓慢，常缓慢，PKZIP、gzip以及以及PNG都在使用都在使用EFLATE。LZW（Lempel-Ziv-Welch）是）是Unisys的专利，直到的专利，直到2003年年6月专利到期限，这种方法用于月专利到期限，这种方法用于GIF图像。图像。19数据压缩数据压缩-理论理论另外值得一提的是另外值得一提的是LZR(LZ-Renau)方法，它是方法，它是Zip方法的基础

21、。方法的基础。LZR方法使用基于表格的压缩模方法使用基于表格的压缩模型，其中表格中的条目用重复的数据串替换。对于大型，其中表格中的条目用重复的数据串替换。对于大多数的多数的LZ方法来说，这个表格是从最初的输入数据方法来说，这个表格是从最初的输入数据动态生成的。这个表格经常采用霍夫曼编码维护（例动态生成的。这个表格经常采用霍夫曼编码维护（例如，如，SHRI、LZX）。）。目前一个性能良好基于目前一个性能良好基于LZ的的编码机制是编码机制是LZX，它用于微软公司的，它用于微软公司的CAB格式。格式。20数据压缩数据压缩-理论理论最好的压缩工具将概率模型预测结果用于算术编码。最好的压缩工具将概率模型

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

23、码器。是一个逆算术编码器。有效输入信息文本的界面有效输入信息文本的界面21数据压缩和信源编码数据压缩和信源编码3.1等长码等长码3.2变长编码变长编码3.3哈夫曼码哈夫曼码3.4算术码算术码香农香农-费诺码费诺码3.5通用信源编码通用信源编码LZW算法算法习题三习题三22数据压缩和信源编码数据压缩和信源编码信源编码定理信源编码定理（定理）（定理）设设X1，X2为无记忆信源，服从共同分为无记忆信源，服从共同分布布p(x)，则，则当码率当码率时，存在码率为时，存在码率为R的的编码，使得当编码，使得当n时时，误误差差码码率率Pe0.最优码的存在性最优码的存在性23数据压缩和信源编码数据压缩和信源编码

24、将信道编码和译码看成是信道的一部分，而突出信源编码；24数据压缩和信源编码数据压缩和信源编码通过信源编码，用尽可能少的信道符号来表达信源，即对信源数据用最有效的表达方式表达，尽可能减少编码后的数据的剩余度；25数据压缩和信源编码数据压缩和信源编码3.1等长码等长码3.2变长编码变长编码3.3哈夫曼码哈夫曼码3.4算术码算术码香农香农-费诺码费诺码3.5通用信源编码通用信源编码LZW算法算法习题三习题三26等长码等长码定义：设为信源字母表，=0,1,D-1为D进码元（码符号）集.映射f:nk (x1,xn)(u1,uk)等长编码；若k不唯一，则为变长编码.映射：k n称为相应的译码；称上述编码为

25、D元码.分分组组码码27等长码等长码定义（续）：f(xn)=uk称为码字，k为码长；R=k/nlogD称为f的编码速率，即码率；由f编出的所有码字的集合称为码字集：C=f(xn),xn n 若任一码字只能被唯一译成所对应的信源符号序列，称这类编码为唯一可译码.又称信源的信息率又称信源的信息率-信信源编码后平均每个码元载荷源编码后平均每个码元载荷的最大信息量的最大信息量28等长码等长码1.若进行二元等长编码，则码字长至少为2；从而：熵H(X)=1.75;码率R=k/nlogD=2H(X).29等长码等长码2.若进行二元不等长编码.变长编码的平均码长：L=p(i)l(i)=1.75;熵H(X)=1

26、.75;码率R=L/nlogD=H(X).30数据压缩和信源编码数据压缩和信源编码3.1等长码等长码3.2变长编码变长编码3.3哈夫曼码哈夫曼码3.4算术码算术码香农香农-费诺码费诺码3.5通用信源编码通用信源编码LZW算法算法习题三习题三31变长编码变长编码该编码的平均码长L=1.5=RH(X);是否说明该码更加实用呢？考查：对收到的码字序列001001译码？32变长编码变长编码必须要求编码是唯一可译的；这是变长码编码要满足的第一个要求！对于所编出的变长码，怎样才能说明它是否是唯一可译的？33变长编码变长编码定义：前缀前缀若一个码字与另一个码字的前面部分相同，则称其为另一码字的前缀；0，01

27、；01，01134变长编码变长编码定义：前缀前缀若一个码字与另一个码字的前面部分相同，则称其为另一码字的前缀；0，01；01，01135变长编码变长编码定义：前缀前缀若一个码字与另一个码字的前面部分相同，则称其为另一码字的前缀；0，01；01，011其中，较长码的剩余部分称为较短码的尾随后缀尾随后缀.36变长编码变长编码如何确定一个变长编码的所有尾随后缀？步骤：步骤：考查码C中最短码字是否是其它码字的前缀若是，列出所有的尾随后缀，再考查这些尾随后缀是否是其它码字的前缀；若不是，考查次长的码字.37变长编码变长编码哪些码是否为唯一可译码？若是请说明；否则，请构造一个有二义的码字序列.38变长编码

28、变长编码定义定义:若f 编出的码字集中，没有一个码字是其它码字的前缀，则称f 编出的码为即时码即时码.即时码一定是唯一可译码，反之不然！39作业作业P753)以及课堂练习.40变长编码变长编码码树图码树图即时码的树图构造法：即时码的树图构造法：给每个节点伸出的树枝从上向下标上码符号0，1，而只对终结点安排码字码字：从根出发到终结点走过的路径所对应的码符号组成；中间节点不安排码字.410001100101110111110变长编码变长编码0000001111111码树图码树图42用树的概念可导出即时码存在的条件，即各码字的用树的概念可导出即时码存在的条件，即各码字的长度长度li应符合克莱夫特不等

29、式：应符合克莱夫特不等式：定理定理克莱夫特（克莱夫特（Kraft，1949）不等式）不等式含含m个个码码字字，码码长长为为l1,l2,lm的的D进进码码是是一一个个即时码，则它满足即时码，则它满足Kraft不等式不等式反之，存在给定码长的即时码；反之，存在给定码长的即时码；变长编码变长编码该不等式对唯一可译码成立！该不等式对唯一可译码成立！43变长编码的平均码长：若信源，编码后的码子为，码长分别为，则平均码长为：变长编码变长编码它是传输信源符号平均需用的码元数！它是传输信源符号平均需用的码元数！编码效率编码效率-衡量各衡量各种编码的优劣种编码的优劣44变长信源编码问题就是求使得给定信源平均码长

30、最小的唯一可译的变长码.注注意意：Kraft不不等等式式是是一一个个存存在在定定理理，不不是唯一可译码的判定定理是唯一可译码的判定定理.存存在在长长度度满满足足Kraft不不等等式式的的码码不不是是即即时时码：码：变长编码变长编码最优码！最优码！45例例1 1：考虑二元码C=0,11,100,110，|D|=2.可以验证其码字长度1，2，3，3满足Kraft不等式；但不是即时码，因为它不是唯一可译码.变长编码变长编码46如何用如何用Kraft不等式的证明过程构造即时码不等式的证明过程构造即时码.例例2.令令U=0,1,2,且且 l1=l2=1，l3=2，l4=l5=4，l6=5.可以证明他们满

31、足可以证明他们满足Kraft不等式不等式；能够构造能够构造U上具有对应码字长度的即时上具有对应码字长度的即时 码：码：变长编码变长编码47由li的取值得到：(a1,a2,a3,a4,a5)=(2,1,0,2,1);任取任取a1个长度为个长度为1的码元：的码元：0，1；任取任取a2个长度为个长度为2，并且不以已经出现的码字为，并且不以已经出现的码字为前缀的码元：前缀的码元：20；任取任取a4个长度为个长度为4，的码元：的码元：2100，2101；任取任取a5个长度为个长度为5，的码元：的码元：21020.变长编码变长编码是即时码48在有些编码码选择中，我们会面临一些最优最优选择的问题。比如下面这

32、样的问题：我们要编码码字符串“7F-0505-12345678-1234567AB”，使得编码码结果序列最短。可使用的编码码方案已给定，有两种选择：每个数字或字符对应一个定长码码，比如1-1001100，F-1010100每两个连续数字可以对应一个定长码码。比如12-1001100，23-1101100注意，给定的编码码方案里，上面两种情况下定长码码均等长(例子中为长度为7)。这里，我们看到，如果要编码码结果序列最短。就需要尽量多的使用第二个方案。变长编码变长编码49这里有两种极限情况：比如ABECDDDEFG.FHE这样的字串只能按第一种方案进行,因为它没有连续数字出现.比如12342353

33、45.32这样的字串,如果有偶数个数字的话,我们完全可以按第二种方案进行.那么既有字符,又有数字的情况,就有一个选择的问题,所以这里的问题就是我们如何识别可以使用第二个方案的字串。变长编码变长编码50作者fineamy变长编码变长编码51变长信源编码问题就是求使得给定信源平均码长最小的唯一可译的变长码.但但是是满满足足Kraft不不等等式式的的码码长长集集未未必必是是最优的，即其平均码长未必是最小的！最优的，即其平均码长未必是最小的！变长编码变长编码52定理定理（最优码码长的下界估计）：随机变量X的任何D进即时码的平均码长L应满足，变长编码变长编码等号成立的充要条件等号成立的充要条件53证明：

34、证明：记记如果如果C是即时码，则根据是即时码，则根据Kraft不等式，有不等式，有变长编码变长编码54定义定义3.2.3相对冗余度相对冗余度作业：作业：P751)变长编码变长编码55定理定理（最优码码长的下界估计）：随机变量X的任何D进即时码的平均码长L应满足，变长编码变长编码等号成立的充要条件等号成立的充要条件对于出现概率大的信息符号，编以短字长的码对于出现概率大的信息符号，编以短字长的码,对于出现对于出现概率小的信息符号编以长字长的码，如果码字长度严格按概率小的信息符号编以长字长的码，如果码字长度严格按照符号概率的大小的相反顺序排列，则平均码字长一定小照符号概率的大小的相反顺序排列，则平均

35、码字长一定小于按任何其他符号顺序排列方式得到的码字长度。于按任何其他符号顺序排列方式得到的码字长度。56某地的A同学要给另外一方B同学传递信息,信息必须以二进制编码码(即01编码码)的方式传递.假设A传递给B的所有字符只有a,b,c,d四个,且不包含空格.一种显而易见的编码码方法是:a-00;b-01;c-10;d-11;这样保证不会产生翻译错误的情况发生,而平均每个字符需要2个Bit的带宽.然而这种方法不是最优最优的;借助统计规律,就可以构造出保证不会产生错误,然而却能更省带宽的编码码方式:变长编码变长编码57给出一个例子:假设P(x=a)=1/2;P(x=b)=1/4;P(x=c)=1/8

36、;P(x=d)=1/8;即对大量的信息作出统计后,发现a出现的频率最高,平均每两个字符中就出现一个a;b其次;c,d再次之.如此对a的编码码进行缩水处理:a-1;b-01;c-001;d-000;这样仍然能保证不会译错,而且,平均每个字符需要1*1/2+2*1/4+3*1/8+3*1/8=7/4=1.75Bit这样就节省了宝贵的0.25Bit上述的编码码方式称为Huffman编码码变长编码变长编码58数据压缩和信源编码数据压缩和信源编码3.1等长码等长码3.2变长编码变长编码3.3哈夫曼码哈夫曼码3.4算术码算术码香农香农-费诺码费诺码3.5通用信源编码通用信源编码LZW算法算法习题三习题三5

37、9数据压缩和信源编码数据压缩和信源编码哈夫曼编码哈夫曼编码/译码器。设计一个哈夫曼编码译码器。设计一个哈夫曼编码/译译码器程序，对一个文本文件中的字符进行哈夫曼码器程序，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件，后缀编码，生成编码文件（压缩文件，后缀.cod）；）；反过来，可将一个压缩文件译码还原为一个文本反过来，可将一个压缩文件译码还原为一个文本文件文件(.txt)。http60数据压缩和信源编码数据压缩和信源编码步骤：步骤：（1）输入一个待压缩的文本文件名，统计文本）输入一个待压缩的文本文件名，统计文本文件中各字符的个数作为权值，生成哈夫曼树；文件中各字符的个数作为权值

38、，生成哈夫曼树；（2）将文本文件利用哈夫曼树进行编码，生成）将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名压缩文件（后缀名cod）（3）输入一个待解压的压缩文件名称）输入一个待解压的压缩文件名称,并利用相并利用相应的哈夫曼树将编码序列译码；应的哈夫曼树将编码序列译码；（4）显示指定的压缩文件和文本文件的内容。）显示指定的压缩文件和文本文件的内容。61数据压缩和信源编码数据压缩和信源编码哈夫曼编码哈夫曼编码(HuffmanCoding)是可变长编码是可变长编码(VLC)的一种。的一种。Huffman于于1952年提出一种编码方法，该方法完全依据年提出一种编码方法，该方法完全依据字符出现概率

39、来构造异字头的平均长字符出现概率来构造异字头的平均长度最短的码字，有度最短的码字，有时称之为最佳编码时称之为最佳编码在计算机信息处理中，在计算机信息处理中，“哈夫曼编码哈夫曼编码”是一种一致性编是一种一致性编码法（又称码法（又称熵编码法熵编码法），用于数据的无损耗压缩。这），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率

40、高的字符使用较短的编码，反之出现概率的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。均期望长度降低，从而达到无损压缩数据的目的）。62数据压缩和信源编码数据压缩和信源编码例如，在英文中，例如，在英文中，e的出现概率很高，而的出现概率很高，而z的出现概率则的出现概率则最低。最低。当利用哈夫曼编码对一篇英文进行压缩时，当利用哈夫曼编码对一篇英文进行压缩时，e极有可能极有可能用一个位用一个位(bit)来表示，而来表示，而z则可能花去则可能花去25个位（不是个位

41、（不是26）。用普通的表示方法时，每个英文字母均占用一个）。用普通的表示方法时，每个英文字母均占用一个字节（字节（byte），即），即8个位。个位。二者相比，二者相比，e使用了一般编码的使用了一般编码的1/8的长度，的长度，z则使用了则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。较准确的估算，就可以大幅度提高无损压缩的比例。63数据压缩和信源编码数据压缩和信源编码哈夫曼压缩是个无损的压缩算法，一般用来压哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长缩文本

42、和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。，而那些很少出现的符号，则用较长的位序列。作者：著述的鸭子非了作者：著述的鸭子非了压缩压缩1M数据少于数据少于100ms（P3处理器，主频处理器，主频1G）。）。64一、二进制哈夫曼编码二进制哈夫曼编码1.步骤步骤(1)信源符号按概率分布大小，以递减次序排列；(2)取两

43、个最小的概率，分别赋以“0”,“1”;然后把这两个概率值相加，作为新概率值与其他概率重新排序(3)按重排概率值，重复(2),直到概率和达到1为止(4)由后向前由后向前排列码序，即得哈夫曼编码哈夫曼哈夫曼（Huffman）码码652.例题例题x10.4 x20.2 x30.2 x40.1 x50.1平均码长码方差12=E(li-L)2=p(xi)(li-L)2=1.360.20.40.61.001010101X:p(x)(0.4,0.2,0.2,0.1,0.1)（合并后概率下放合并后概率下放）哈夫曼哈夫曼（Huffman）码码0110000010001166方法一：合并后的新符号排在其它相同概率

44、符号的后面；哈夫曼哈夫曼（Huffman）码码673.上例上例00 x10.410 x20.211x30.2010 x40.1011x50.1010.20.40.61.0010101（合并后概率上放）（合并后概率上放）哈夫曼哈夫曼（Huffman）码码683.上例上例00 x10.410 x20.211x30.2010 x40.1011x50.1平均码长结论码方差22=0.16两法平均码长相同，故信息率R、冗余度相同；但码方差不同，码方差小要好.010.20.40.61.0010101（合并后概率上放）（合并后概率上放）哈夫曼哈夫曼（Huffman）码码69方法二：合并后的新符号排在其它相同概

45、率符号的前面.哈夫曼哈夫曼（Huffman）码码70两种编码的平均码长是一样的，都是2.2，那一种更好呢，我们可以计算一下平均码长的方差。定义码字长度的方差2：哈夫曼哈夫曼（Huffman）码码71n可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。l第一种方法编出的5个码字有4种不同的码长；l第二种方法编出的码长只有两种不同的码长；l显然，第二种编码方法更简单、更容易实现，所以更好。结论结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到

46、充分利用。哈夫曼哈夫曼（Huffman）码码723.上例上例00 x10.410 x20.211x30.2010 x40.1011x50.1平均码长 结论结论 码方差22=0.16两法平均码长相同，故信息率R、冗余度相同；但码方差不同，码方差小要好.010.20.40.61.0010101（合并后概率上放）（合并后概率上放）哈夫曼哈夫曼（Huffman）码码73定理：定理：在变长编码中，若各码字长度严格按照所对应符号出现概率的大小逆序排列，则其平均长度为最小。结论结论：霍夫曼编码方法，它完全依据字符出现概率来构造平均长度最短的异字头码字，有时称之为最佳编码。哈夫曼哈夫曼（Huffman）码码7

47、4应该指出的是，由霍夫曼编码过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。此外，由于码长不等，还存在一个输入与输出的速率匹配问题。解决的办法是设置一定容量的缓冲寄存器。而随着微电子与计算技术的发展，霍夫曼编码已可做成单片IC，并成为许多国际标准中的主要技术内核之一。能够用较低的处理代价，来换取昂贵的通信开销，是完全值得的。哈夫曼哈夫曼（Huffman）码码方差最小者最佳方差最小者最佳75应该指出的是，由霍夫曼编码过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。此外，由于码长不等，还存在一个输入与输出的速率匹配问题。解决的办法

48、是设置一定容量的缓冲寄存器。而随着微电子与计算技术的发展，霍夫曼编码已可做成单片IC，并成为许多国际标准中的主要技术内核之一。能够用较低的处理代价，来换取昂贵的通信开销，是完全值得的。哈夫曼哈夫曼（Huffman）码码方差最小者最佳方差最小者最佳760.60010.090.130.190.230.371.00101010101010100 x50.070101x60.0600010 x70.0500011x80.04011x30.10000 x40.1001x20.181x10.4010010110101010000000001000011哈夫曼哈夫曼（Huffman）码码4.4.例题例题X:

49、p(x)(0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04)77二、二、D进制哈夫曼编码进制哈夫曼编码1.编码步骤同二进制，但需注意两点：每次取最小的D个概率,分别赋以0,1,D-1；信源符号个数r必须满足：r=(D-1)+D.当r不满足时，在信源符号集中补充一些对应概率为0的符号.哈夫曼哈夫曼（Huffman）码码782.例题例题某离散无记忆信源符号集某离散无记忆信源符号集a1,a2,a3,a4,a5,a6,a7,a8，已知所对应的概率，已知所对应的概率，试对其进行四元编码！试对其进行四元编码！哈夫曼哈夫曼（Huffman）码码有误！有误！79解：其中D=4.若取=2

50、可得大于9但与9最接近的正整数10，因此在编码是加入一个零概率符号.对其进行四元编码：哈夫曼哈夫曼（Huffman）码码80哈夫曼哈夫曼（Huffman）码码81哈夫曼码考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；哈夫曼码的编码方法都不惟一；哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，因此综合性较优.哈夫曼哈夫曼（Huffman）码码82Huffman码在具体实用时，设备较复杂码在具体实用时，设备较复杂.在编在编码器中需要增加缓冲寄存器，因为每个信源符码器中需要增加缓冲寄存器，因为每个信源符号所对应的码符号长度不一，负责会造