统计编码(2015)

1、1 1压缩编码技术压缩编码技术 2数据压缩的类型可逆的无失真编码可逆的无失真编码不可逆的有失真编码不可逆的有失真编码不允许在压缩过程中丢失信息。利用消息或消息序列出现概不允许在压缩过程中丢失信息。利用消息或消息序列出现概率的分布特性，注重寻找概率与码字长度间的最优匹配。率的分布特性，注重寻找概率与码字长度间的最优匹配。语音、图像或其他物理过程的量化采样。语音、图像或其他物理过程的量化采样。本章讨论的内容3对于计算机文件对于计算机文件逻辑压缩逻辑压缩(Logical Compression)物理压缩物理压缩(Physical Compression)由数据自身特点及设计者技巧来决定的由数据自身特

2、点及设计者技巧来决定的 “压缩表示压缩表示法法”，这种技巧在数据库的数据结构设计中特别有效。，这种技巧在数据库的数据结构设计中特别有效。减少计算机文件内部冗余度的统计编码方法。减少计算机文件内部冗余度的统计编码方法。本章讨论的内容44.1 基本原理基本原理 4.2 Huffman编码编码4.3 游程编码游程编码4.4 算术编码算术编码4.5 LZW编码编码第四章第四章 统计编码方法统计编码方法54.1 4.1 统计编码方法的基本原理统计编码方法的基本原理文件的冗余度类型文件的冗余度类型编码器的数学描述编码器的数学描述变长码的基本分析变长码的基本分析唯一可译码的存在唯一可译码的存在6计算机文件字

3、符集合(如文本);二进制符号集合(如数据);压缩必须压缩必须“透明透明”，恢复后的文件不允许有任何失真。，恢复后的文件不允许有任何失真。7 文件的冗余度类型文件的冗余度类型冗余度，专指对数据解释一无所知时由数据流中即可观察到的，与具体应用背景无关。了解文件的冗余度，意在考虑有针对性的编码方法。了解文件的冗余度，意在考虑有针对性的编码方法。8冗余类型冗余类型 字符分布字符分布(Character Distribution) 字符重复字符重复(Character Repetition)在典型的字符串中，某些符号要比其他符号出现的更频繁，在一份具体的文件中字符不会以等概率出现，字符的分布明显地因文件

4、而异，影响到字符的统计特性。对于字符重复所形成的符号串常常有更紧凑的编码方式，例如：格式化文件中的空白、报表中的空格串和零串、业务图表中的线图包含成片的空白等。 字符分布字符分布(Character Distribution) 字符重复字符重复(Character Repetition)9 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Positional Redundancy)这四类冗余度之间有重叠这四类冗余度之间有重叠某些符号序列会以较高的频率反复出现，可用较少的位数表示，从而得到时间和空间的净节约。若某些字符总是在各数据块中可预见的位置上出现，那么

5、这些字符至少是部分冗余的 ，例如：光栅扫描图像中含有的竖线、报表文件中的某些字段的记录几乎总是相同的等等。 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Positional Redundancy) 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Positional Redundancy) 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Positional Redundancy) 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Posit

6、ional Redundancy) 高使用率模式高使用率模式(High-usage Patterns)10一份零件报表中的冗余度的类型零件名: HEX NUT 1/4 20说 明: STEEL, STANDARD THREAD颜色码:仓 库: 45th STREET货 位: 4R9存货量: 0020再进货量:0010文字长度可变,字母分布不同;空字段同样的名字在文件中多次出现;数值字段, 有限的字符变化;11u 编码器的数学描述编码器的数学描述 4.1 4.1 统计编码方法的基本原理统计编码方法的基本原理 消息集X：元素 x 叫做信号单元或消息； 输出集W (代码、码组或码书)：元素 w叫做码

