数据压缩第3章统计编码.ppt
《数据压缩第3章统计编码.ppt》由会员分享,可在线阅读,更多相关《数据压缩第3章统计编码.ppt(125页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第三章第三章 统计编码统计编码数据压缩的类型可逆的无失真编码可逆的无失真编码不可逆的有失真编码不可逆的有失真编码大多数计算机文件不允许在压缩过程中丢失信息。大多数计算机文件不允许在压缩过程中丢失信息。利用消息或消息序列出现概率的分布特性,注重寻找概率与利用消息或消息序列出现概率的分布特性,注重寻找概率与码字长度间的最优匹配。码字长度间的最优匹配。语音、图像或其他物理过程的量化采样。语音、图像或其他物理过程的量化采样。本章讨论的内容对于计算机文件对于计算机文件逻辑压缩逻辑压缩(Logical Compression)物理压缩物理压缩(Physical Compression)由数据自身特点及设计
2、者技巧来决定的由数据自身特点及设计者技巧来决定的“压缩表示法压缩表示法”,这种技巧在数据库的数据结构设计中特别有效。,这种技巧在数据库的数据结构设计中特别有效。减少计算机文件内部冗余度的统计编码方法。减少计算机文件内部冗余度的统计编码方法。本章讨论的内容1基本原理基本原理2霍夫曼编码霍夫曼编码 3游程编码游程编码 4算术编码算术编码 本章内容本章内容5基于字典的编码基于字典的编码 唯一可译码的构造4.14.1 基本原理基本原理 文件的冗余类型 编码器的数字描述 变长码的基本分析 唯一可译码的存在计算机文件字符集合(如文本);二进制符号集合(如数据);压缩必须“透明”,恢复后的文件不允许有任何失
3、真。文件的冗余度类型本节所指的冗余度,专指对数据解释一无所知时由数据流中即可观察到的,与具体应用背景无关的冗余。了解文件的冗余度,意在考虑有针对性的编码方法。冗余类型 字符分布(Character Distribution)字符重复(Character Repetition)在典型的字符串中,某些符号要比其他符号出现的更频繁,在一份具体的文件中字符不会以等概率出现,字符的分布明显地因文件而异,影响到字符的统计特性。对于字符重复所形成的符号串常常有更紧凑的编码方式,例如:格式化文件中的空白、报表中的空格串和零串、业务图表中的线图包含成片的空白等。高使用率模式(High-usage Pattern
4、s)位置冗余(Positional Redundancy)这四类冗余度之间有重叠某些符号序列会以较高的频率反复出现,可用较少的位数表示,从而得到时间和空间的净节约。若某些字符总是在各数据块中可预见的位置上出现,那么这些字符至少是部分冗余的,例如:光栅扫描图像中含有的竖线、报表文件中的某些字段的记录几乎总是相同的等等。图3.1 一份零件报表中的冗余度的类型零件名:HEX NUT 1/4 20说 明:STEEL,STANDARD THREAD颜色码:仓 库:45th STREET货 位:4R9存货量:0020再进货量:0010文字长度可变,字母分布不同;空字段同样的名字在文件中多次出现;数值字段,
5、有限的字符变化;编码器的数字描述X=x1,xnW=w1,wnA=a1,am编码器图3.2 编码器的描述实际信源的编码过程 消息集X:元素 x 叫做信号单元或消息;输出集W(代码、码组或码书):元素 w叫做码字;码字的符号集A:元素 a 叫做码元或者符号 以符号 A 构建代码 W;建立 XW 对应关系;编码过程例3-1X=x1,x2,x3,A=0,1,W=w1,w2,w3A2=00,01,10,11假设用构成代码W,W 到 A2 的映射关系为 (完成步骤):R1=(w1,01),(w2,10),(w3,11)R2=(x1,w1),(x2,w2),(x3,w3)建立X 与 W 的映射关系为 (完成
6、步骤):若xi(dk,dk+1,1in,0kJ-1,为一模拟信号,该编码器实际就是一个量化器。编码,就是将不同的消息用 不同的码字来代替,或称为从消息集到码字集的一种映射(分组编码或块码的概念)。码长:组成码字的符号个数,Li=2,1i3,等长(或定长)编码:采用相同长度的不同码字去 代表一个消息集合中的不同消息;M元编码(或M进制):取M个不同字符来组成码字,最常用的有二元编码(或二进制)。变长码的基本分析对一个消息集合中的不同消息,采用不同长度的码字表示。不等长(或变长)编码:采用变长码可以提高编码效率,即对相同的信息量所需的平均编码长度可以短一些。平均码长:对对P(aj)大的大的aj 用
7、短码用短码;对对P(aj)小的小的aj 用长码用长码;当这些信息符号互不相关时当这些信息符号互不相关时,平均码长比等长编码的码长短平均码长比等长编码的码长短1843年,莫尔斯电报码:表3.1莫尔斯码莫尔斯码的形成:首先找到各消息符号的统计特性:再根据各符号出现的概率分布分 配不同长度的码字:变长码在编码时要预先知道各种信息符号出现的概率,解码也远比等长码复杂:正确识别码字起点不容易;存在唯一可译性问题;译码实时性问题;匀速输入输出匹配的缓存问题;定义定义 3-1若W 中任一有限长的码字序列(即有限长的一串W),可唯一地分割成一个一个码字,称为单义可译或唯一可译的,W 也叫做单义代码。单义可译码
8、例3-2考虑以下几种变长码:码A不是一一对应;码B是一一对应,但构成的序列不能被唯一分割;01110(0,1,1,1,0)(0,1,11,0)(0,11,1,0)(0,111,0)100111011010(10,0,111,0,110,10)码C是唯一可译的;码D是在码B各码字(除了w1)之前加一个码元“0”,成为唯一可译的,但平均码长增加0.5bit;码F 即使从尾开始判断,也不是唯一可译的;101111010(10,111,10,10)(101,111,0,10)问题:什么样的码才是唯一可译的?码E的译码要求等到收到全部序列,才能从尾开始进行判决,产生了时间上延时和存储容量的增加;0111
9、111 111(a1 1111)(a2111)(a311)唯一可译码的存在目前还没有一个明确的判断唯一可译码的准则,只有一个判断不是唯一可译码的准则。定理 3.1(Kraft不等式)长度为L1,L2,Ln 的 m 进制唯一可译码存在的充分必要条件是:含义:要求 Li 比较大(码长不能过短),意味着码字可能的组合数多,不为别的码字的字首。(3.1-1)Kraft不等式:只涉及唯一可译码的存在问题而并不涉及具体的码。可用来判定某一组码不是唯一可译的,但不能判定是唯一可译的。不满足Kraft不等式的码肯定不是唯一可译码,而满足的也不一定就是唯一可译的,但可以肯定若按这样的Li 分配码组,则必存在有一
10、个唯一可译码(也可能不止一个)对应于信源符号。例3-3对于例3-2问题:如何来确定码字长度?如何在确定了码字长度后找出唯一可译码?定理 3.2(按符号)变长编码定理)对于符号熵为H(X)的离散无记忆信源进行m 进制不等长编码,一定存在一种无失真编码方法,其码字平均长度 l 满足:(3.1-2)小于上限的单义代码总是存在的。当m=2,有(二进制编码定理):此时l 叫编码速率,有时又叫比特率。对于m进制的不等长编码的编码速率定义为:(3.1-4)(3.1-3)定理3.2改述为:若H(X)R H(X)+,就存在唯一可译的变长码;若R 1.75 码长的一种设计为:L1=1,L2=2,L3=L4=3满足
11、上述码长设计的码如:例3.2中的码C、E、F(满足Kraft不等式)。如何做出具体的变长码是变长码的构造问题。唯一可译码的构造唯一可译码的基本要求:码字非续长对码字序列能做出唯一正确的分割。充分条件若W 中任一码字都不是另一个码字的字头;或换句话说,任一码字都不是由另一个码字加上若干个码元所构成,则W 就叫作非续长码字或异字头码(Prefix Condition Code)。定义 3-2码字非续长例3.2中:码A、码B、码D、码E和码F都含有续长码,或同字头码;码C是异字头码。不过非异字头码也并非一定不是唯一可译,码D和码E就唯一可译;码D:各码组靠“逗号”(码元0)分开;码E:为码C的“镜像
12、”,具有“异后尾”,从 后向前即具有唯一可译性。异字头条件保证译出的码字是唯一的且具有“即时性”,减少了译码延时。异字头性质只是码字可分离的充分条件,非续长码也只是单义可译代码集合的一个子集。单义可译码非续长码图3.3 单义可译码与非续长码二进制编码通常可用二进码树(二叉树)来表示各码字的构成(根)(节点)图3.4 二进码树C(节点)D(节点)串接的最大枝数为树的节数,图3.4的节数为3。用码树表述任何一个代码W,异字头条件就成为:W中所有的码字 wi 均只对应地配置在终端节点上。图3.5 码C的树结构(异字头码)根001110010110111根011100(011)(111)11(0)(0
13、1)码E的树结构(非异字头码)此时码C为用尽的异字头码,有:倘若有一码字为(0,10,110),则该码为非用尽的异字头码,有:按照Kraft 不等式的要求,对n个消息x1,x2,xn分配了编码长度L1,L2,Ln,即可用二进码树来生成异字头码,生成规律是:从根出发开始生出2枝;每一枝用一个码元aj A=0,1来表示;枝尽节来,节外生枝;在第Li级端节点(Li级节点共有2Li个)上,配置信 号单元 xi,i=1,2,n;从根开始直奔对应的端节点,沿途(联枝)所遇到 的码元 aj 所构成的符号,即为对应于该信号单元 xi 的码字 wi。异字头码无译码延时,构造简单。结论:任一唯一可译码,总可以用与
14、各相应码字长度一样的异字头码代替。异字头码虽然只是唯一可译码的一种,但它具有代表性和普遍意义,在信息保持编码中广泛应用。长度为L1,L2,Ln的M进制异字头码存在的充要条件,也使Kraft不等式成立。3.2 霍夫曼编码1952年,霍夫曼(D.A.Huffman)提出霍夫曼编码,又称最佳编码根据字符出现概率来构造平均长度最短的异字头码字。霍夫曼码的构造理论基础定理3.3在变长编码中,若码字长度严格按照所对应符号出现概率的大小逆序排列,则其平均长度最短。例3-6对一个7符号信源A=a1,a2,a7,求其霍夫曼编码信源符号 出现概率 a1 0.20 a2 0.19 a3 0.18 a4 0.17 a
15、5 0.15 a6 0.10 a7 0.01 码长 码 字 2 11 2 10 3 011 3 010 3 001 4 0001 4 00000.26010.11010.35010.390110.61101.000编码步骤:将信源符号概率按递减顺序排列将信源符号概率按递减顺序排列;将两个最小的概率进行相加,并继续这一步骤,直到概率将两个最小的概率进行相加,并继续这一步骤,直到概率 达到达到1.0为止为止;在每对组合中的上部指定为在每对组合中的上部指定为1(或或0),下部指定为下部指定为0(或或1);画出每个信源符号概率到画出每个信源符号概率到1.0处的路径处的路径,记下沿路径的记下沿路径的1和
16、和0;对于每个信源符号都写出对于每个信源符号都写出1 1、0 0序列,则序列,则从右到左从右到左就得到霍就得到霍 夫曼编码。夫曼编码。011a3根例3-6的Huffman二进码树11a110a2010a4001a50001a60000a7例3-6的信源熵为:霍夫曼编码的平均字长为:编码效率:注意:在哈夫曼编码过程中,对缩减信源符号按概率注意:在哈夫曼编码过程中,对缩减信源符号按概率由大到小的顺序重新排列时,由大到小的顺序重新排列时,应使应使合并后的新符号尽合并后的新符号尽可能排在靠前的位置可能排在靠前的位置,这样可使合并后的新符号重复,这样可使合并后的新符号重复编码次数减少,使短码得到充分利用
17、编码次数减少,使短码得到充分利用。Huffman编码和译码过程编码和译码过程编码输出Huffman码流Huffman码表传输接收的Huffman码流缓冲器信源符号序列解码解码后的字符序列Huffman码表 信源编码基本定理霍夫曼编码变长的代码(只能分配接近log2pj的整数长码字)定长的数据段当信源符号的概率 pj=2-k编码效率等于100%例3-7:对于二值图像,如传真机文件,输出非“黑”即“白”,有:X=x1,x2=白,黑,其概率与所传文件有关,假设对某页文件,有P(x1)=0.9,P(x2)=0.1。不考虑信号间的关联时,其信息熵为:此时W=0,1,无论用定长码还是最佳编码,平均码长至少
18、为l1=1(bit);此时霍夫曼编码无压缩作用编码效率为1=H(X)/l1=46.9%解决办法:定理3.4(信源编码定理):A=a1,am;X K -X=x1,xn 的延长;W K-W=w1,wn 的延长,其平均长度为lK;P(wi)=P(xi),P(W)=P(wi),i=1,2,n;如果要求W K 为单义代码,则:(3.2-1)式(3.2-1)也叫做无失真编码的基本定理。含义:如果我们把 X 延长后再对 K 元组(K 为延长长度)进行编码,那么不必利用数据前后的关联,只要K 足够大,则代表每消息单元 X 的平均符号个数l/K 可以任意趋向于下限。例3-8:利用最佳编码,以例4-7来说明l/K
19、趋向于下限的情况。把 X 延长到 X 2 ,假定信源是离散无记忆信源,有图3.7所示 X 2 的最佳编码:图3.7 2单元延长信号的最佳编码P(x1,x1)=P(x1)P(x1)=0.81P(x1,x2)=P(x1)P(x2)=0.09P(x2,x1)=P(x2)P(x1)=0.09P(x2,x2)=P(x2)P(x2)=0.010.100.191.00111000W 2 010110111W 2平均长度为:l2=0.81+0.092+0.093+0.013=1.29 bit/pelW 2的每一个元素代表两个消息单元,因此平均每一个消息单元的符号个数是:l2/2=1.29/2=0.645 bi
20、t/pel2=H(X)/(l2/2)=72.7%编码效率提高到:把 X 延长到 X 3 ,有图3.8所示 X 3 的最佳编码:图3.8 3单元延长信号的最佳编码P(x1,x1,x1)=0.729P(x1,x1,x2)=0.081P(x1,x2,x1)=0.081P(x2,x1,x1)=0.0810.0100.109111000P(x1,x2,x2)=0.009P(x2,x1,x2)=0.009P(x2,x2,x1)=0.009P(x2,x2,x2)=0.0010.0180.0280.1620.2711.0000111001W 3111111111011101110101100011100W 3
21、平均长度为:l3=0.729+0.08133+5(30.09+0.001)=1.598 bit/pelW 3的每一个元素代表三个消息单元,因此平均每一个消息单元的符号个数是:l3/3=1.598/3=0.5327 bit/pel3=H(X)/(l3/3)=88.0%编码效率提高到:继续下去,就可使 lK/K 0.469,或=100%进一步减小 l/K,利用信号的前后关联减小下限,即利用:H(X,Y)H(X)+H(Y)H(X|Y)H(X)或:可以减小下限,从而减小l/K要求知道P(X),P(X,Y)或 P(X|Y)才能进行最佳编码。如果信号继续有关联可供利用,继续延长,会使下限变得很小。信源编码
22、理论:给定消息单元集合X、符号集合A和X的概率分布P(X),可以采用最佳编码,使代码W 的平均长度满足;如果把X 延长至 X K,则不必考虑信号前后的关联性,就可以是代表一个消息单元的符号个数 l/K 任意接近 下限 H(X)/logm;如果利用延长信号X K的前后关联,可使下限减小。具体实现时,如果将信号延长得过长,会使实际设备复杂到不合理的程度。霍夫曼编码选择模型静态统计模型 在编码前统计要编码的信息中所有字符的出现概率,然后根据统计出的信息建立编码树,进行编码。缺点:对数据量较大的信息,静态统计要消耗大量的时间;必须保存统计出的结果以便解码时构造相同的编码树,或者直接保存编码树本身,而且
23、,对于每次静态统计,都有不同的结果,必须分别予以保存,这要消耗大量的空间(这意味着压缩效率的下降);静态统计模型统计出的频率是字符在整个文件中的出现频率,往往反映不出字符在文件中不同局部出现频率的变化情况,使用这一频率进行压缩,大多数情况下得不到太好压缩效果,文件有时甚至在压缩后反而增大了。一种有效的“静态统计模型”的替代方案 如果要压缩的所有信息在分布上存在着共同的特征,使用语言学家事先已经建立好的字母频率表来进行压缩和解压缩,不但不用保存多份统计信息,而且一般说来对该类文件有着较好的压缩效果。比如我们要压缩的是普通的英文文本,那么,字母 a 或者字母 e 的出现频率应当是大致稳定的。这种方
24、案除了适应性不太强以外,偶尔还会有一些尴尬的时候。缺点:If Youth,throughout all history,had a champion to stand up for it;to show a doubting world that a child can think;and,possibly,do it practically;you wouldnt constantly run across folks today who claim that a child dont know anything.-Gadsby by E.V.Wright,1939.发现什么问题了吗?整段话
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据压缩 统计 编码
限制150内