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

第三章 统计编码,数据压缩的类型,可逆的无失真编码,不可逆的有失真编码,大多数计算机文件不允许在压缩过程中丢失信息。利用消息或消息序列出现概率的分布特性，注重寻找概率与码字长度间的最优匹配。,语音、图像或其他物理过程的量化采样。,本章讨论的内容,对于计算机文件,逻辑压缩(Logical Compression),物理压缩(Physical Compression),由数据自身特点及设计者技巧来决定的“压缩表示法”，这种技巧在数据库的数据结构设计中特别有效。,减少计算机文件内部冗余度的统计编码方法。,本章讨论的内容,1,基本原理,2,霍夫曼编码,3,游程编码,4,算术编码,本章内容,5,基于字典的编码,唯一可译码的构造,4.1 基本原理,文件的冗余类型 编码器的数字描述,变长码的基本分析,唯一可译码的存在,压缩必须“透明”，恢复后的文件不允许有任何失真。,文件的冗余度类型,本节所指的冗余度，专指对数据解释一无所知时由数据流中即可观察到的，与具体应用背景无关的冗余。,了解文件的冗余度，意在考虑有针对性的编码方法。,冗余类型,字符分布(Character Distribution),字符重复(Character Repetition),在典型的字符串中，某些符号要比其他符号出现的更频繁，在一份具体的文件中字符不会以等概率出现，字符的分布明显地因文件而异，影响到字符的统计特性。,对于字符重复所形成的符号串常常有更紧凑的编码方式，例如：格式化文件中的空白、报表中的空格串和零串、业务图表中的线图包含成片的空白等。,高使用率模式(High-usage Patterns),位置冗余(Positional Redundancy),这四类冗余度之间有重叠,某些符号序列会以较高的频率反复出现，可用较少的位数表示，从而得到时间和空间的净节约。,若某些字符总是在各数据块中可预见的位置上出现，那么这些字符至少是部分冗余的，例如：光栅扫描图像中含有的竖线、报表文件中的某些字段的记录几乎总是相同的等等。,图3.1 一份零件报表中的冗余度的类型,编码器的数字描述,实际信源的编码过程,消息集X：元素 x 叫做信号单元或消息；,输出集W(代码、码组或码书)：元素 w叫做码字；,码字的符号集A：元素 a 叫做码元或者符号,以符号 A 构建代码 W;建立 XW 对应关系;,编码过程,例3-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,为一模拟信号,该编码器实际就是一个量化器。,编码，就是将不同的消息用 不同的码字来代替，或称为从消息集到码字集的一种映射(分组编码或块码的概念)。,码长:组成码字的符号个数,Li=2,1i3,等长(或定长)编码:采用相同长度的不同码字去 代表一个消息集合中的不同消息;,M元编码(或M进制):取M个不同字符来组成码字,最常用的有二元编码(或二进制)。,变长码的基本分析,对一个消息集合中的不同消息，采用不同长度的码字表示。,不等长(或变长)编码：,采用变长码可以提高编码效率，即对相同的信息量所需的平均编码长度可以短一些。,平均码长：,对P(aj)大的aj 用短码;对P(aj)小的aj 用长码;,当这些信息符号互不相关时,平均码长比等长编码的码长短,1843年，莫尔斯电报码：,表3.1莫尔斯码,莫尔斯码的形成:,首先找到各消息符号的统计特性:,再根据各符号出现的概率分布分 配不同长度的码字:,变长码在编码时要预先知道各种信息符号出现的概率，解码也远比等长码复杂:正确识别码字起点不容易;存在唯一可译性问题;译码实时性问题;匀速输入输出匹配的缓存问题;,定义 3-1,若W 中任一有限长的码字序列(即有限长的一串W),可唯一地分割成一个一个码字,称为单义可译或唯一可译的,W 也叫做单义代码。,单义可译码,例3-2,考虑以下几种变长码：,码A不是一一对应;,码B是一一对应，但构成的序列不能被唯一分割;,码C是唯一可译的;,码D是在码B各码字(除了w1)之前加一个码元“0”,成为唯一可译的,但平均码长增加0.5bit;,码F 即使从尾开始判断,也不是唯一可译的;,问题:什么样的码才是唯一可译的?,码E的译码要求等到收到全部序列,才能从尾开始进行判决,产生了时间上延时和存储容量的增加;,唯一可译码的存在,目前还没有一个明确的判断唯一可译码的准则,只有一个判断不是唯一可译码的准则。,定理 3.1(Kraft不等式),长度为L1,L2,Ln 的 m 进制唯一可译码存在的充分必要条件是:,含义：要求 Li 比较大(码长不能过短)，意味着码字可能的组合数多,不为别的码字的字首。,(3.1-1),Kraft不等式：只涉及唯一可译码的存在问题而并不涉及具体的码。可用来判定某一组码不是唯一可译的，但不能判定是唯一可译的。,不满足Kraft不等式的码肯定不是唯一可译码，而满足的也不一定就是唯一可译的，,但可以肯定若按这样的Li 分配码组，则必存在有一个唯一可译码(也可能不止一个)对应于信源符号。,例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 H(X),则不存在唯一可译的变长码；其中为任一正数。,例3-4,例3.2信源的的熵为:,码长的一种设计为:,L1=1,L2=2,L3=L4=3,满足上述码长设计的码如：例3.2中的码C、E、F（满足Kraft不等式）。,如何做出具体的变长码是变长码的构造问题。,唯一可译码的构造,唯一可译码的基本要求:,码字非续长,对码字序列能做出唯一正确的分割。,充分条件,若W 中任一码字都不是另一个码字的字头；或换句话说,任一码字都不是由另一个码字加上若干个码元所构成，则W 就叫作非续长码字或异字头码(Prefix Condition Code)。,例3.2中:,码A、码B、码D、码E和码F都含有续长码，或同字头码；码C是异字头码。,不过非异字头码也并非一定不是唯一可译，码D和码E就唯一可译；码D：各码组靠“逗号”（码元0）分开；码E：为码C的“镜像”，具有“异后尾”，从 后向前即具有唯一可译性。,异字头条件保证译出的码字是唯一的且具有“即时性”，减少了译码延时。,异字头性质只是码字可分离的充分条件，非续长码也只是单义可译代码集合的一个子集。,图3.3 单义可译码与非续长码,二进制编码,通常可用二进码树(二叉树)来表示各码字的构成,串接的最大枝数为树的节数，图3.4的节数为3。,用码树表述任何一个代码W,异字头条件就成为:,W中所有的码字 wi 均只对应地配置在终端节点上。,图3.5 码C的树结构(异字头码),码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。,异字头码无译码延时，构造简单。,结论：任一唯一可译码，总可以用与各相应码字长度一样的异字头码代替。,异字头码虽然只是唯一可译码的一种，但它具有代表性和普遍意义，在信息保持编码中广泛应用。,长度为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 a5 0.15 a6 0.10 a7 0.01,码长 码 字 2 11 2 10 3 011 3 010 3 001 4 0001 4 0000,编码步骤：,将信源符号概率按递减顺序排列;,将两个最小的概率进行相加，并继续这一步骤，直到概率 达到1.0为止;,在每对组合中的上部指定为1(或0),下部指定为0(或1);,画出每个信源符号概率到1.0处的路径,记下沿路径的1和0;,对于每个信源符号都写出1、0序列，则从右到左就得到霍 夫曼编码。,011a3,根,例3-6的Huffman二进码树,11a1,10a2,010a4,001a5,0001a6,0000a7,例3-6的信源熵为:,霍夫曼编码的平均字长为:,编码效率:,注意：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。,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，无论用定长码还是最佳编码,平均码长至少为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趋向于下限的情况。,把 X 延长到 X 2，假定信源是离散无记忆信源，有图3.7所示 X 2 的最佳编码：,W 2平均长度为:,l2=0.81+0.092+0.093+0.013=1.29 bit/pel,W 2的每一个元素代表两个消息单元,因此平均每一个消息单元的符号个数是:,l2/2=1.29/2=0.645 bit/pel,2=H(X)/(l2/2)=72.7%,编码效率提高到:,把 X 延长到 X 3，有图3.8所示 X 3 的最佳编码：,W 3平均长度为:,l3=0.729+0.08133+5(30.09+0.001)=1.598 bit/pel,W 3的每一个元素代表三个消息单元,因此平均每一个消息单元的符号个数是:,l3/3=1.598/3=0.5327 bit/pel,3=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)才能进行最佳编码。,如果信号继续有关联可供利用，继续延长，会使下限变得很小。,信源编码理论：,给定消息单元集合X、符号集合A和X的概率分布P(X)，可以采用最佳编码，使代码W 的平均长度满足;,如果把X 延长至 X K,则不必考虑信号前后的关联性,就可以是代表一个消息单元的符号个数 l/K 任意接近 下限 H(X)/logm;,如果利用延长信号X K的前后关联,可使下限减小。,具体实现时，如果将信号延长得过长，会使实际设备复杂到不合理的程度。,霍夫曼编码选择模型,静态统计模型,在编码前统计要编码的信息中所有字符的出现概率，然后根据统计出的信息建立编码树，进行编码。,缺点：,对数据量较大的信息，静态统计要消耗大量的时间；必须保存统计出的结果以便解码时构造相同的编码树，或者直接保存编码树本身，而且，对于每次静态统计，都有不同的结果，必须分别予以保存，这要消耗大量的空间（这意味着压缩效率的下降）；静态统计模型统计出的频率是字符在整个文件中的出现频率，往往反映不出字符在文件中不同局部出现频率的变化情况，使用这一频率进行压缩，大多数情况下得不到太好压缩效果，文件有时甚至在压缩后反而增大了。,一种有效的“静态统计模型”的替代方案,如果要压缩的所有信息在分布上存在着共同的特征，使用语言学家事先已经建立好的字母频率表来进行压缩和解压缩，不但不用保存多份统计信息，而且一般说来对该类文件有着较好的压缩效果。,比如我们要压缩的是普通的英文文本，那么，字母 a 或者字母 e 的出现频率应当是大致稳定的。,这种方案除了适应性不太强以外，偶尔还会有一些尴尬的时候。,缺点：,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.,发现什么问题了吗？整段话中竟没有出现一次英文中出现频率最高的字母 e。,对英文或中文文本，有一种比较实用的静态模型：不是把字符而是把英文单词或中文词语作为统计频率和编码的单位进行压缩。,这种压缩方式可以达到相当不错的压缩效果，并被广泛地用于全文检索系统。,自适应模型,无需为解压缩预先保存任何信息，整个编码是在压缩和解压缩过程中动态创建的，而且自适应编码由于其符号频率是根据信息内容的变化动态得到的，更符合符号的局部分布规律，因此在压缩效果上比静态模型好许多。,根据已经编码的符号频率决定下一个符号的编码。,算术编码、字典编码等更为适合采用自适应模型,但是，采用自适应模型必须考虑编码表的动态特性，即编码表必须可以随时更新以适应符号频率的变化。对于 Huffman 编码来说，我们很难建立能够随时更新的二叉树，,霍夫曼码的局限性,局限性:,输入符号数受限于可实现的霍夫曼码表尺寸;,译码复杂度;,需要知道输入符号集的概率分布；,由于码长不等，还存在一个输入与输出的速率 匹配问题。,3.3 游程编码,游程长度(RL:Run Length,简称游程或游长)：,由字符(或信号采样值)构成的数据流中各字符重复出现而形成的字符串的长度。,用二进制码字给出形成串的字符、串的长度及串的位置等信息，以此来恢复出原来的数据流。,游程长度编码(RLC)：,游程编码类型：,变长游程编码,使用位数是固定的，即RL位数是固定的，如果灰度连续相同的个数超过了固定位数所能表示的最大值，则进入下一轮游程编码；,定长游程编码,对不同范围的游程采用不同位数的编码，即表示RL位数不固定。,基本的游程编码,基本的RLC压缩方法：,最初出现在 IBM 3780 BYSYNC(Binary Synchronous Communication)通信协议中。,基本的RLC数据结构：,图3.9 基本的RLC数据结构,其中,X：代表数据字符；,Sc：Sc X，表示有一个字符在此位置；,RL：代表串（游程）的长度，字符重复出现的次数；,只有当RL 3时,才有数据压缩效益。,编码时：先判断RL值，再决定是否RLC；,解码时：根据每一X后的码字是否为Sc，再 决定下一个字的含义。,Assumption:Long sequences of identical symbols.Example,RLC压缩效能:,取决于数据流中重复字符出现次数、平均游程长度及所采用的编码结构。,表3.2 基本的游程编码压缩比,二值图像的游程编码,二值图像,仅有黑(“1”代表)、白(“0”代表)两个亮度值的图像。,经扫描仪得到的气象图、工程图、地图、线 路图等；文字组成的文件图像；灰度图像经过位平面分解或抖动处理后 的图像。,最常用的传输方式：传真,二值图像编码也往往指数字传真编码。,二值图像的游程编码,数据字符 X=白，黑,对二值图像每一扫描行：,白像素游程（白长）,黑像素游程（黑长）,对不同长度的白长和黑长，按其出现概率的不同分别配以不同长度的码字。,RLC利用多个像素之间的相关性，可得到较低的码率下限。,二值图像的RLC的两种方式,不分白长和黑长，只根据长度进行编码,对白长和黑长分别编码(前CCITT建议),由于在实际图像中,白长和黑长的概率分布各异,此方法不是很有效;,其最低比特率 满足:,(3.3-1),其中：PW和PB分别是白像素和黑像素出现的概率;lW和lB分别是白长和黑长的平均像素数(平均长度);hWB为每个像素的熵值。,编码过程：,先对图像进行统计分别得出白长为 i 的 概率 PiW 和黑长为 i 的概率 PiB，,然后根据霍夫曼原则按RL出现概率来分 配码字。,二值图像的RLC实为霍夫曼码的具体应用,由于各种 RL 的出现概率在行间、页间都不相同，且为求得概率，需要存储数据并做统计计算，难以实时编码,CCITT的T.4建议:推荐8幅标准传真样张为统计依据,根据各种RL的出现概率编出霍夫曼码表，称为改进型霍夫曼编码(MHC)。,MH编码规则:(见表4.7),RL=063，用一个相应的结尾码表示;,RL=641728，用一个组合基干码加一个补充结尾码；RL(白)=128,补充结尾码为0(白)=00110101,其编码为:10010|00110101 RL(白)=129,补充结尾码为1(白)=000111,其编码为:10010|000111,规定每行都从白游程开始，若实际扫描由黑开始，则 需在行首加零长度白游程；每行结束要加同步码EOL。,游程编码的局限性,对二值图像最为有效，但对数据文件就不那 么显著，而对于课文实质已无使用价值;,压缩字符与数值混合序列比较麻烦，要求区分 计数字段和常规字符；,需要较大容量的缓冲和较低误码的优质信道。,连续色调图像的二维编码,连续色调图像的二维编码,原码，若ZZ（k）0,反码，若ZZ（k）0,由ZZ（k）之间的零游程计数值得ZRL=NNNN，SSSS在中已知，查表4.9/4.10可得NNNN/SSSS码字；,尾码=ZZ（k）的B位,综合和可得AC系数编码“NNNN/SSSS+尾码”,若ZZ=5，B=3，得原码101若ZZ=-2，B=2，得反码01,连续色调图像的二维编码,若最后一个“零游程/非零值”中只有零游程，则直接发送块结束码字“EOB”结束本块，否则无需加EOB码。,一般情况NNNN=ZRL=015。若ZRL15，则先用ZRL=16即NNNN/SSSS=F/0得到码字，再对ZRL=ZRL-16继续编码，得到NNNN/SSSS码字，结合尾码就可得AC系数编码。,连续色调图像的二维编码,例题：设某亮度图像块的量化系数矩阵按Z形扫描得到：K 0 1 2 3 4 5 6 7 8 930 31 3263ZZ（k）12 5-2 0 2 0 0 0 1 0-1 0,而其前一亮度块的量化DC系数也为12，写出编码过程。,解(1)DC系数编码因为DIFF=0，查表4.2得其码字即为前缀码“00”。(2)AC系数编码第一个非零值ZZ(1)=5，查表4.8得SSSS=3，根据规则得尾码为原码101；与ZZ(0)间无零系数，故NNNN=0，NNNN/SSSS=0/3查表4.9码字100；从而ZZ(1)=5的编码为“NNNN/SSSS+尾码”即100+101得100101。第二个非零值ZZ(2)=-2，SSSS=2，尾码为反码01；又与ZZ(1)无零系数，所以NNNN/SSSS=0/2查表得码字为01；从而ZZ(1)ZZ(2)编码为0101。ZZ(3)ZZ(4)编码为1101110。ZZ(5)ZZ(8)编码为1110101。,连续色调图像的二维编码,例题：设某亮度图像块的量化系数矩阵按Z形扫描得到：K 0 1 2 3 4 5 6 7 8 930 31 3263ZZ（k）12 5-2 0 2 0 0 0 1 0-1 0,而其前一亮度块的量化DC系数也为12，写出编码过程。,ZZ(31)=-1，查表得SSSS=1，尾码为反码0；由于NNNN=30-9+1=2215，故先编ZRL=16，NNNN/SSSS=F/0查表得码字；此后NNNN=22-16=615再编码，NNNN/SSSS=6/1查表得码字为1111011；所以ZZ(9)ZZ(31)编码为。此后无非零值，最直接用一个EOB结束本块，查表得码字为1010。(3)综合前面(1)和(2)，可知该图像块的编码为 00 100101 0101 1101110 1110101 1010(4)原始图像块要用8*8*8=512位，压缩后为49位，压缩比为10.45:1。,游程编码总结,3.4 算术编码(Arithmetic Coding),3.4.1 多元符号算术编码原理 3.4.2 自适应模型算术编码 3.4.3 二进制算术编码 3.4.4 二进制算术解码 3.4.5 算术编码评价,算术编码定义,它是一种非分组编码算法。它是从全序列出发，采用递推形式的连续编码。它不是将单个的信源符号映射成一个码字，而是将整个输入序列的符号依据它们的概率映射为实数轴上区间0 1)内的一个小区间，再在该小区间内选择一个代表性的二进制小数，作为实际的编码输出。,例如算术编码对某条信息的输出为 1010001111，那么它表示小数 0.1010001111，也即十进制数 0.64。,85,3.4.1 多元符号算术编码,1)码字刷新：C(sai)=C(s)+P(ai)A(s)2)区间刷新：A(sai)=p(ai)A(s),设输入符号串s取自符号集S=a1,a2,a3,am，p(ai)=p1,p2,p3,pm，s后跟符号ai扩展成符号串sai，算术编码的迭代关系为:,符号累积概率：初始条件：,一、算术编码,多元符号算术编码,当处理ai时，区间A(s)宽度根据ai出现概率p(ai)而变窄，符号序列越长，相应的子区间越窄，编码的位数越多。符号串每一步新扩展的码字C(sai)都是由原符号串的码字C(s)与新区间宽度A(sai)的算术相加，“算术码”由此得名。,算术编码在传输任何信号ai之前，信号的完整范围是,多元符号算术编码,例题1：设某信源取自符号集S=a,b,c,d,e,!，!表示编码结束，各符号概率和初始子区间如下，设待编码的为“dead！”，编码器和解码器的初值区间0，1),表1,多元符号算术编码,编码第一个字符d时,编码第二个字符e时,多元符号算术编码,编码第三个字符a时,依此类推，结果如下表,多元符号算术编码,最后在区间0.61804,0.6184)中任取一个代表性的小数，譬如0.6183，转化成二进制小数0.1001111，最后编码输出1001111。,91,多元符号算术编码,编码,多元符号算术编码,二、算术解码,解码器首先输入符号及区间，重构表1.然后输入其余码字。比如第一个数字是“6”，解码器立即知道是形如0.6的数字。该数字位于d的子区间0.4,0.7)中，所以第一个符号就是d。然后从该数字中减去d子区间的低端值0.4，再除以d子区间宽度0.3，以消除符号d对码字的影响。结果是0.727667，告诉解码器下一个符号是e(因为e的子区间是0.7,0.9)。,93,为了从码字中消除符号x的影响，解码器执行 Code:=(Code-LowRange(x)/Range的操作，Range是符号x的子区间宽度。表2总结了本例解码步骤。,表2 算术解码过程,94,二进制算术编码,一、基本工作原理设编码初始化子区间为0，1)MPS与LPS分配如图 大概率 Pe MPS（Most Probable Symbol）小概率 Qe LPS（Least Probable Symbol）Pe=1-Qe 设置（C，A）,令C=0 A=1 C 寄存器的值为子区域的起始位置 A 寄存器的值为子区域的宽度,95,96,例题1:设输入信源为11011111，对其编码0为 LPS,Qe=（0.001）b;1为MPS,Pe=（0.111）b初始状态：C=0,A=11)1 为MPS C=C+AQe=0+1 0.001=0.001 A=APe=1 0.111=0.111,3.4.2 二进制算术编码,97,2)1 为MPS C=C+AQe=0.001+0.111 0.001=0.001111 A=APe=0.111 0.111=0.110001,3.4.2 二进制算术编码,3)0 为LPS C=C=0.001111;A=A Qe=0.110001 0.001=0.000110001,98,头 0.0101尾 传送码字为 0101,编码过程,3.4.2 二进制算术编码,99,算术编码原理图,100,二进制解码：按 Qe Pe分成两个子区间，判断被解码的码字落在哪个区间，并赋予对应符号；设 c=（0.0101）b 是被解码的值初始值 A=1 Qe=0.001当c落在0-QeA之间，解码符号为 D=0；C=C；A=QeA；当c落在Qe A-A之间，解码符号为D=1；C=C-QeA；A=A（1-Qe）,3.4.3 二进制算术解码,101,1）C=0.0101 落在Qe A-A之间，解码符号为D=1 C=C-QeA=0.0101-0.001=0.0011 A=A（1-Qe）=0.111,2）C=0.0011 落在Qe A-A之间，解码符号为D=1 C=C-QeA=0.0011-0.000111=0.000101 A=A（1-Qe）=0.1110.111=0.110001,3）C=0.000101 落在0-QeA之间，解码符号为D=0 C=C=0.000101 A=AQe=0.1100010.001=0.000110001,3.4.3 二进制算术解码,102,算术解码原理图,103,3.4.4 算术编码评价,算术编码是一种非分组编码，编码方案众多，压缩效率最高。当信源符号概率接近时，建议用算术编码。,信源的每一个符号对应0，1）的一个子区间，该子区间的长度等于对应符号的出现的概率。,算术编码把信源X的任一给定序列和0，1）的一个子区间联系在一起，该子区间的长度等于这个序列的概率。,算术编码比霍夫曼编码复杂，需要缓冲存储器，硬件实现难；,比分组码的误差扩散更严重，要求有高质量的信道，或采用检错重发的方式；,概率大的符号对应区间大，描述所需比特少。随着输入序列长度增加，平均编码所用比特数趋向信源熵。,104,3.5 基于字典的编码,以Huffman编码为代表的压缩模型都是基于对信息中单个字符出现频率的统计而设计的，直到 70 年代末期，这种思路在数据压缩领域一直占据着统治地位。在我们今天看来，这种情形在某种程度上显得有些可笑，但事情就是这样，一旦某项技术在某一领域形成了惯例，人们就很难创造出在思路上与其大相径庭的哪怕是更简单更实用的技术来。,3.5.1 LZ算法,1977 年，Jacob Ziv 和 Abraham Lempel发表了论文顺序数据压缩的一个通用算法。1978 年，他们发表了该论文的续篇通过可变比率编码的独立序列的压缩。这两篇论文提出的两个压缩技术被称为 LZ77 和 LZ78算法。它们的思路和字典法颇为相似，因此，人们将基于这一思路的编码方法称作字典式编码。字典式编码不但在压缩效果上大大超过了哈夫曼编码，而且，对于好的实现，其压缩和解压缩的速度也异常惊人。,LZ77算法,LZ77 算法又称为“滑动窗口压缩”，如下图：,LZ77 算法的基本流程,重复进行以下处理，直至所有数据处理完毕：1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，2、如果找到，输出三元符号组(off,len,c)，其中off为窗口中匹配字符串相对窗口边界的偏移，len为可匹配的长度，c为下一个字符；将窗口向后滑动len+1个字符。3、如果未找到，输出三元符号组(0,0,c)，其中c为下一个字符；将窗口向后滑动 1个字符。,假设窗口的大小为 10 个字符，我们刚编码过的 10 个字符是：abcdbbccaa，即将编码的字符为：abaeaaabaee。,窗口,首先发现，可以和要编码字符匹配的最长串为 ab(off=0,len=2),ab 的下一个字符为 a，我们输出三元组：(0,2,a)。,a,b,a,LZ77 算法举例,现在将窗口向后滑动3(2+1)个字符，窗口中的内容为：dbbccaaaba，剩余字符为eaaabaee，下一个字符 e 在窗口中没有匹配，我们输出三元组：(0,0,e)。,LZ77 算法举例,又将窗口向后滑动 1 个字符，其中内容变为：bbccaaabae。这时发现，要编码的 aaabae 在窗口中存在(off=4,len=6)，其后的字符为 e，可以输出：(4,6,e)。,LZ77 算法举例,最后又将窗口向后滑动 7 个字符。这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。,LZ77 算法举例,LZ77 算法的解压缩,LZ77 算法的解压缩的过程十分简单，只要我们像压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符 c 输出（如果 off 和 len 都为 0 则只输出后继字符c)，即可还原出原始数据。,LZ78算法,LZ78算法的基本思路与LZ77算法类似，也是利用已经处理过的编码信息，但它发生匹配时，不是保存一个三元组，而是一个二元组：匹配位置和不匹配的第一个字符。同时，还要将这个字符串保存到内存中，为此，它需要一个不断增长的编码字串表（字典）。与LZ77相比，LZ78的最大优点是在每个编码步骤中减少了字符串比较的数目，而压缩率与LZ77类似。,如对符号串“ababcbabaaaaaaa”编码，需要的字典：,LZ78算法,LZ78算法的框架,void LZ78(void)将字典D置空;while(还有字符未处理完)current=0;goon=1;read(w);while(goon)if(w D)current=#w;read(k);w=w+k;else goon=0;append(D,w);/*将字符串w放到字典的尾部*/w=last_char(w);/*取字符串w的末尾字符*/write(current,w);/*输出匹配位置和不匹配字符*/,#w表示w在字典中的序号,LZW算法,LZ78算法很难一次匹配到更长的字符串，而且，它所保存的信息量仍然有冗余，因为如果每一个字符都一定能匹配成功的话，也可以不需要保存匹配不成功的字符。LZW算法的基本思路就是要尽量“拉长”这些串，为此，它将LZ78算法中的每一个被分割的子串的最后一个字符作为下一个子串的开始。当然这么做肯定会增加字典的长度。而且需要先将所有可能出现的单字符先放到字典中以保证单字符一定能匹配成功。WinZIP，WinRAR等压缩工具及GIF、PNG等文件格式都是LZ系列算法的受益者。,LZW算法的框架,void LZW(void)将所有单字符放入字典D中；read(w);while(还有字符未处理完)read(k);if(w+k D)w=w+k;else write(w在字典中的序号);append(dictionary,w+k);w=k;,对于字符串“ababcbaaaaaaaa”，得到的字典如右：,原字符串,压缩码,序号,压缩后的编码为：a,b,c+1,2,4,3,5,1,9,10,单字符可事先约定，从而无需传输。,LZW解压缩算法,void unLZW(void)将所有单字符放入字典D；orign_len=length(D);i=orign_len+1;while(还有编码未处理完)read(k);ch=first_char(Dk);/*D中第k行首字符*/if(i orign_len+1)Di 1=Di 1+ch;Di=Dk;/*生成本行字符串的前一部分*/write(Dk);/*输出还原后的数据*/i:=i+1;,压缩码为：1,2,4,3,5,1,9,10,首先将单字符放入字典。,orign_len=length(D)=3;i=orign_len+1=4;read(k);k=1;ch=first_char(Dk)=a;i orign_len+1 D4=D1;i=i+1=5,a 4,LZW解压缩算法,压缩码为：1,2,4,3,5,1,9,10,a 4,i=5read(k);k=2;ch=first_char(Dk)=b;i orign_len+1 Di 1=Di 1+ch，即，D4=ab;D5=D2=b;i=i+1=6;,b,b 5,LZW解压缩算法,压缩码为：1,2,4,3,5,1,9,10,ab 4,b 5,i=6read(k);k=4;ch=first_char(D4)=a;i orign_len+1 Di 1=Di 1+ch，即，D5=ba;D6=D4=ab;i=i+1=7;,a,ab 6,剩下的以此类推。,LZW解压缩算法,例4-15,设有输入字符流“ababcbababaaaaaaa”，试对其进行LZW编码。,习题与思考题,习题：4.2思考题：4-12,