第4章统计编码1

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

2、者技巧来决定的由数据自身特点及设计者技巧来决定的 “压缩表示压缩表示法法”，这种技巧在数据库的数据结构设计中特别有效。，这种技巧在数据库的数据结构设计中特别有效。减少计算机文件内部冗余度的统计编码方法。减少计算机文件内部冗余度的统计编码方法。本章讨论的内容1基本原理基本原理2霍夫曼编码霍夫曼编码 3游程编码游程编码 4算术编码算术编码 本章内容本章内容5基于字典的编码基于字典的编码 唯一可译码的构造4.14.1 基本原理基本原理 编码器的数字描述 变长码的基本分析 唯一可译码的存在计算机文件字符集合(如文本);二进制符号集合(如数据);压缩必须“透明”，恢复后的文件不允许有任何失真。 文件的冗

3、余度类型本节所指的冗余度，专指对数据解释一无所知时由数据流中即可观察到的，与具体应用背景无关的冗余。了解文件的冗余度，意在考虑有针对性的编码方法。冗余类型 字符分布(Character Distribution) 字符重复(Character Repetition)在典型的字符串中，某些符号要比其他符号出现的更频繁，在一份具体的文件中字符不会以等概率出现，字符的分布明显地因文件而异，影响到字符的统计特性。对于字符重复所形成的符号串常常有更紧凑的编码方式，例如：格式化文件中的空白、报表中的空格串和零串、业务图表中的线图包含成片的空白等。 高使用率模式(High-usage Patterns) 位

4、置冗余(Positional Redundancy)这四类冗余度之间有重叠某些符号序列会以较高的频率反复出现，可用较少的位数表示，从而得到时间和空间的净节约。若某些字符总是在各数据块中可预见的位置上出现，那么这些字符至少是部分冗余的 ，例如：光栅扫描图像中含有的竖线、报表文件中的某些字段的记录几乎总是相同的等等。图4.1 一份零件报表中的冗余度的类型零件名: HEX NUT 1/4 20说 明: STEEL, STANDARD THREAD颜色码:仓 库: 45th STREET货 位: 4R9存货量: 0020再进货量:0010文字长度可变,字母分布不同;空字段同样的名字在文件中多次出现;数

5、值字段, 有限的字符变化; 编码器的数字描述X =x1, , xnW =w1, , wnA =a1, , am编码器图4.2 编码器的描述实际信源的编码过程 消息集X：元素 x 叫做信号单元或消息； 输出集W (代码、码组或码书)：元素 w叫做码字； 码字的符号集A：元素 a 叫做码元或者符号 以符号 A 构建代码 W ; 建立 XW 对应关系;编码过程例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)

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

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

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

9、码例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)100111011010(10, 0, 111, 0, 110, 10) 码C是唯一可译的;信源字母码B码C码Da1a2a3a401111110101101110010110111 码D是在码B各码字(除了w1)之前加一个码元“0”

10、, 成为唯一可译的, 但平均码长增加0.5bit; 码F 即使从尾开始判断, 也不是唯一可译的;信源字母码E码Fa1a2a3a4001011111010101111101111010(10, 111, 10, 10)(101, 111, 0, 10)问题: 什么样的码才是唯一可译的? 码E的译码要求等到收到全部序列, 才能从尾开始进行判决, 产生了时间上延时和存储容量的增加;0111111 111(a1 1111) (a2111) ( a311) 唯一可译码的存在目前还没有一个明确的判断唯一可译码的准则, 只有一个判断不是唯一可译码的准则。定理 4.1(Kraft不等式)长度为L1, L2,