7、字； 码字的符号集A：元素 a 叫做码元或者符号； 以符号 A 构建代码 W ; 建立 XW 对应关系;12例例4-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 的映射关系为的映射关系为 (完成步骤完成步骤):若若xi(dk,dk+1, 1in, 0kJ-1, 为一模拟信号为一模拟信号, ,

8、 该该编码器实际就是一个量化器。编码器实际就是一个量化器。编码就是信息集编码就是信息集X 到到 码字集码字集W 的一个映射的一个映射建立建立X 与与 W 的映射关系为的映射关系为 (完成步骤完成步骤):13编码，就是将不同的消息用 不同的码字来代替，或称为从消息集到码字集的一种映射(分组编码或块码的概念)。 码长: 组成码字的符号个数, Li=2, 1i3, 等长(或定长)编码: 采用相同长度的不同码字去 代表一个消息集合中的不同消息; M元编码(或M进制):取M个不同字符来组成码字, 最常用的有二元编码(或二进制)。 14 变长码的基本分析变长码的基本分析对一个消息集合中的不同消息，采用不同

9、长度的码字表示。不等长(或变长)编码：采用变长码可以提高编码效率，即对相同的信息量所需的平均编码长度可以短一些。151()njjjlP aL平均码长：对对P(aj)大的大的aj 用短码用短码;对对P(aj)小的小的aj 用长码用长码; 当这些信息符号互不相关时当这些信息符号互不相关时,平均码长比等长编码的码长短平均码长比等长编码的码长短161843年，莫尔斯电报码年，莫尔斯电报码字母莫尔斯码铅字数E12000T9000A 8000I 8000N 8000O 8000S 8000H 6400R 6200D 4400L 4000U 3400C 3000字母莫尔斯码铅字数M 3000F 2500W

10、2000Y 2000G 1700P 1700B 1600V 1200K 800Q 500J 400X 400Z 200表4.1莫尔斯码17莫尔斯码的形成莫尔斯码的形成: 首先找到各消息符号的统计特性: 再根据各符号出现的概率分布分 配不同长度的码字:变长码在编码时要预先知道各种信息符号出现的概率,解码也远比等长码复杂:正确识别码字起点不容易;存在唯一可译性问题;译码实时性问题;匀速输入输出匹配的缓存问题; 18定义定义 4-1若W 中任一有限长的码字序列(即有限长的一串W) ,可唯一地分割成一个一个码字,称为单义可译或唯一可译的,W 也叫做单义代码。单义可译码（唯一可译码）单义可译码（唯一可译

11、码）19例例4-2考虑以下几种变长码：信源字母概率码A码B码C码D码E码Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111 码A不是一一对应 ; 码B是一一对应，但构成的序列不能被唯一分割;01110(0,1,1,1,0) (0,1,11,0) (0,11,1,0) (0,111,0)20100111011010(10, 0, 111, 0, 110, 10) 码C是唯一可译的;信源字母码B码C码Da1a2a3a401111110101101110010110111 码D是在码B各码字(除了w1)之前加一

12、个码元“0”, 成为唯一可译的, 但平均码长增加0.5bit;21 码F 即使从尾开始判断, 也不是唯一可译的;信源字母码E码Fa1a2a3a4001011111010101111101111010(10, 111, 10, 10)(101, 111, 0, 10)问题: 什么样的码才是唯一可译的? 码E的译码要求等到收到全部序列, 才能从尾开始进行判决, 产生了时间上延时和存储容量的增加;0111111 111(a1 1111) (a2111) ( a311)22 唯一可译码的存在唯一可译码的存在定理 4.1(Kraft不等式)长度为L1, L2, Ln 的 m 进制唯一可译码存在的充分必要

13、条件是:含义：要求 Li 比较大(码长不能过短)，意味着码字可能的组合数多,不为别的码字的字首。11niLim(4.1-1)目前还没有一个明确的判断唯一可译码的准则, 只有一个判断不是唯一可译码的准则。含义：要求 Li 比较大(码长不能过短)，意味着码字可能的组合数多,不为别的码字的字首。23Kraft不等式：只涉及唯一可译码的存在问题而并不涉及具体的码。可用来判定某一组码不是唯一可译的，但不能判定是唯一可译的。不满足Kraft不等式的码肯定不是唯一可译码，而满足的也不一定就是唯一可译的，但可以肯定若按这样的Li 分配码组，则必存在有一个唯一可译码(也可能不止一个)对应于信源符号。24码A码B

14、码C码D码E码F 的值7/411/4115/1611是否满足Kraft不等式是否唯一可译例例4-3对于例4-2,有:412iLi25问题: 如何来确定码字长度?如何在确定了码字长度后找出唯一可译码?定理 4.2(按符号)变长编码定理)对于符号熵为H(X)的离散无记忆信源进行m 进制不等长编码, 一定存在一种无失真编码方法, 其码字平均长度 l 满足:mXHlmXHlog)(1log)(4.1-2)小于上限的唯一可译码总是存在的。26当m=2，有(二进制编码定理):此时l 叫编码速率, 有时又叫比特率。对于m进制的不等长编码的编码速率定义为：mlRlog(4.1-4)(bit) )(1)(XHl

15、XH(4.1-3)定理4.2改述为：若H(X)R H(X)+, 就存在唯一可译的变长码;若R 1.75 码长的一种设计为: L1 = 1, L2 = 2, L3 = L4 = 3信源字母概率码A码B码C码D码E码Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111满足上述码长设计的码如：例4.2中的码C、E、F（满足Kraft不等式）。如何做出具体的变长码是变长码的构造问题。28 唯一可译码的构造唯一可译码的构造唯一可译码的基本要求:码字非续长对码字序列能做出唯一正确的分割。充分条件码字非续长对码字序列能做

16、出唯一正确的分割。29若W 中任一码字都不是另一个码字的字头；或换句话说,任一码字都不是由另一个码字加上若干个码元所构成，则W 就叫作非续长码字或异字头码(Prefix Condition Code)。定义 4-2码字非续长30例4.2中:信源字母概率码A码B码C码D码E码Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111码A、码B、码D、码E和码F都含有续长码，或同字头码；码C是异字头码。31u 唯一可译码唯一可译码4.1 4.1 统计编码方法的基本原理统计编码方法的基本原理32不过非异字头码也并非一定

17、不是唯一可译，码D和码E就唯一可译；码D：各码组靠“逗号”（码元0）分开；码E：为码C的“镜像”，具有“异后尾”，从 后向前即具有唯一可译性。异字头条件保证译出的码字是唯一的且具有“即时性”，减少了译码延时。33异字头性质只是码字可分离的充分条件，非续长码也只是唯一可译代码集合的一个子集。唯一可译码非续长码图4.3 唯一可译码与非续长码34二进制编码二进制编码通常可用二进码树(二叉树)来表示各码字的构成(根)(节点)图4.4 二进码树C(节点)D(节点)串接的最大枝数为书的节数， 图4.4的节数为3。35用码树表述任何一个代码W, 异字头条件就成为: W中所有的码字中所有的码字 wi 均只对应

18、地配置在终端节点上。均只对应地配置在终端节点上。图4.5 码C的树结构(异字头码)根001110010110111根011100(011)(111)11(0)(01)码E的树结构(非异字头码)3611niLim此时码C为用尽的异字头码, 有:倘若有一码字为(0,10,110), 则该码为非用尽的异字头码, 有:11niLim37按照Kraft 不等式的要求，对n个消息x1, x2, ,xn分配了编码长度L1,L2, ,Ln, 即可用二进码树来生成异字头码, 生成规律是: 从根出发开始生出2枝 ; 每一枝用一个码元aj A=0,1来表示; 枝尽节来,节外生枝; 在第Li级端节点(Li级节点共有2

19、Li个)上,配置信 号单元 xi , i=1,2, , n ; 从根开始直奔对应的端节点,沿途(联枝)所遇到 的码元 aj 所构成的符号,即为对应于该信号单元 xi 的码字 wi 。异字头码无译码延时，构造简单。38结论：任一唯一可译码，总可以用与各相应码字长度一样的异字头码代替。异字头码虽然只是唯一可译码的一种，但它具有代表性和普遍意义，在信息保持编码中广泛应用。长度为L1,L2, ,Ln的M进制异字头码存在的充要条件，也使Kraft不等式成立。394.1 基本原理基本原理 4.2 Huffman编码编码4.3 游程编码游程编码4.4 算术编码算术编码4.5 LZW编码编码第四章第四章 统计

20、编码方法统计编码方法40Shannon-Fano 编码编码 贝尔实验室的 Claude Shannon 和 MIT 的 R.M.Fano 几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的 Shannon-Fano 编码方法。信源字母概率a1a2a3a41/2=0.51/4=0.251/8=0.1251/8=0.125对于例4.2中的信源:Shannon-Fano 编码的核心是构造二进码树，构造的方式非常简单： 411) 将给定符号按照其概率从大到小排序 2) 将序列分成上下两部分，使得上部概率总和尽可能接近下部概率总和,有：a1 0.5a2 0.25a3 0.125a4 0.125a1

