《第4章_统计编码_1讲义》由会员分享，可在线阅读，更多相关《第4章_统计编码_1讲义（83页珍藏版）》请在金锄头文库上搜索。
1、第四章 统计编码,数据压缩的类型,可逆的无失真编码,不可逆的有失真编码,大多数计算机文件不允许在压缩过程中丢失信息。 利用消息或消息序列出现概率的分布特性，注重寻找概率与码字长度间的最优匹配。,语音、图像或其他物理过程的量化采样。,本章讨论的内容,对于计算机文件,逻辑压缩(Logical Compression),物理压缩(Physical Compression),由数据自身特点及设计者技巧来决定的 “压缩表示法”，这种技巧在数据库的数据结构设计中特别有效。,减少计算机文件内部冗余度的统计编码方法。,本章讨论的内容,1,基本原理,2,霍夫曼编码,3,游程编码,4,算术编码,本章内容,5,基于
2、字典的编码,唯一可译码的构造,4.1 基本原理,编码器的数字描述,变长码的基本分析,唯一可译码的存在,压缩必须“透明”，恢复后的文件不允许有任何失真。,文件的冗余度类型,本节所指的冗余度，专指对数据解释一无所知时由数据流中即可观察到的，与具体应用背景无关的冗余。,了解文件的冗余度，意在考虑有针对性的编码方法。,冗余类型,字符分布(Character Distribution),字符重复(Character Repetition),在典型的字符串中，某些符号要比其他符号出现的更频繁，在一份具体的文件中字符不会以等概率出现，字符的分布明显地因文件而异，影响到字符的统计特性。,对于字符重复所形成的符
3、号串常常有更紧凑的编码方式，例如：格式化文件中的空白、报表中的空格串和零串、业务图表中的线图包含成片的空白等。,高使用率模式(High-usage Patterns),位置冗余(Positional Redundancy),这四类冗余度之间有重叠,某些符号序列会以较高的频率反复出现，可用较少的位数表示，从而得到时间和空间的净节约。,若某些字符总是在各数据块中可预见的位置上出现，那么这些字符至少是部分冗余的 ，例如：光栅扫描图像中含有的竖线、报表文件中的某些字段的记录几乎总是相同的等等。,图4.1 一份零件报表中的冗余度的类型,编码器的数字描述,实际信源的编码过程,消息集X：元素 x 叫做信号单
4、元或消息；,输出集W (代码、码组或码书)：元素 w叫做码字；,码字的符号集A：元素 a 叫做码元或者符号, 以符号 A 构建代码 W ; 建立 XW 对应关系;,编码过程,例4-1,X =x1, x2 , x3, A =0, 1, W =w1, w2, w3,A2 =00, 01, 10, 11,假设用,构成代码W , W 到 A2 的映射关系为 (完成步骤):,R1 = (w1,01), (w2,10), (w3,11),R2 =(x1 ,w1), (x2 ,w2), (x3 ,w3),建立X 与 W 的映射关系为 (完成步骤):,若xi(dk,dk+1, 1in, 0kJ-1, 为一模拟
5、信号, 该编码器实际就是一个量化器。,编码，就是将不同的消息用 不同的码字来代替，或称为从消息集到码字集的一种映射(分组编码或块码的概念)。,码长: 组成码字的符号个数, Li=2, 1i3,等长(或定长)编码: 采用相同长度的不同码字去 代表一个消息集合中的不同消息;,M元编码(或M进制):取M个不同字符来组成码字, 最常用的有二元编码(或二进制)。,变长码的基本分析,对一个消息集合中的不同消息，采用不同长度的码字表示。,不等长(或变长)编码：,采用变长码可以提高编码效率，即对相同的信息量所需的平均编码长度可以短一些。,平均码长：,对P(aj)大的aj 用短码; 对P(aj)小的aj 用长码
6、;,当这些信息符号互不相关时,平均码长比等长编码的码长短,1843年，莫尔斯电报码：,表 4.1 莫尔斯码,莫尔斯码的形成:,首先找到各消息符号的统计特性:,再根据各符号出现的概率分布分 配不同长度的码字:,变长码在编码时要预先知道各种信息符号出现的概率，解码也远比等长码复杂: 正确识别码字起点不容易; 存在唯一可译性问题; 译码实时性问题; 匀速输入输出匹配的缓存问题;,定义 4-1,若W 中任一有限长的码字序列(即有限长的一串W) ,可唯一地分割成一个一个码字,称为单义可译或唯一可译的,W 也叫做单义代码。,单义可译码,例4-2,考虑以下几种变长码：, 码A不是一一对应 ;, 码B是一一对
7、应，但构成的序列不能被唯一分割;, 码C是唯一可译的;, 码D是在码B各码字(除了w1)之前加一个码元“0”, 成为唯一可译的, 但平均码长增加0.5bit;, 码F 即使从尾开始判断, 也不是唯一可译的;,问题: 什么样的码才是唯一可译的?, 码E的译码要求等到收到全部序列, 才能从尾开始进行判决, 产生了时间上延时和存储容量的增加;,唯一可译码的存在,目前还没有一个明确的判断唯一可译码的准则, 只有一个判断不是唯一可译码的准则。,定理 4.1(Kraft不等式),长度为L1, L2, Ln 的 m 进制唯一可译码存在的充分必要条件是:,含义：要求 Li 比较大(码长不能过短)，意味着码字可
8、能的组合数多,不为别的码字的字首。,(4.1-1),Kraft不等式：只涉及唯一可译码的存在问题而并不涉及具体的码。可用来判定某一组码不是唯一可译的，但不能判定是唯一可译的。,不满足Kraft不等式的码肯定不是唯一可译码，而满足的也不一定就是唯一可译的，,但可以肯定若按这样的Li 分配码组，则必存在有一个唯一可译码(也可能不止一个)对应于信源符号。,例4-3,对于例4-2,问题: 如何来确定码字长度? 如何在确定了码字长度后找出唯一可译码?,定理 4.2(按符号)变长编码定理),对于符号熵为H(X)的离散无记忆信源进行m 进制不等长编码, 一定存在一种无失真编码方法, 其码字平均长度 l 满足
9、:,(4.1-2),小于上限的单义代码总是存在的。,当m=2，有(二进制编码定理):,此时l 叫编码速率, 有时又叫比特率。,对于m进制的不等长编码的编码速率定义为：,(4.1-4),(4.1-3),定理4.2改述为：,若H(X)R H(X)+, 就存在唯一可译的变长码; 若R H(X), 则不存在唯一可译的变长码； 其中为任一正数。,例4-4,例4.2信源的的熵为:,码长的一种设计为:,L1 = 1, L2 = 2, L3 = L4 = 3,满足上述码长设计的码如：例4.2中的码C、E、F（满足Kraft不等式）。,如何做出具体的变长码是变长码的构造问题。,唯一可译码的构造,唯一可译码的基本
10、要求:,码字非续长,对码字序列能做出唯一正确的分割。,充分条件,若W 中任一码字都不是另一个码字的字头；或换句话说,任一码字都不是由另一个码字加上若干个码元所构成，则W 就叫作非续长码字或异字头码(Prefix Condition Code)。,例4.2中:,码A、码B、码D、码E和码F都含有续长码，或同字头码； 码C是异字头码。,不过非异字头码也并非一定不是唯一可译，码D和码E就唯一可译； 码D：各码组靠“逗号”（码元0）分开； 码E：为码C的“镜像”，具有“异后尾”，从 后向前即具有唯一可译性。,异字头条件保证译出的码字是唯一的且具有“即时性”，减少了译码延时。,异字头性质只是码字可分离的
11、充分条件，非续长码也只是单义可译代码集合的一个子集。,图4.3 单义可译码与非续长码,二进制编码,通常可用二进码树(二叉树)来表示各码字的构成,串接的最大枝数为树的节数， 图4.4的节数为3。,用码树表述任何一个代码W, 异字头条件就成为:,W中所有的码字 wi 均只对应地配置在终端节点上。,图4.5 码C的树结构(异字头码),码E的树结构(非异字头码),此时码C为用尽的异字头码, 有:,倘若有一码字为(0,10,110), 则该码为非用尽的异字头码, 有:,按照Kraft 不等式的要求，对n个消息x1, x2, ,xn分配了编码长度L1,L2, ,Ln, 即可用二进码树来生成异字头码, 生成
12、规律是:, 从根出发开始生出2枝 ;, 每一枝用一个码元aj A=0,1来表示;, 枝尽节来,节外生枝;, 在第Li级端节点(Li级节点共有2Li个)上,配置信 号单元 xi , i=1,2, , n ;, 从根开始直奔对应的端节点,沿途(联枝)所遇到 的码元 aj 所构成的符号,即为对应于该信号单元 xi 的码字 wi 。,异字头码无译码延时，构造简单。,结论：任一唯一可译码，总可以用与各相应码字长度一样的异字头码代替。,异字头码虽然只是唯一可译码的一种，但它具有代表性和普遍意义，在信息保持编码中广泛应用。,长度为L1,L2, ,Ln的M进制异字头码存在的充要条件，也使Kraft不等式成立。
13、,4.2 霍夫曼编码,1952年 ，霍夫曼(D.A.Huffman) 提出霍夫曼编码, 又称最佳编码,根据字符出现概率来构造平均长度最短的异字头码字。,霍夫曼码的构造,理论基础,定理4.3,在变长编码中,若码字长度严格按照所 对应符号出现概率的大小逆序排列,则 其平均长度最短。,例4-6,对一个7符号信源A=a1,a2, ,a7, 求其霍夫曼编码,信源符号 出现概率 a1 0.20 a2 0.19 a3 0.18 a4 0.17 a5 0.15 a6 0.10 a7 0.01,码长 码 字 2 11 2 10 3 011 3 010 3 001 4 0001 4 0000,编码步骤：, 将信源
14、符号概率按递减顺序排列;, 将两个最小的概率进行相加，并继续这一步骤，直到概率 达到1.0为止;, 在每对组合中的上部指定为1(或0),下部指定为0(或1);, 画出每个信源符号概率到1.0处的路径,记下沿路径的1和0 ;, 对于每个信源符号都写出1、0序列，则从右到左就得到霍 夫曼编码。,011 a3,根,例4-6的Huffman二进码树,11 a1,10 a2,010 a4,001 a5,0001 a6,0000 a7,例4-6的信源熵为:,霍夫曼编码的平均字长为:,编码效率:,另例1,对一个7符号信源A=a1,a2, ,a7, 求其霍夫曼编码:,信源符号 出现概率 a1 0.35 a2
15、0.20 a3 0.15 a4 0.12 a5 0.10 a6 0.05 a7 0.03,关键：在每一步，总是最低概率的两个符号构成一对。,注意：哈夫曼的编法并不唯一 每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。 不同的码元分配，得到的具体码字不同，但码长ki不变，平均码长也不变，所以没有本质区别； 缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度ki也不尽相同。,单符号离散无记忆信源 对其编二进制哈夫曼码。,解：方法一 合并后的新符号排在其它相同概率符号之后,另例2,这两种编码哪一种更好呢，我们来计算一下二者的码长。,方法二：合并后的新符号排在其它相同概率符号的前面。,引入码字长度偏离平均码长方差的概念：,方法一：,方法二：,两种编码的平均码长是一样的，都是2.2，那一种更好呢，我们可以计算一下平均码长的方差。,可见：第二种编码方法的码长
