数据压缩第三章统计编码.ppt

第三章 统计编码;数据压缩的类型可逆的无失真编码;对于计算机文件逻辑压缩(Log;1基本原理2霍夫曼编码 3游程;唯一可译码的构造4.1 基本原;计算机文件字符集合(如文本);;文件的冗余度类型本节所指的冗余;冗余类型 字符分布(Cha;高使用率模式(High-usa;图3.1 一份零件报表中的;编码器的数字描述X ={x1,;例3-1X ={x1, x2 ;编码，就是将不同的消息用 不同;变长码的基本分析对一个消息集合;平均码长：对P(aj)大的aj;1843年，莫尔斯电报码：字母;莫尔斯码的形成: 首先找到;[定义 3-1]若W 中任一有;例3-2考虑以下几种变长码：信;100111011010(10;⑥ 码F 即使从尾开始判断, ;唯一可译码的存在目前还没有一个;Kraft不等式：只涉及唯一可;码A码B码C码D码E码F ;问题: 如何来确定码字长度;当m=2，有(二进制编码定理);例3-4例3.2信源的的熵为:;唯一可译码的构造唯一可译码的基;若W 中任一码字都不是另一个码;例3.2中:信源字母概率码A码;不过非异字头码也并非一定不是唯;异字头性质只是码字可分离的充分;二进制编码通常可用二进码树(二;用码树表述任何一个代码W, 异;此时码C为用尽的异字头码, 有;按照Kraft 不等式的要求，;结论：任一唯一可译码，总可以用;3.2 霍夫曼编码1952年 ;霍夫曼码的构造理论基础[定理3;例3-6对一个7符号信源A={;编码步骤：① 将信源符号概率按;011a3根１１１１０００００;例3-6的信源熵为:霍夫曼编码;注意：在哈夫曼编码过程中，对缩;Huffman编码和译码过程编;信源编码基本定理霍夫曼编码变长;例3-7:对于二值图像，如传真;解决办法:定理3.4(信源编码;含义：如果我们把 X 延长后再;例3-8:利用最佳编码, 以例;W 2平均长度为:l2 =0.;把 X 延长到 X 3 ，有;W 3平均长度为:l3 =0.;进一步减小 l/K , 利用信;信源编码理论：① 给定消息单元;霍夫曼编码选择模型静态统计模型;缺点 ： 对数据量较大的信息;一种有效的“静态统计模型”的替;这种方案除了适应性不太强以外，;对英文或中文文本，有一种比较实;自适应模型无需为解压缩预先保存;算术编码、字典编码等更为适合采;霍夫曼码的局限性霍夫曼编码文本;局限性:① 输入符号数受限于可;3.3 游程编码游程长度(;游程编码类型：变长游程编码使用;基本的游程编码基本的RLC压缩;其中X ： 代表数据字符；;Assumption:Long;RLC压缩效能:取决于数据流中;二值图像的游程编码二值图像仅有;二值图像的游程编码数据字符 X;二值图像的RLC的两种方式 ;编码过程： 先对图像进行统;由于各种 RL 的出现概率在;MH编码规则: (见表4.7;游程编码的局限性 对二值图;连续色调图像的二维编码前面介绍;连续色调图像的二维编码求出差分;连续色调图像的二维编码二维编码;连续色调图像的二维编码例题：设;连续色调图像的二维编码例题：设;游程编码总结游程编码RCL是一;3.4 算术编码(Arithm;算术编码定义它是一种非分组编码;3.4.1 多元符号算术编码1;3.4.1多元符号算术编码当处;3.4.1多元符号算术编码例题;3.4.1多元符号算术编码编码;3.4.1多元符号算术编码编码;3.4.1多元符号算术编码最后;3.4.1多元符号算术编码编码;3.4.1多元符号算术编码二、;为了从码字中消除符号x的影响，;3.4.2二进制算术编码一、基;*;例题1:设输入信源为11011;2) 1 为;头 0.0101尾 ;算术编码原理图*;二进制解码：按 Qe Pe分成;1） C’=0.0101 ;算术解码原理图*;3.4.4 算术编码评价算术编;3.5 基于字典的编码以Huf;3.5.1 LZ算法 19;LZ77算法 LZ77 算法又;LZ77 算法的基本流程 重复;假设窗口的大小为 10 个字???;现在将窗口向后滑动3(2+1);又将窗口向后滑动 1 个字符，;a b c d b b c c;LZ77 算法的解压缩LZ77;LZ78算法 LZ78算法的基;如对符号串“ababcbaba;LZ78算法的框架 void ;LZW算法 LZ78算法很难一;LZW算法的框架void LZ;对于字符串“ababcbaaa;LZW解压缩算法void un;压缩码为： {1, 2, 4;压缩码为： {1, 2, 4;压缩码为： {1, 2, 4;例4-15设有输入字符流“ab;习题与思考题 习题：4.2思考