21、 0.5 -a2 0.25a3 0.125a4 0.125Shannon-Fano 编码步骤编码步骤424) 分别对左右子树重复2 、3两步，直到所有的符号都成为二进码树的终端节点为止。现在如下的二进码树：3) 把第2步中划分出的上部作为二进码树的左子树，记 0，下部作为二进码树的右子树，记 1。 a1 0.5 0-a2 0.25 1a3 0.125a4 0.125a1 0.5 0-a2 0.25 1 0 -a3 0.125 1 0-a4 0.125 143a1 - 0 a2 10 a3 - 110 a4 - 111 根001110a1a2a3a4于是得到了此信息的编码表：得到的码表就是码C4

22、4习题：二进制费诺编码 信信源源符符号号 概概率率 编编码码 码码字字 码码长长 x1 0.32 0 00 2 x2 0.22 0 1 01 2 x3 0.18 0 10 2 x4 0.16 0 110 3 x5 0.08 0 1110 4 x6 0.04 1 1 1 1 1111 4 123456,()0.320.220.180.160.080.04XxxxxxxP X解：编码过程如下表。对该信源编二进制费诺码。平均码长平均码长 码元码元/符号符号 编码效率编码效率61( )2.4iiiLp x L()2.350.982.4H XL设有一单符号离散信源454.2 霍夫曼编码霍夫曼编码1952

23、年 ，霍夫曼(D.A.Huffman) 提出霍夫曼编码, 又称最佳编码根据字符出现概率来构造平均长度根据字符出现概率来构造平均长度最短的异字头码字。最短的异字头码字。 46 霍夫曼码的构造霍夫曼码的构造理论基础定理定理4.3在变长编码中,若码字长度严格按照所对应符号出现概率的大小逆序排列,则其平均长度最短。47编码步骤：编码步骤： 将信源符号概率按递减顺序排列将信源符号概率按递减顺序排列; ; 将两个最小的概率进行相加，并继续这一步骤，直到概率将两个最小的概率进行相加，并继续这一步骤，直到概率 达到达到1.0为止为止; ; 在每对组合中的上部指定为在每对组合中的上部指定为1(或或0), ,下部