11、Ln 的 m 进制唯一可译码存在的充分必要条件是:含义：要求 Li 比较大(码长不能过短)，意味着码字可能的组合数多,不为别的码字的字首。11niLim(4.1-1)Kraft不等式：只涉及唯一可译码的存在问题而并不涉及具体的码。可用来判定某一组码不是唯一可译的，但不能判定是唯一可译的。不满足Kraft不等式的码肯定不是唯一可译码，而满足的也不一定就是唯一可译的，但可以肯定若按这样的Li 分配码组，则必存在有一个唯一可译码(也可能不止一个)对应于信源符号。码A码B码C码D码E码F 的值7/411/4115/1611是否满足Kraft不等式是否唯一可译例4-3对于例4-2412iLi信源字母概率

12、码A码B码C码D码E码Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111问题: 如何来确定码字长度?如何在确定了码字长度后找出唯一可译码?定理 4.2(按符号)变长编码定理)对于符号熵为H(X)的离散无记忆信源进行m 进制不等长编码, 一定存在一种无失真编码方法, 其码字平均长度 l 满足:mXHlmXHlog)(1log)(4.1-2)小于上限的单义代码总是存在的。当m=2，有(二进制编码定理):此时l 叫编码速率, 有时又叫比特率。对于m进制的不等长编码的编码速率定义为：mlRlog(4.1-4)(b

13、it) )(1)(XHlXH(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不等式）。如何做出具体的变长码是变长码的构造问题。 唯一可译码的构造唯一可译码的基本要求:码字非续长对码字序列能做出唯一正确的分割。充分条件若W 中任一码字都不

14、是另一个码字的字头；或换句话说,任一码字都不是由另一个码字加上若干个码元所构成，则W 就叫作非续长码字或异字头码(Prefix Condition Code)。定义 4-2码字非续长例4.2中:信源字母概率码A码B码C码D码E码Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111码A、码B、码D、码E和码F都含有续长码，或同字头码；码C是异字头码。不过非异字头码也并非一定不是唯一可译，码D和码E就唯一可译；码D：各码组靠“逗号”（码元0）分开；码E：为码C的“镜像”，具有“异后尾”，从 后向前即具有唯一可译

15、性。异字头条件保证译出的码字是唯一的且具有“即时性”，减少了译码延时。异字头性质只是码字可分离的充分条件，非续长码也只是单义可译代码集合的一个子集。单义可译码非续长码图4.3 单义可译码与非续长码二进制编码通常可用二进码树(二叉树)来表示各码字的构成(根)(节点)图4.4 二进码树C(节点)D(节点)串接的最大枝数为树的节数， 图4.4的节数为3。用码树表述任何一个代码W, 异字头条件就成为: W中所有的码字 wi 均只对应地配置在终端节点上。图4.5 码C的树结构(异字头码)根001110010110111根011100(011)(111)11(0)(01)码E的树结构(非异字头码)11ni

16、Lim此时码C为用尽的异字头码, 有:倘若有一码字为(0,10,110), 则该码为非用尽的异字头码, 有:11niLim按照Kraft 不等式的要求，对n个消息x1, x2, ,xn分配了编码长度L1,L2, ,Ln, 即可用二进码树来生成异字头码, 生成规律是: 从根出发开始生出2枝 ; 每一枝用一个码元aj A=0,1来表示; 枝尽节来,节外生枝; 在第Li级端节点(Li级节点共有2Li个)上,配置信 号单元 xi , i=1,2, , n ; 从根开始直奔对应的端节点,沿途(联枝)所遇到 的码元 aj 所构成的符号,即为对应于该信号单元 xi 的码字 wi 。异字头码无译码延时，构造简

17、单。结论：任一唯一可译码，总可以用与各相应码字长度一样的异字头码代替。异字头码虽然只是唯一可译码的一种，但它具有代表性和普遍意义，在信息保持编码中广泛应用。长度为L1,L2, ,Ln的M进制异字头码存在的充要条件，也使Kraft不等式成立。4.2 霍夫曼编码1952年 ，霍夫曼(D.A.Huffman) 提出霍夫曼编码, 又称最佳编码根据字符出现概率来构造平均长度最短的异字头码字。 霍夫曼码的构造理论基础定理4.3在变长编码中,若码字长度严格按照所对应符号出现概率的大小逆序排列,则其平均长度最短。例4-6对一个7符号信源A=a1,a2, ,a7, 求其霍夫曼编码信源符号 出现概率 a1 0.2

18、0 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.35010.390110.61101.000编码步骤： 将信源符号概率按递减顺序排列将信源符号概率按递减顺序排列; ; 将两个最小的概率进行相加，并继续这一步骤，直到概率将两个最小的概率进行相加，并继续这一步骤，直到概率 达到达到1.0为止为止; ; 在每对组合中的上部指定为在每对组合中的上部指定为1(或或0), ,下部指定为下部指定为0(或或1); ; 画出每个信源符号概

19、率到画出每个信源符号概率到1.0处的路径处的路径, ,记下沿路径的记下沿路径的1和和0 ; 对于每个信源符号都写出对于每个信源符号都写出1 1、0 0序列，则序列，则从右到左从右到左就得到霍就得到霍 夫曼编码。夫曼编码。011a3根例4-6的Huffman二进码树11a110a2010a4001a50001a60000a7例4-6的信源熵为:霍夫曼编码的平均字长为:(bit) 61. 2)(log)()(71iiiapapAH(bit) 72.2)(71iiiLapl编码效率:( )2.6196 %2.72H Al另例1对一个7符号信源A=a1,a2, ,a7, 求其霍夫曼编码:信源符号 出现

20、概率 a1 0.35 a2 0.20 a3 0.15 a4 0.12 a5 0.10 a6 0.05 a7 0.03 码长 码 字 2 00 2 10 3 010 3 011 3 110 4 1110 4 11110.080.180.270.620.381.00111111000000关键：在每一步，总是最低概率的两个符号构成一对。 注意注意：哈夫曼的编法并不唯一哈夫曼的编法并不唯一每次对缩减信源两个概率最小的符号分配每次对缩减信源两个概率最小的符号分配“0”和和“1”码元是任意的，所以可得到不同的码字。只要码元是任意的，所以可得到不同的码字。只要在各次在各次缩减信源中保持码元分配的一致性缩减

21、信源中保持码元分配的一致性，即能得到可分离即能得到可分离码字。码字。不同的码元分配，得到的具体码字不同，但码长不同的码元分配，得到的具体码字不同，但码长ki不不变，平均码长也不变，所以没有本质区别；变，平均码长也不变，所以没有本质区别；缩减信源时，若合并后的新符号概率与其他符号概率缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，相等，从编码方法上来说，这几个符号的次序可任意这几个符号的次序可任意排列，编出的码都是正确的，但得到的排列，编出的码都是正确的，但得到的码字不相同码字不相同。不同的编法得到的不同的编法得到的码字长度码字长度k ki i也不尽相同也不尽相同。 单符号

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

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

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

25、译码过程编码输出Huffman码流Huffman码表传输接收的Huffman码流缓冲器信源符号序列解码解码后的字符序列Huffman码表 信源编码基本定理霍夫曼编码变长的代码(只能分配接近log2pj的整数长码字)定长的数据段当信源符号的概率 pj=2-k编码效率等于100%例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，无论用定长码还是最佳编

26、码, 平均码长至少为l1=1 (bit) ；此时霍夫曼编码无压缩作用编码效率为1 =H(X)/ l1=46.9 %解决办法:定理4.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 为单义代码, 则:( )( )1loglogH XlH XmKmK(4.2-1)式(4.2-1)也叫做无失真编码的基本定理。含义：如果我们把 X 延长后再对 K 元组( K 为延长长度)进行编码，那么不必利用数据前后的关

27、联，只要K 足够大，则代表每消息单元 X 的平均符号个数l/K 可以任意趋向于下限。例4-8: 利用最佳编码, 以例4-7来说明l/K趋向于下限的情况。把 X 延长到 X 2 ，假定信源是离散无记忆信源，有图4.7所示 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 010110111W 2平均长度为:l2 =0.8

28、1+0.092+0.093+0.013=1.29 bit/pelW 2的每一个元素代表两个消息单元,因此平均每一个消息单元的符号个数是:l2 /2 = 1.29/2 = 0.645 bit/pel2 =H(X)/( l2/2)=72.7 %编码效率提高到:把 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

29、, x2) =0.009P(x2, x2, x1) =0.009P(x2, x2, x2) =0.0010.0180.0280.1620.2711.0000111001W 3111111111011101110101100011100W 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/3)=88.0 %编码效率提高到:继续下去,就可使 lK /K 0.469, 或=100

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