24、指定为下部指定为0(或或1); ; 画出每个信源符号概率到画出每个信源符号概率到1.0处的路径处的路径, ,记下沿路径的记下沿路径的1和和0 ; 对于每个信源符号都写出对于每个信源符号都写出1 1、0 0序列，则序列，则从右到左从右到左就得到霍就得到霍 夫曼编码。夫曼编码。48例例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 00000.26010.11010

25、.35010.390110.61101.00049011a3根例4-6的Huffman二进码树11a110a2010a4001a50001a60000a750例4-6的信源熵为:霍夫曼编码的平均字长为:(bit) 61. 2)(log)()(71iiiapapAH(bit) 72.2)(71iiiLapl编码效率:( )2.6196 %2.72H Al51另例另例1对一个对一个7符号信源符号信源A=a1,a2, ,a7, 求其霍夫曼编码求其霍夫曼编码:信源符号 出现概率 a1 0.35 a2 0.20 a3 0.15 a4 0.12 a5 0.10 a6 0.05 a7 0.03 码长 码 字

26、 2 00 2 10 3 010 3 011 3 110 4 1110 4 11110.080.180.270.620.381.00111111000000关键：在每一步，总是最低概率的两个符号构成一对。关键：在每一步，总是最低概率的两个符号构成一对。52注意注意：哈夫曼的编法并不唯一哈夫曼的编法并不唯一每次对缩减信源两个概率最小的符号分配每次对缩减信源两个概率最小的符号分配“0”0”和和“1”1”码码元是任意的，所以可得到不同的码字。只要元是任意的，所以可得到不同的码字。只要在各次缩减信在各次缩减信源中保持码元分配的一致性源中保持码元分配的一致性，即能得到可分离码字。即能得到可分离码字。不同

27、的码元分配，得到的具体码字不同，但码长不同的码元分配，得到的具体码字不同，但码长k ki i不变，不变，平均码长也不变，所以没有本质区别；平均码长也不变，所以没有本质区别；缩减信源时，若合并后的新符号概率与其他符号概率相等，缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，从编码方法上来说，这几个符号的次序可任意排列，编出这几个符号的次序可任意排列，编出的码都是正确的，但得到的的码都是正确的，但得到的码字不相同码字不相同。不同的编法得到不同的编法得到的的码字长度码字长度k ki i也不尽相同也不尽相同。53 单符号离散无记忆信源单符号离散无记忆信源对其编二进制哈夫曼码。对其

28、编二进制哈夫曼码。解：解：方法一方法一 合并后的新符号排在其它相同概率符号之后合并后的新符号排在其它相同概率符号之后12345,()0.40.20.20.10.1XxxxxxP X另例另例254 这两种编码哪一种更好呢？这两种编码哪一种更好呢？我们来计算一下二者的码长。我们来计算一下二者的码长。方法二：方法二：合并后的新符号排在其它相同概率符号的前面。合并后的新符号排在其它相同概率符号的前面。552221() ( )()qiiiiE lLP slL引入码字长度偏离平均码长的方差的概念：36. 1 2)2 . 24(1 . 0)2 . 23(2 . 0 )2 . 22(2 . 0)2 . 21

29、(4 . 0 22222方法一：16. 0 2)2 . 23(1 . 0 2)2 . 22(2 . 0)2 . 22(4 . 02222方法二：两种编码的平均码长是一样的，都是两种编码的平均码长是一样的，都是2.2，那一种更好呢，我，那一种更好呢，我们可以计算一下平均码长的方差。们可以计算一下平均码长的方差。56n可见：第二种编码方法的码长方差要小许多。意味着第二种可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。编码方法的码长变化较小，比较接近于平均码长。第一种方法编出的第一种方法编出的5 5个码字有个码字有4 4种不同的码长；种不同的码长；第二

30、种方法编出的码长只有第二种方法编出的码长只有2 2种不同的码长；种不同的码长；显然，显然，第二种编码方法更简单、更容易实现，所以更好。第二种编码方法更简单、更容易实现，所以更好。57结论：在哈夫曼编码过程中，对缩减信源符号按概率由结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使大到小的顺序重新排列时，应使合并后的新符号尽可能合并后的新符号尽可能排在靠前的位置排在靠前的位置，这样可使合并后的新符号重复编码次，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。数减少，使短码得到充分利用。58Huffman编码和译码过程编码和译码过程编码编码输出输出Huffma

31、nHuffman码流码流Huffman码表码表传传输输接收的接收的Huffman码码流缓冲器流缓冲器信源符号序列信源符号序列解码解码解码后的解码后的字符序列字符序列Huffman码表码表编码编码输出输出HuffmanHuffman码流码流Huffman码表码表传传输输接收的接收的Huffman码码流缓冲器流缓冲器信源符号序列信源符号序列解码解码解码后的解码后的字符序列字符序列Huffman码表码表编码编码输出输出HuffmanHuffman码流码流Huffman码表码表传传输输接收的接收的Huffman码码流缓冲器流缓冲器信源符号序列信源符号序列解码解码解码后的解码后的字符序列字符序列Huff

32、man码表码表编码编码输出输出HuffmanHuffman码流码流Huffman码表码表传传输输接收的接收的Huffman码码流缓冲器流缓冲器信源符号序列信源符号序列解码解码解码后的解码后的字符序列字符序列Huffman码表码表编码编码输出输出HuffmanHuffman码流码流Huffman码表码表传传输输接收的接收的Huffman码码流缓冲器流缓冲器信源符号序列信源符号序列解码解码解码后的解码后的字符序列字符序列Huffman码表码表Huffman码表码表信源符号序列信源符号序列解码后的解码后的字符序列字符序列Huffman码表码表信源符号序列信源符号序列解码后的解码后的字符序列字符序列H

33、uffman码表码表信源符号序列信源符号序列Huffman码表码表接收的接收的Huffman码码流缓冲器流缓冲器Huffman码表码表输出输出HuffmanHuffman码流码流接收的接收的Huffman码码流缓冲器流缓冲器输出输出HuffmanHuffman码流码流Huffman码表码表接收的接收的Huffman码码流缓冲器流缓冲器输出输出HuffmanHuffman码流码流解码后的解码后的字符序列字符序列Huffman码表码表接收的接收的Huffman码码流缓冲器流缓冲器输出输出HuffmanHuffman码流码流信源符号序列信源符号序列解码后的解码后的字符序列字符序列Huffman码表码

34、表接收的接收的Huffman码码流缓冲器流缓冲器输出输出HuffmanHuffman码流码流Huffman码表码表信源符号序列信源符号序列解码后的解码后的字符序列字符序列Huffman码表码表接收的接收的Huffman码码流缓冲器流缓冲器输出输出HuffmanHuffman码流码流59 信源编码基本定理信源编码基本定理霍夫曼编码霍夫曼编码定长的数据段定长的数据段当信源符号的概率当信源符号的概率 pj=2-k编码效率等于编码效率等于100%定长的数据段定长的数据段定长的数据段定长的数据段编码效率等于编码效率等于100%定长的数据段定长的数据段编码效率等于编码效率等于100%定长的数据段定长的数据

35、段编码效率等于编码效率等于100%定长的数据段定长的数据段编码效率等于编码效率等于100%定长的数据段定长的数据段变长的代码变长的代码( (只能分配接只能分配接近近log2pj的整数长码字的整数长码字) )60例4-7:对于二值图像，如传真机文件，输出非“黑”即“白”，有：X=x1，x2=白，黑，其概率与所传文件有关，假设对某页文件，有P(x1)=0.9, P(x2)=0.1 。不考虑信号间的关联时，其信息熵为：不考虑信号间的关联时，其信息熵为：()0.9log0.90.1 log0.10.469 (bit/pel)H X 此时此时W=0,1，无论用定长码还是最佳编码，无论用定长码还是最佳编码

36、, 平均码长至平均码长至少为少为l1=1 (bit) ；此时霍夫曼编码无压缩作用此时霍夫曼编码无压缩作用编码效率为编码效率为1 =H(X)/ l1=46.9 %61解决办法: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 为单义代码为单义代码, , 则则: :(4.2-1)式式(4.2-1)也叫做无失真编码的基本定理。也叫做无失真编码的基本定理。定理定理4.4(信源编码定理信源编码

37、定理):( )( )1loglogH XlH XmKmK62含义：含义：如果我们把如果我们把 X 延长后再对延长后再对 K 元组元组( K 为为延长长度延长长度)进行编码，那么不必利用数据前后的关联，只要进行编码，那么不必利用数据前后的关联，只要K 足够大，则代表每消息单元足够大，则代表每消息单元 X 的平均符号个数的平均符号个数l/K 可以任意趋向于下限。可以任意趋向于下限。63例例4-8: 利用最佳编码利用最佳编码, 以例以例4-7来说明来说明l/K趋向于下限的情况。趋向于下限的情况。把把 X 延长到延长到 X 2 ，假定信源是离散无记忆信源，有图假定信源是离散无记忆信源，有图4.7所所示

38、示 X 2 的最佳编码：的最佳编码：图图4.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 01011011164W 2平均长度为平均长度为:l2 =0.81+0.092+0.093+0.013=1.29 bit/pelW 2的每一个元素代表两个消息单元的每一个元素代表两个消息单元,因此平均每一个消因此平均每一个消息单元

39、的符号个数是息单元的符号个数是:l2 /2 = 1.29/2 = 0.645 bit/pel2 =H(X)/ l2=72.7 %编码效率提高到编码效率提高到: :65把 X 延长到 X 3 ，有图4.8所示 X 3 的最佳编码：图4.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)