31、的前后关联,可使下限减小。具体实现时，如果将信号延长得过长，会使实际设备复杂到不合理的程度。1log)(,log)(mXHmXHl霍夫曼编码选择模型静态统计模型 在编码前统计要编码的信息中所有字符的出现概率，然后根据统计出的信息建立编码树，进行编码 。缺点 ： 对数据量较大的信息，静态统计要消耗大量的时间； 必须保存统计出的结果以便解码时构造相同的编码树，或者直接保存编码树本身，而且，对于每次静态统计，都有不同的结果，必须分别予以保存，这要消耗大量的空间（这意味着压缩效率的下降）； 静态统计模型统计出的频率是字符在整个文件中的出现频率，往往反映不出字符在文件中不同局部出现频率的变化情况，使用这

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

33、 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 。对英文或中文文本，有一种比较实用的静态模型：不是把字符而是把英文单词或中文词语作为统计频率和编码的单位进行压缩。这种压缩方式可以达到相当不错的压

34、缩效果，并被广泛地用于全文检索系统。自适应模型无需为解压缩预先保存任何信息，整个编码是在压缩和解压缩过程中动态创建的，而且自适应编码由于其符号频率是根据信息内容的变化动态得到的，更符合符号的局部分布规律，因此在压缩效果上比静态模型好许多。根据已经编码的符号频率决定下一个符号的编码。算术编码、字典编码等更为适合采用自适应模型 但是，采用自适应模型必须考虑编码表的动态特性，即编码表必须可以随时更新以适应符号频率的变化。对于 Huffman 编码来说，我们很难建立能够随时更新的二叉树， 霍夫曼码的局限性霍夫曼编码文本文件压缩二进制文件压缩适用于经过符号合并局限性: 输入符号数受限于可实现的霍夫曼码表

35、尺寸 ; 译码复杂度; 需要知道输入符号集的概率分布； 由于码长不等，还存在一个输入与输出的速率 匹配问题。4.3 游程编码游程长度(RL: Run Length,简称游程或游长)： 由字符(或信号采样值)构成的数据流中各字符重复出现而形成的字符串的长度。用二进制码字给出形成串的字符、串的长度及串的位置等信息，以此来恢复出原来的数据流。 游程长度编码(RLC)：游程编码类型：变长游程编码变长游程编码使用位数是固定的，即RL位数是固定的，如果灰度连续相同的个数超过了固定位数所能表示的最大值，则进入下一轮游程编码；定长游程编码定长游程编码对不同范围的游程采用不同位数的编码，即表示RL位数不固定。

36、基本的游程编码基本的RLC压缩方法：最初出现在 IBM 3780 BYSYNC (Binary Synchronous Communication)通信协议中。基本的RLC数据结构：XScRL数 据 流图4.9 基本的RLC数据结构其中X ： 代表数据字符； Sc： Sc X，表示有一个字符在此位置； RL： 代表串（游程）的长度，字符重复出现的次数；只有当RL 3时, 才有数据压缩效益。编码时：先判断RL值，再决定是否RLC； 解码时：根据每一X后的码字是否为Sc，再 决定下一个字的含义。 Assumption: Long sequences of identical symbols. Example,RLC压缩效能:取决于数据流中重复字符出现次数、平均游程长度及所采用的编码结构。平均重复长度重复出现10次的压缩