40、 =0.0010.0180.0280.1620.2711.0000111001W 311111111101110111010110001110066W 3平均长度为: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=88.0 %编码效率提高到:继续下去,就可使 lK /K 0.469, 或=100% 67进一步减小 l/K , 利用信号的前后关联减小下限, 即利用:H(X, Y )H(X)

41、+H(Y)(3.2-13)H(X | Y )H(X)(3.2-11b)或:可以减小下限,从而减小l/K要求知道P(X), P(X,Y) 或 P(X|Y) 才能进行最佳编码。如果信号继续有关联可供利用，继续延长，会使下限变得很小。68信源编码理论信源编码理论 给定消息单元集合X、符号集合A和X的概率分布P(X)， 可以采用最佳编码，使代码W 的平均长度满足; 如果把X 延长至 X K ,则不必考虑信号前后的关联性, 就可以是代表一个消息单元的符号个数 l /K 任意接近 下限 H(X)/logm; 如果利用延长信号X K的前后关联,可使下限减小。具体实现时，如果将信号延长得过长，会使实际设备复杂

42、到不合理的程度。1log)(,log)(mXHmXHl69霍夫曼编码选择模型霍夫曼编码选择模型静态统计模型 在编码前统计要编码的信息中所有字符的出现概率，然后根据统计出的信息建立编码树，进行编码 。70缺点缺点 对数据量较大的信息，静态统计要消耗大量的时间； 必须保存统计出的结果以便解码时构造相同的编码树，或者直接保存编码树本身，而且，对于每次静态统计，都有不同的结果，必须分别予以保存，这要消耗大量的空间（这意味着压缩效率的下降）； 静态统计模型统计出的频率是字符在整个文件中的出现频率，往往反映不出字符在文件中不同局部出现频率的变化情况，使用这一频率进行压缩，大多数情况下得不到太好压缩效果，文

43、件有时甚至在压缩后反而增大了。71一种有效的“静态统计模型”的替代方案 如果要压缩的所有信息在分布上存在着共同的特征，使用语言学家事先已经建立好的字母频率表来进行压缩和解压缩，不但不用保存多份统计信息，而且一般说来对该类文件有着较好的压缩效果。比如我们要压缩的是普通的英文文本，那么，字母 a 或者字母 e 的出现频率应当是大致稳定的。一种有效的“静态统计模型”的替代方案 比如我们要压缩的是普通的英文文本，那么，字母 a 或者字母 e 的出现频率应当是大致稳定的。72这种方案除了适应性不太强以外，偶尔还会有一些尴尬的时候。缺点缺点 If Youth，throughout all history，

44、 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. 发现什么问题了吗？整段话中竟没有出现一次英文中出现频率最高的字母 e 。这种方案除了适应性不太强以外，偶尔还会有一些尴尬的时候

45、。发现什么问题了吗？整段话中竟没有出现一次英文中出现频率最高的字母 e 。73对英文或中文文本，有一种比较实用的静态模型：不是把字符而是把英文单词或中文词语作为统计频率和编码的单位进行压缩。这种压缩方式可以达到相当不错的压缩效果，并被广泛地用于全文检索系统。74自适应模型自适应模型无需为解压缩预先保存任何信息，整个编码是在压缩和解压缩过程中动态创建的，而且自适应编码由于其符号频率是根据信息内容的变化动态得到的，更符合符号的局部分布规律，因此在压缩效果上比静态模型好许多。根据已经编码的符号频率决定下一个符号的编码。根据已经编码的符号频率决定下一个符号的编码。75算术编码、字典编码等更为适合采用自

46、适应模型 但是，采用自适应模型必须考虑编码表的动态特性，即编码表必须可以随时更新以适应符号频率的变化。对于 Huffman 编码来说，我们很难建立能够随时更新的二叉树，76 霍夫曼码的局限性霍夫曼码的局限性霍夫曼编码霍夫曼编码文本文件压缩文本文件压缩二进制文件压缩二进制文件压缩适用于适用于经过符号合并经过符号合并77局限性局限性: : 输入符号数受限于可实现的霍夫曼码表尺寸输入符号数受限于可实现的霍夫曼码表尺寸 ; ; 译码复杂度译码复杂度; ; 需要知道输入符号集的概率分布；需要知道输入符号集的概率分布； 由于码长不等，还存在一个输入与输出的速率由于码长不等，还存在一个输入与输出的速率 匹配

47、问题。匹配问题。784.1 基本原理基本原理 4.2 Huffman编码编码4.3 游程编码游程编码4.4 算术编码算术编码4.5 LZW编码编码第四章第四章 统计编码方法统计编码方法794.3 游程编码游程编码游程长度游程长度(RL: Run Length,简称游程或游长简称游程或游长) )： 由字符由字符( (或信号采样值或信号采样值) )构成的数据流中各字符构成的数据流中各字符重复出现而形成的字符串的长度。重复出现而形成的字符串的长度。用二进制码字给出形成串的字符、串的长度用二进制码字给出形成串的字符、串的长度及串的位置等信息，以此来恢复出原来的数及串的位置等信息，以此来恢复出原来的数据

48、流。据流。 游程长度编码游程长度编码(RLC) )：80游程编码类型：游程编码类型：变长游程编码变长游程编码使用位数是固定的，即使用位数是固定的，即RLRL位数是固定的，如果灰度位数是固定的，如果灰度连续相同的个数超过了固定位数所能表示的最大值，连续相同的个数超过了固定位数所能表示的最大值，则进入下一轮游程编码；则进入下一轮游程编码；定长游程编码定长游程编码对不同范围的游程采用不同位数的编码，即表示对不同范围的游程采用不同位数的编码，即表示RLRL位数不固定。位数不固定。81 基本的游程编码基本的游程编码基本的基本的RLC压缩方法：压缩方法：最初出现在最初出现在 IBM 3780 BYSYNC

49、 (Binary Synchronous Communication)通信协议中。通信协议中。基本的基本的RLC数据结构：数据结构：XScRL数数 据据 流流图图4.9 基本的基本的RLC数据结构数据结构82其中其中X ： 代表数据字符；代表数据字符； Sc： Sc X，表示有一个字符在此位置；，表示有一个字符在此位置； RL： 代表串（游程）的长度，字符重复出现的次数；代表串（游程）的长度，字符重复出现的次数；只有当只有当RL 3时时, 才有数据压缩效益。才有数据压缩效益。编码时：先判断编码时：先判断RL值，再决定是否值，再决定是否RLC； 解码时：根据每一解码时：根据每一X后的码字是否为后

50、的码字是否为Sc，再，再 决定下一个字的含义。决定下一个字的含义。83RLC压缩效能:取决于数据流中重复字符出现次数、平均游程长度及所采用的编码结构。平均重复平均重复长度长度重复出现重复出现1010次的压缩比次的压缩比重复出现重复出现2020次的压缩比次的压缩比重复出现重复出现3030次的压缩比次的压缩比重复出现重复出现4040次的压缩比次的压缩比重复出现重复出现5050次的压缩比次的压缩比41.0101.0201.0311.0421.05351.0201.0421.0641.0731.11161.0311.0641.0991.1361.17671.0421.0871.1361.1901.25

51、081.0531.1111.1761.2501.33391.0641.1361.2201.3161.429101.0751.1631.2661.3841.538表4.2 基本的游程编码压缩比84 二值图像的游程编码二值图像的游程编码仅有黑(“1”代表)、白(“0”代表)两个亮度值的图像。 经扫描仪得到的气象图、工程图、地图、线 路图等； 文字组成的文件图像； 灰度图像经过位平面分解或抖动处理后 的图像。最常用的传输方式：传真二值图像二值图像编码也往往指数字传真编码。85二值图像的游程编码二值图像的游程编码数据字符 X=白，黑对二值图像每一扫描行： 白像素游程（白长） 黑像素游程（黑长）对不同长

52、度的白长和黑长，按其出现概率的不同分别配以不同长度的码字。RLC利用多个像素之间的相关性，可得到较低的码率下限。86二值图像的二值图像的RLC的两种方式的两种方式 不分白长和黑长，只根据长度进行编码由于在实际图像中, 白长和黑长的概率分布各异, 此方法不是很有效; 其最低比特率 满足:WBnWBWBWBWBWBPPhnhll(4.3-1)其中：PW和PB分别是白像素和黑像素出现的概率; lW和lB分别是白长和黑长的平均像素数(平均长度 ); hWB为每个像素的熵值。 不分白长和黑长，只根据长度进行编码 对白长和黑长分别编码(前CCITT建议)87编码过程：编码过程： 先对图像进行统计分别得出白

53、长为先对图像进行统计分别得出白长为 i 的的 概率概率 PiW 和黑长为和黑长为 i 的概率的概率 PiB， 然后根据霍夫曼原则按然后根据霍夫曼原则按RL出现概率来分出现概率来分 配码字。配码字。二值图像的二值图像的RLC实为霍夫曼码的具体应用实为霍夫曼码的具体应用88由于各种由于各种 RL 的出现概率在行间、页的出现概率在行间、页间都不相同，且为求得概率，需要存间都不相同，且为求得概率，需要存储数据并做统计计算，难以实时编码储数据并做统计计算，难以实时编码CCITT的的T.4建议建议: 推荐推荐8幅标准传真样张为幅标准传真样张为统计依据统计依据,根据各种根据各种RL的出现概率编出霍夫的出现概

54、率编出霍夫曼码表，称为改进型霍夫曼编码曼码表，称为改进型霍夫曼编码(MHC) 。89MH编码规则: (见表4.7) RL=063， 用一个相应的结尾码表示用一个相应的结尾码表示 ; ; RL=641728，用一个组合基干码加一个补充结尾码；，用一个组合基干码加一个补充结尾码； RL(白白)=128, 补充结尾码为补充结尾码为0(白白)=00110101, 其编码为其编码为: 10010 | 00110101 RL(白白)=129, 补充结尾码为补充结尾码为1(白白)=000111, 其编码为其编码为: 10010 | 000111 规定每行都从白游程开始，若实际扫描由黑开始，则规定每行都从白游

55、程开始，若实际扫描由黑开始，则 需在行首加零长度白游程；每行结束要加同步码需在行首加零长度白游程；每行结束要加同步码EOL。90 游程编码的局限性游程编码的局限性 对二值图像最为有效，但对数据文件就不那对二值图像最为有效，但对数据文件就不那 么显著，而对于课文实质已无使用价值么显著，而对于课文实质已无使用价值; 压缩字符与数值混合序列比较麻烦，要求区分压缩字符与数值混合序列比较麻烦，要求区分 计数字段和常规字符；计数字段和常规字符； 需要较大容量的缓冲和较低误码的优质信道。需要较大容量的缓冲和较低误码的优质信道。914.1 基本原理基本原理 4.2 Huffman编码编码4.3 游程编码游程编

56、码4.4 算术编码算术编码4.5 LZW编码编码第四章第四章 统计编码方法统计编码方法92u 问题的引入问题的引入 Huffman码等在实际应用过程中，只有在信源符号概率分码等在实际应用过程中，只有在信源符号概率分布等于布等于2的负整次幂时，它们才能产生最佳效果，即产生最佳的负整次幂时，它们才能产生最佳效果，即产生最佳变长码。变长码。 假设某个字符的出现概率为假设某个字符的出现概率为 80%，那么该字符事实上只需，那么该字符事实上只需要要 -log2(0.8) = 0.322 位编码，但位编码，但Huffman 编码一定会为其分编码一定会为其分配一位配一位 0 或或1 的编码。的编码。 真的能

57、只输出真的能只输出 0.322 个个 0 或或 0.322 位信息吗位信息吗？4.4 算术编码（算术编码（Arithmetic Coding）934.4 算术编码（算术编码（Arithmetic Coding）u 算术编码基本思路算术编码基本思路 算术编码一种非分组编码算法。它是从全序列出发，算术编码一种非分组编码算法。它是从全序列出发，采用递推形式的连续编码。它不是将单个的信源符号映射采用递推形式的连续编码。它不是将单个的信源符号映射成一个码字，而是将整个输入序列的符号依据它们的概率成一个码字，而是将整个输入序列的符号依据它们的概率映射为实数轴上区间映射为实数轴上区间0 1)0 1)内的一个

58、小区间，再在该小区间内的一个小区间，再在该小区间内选择一个代表性的二进制小数，作为实际的编码输出。内选择一个代表性的二进制小数，作为实际的编码输出。 例如算术编码对某条信息的输出为例如算术编码对某条信息的输出为 10100011111010001111，那么它，那么它表示小数表示小数 0.10100011110.1010001111，也即十进制数，也即十进制数 0.640.64。941) 码字刷新：码字刷新：C(sai)=C(s)+P(ai)A(s)2) 区间刷新：区间刷新：A(sai)=p(ai)A(s) 设输入符号串设输入符号串s取自符号集取自符号集S=a1,a2,a3,am, p(ai)

59、=p1,p2,p3,pm, s后跟符号后跟符号ai扩展成符号串扩展成符号串sai，算术编码的迭代关系为，算术编码的迭代关系为: 符号累积概率：符号累积概率：初始条件：初始条件： 11)()(ikkiapaP1)(, 0)(, 1)(, 0)(pPACu 算术编码方法具体过程算术编码方法具体过程4.4 算术编码（算术编码（Arithmetic Coding）95当处理当处理ai时，区间时，区间A(s)宽度根据宽度根据ai出现概率出现概率p(ai)而变窄，符号而变窄，符号序列越长，相应的子区间越窄，编码的位数越多。符号串每序列越长，相应的子区间越窄，编码的位数越多。符号串每一步新扩展的码字一步新扩

60、展的码字C(sai)都是由原符号串的码字都是由原符号串的码字C(s)与新区间与新区间宽度宽度A(sai)的算术相加，的算术相加，“算术码算术码”由此得名。由此得名。算术编码在传输任何信号算术编码在传输任何信号ai之前，信号的完整范围是之前，信号的完整范围是) 1 , 0)()(),(ACC4.4 算术编码（算术编码（Arithmetic Coding）u 算术编码方法具体过程算术编码方法具体过程964.4 算术编码（算术编码（Arithmetic Coding）u 例：算术编码方法具体编码过程例：算术编码方法具体编码过程 设某信源取自符号集设某信源取自符号集S=a,b,c,e,r,!，!表示编