数;据压缩技术

数据压缩技术主讲戴永教材DavidSalomon,数据压缩原理与应用,北京:电子工业出版社,20032023/2/6

信息工程学院戴永2引言总思路通过去掉源文件原始数据中的冗余度来压缩数据.数据压缩:把输入数据流变换成较小的输出数据流.输入数据流:源流或原始数据输出数据流:输出流或压缩流流:文件数据压缩的实现:把低效(长的)表达方式改为高效(短的)表达方式.人们常用数据的低效表达方式是因为方便处理.比如说ASCII码用7位定长码表示,人们都遵循同一标准而给工作带来方便.但实际上ASCII码中各字符使用频度差别很大,因而可采用不同长度的的代码来表示,即形成变长码.2023/2/6

信息工程学院戴永3变长码:常用的字符用短码,不常用的用长码.SP理论:S(simplicity):简洁P(power):能力即在保证实现功能的前提下,尽可能地去掉不必要的复杂度和多余的信息.实现SP理论的可能性为(1)把各类计算和形式推理视为用模式匹配、联合及搜索来进行信息压缩有助于理解。（2）找到并去除冗余的过程总可以在基础上理解为搜索互相匹配的模式，把任何模式的重复实例合并。2023/2/6

信息工程学院戴永4数据压缩领域的专业名词（1）压缩器（编码器）：压缩输入流中的原始数据，建立由低冗余度数据构成的输出流的程序。（2）解压缩器（解码器）：进行以上相反转换的程序（有时同时指编码器和解码器）。压扩：压缩/扩展（3）原始输入流：未编码、原或原始数据（4）输出流（最末压缩流）：已编码或已压缩的数据。（5）位（比特）流：已压缩的文件。（6）非自适用压缩：为某种专用传送而设计的压缩方法，压缩其他数据效果很差。（7）自适用压缩：通过考察原始数据而自动修改运算方法、参数和码表等以完成相应的压缩。（8）半自适用压缩：按以下两步进行压缩称为半自适用压缩，

STEP1读输入流，统计待压缩数据的信息；

STEP2根据第一步信息设定参数进行实际压缩。2023/2/6

信息工程学院戴永5有损压缩：通过丢失一些信息来得到更好的压缩。解压时结果与原始的数据流不完全相同。此方法多用于图像、电影、声音等的信息压缩。无损压缩：完全可以恢复原始流的压缩。该方法主要用于计算机程序文件的压缩。有的文本文件可视情况进行有损压缩。对称压缩：压缩器和解压器使用基本相同的算法，但处理方向相反。该方法适用两方文件数相同的的常规压缩传送工作。非对称压缩：压缩器或解压缩器承担的工作量比另一方大得多。例：当需把某文件进行压缩存档供频繁解压、使用时，则可让压缩器的算法复杂，而让解压器运行快捷。仅作备份时更是这样。通用压缩方法:压缩器和解压缩器不需要输入流的统计特性的压缩方法.两大类压缩方法:(1)按流模式工作,即有序输入一个或多个字节进行压缩,直到遇到文件结尾标志.(2)按块压缩,每块独立编码.此时块的长度是影响该方法性能的重要参数,可由用户控制.物理意义的压缩:不考虑数据含义,只从位的角度进行数据压缩,即只是把一个位流转换成另一个更短的位流.这种压缩只要搞清楚输出流是怎样被编码的便可.2023/2/6

信息工程学院戴永6逻辑压缩:通过对源流中的各项数据进行统计,采用不同长度代码对数据进行编码.该方法对特定数据类型有好效果.表示压缩性能参数:(1)压缩比:压缩比=输出流量/输入流量单位:bpb,bpc,bpp压缩比>1,为负压缩或膨胀或扩展;压缩比=1,压缩器未起作用;压缩比<1,压缩器起到压缩作用.比特率:主指bpb,bpc.表明压缩之目的为用低比特率来表示任何给定的数据.比特预算:对一个压缩文件规定其中多少(以百分率计算)为符号的变长码字,多少为用于表格编码.给符号之外内容留多少长度称为比特预算.例留10%长度用于某些表格编码,则表的比特预算为10%.(2)压缩因子:压缩比的倒数压缩因子=输入流量/输出流量压缩因子>1,压缩器起到压缩作用;压缩因子=1,压缩器未起作用;压缩因子<1,扩展.2023/2/6

信息工程学院戴永7(3)压缩空间度量:用100×(1-压缩比)度量压缩程度.当此值为30,表明压缩后空间节省30%.(4)像素压缩前后的bpp比较:显示像素压缩的有效程度.(5)压缩增益:100Ln(参考大小/压缩后的大小)参考大小:输入流的量或某种标准无损压缩方法所产生的输出流的量.(6)压缩速度:每字节多少周期(CPB).用硬件来压缩时此指标很重要.(7)均方差(MSE)、峰值信噪比（PSNR）：用于度量有损压缩图像、电影所引入的失真。2023/2/6

信息工程学院戴永8第一章基本技术1.1直观压缩压缩与可靠性的对立统一:减少冗余度可实现数据压缩,但同时也降低了可靠性.如果为了可靠性增加校验位却又增加了代码长度即增加了冗余度.尽管如此,人们更早、更多考虑的是压缩，不过一般为直观压缩。以下是直观压缩的几个例子。1.1.1盲文中的压缩图1.1为26个盲文字母表.每一个字母用6点组合表示,每一个点按两个状态取值,6个点可形成64个组合状态.而26个字母仅为其中一部分,另外再加上一些数字和符号,还多出一些组合状态.对此又将多出状态对应一些常用单词和使用频率很高的字母串,如表1.2.将多出状态对应一些常用单词和使用频率很高的字母串,是盲文中体现出来的压缩思想.2023/2/6

信息工程学院戴永91.1.2不可逆文本压缩通过简单地舍弃一些信息来压缩文本,解码时不能还原,称之为不可逆文本压缩或紧缩.1.1.3特定的文本压缩主要针对无损压缩(可恢复).以下是一些特定压缩例子.(1)文本中有很多空格的情况:比如Herearesomeideas

用0表示非空格,用1表示空格,该句可进行如下的压缩表示0000100010000100000Herearesomeideas一个空格占8位,而8个0,1占一个字节,总的来说是压缩了.(2)以7位ASCII码代替8位ASCII码,称之为紧缩,压缩比为7/8(3)选择合适的数据长度进行压缩如果采用40个字符集元素(26个字母,10个数字,1个空格,3个符号)构成文本.为适用压缩,将文本按3个字符为一段进行分割,则一段字符可能出现的组合状态为403=64000.2023/2/6

信息工程学院戴永10表达1段3字符需3个字节共24BIT.而403<216=65536,即16BIT的组合状态多于403的组合状态,用此方法压缩,压缩因子可达24/16=1.5(4)选用合适的代码形式进行压缩,将8位ASCII码的文本根据其文本中所含字符的范围可采用少位代码实现压缩如果仅含大写字母,数字,及一些标点符号可选用老式6位CDC码(表1.3),也可采用老式5位Baudot码(表1.4).(5)根据数制压缩,比如两个10进制数可压缩在一个字节中.2023/2/6

信息工程学院戴永11(6)按字典结构方式压缩:比较前面单词,前位有N个相同的字母,就用N打头,后跟不同的字母,如aaaardvark1ardvarkabaft1baftabandon3ndonabandoning7ingabated3tedabate5abbot2bot2023/2/6

信息工程学院戴永121.2游程编码如果数据项d在输入流中连续出现n次,则以单个字符对nd替换n次出现者.称n个连续出现的数据项为游程,这种数据压缩方法称为游程编码,常用RLE表示.1.3RLE文本压缩对重复字段采用3符号标识法:(1)重复提示符,比如@,#等;(2)游程长度参数或重复次数,若用一个字节表示,最大长度可为255个重复字;(3)重复字符.以上三部分合称为重复因子.可见要获得压缩效益,重复字符应在3个以上.2023/2/6

信息工程学院戴永13重复因子替代法有如下缺点:(1)普通文本中并没有多少字符重叠.重复较多的为空格,点划线,星号等.(2)要单独占用一个符号,该符号在被压缩的文本中不能出现.(3)压缩长度有限,如255或258个重复字符.重复因子压缩举例以@为压缩标识符,重复长度从1开始计数例1.有如下注释文本;***************************************;input:no;output:no;***************************************写成RLE压缩文本如下;@39*Enter;input:noEnter;output:no

Enter;@39*2023/2/6

信息工程学院戴永14输入流为102个字节,输出流为30个字节,压缩比30/102*%=29.4%即输出被压缩70%多,压缩效率很高.例2.被压文本为6.allistoowell压缩输出的文本为6.A@2list@2o

we@2l输入文本为18个字节,输出文本21个字节,结果不但没有压缩反而扩大.可见重复次数少于3时不适宜采用此压缩方法.例3.被压缩文本为25,25,25,25,25,25,30,30,30,30,30,30,30压缩输出的文本为@325@430以上表达方式将长度减3,这是从使用此方法的最低要求出发,因而重复长度可达258.2023/2/6

信息工程学院戴永15RLE文本压缩算法:设C为字符数目计数单元,设R为重复计数单元,C←0,R←0从文本缓冲区顺序读1个字符到CH单元是文本结束符否?结束YNC

←C+1C=1?YSC←CHCH为当前字符存放单元,SC为比较或匹配字符存放单元.NSC=CH?YR←R+1R<4?按R值将SC中字符写入压缩文件YNN在压缩文件中写压缩格式内容(占3个字节)R←0,SC←CH2023/2/6

信息工程学院戴永16RLE文本解压缩算法流程清压缩标志顺序读文本字符是文本结束符否?结束YN压缩标志清除否?NYChar=`@`?置压缩标志Y输出字符读入N,输出N个N后相同字符以上算法表明当输入流发现至少3个连续相同的字节时,压缩器在输出流中加入3个字节的压缩标志段.当解压器读到压缩标志段特定的标志符号时,将3字节还原成未压缩的符号串.2023/2/6

信息工程学院戴永17RLE的压缩比概念设待压缩的字符串长度为N,字符中包含M次重复,每次重复的平均长度为L.M次中的每一次重复可用3字节代替(提示字符,计数值,数据),压缩后的字符串的长度为

N-M*L+M*3=N-M(L-3)压缩因子为N/(N-M(L-3))例1.N=1000,M=10,L=4压缩因子为1000/(1000-10(4-3))=1.01例2.N=1000,M=50,L=10,压缩因子为1000/(1000-50(10-3))=1.538以上例子表明,当重复的平均长度L越大,压缩因子就越大,压缩效果越好.MNP5方法为游程和自适用编码结合而成,其标识符占4字节.2023/2/6

信息工程学院戴永181.1.3相关编码当数据是一串差不多的数,或是由彼此相似的字符串构成时,可以用相关编码进行压缩.例1.当某电机转速稳定在额定速度1000转/分时,假定容许偏差为±3转/分,测速器一般测出的速度为1000,999,998,998,999,999,1000,1000,1001,1001,1002,1002,1002,1002,1003,1003,1003,1002······,可以压缩为如下的相关编码1000,-1,-1,0,1,0,1,0,1,0,1,0,1,0,0,0,-1,······,例2.当某系统从一个状态突跳到另一种状态时,假定检测出的参数为2023/2/6

信息工程学院戴永19110,115,121,119,117,117,115,115,114,118,122,126,129,130,200,203,205,207,209,211,214,217,220,223,227,228,231,······,压缩为相关编码为110,5,6,-2,-2,0,-2,0,-1,4,4,4,4,3,1,200,3,2,2,2,2,3,3,3,3,4,1,3,······,以上例子表明,当系统为某一稳定状态工作时,采样子系统只要给出第一个值或从规定的额定值开始传送,后跟差分值,便可对采样值进行高效压缩.另外由于差分值常常较小,可以将两个差分值合放于1个字节,可进一步提高压缩效率,如1000,(-1,-1),(0,1),(0,1),(0,1),······2023/2/6

信息工程学院戴永201.4RLE图像压缩RLE是压缩图形图像数据的常用方法当图像为黑白图像时每个像素只需一个二进制位表示,当前的位状态要么表示黑,要么表示白.如果一个像素用多位2进制表示,则可使像素显现出黑白的灰度或色彩.以下用位图(像素+灰度)形式讨论RLE的压缩原理图像按位图存储的结构如下图所示。位图是图像输入流···································································································································································································第1个位图像素最后1个位图像素图像输入流从第一个位图像素开始顺序进入压缩器2023/2/6

信息工程学院戴永21用RLE压缩图像的基本依据是：在位图中随机选择一个像素，其相邻像素色彩相同的可能性很大，因此压缩器逐行扫描位图，搜索色彩相同像素的游程。压缩流的大小取决于图像的复杂度：细节越多，压缩效果越差。注意如下的两个现象（1）一条扫描线从均匀区域（在此区域相邻像素的灰度基本无突变）边界的一点进入，通过另一点出来，并且这两点未被其他扫描线占用，根据统计，横穿一块均匀区域的扫描线数目粗略等于该区域周长（以周边像素数目计算）的一半。（2）对于均匀区域，每一条扫描线向输出流提供一个数据，则该块均匀区域的压缩比大致等于：周长的一半/区域内总的点数。比如压缩一个3*3均匀区域点阵，压缩比为4/9，其提供的压缩数据为3个。例1.设有一幅24*24的2值位图,其像素分布如图所示,压缩器从白像素开始.2023/2/6

信息工程学院戴永22第1行压缩结果为:0,24第2行压缩结果为:0,6,1,4,2,11第3行压缩结果为:0,1,2,2,2,3,2,3,5,4第4行压缩结果为:0,5,3,2,3,7,4第8行压缩结果为:2,2,2,3,2,2,9,2第24行压缩结果为:0,242023/2/6

信息工程学院戴永23该图像文件从压缩器输出的结果为0,24,0,6,1,4,2,11,0,1,2,2,2,3,2,3,5,4,0,5,3,2,3,7,4,········，2,2,2,3,2,2,9,2，········，0,242值位图输出流的解压原理：按约定的首像素颜色开始，依次变色，变色长度由当前对应的数据确定，每输出一个确定颜色的像素序列，像素数目累加该长度数据，当累加的像素数目等于图域列数，则此列像素解压完毕。重复上一行解压过程，直到被解压行数与图域行数相同，则整个图域解压完毕。RLE进行灰度压缩时，连续的同一亮度的像素用（游程，像素值）的对偶参数表示或编码。游程通常占一个字节，可长达255个同一亮度数据。像素值的位数与灰度级有关，一般为4~8位。例2.具有灰度图像的压缩.一个8位灰度序列为12,12,12,12,12,12,12,12,12,35,76,112,67,87,87,87,5,5,5,5,5,5,1,······的位图，经压缩后输出为9，12，35，76，112，67，3，87，6，5，1，

·······游程参数与灰度值的区别方法如下2023/2/6

信息工程学院戴永241).如果图像限制为只有128级灰度,可以用每个字节中的1位来表示该字节是灰度值还是计数值,比如说以每字节的D7来标识,令D7=0,该字节低7位表示计数值,=1表示灰度值.按此法上述输出流可写为9，12+128，35+128，76+128，112+128，67+128，3，87+128，6，5+128，1+128，

·······2).如果灰度级为256,可降为255,留出一个状态标识(计数值,灰度)对偶参数.假如以255作标识参数,则上述输出流可写为255,9，12，35，76，112，67，255,3，87，255,6，5，1，

·······3).将输出流按8个数据一组分段,每段前加一个标识字节,标识字节中从左到右或从D7到D0分别依此对应标识字节后的8个参数,某参数为计数值,其在标识字节中对应的标识位为1,反之为0.按此法,上述输出流可写为10000010,9，12，35，76，112，67，3，87,100······,6，5，1，

·······当然也可以反过来标识.此方法给输出流的总长度增加了1/8的长度.2023/2/6

信息工程学院戴永254).对完全不同的连续像素进行标识.将连续像素长度用正数表示,而完全不同的连续像素则用负数表示.如果有M个完全不同的连续像素,则用-M置于这M个完全不同的连续像素之前.按此方法,上述输出流可写为9，12，-4,35，76，112，67，3，87，6，5，?,1，

·······“?”看1的性质取值,如果1是完全不同的连续像素之首,“?”取负,如果是灰度则取正.如果遇到形如(P1,P2,P2)的重复序列将出现扩展的现象,因为这种序列的标识结果为(-1,P1,2,P2),即由3个字节变成了4个字节.不过如果1个像素3字节(彩色),则也略有压缩效果,即(P1,P2,P2)占9字节,压缩输出为(-1,P1,2,P2),占1+3+1+3=8字节.以上各方法使用时还有三点要注意<1>由于游程不能为0,在输出流中可写入“游程-1”,(3,87)表示有4个87灰度的游程,此方法1个字节表示的游程可达256.<2>对于彩色图像,通常将像素存为3字节,依此代表红绿蓝3基色的强度.2023/2/6

信息工程学院戴永26假定有如下的彩色像素序列(171,85,34),(172,85,35),(172,85,30),(173,85,33),(173,86,34),····将3色分离形成3基色序列为红序列：171，172，172，173，173，·········绿序列：85，85，85，85，86，·············蓝序列：34，35，30，33，34，············显然3基色序列可分别进行RLE编码，表明任何用于灰度图像压缩的方法同样可用于彩色图像压缩。<3>位图图像最好按行编码压缩,每行结束加上EOL(END-OF-LINE)作标志符.采用每行加标志符的最大优点是可实现对图像有选择的压缩和解压.尤其是解压,可以根据用户的要求进行图像重构,如图所示,恢复一幅图像可以先解码和显示2,6,10,14,········，然后再解码和显示3，7，11，15，19，·······2610142023/2/6

信息工程学院戴永27按行单独编码的主要优点（1）可方便实现较快了解一幅图像的大致情况，以确定对该幅图像的处理方案。（2）可实现在一幅压缩的位图中只抽取其中一部分的目的，如从K行到L行。（3）可方便实现两幅压缩图像的合并，而不必先将它们先解压后合并。按行单独编码的主要缺点（1）压缩流中每一行要增加行的起始信息标志字节（书中为每行增加4字节的起始信息），从而扩大了压缩流的长度。（2）如果图像变动，则必须重算全部游程，即互动性差。（3）对于复杂图像不但不能压缩还有可能扩大。如果仅采用按行扫描压缩，对于具有很多垂直线的图像，则可能产生很多的短游程。短游程越多压缩效果越差。2023/2/6

信息工程学院戴永28为获得较好的RLE压缩效果，通常的RLE压缩器包含3个方向扫描的压缩环节输出流选择其中结果较好的。3个方向扫描包括按行，按列，按锯齿形，如图所示。261014261014261014按行扫描按列扫描按锯齿扫描2023/2/6

信息工程学院戴永291.1.4有损图像压缩有些图像并不需要其非常细致的内容,而只需要一个大概;有些只需知道图像的轮廓便可等.如一些模式识别图案,X射线图案等,这些图案压缩可采用忽略短游程的方法,即可获得好的压缩比,其效果也可接受.忽略短游程意味着压缩过程中要损失一些信息.用此方法压缩图像称为有损图像压缩.可以忽略的游程长度,一般由用户自行指定,比如用户指定最长可忽略的游程长度为3,则游程为1,2,3的相同像素将与其邻点合并.例.假定一幅二值图像经无损游程压缩输出序列为6,8,9,10,2,3,1,3,4,3,10,2,1，3，·········以用户指定可忽略游程长度为3，进行有损图像压缩，相应的输出流为6，8，9，10，6，10，10，6，·········6=2+3+1，10=3+4+3，6=2+1+3除了游程长度为3外,游程数目也是3,此方法尤其适用高分辨率大图像压缩.2023/2/6

信息工程学院戴永301.4.2有条件的图像RLERLE的一种改进形式:设有一幅2n级灰度的图像,在考虑每一个像素的灰度时同时考虑邻近像素也用n位代码表示灰度,然后以邻近像素灰度的出现而使本像素灰度出现的条件概率为依据,将像素的灰度转换为具有规定游程的n位代码.扫描完一行后,将一行中所有列的n位代码连成一长串,计算游程,把游程编为前缀码,写入压缩流.条件概率的常见预测模式如图所示XAB以A,B作为条件,X出现的概率为P(X|A,B),X是当前像素,A及B是X的两个邻点(不必是最靠近的).A,B,X的灰度到n位具有规定游程代码的转换,是通过条件概率表来完成的.下面以n=4为例进行讨论.4位2进制码的16种组合是0000,0001,0010,0011,··········1110，11112023/2/6

信息工程学院戴永31将16个代码按游程分类：1个游程有：0000，1111；分别定义为W1，W22个游程有：0001,0011,0111,1110,1100,1000分别定义为W3,W4,W5,W6,W7,W83个游程有：0100,0010,0110,1011,1101,1001分别定义为W9,W10,W11,W12,W13,W144个游程有：0101,1010分别定义为W15,W16以上每一组代码具有互补性.P(X|A,B)与W1~W16的对应关系如表1.11.其中“值”对应参数是X的灰度值,“计数”对应的值是指左边A,B取值的情况下X出现此灰度值的次数,统计值可以是任何一幅或几幅图像2023/2/6

信息工程学院戴永32

A

BW1W2W3W4W5W6W7···215值计数421361050462821······1······30值计数04431114375264115641915······12······

31值计数11139281735524750555206······8······32值计数2790234636142642645646180······6······33值计数333972228694251151381936517······18······34值计数4285932442524022316537311······13······大小新代码游程数目:小大2023/2/6

信息工程学院戴永33表中红线标注的是，当A=B时使得X=A=B的现象最多，因此将其对应单游程。对应什么结构的单游程无硬性规定。当A与B大不相同时，X成为各种灰度的概率都很小，一旦遇到只能根据预测赋予W，但多为多游程W。表中计数值左起从高到低排列，与此对应是W1~W16从少游程到多游程顺序排列。这样一来由W构成的新图像码串的游程数目会有效减少，从而实现压缩。此方法的工作过程为图像以光栅顺序扫描。对每一像素X，其邻点A和B已定位。在条件概率表中查找A，B及X。如果在第i列发现，则选中相应Wi。如图若X位于图像顶行，则X按只有邻点A而无B（但并不按B=0处理）,处理原则是选择A=3,X=2对应的计数值最大的那个W,本例为7902对应的W1.XA2023/2/6

信息工程学院戴永34其它类型边界点可类同处理.互补规则:选中对应于X的代码后,将其与前面一个代码相比较.若前者最低位是1,则当前代码取为补码(反码或互补码),以此减少游程数.例1.假定压缩器按前述安排获得如下序列W2,W4,W1,W6,W3,W2,W1:1111,0011,0000,1110,0001,1111,0000:8个游程1111,1100,0000,1110,0001,1111,0000:6个游程1111,1100,0000,1110,0001,0000,0000:6个游程2023/2/6

信息工程学院戴永351.4.3BinHex4.0格式文本文件传送比2进制文件传送安全一些,因为2进制文件传送是任何位都不能丢失的.BinHex的思想是企图将任何文件都译成文本文件传送,或者说用一个新的文本文件代替原来的任何一种形式的文件.BinHex4.0是一个用于文件安全传输的文件格式.传输文件进入BinHex后,输出的BinHex4.0文件格式如下1.注释:(ThisfilemustbeconvertedwithBinhex4.0)2.文件头2023/2/6

信息工程学院戴永36包括表1.13所列各项3.读入输入文件,第一步进行RLE.RLE的标志字符为90H例1.90H既作标志又作数据.作数据时后跟00H,表示游程长度为0,以示该90H为数据.源串和压缩串的关系如下表所示.源串压缩串001122334455667700112233445566771122222222222233119006223311229033441122900033442023/2/6

信息工程学院戴永374.编写7位ASCII码字符(该步骤是此方法的核心).将输入文件看成是位流,把正读入的文件分成6位1块(或6位1段),并把每个6位代码当作指针,从给定的字库中读取字符,将读出的字符对应的7位ASCII代码写入输出流,构成新的文本文件流.例1.将2进制文件“7401F590··········”转换成新的文本文件(此例未考虑先进行RLE).原文本文件:7401MOVA,#01HF590MOVP1,A

··········设定6位指针字库如表2所示.000000!010000100110100110000000001“01000100011101011000100111120110010010110901110010100003011001101000140110100010010501101012023/2/6

信息工程学院戴永387401F590··········的2进制代码为01110100000000011111010110010000按6位一块分割011101,000000,000111,110101,100100,00··········查新文本转换表得F!(bM··········与此对应的7位ASCII代码位流为10001100100001010100011000101001101··········1.5前移编码此方法的基本思想是:建立一张1维位置可变转换表,该表将常用或重复使用符号靠前排列,并不断改变编号.2023/2/6

信息工程学院戴永39基本原理如下设A是一张用于转换的1维字母表,表中元素位置编号不变,元素内容根据输入流内容变化,令A=(a0,a1,a2,a3,a4········an）A中每个元素的编号与A中初始元素符号的下标相同，用FA表示A的元素标号即FA=（0，1，2，3，4,··········n）设x1x2x3x4x5·········xm为输入流.如果xi=xi-1,而xi=aj,则A中元素位置作如下调整2023/2/6

信息工程学院戴永40A’=(aj,aj-1aj-2,···a4,a3,a2,a1,a0,aj+1,aj+2aj+3,···an）=(a0’,a1’,a2’,a3’,a4’········an’）FA仍不变,即FA=（0，1，2，3，4,··········n）.以上aj=a0’对应0,aj-1=a1’对应1,aj-2=a2’对应2,··········其余类推.例1.设原始A0=(a,b,c,d,m,n,o,p),FA=（0,1,2,3,4,5,6,7,）,输入流为“abcddcbamnopponm”.不采用前移编码C’=(0,1,2,3,3,2,1,0,4,5,6,7,7,6,5,4)采用前移编码:C1=(0,1,2,3,········），已编完输入流的abcd，输入流的下1个字母与前一个字母相同，相同字母为d，字母表从d往前翻，元素按新位置重新编号，即2023/2/6

信息工程学院戴永41A1=(d,c,b,a,m,n,o,p),仍有FA=（0,1,2,3,4,5,6,7,）,此时d↔0,c↔1,其余类推.在A1基础上往后编,有C2=(0,1,2,3,0,1,2,3,4,5,6,7,········）,已编完输入流的abcddcbamnop,输入流的下1个字母与前一个字母相同，相同字母为p，字母表从p往前翻，元素按新位置重新编号，即A2=(p,o,n,m,a,b,c,d),仍有FA=（0,1,2,3,4,5,6,7,）,此时p↔0,o↔1,其余类推.在A2基础上往后编,有C3=(0,1,2,3,0,1,2,3,4,5,6,7,0,1,2,3）.以上方法为集中前移法,结果使得前移法编码后的代码平均值小于不前移编码代码平均值.2023/2/6

信息工程学院戴永42例2.非集中前移现象.其原理是在输入流中遇到哪个符号,就将A中相同符号提到最前面,A中元素重新编号.设输入流为Z=(abcdmnopabcdmnop),A、FA仍为例1的A、FA

。不前移的编码为C’=(0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7);前移的编码为C=(0,1,2,3,4,5,6,7,7,7,7,7,7,7,7,7)C中第2个“7”的来源如下A0=(a,b,c,d,m,n,o,p),FA=（0,1,2,3,4,5,6,7,）,遇Z(a)，A1=(a,b,c,d,m,n,o,p),C=(0,········），a↔0遇Z(b)

，A2=(b,a,c,d,m,n,o,p),C=(0,1,········),a↔0,b↔1,遇Z(c)

，A3=(c,b,a,d,m,n,o,p),C=(0,1,2,········),a↔0,b↔1,c↔2,·····························遇Z(p)

，A8=(p,o,n,m,d,c,b,a),C=(0,1,2,···7·····),a↔0,·····,p↔7,遇Z(a),A9=(a,p,o,n,m,d,c,b),C=(0,1,2,···7,7·····),a↔0,···,p↔7,a↔7,其余类推.显然这种前移得出的编码的平均值太大,还不如非前移编码.2023/2/6

信息工程学院戴永43两个例子的输入流,编码及A的变化比较见表1.14.之所以希望以上前移编码的平均值要小,是为了后面要介绍的高效霍夫曼码(算术码)作准备.只有编码的平均值小,整数代码就少,随之霍夫曼码的码长就短.实现高效霍夫曼码的常见4种办法为(1)把霍夫曼码赋给[0,N]范围的整数,使较小的数对应较短的码,如0↔0,1↔10,2↔110,3↔1110,4↔11110,5↔111110,6↔1111110,7↔1111111.(2)给整数分配代码,使整数i>=1的代码为她的2进制代码前加Log2i个0,

i霍夫曼代码加的0数霍夫曼码字长11Log21=012010Log22=133011Log23=13400100Log24=25···················································································150001111Log215=3716000010000Log216=492023/2/6

信息工程学院戴永44（3）采用自适用霍夫曼编码（下节讲）（4）为了尽可能地压缩，对C扫描两次，第1次计算代码频度,第2次具体编码.第1次扫描所统计的代码频度用于计算概率,第2次扫描根据第1次扫描形成的概率构造霍夫曼代码(具体在第2章介绍).前移方法的变形1>前移k把A中为当前符号所匹配的元素前移k个位置,而不是一直移到A的前部.参数k可由用户指定,默认值为n或1.此举虽然降低了集中特性的性能,但能根据需要满足一些特殊序列的压缩要求.k=n为原形的前移方法;k=1,只是和前面一个元素交换位置.2>等c次再移仅当A中某元素与输入流中符号匹配c次(不必连续c次)后,才将其移到前面.A中各元素要安排计数器计数匹配次数.此方法较适用移动或重排A的元素速度很慢的情况.3>通常把从输入中读入的一个字(或一个单词)作为一个字节.此方法A必须从空开始,元素内容在输入和编码时加入.例有以下文本theboyonmyrightistherightboy输入第1个“the”时,A是空的,找不到,在A中添加“the”,编码器给出0,后跟“the”.2023/2/6

信息工程学院戴永45解码器也从空A开始,以0表示在A中选择第1个字.但此时解码器中的A是空的,解码器从编码器中取出0后跟的字(这里是the)添加到A中.下一个字是“boy”,加到A中,使A=(“the”,“boy”),编码器发出“1boy”.加入后作非集中前移处理,即将“boy”移到A的前面,A=(“boy”,“the”).解码器处理和前面相似.字A(添加前)A(添加后)编码器输出the()the0the

boy(the)(the,boy)1boyon(boy,the)(boy,the,on)2onmy(on,boy,the)(on,boy,the,my)3myright(my,on,boy,the)(my,on,boy,the,right)4rightis(right,my,on,boy,the)(right,my,on,boy,the,is)5isthe(is,right,my,on,boy,the)(is,right,my,on,boy,the)5(按添加前的排序)right(the,is,right,my,on,boy)(the,is,right,my,on,boy)2boy(right,the,is,my,on,boy)(right,the,is,my,on,boy)52023/2/6

信息工程学院戴永461.6标量量化从数据压缩的角度出发,量化也是为了有益于数据压缩,包含两个方面的内容(1)如果被压缩数据是大值,量化用于将其转换为小值.小值比大值占用空间少,这种量化本身就是压缩,但为有损压缩,因小值比大值含的信息量少.(2)如果被压缩数据是模拟量,这种量化仍是将其离散后化为小的数值.数值越小,压缩效果越好,但信息损失也越大.方法1.假如输入流每一个数据都是8位构成,可以删去每项数据的低4位,而获得压缩因子=2.但此方法使得输出数据由256种符号变成了16种符号,即16,32,48,64,·······,丢失了256-16个符号信息.2023/2/6

信息工程学院戴永47方法2.仍是一个8位数,输入符号在[0,255]范围内.设置一个间隔参数s(也可称为步长值),以s为均匀间隔的量化值(量化序列)为0,s,2s,3s,4s,······，ks，255，并使(k+1)s>255,而ks<=255.当s=3时,均匀间隔的量化值为0,3,6,9,12,······，252，255;当s=4时,均匀间隔的量化值为0,4,8,12,16,······，252，255;每一个输入符号在以给定的s均匀间隔序列中寻找最接近的量化值(取小).方法3.选择合适的量化值,使得[0,255]间任何一个数,总可以在待量化数据中找到一个不大于d个单位的数据(局部量化法).处理方法:将量化范围按2d+1长度分段,并置于[0,255]的中心.2023/2/6

信息工程学院戴永48例.设d=16,则2d+1=33,256/33=7余25,即[0,255]被分成7段余25个数.显然在[0,255]任取一个序列都能满足基本结果.从距区间25以内的数据开始都能获得8个数值以内的量化序列,如20,53,86,119,152,185,218,251标量量化是有损压缩,它易于控制压缩比和数据损失间的平衡,但实现简单,而只适用于可以大失真的情况.标量量化压缩不适合图像压缩,因为标量量化压缩过于陡峭,会使本来连续的灰度变成对比度很强的杂线条比如一幅几乎均匀的图像区域(像素值为127或128).如果127量化为111,128量化为144,解压后该图像会成为格状图案,相邻像素总在111,144之间跳变.图像和声音常采用的有损压缩为矢量量化法.2023/2/6

信息工程学院戴永49第2章统计方法第1章讨论的基本技术各方法采用的编码主要是定长码,如RLE,BinHex,前移编码,量化编码等.本章主要介绍变长编码,总的思路是根据数据出现的概率大小赋其长码或短码.设计和实现变长码必须要解决的问题(1)解码要唯一;(2)平均码长与其他方法比较要最短.2.1信息论信息是难以理解的不确定量,无法精确定义,捕获和度量.信息的标准定义:(1)通过学习,经验或教训所获得的知识;(2)关于某一特定事件或情景的知识,情报;(3)收集的事实或数据;(4)通知的行为或被通知的条件,知识的交流.2023/2/6

信息工程学院戴永50信息论在于用量化方法来处理信息,度量信息,使人们能用精确的数字来描述一个事件所含的信息信息量化的依据:一条消息的信息含量等于该消息引起人们的惊奇度一种最简单的量化方法是:将问题数等于表达结果所含信息需用的位数.实际上是从两个方面考虑:(1)表达考察范围内所有信息所需的位数.比如用2进制表达1~64(其中每一个作为一个信息),需要log264=6位,即6位可表达1~64中所有信息.(2)按“是/否”判断找到结果的最多提问次数.比如在1~64中按2分法找到一个数的最多次数为6次.2进制和其它进制包含信息量的换算以10进制为例.给定k位10进制数和x位2进制数,使两个数表达的信息量相等有2023/2/6

信息工程学院戴永5110k-1=2x-1解之得x=k(Log10/Log2)将底改为2,有x=kLog210~~3.32k,表明1位10进制数所含信息量相当与3.32位2进制数所含的信息量.推广到一般有x=kLog2n,n为n进制.n进制有n个符号,以下按n个符号出现的概率来表示x对应的信息量.设n个符号分别对应出现的概率为P1,P2,···,Pn,显然P1+P2+···+Pn=1,在等概率条件下有nP=1,即P=1/n或n=1/P于是x=kLog2n=kLog2(1/P)=-kLog2P(这里的k要理解为流输送了多少位,与进制无关,x为信息量)当各符号出现的概率各不相同时,设其中第i符号出现了k次,出现概率记为Pi,那么在单位时间内平均出现的次数为kPi.2023/2/6

信息工程学院戴永52仅第i符号出现的信息量为-kPiLog2Pi.n个符号出现而产生的总的信息量为

x=-k∑n1PiLog2Pi改写为(x/k)=-∑n1PiLog2Pi表明每一位n进制符号对应的2进制信息量为-∑n1PiLog2Pi从传送信息的角度讨论,传送一个bit需1/k时间,那么传送x个2进制代码需要的时间x/k,其对应的信息量为-∑n1PiLog2Pi,称之为被传送数据的“熵”,即一种用概率表示的信息量.对于单个符号的熵定义为-PiLog2Pi.数据的熵取决于各符号的概率Pi,当n个符号出现的概率相等时,数据的熵值达到最大,即用熵来计算数据冗于度R的方法为

R=x/k-(-∑n1PiLog2Pi)=-Log2(1/P)+∑n1PiLog2Pi

=-Log2(n)+∑n1PiLog2Pi当输入流被压缩到无冗于度,即R=0时,数据熵为∑n1PiLog2Pi=-Log2(n)2023/2/6

信息工程学院戴永532.1.1算法信息容量算法信息容量也称计算机程序长度.描述计算机程序的一个述语是2进制序列的复杂度.复杂度(KCC)定义:能生成2进制字符串S的最短的计算机程序的长度(以位为单位).比如生成将2进制字符串S去打印,显示或写进文件等的程序.一般如果长度为n的2进制字符串是随机的,则其KCC也接近于n.从压缩的角度考虑文本,图像及声音的复杂度多为中等的复杂度.2023/2/6

信息工程学院戴永54低等KCC为具有大量重复内容的文件,如书中S1,实际少见;高等KCC为文件内容大量的是随机数据,很不利于压缩,如书中S2.中等KCC为既有随机数据也有相当数量便于压缩的重复块.算法信息容量也是对某消息所含信息的度量.信息论中对信息量是预测形式,而算法信息容量衡量的是已经出现的信息,即人们对已出现信息的惊奇度.比如处理那一段代码程序很简单,或很长,或一般等.简单的,重复的内容不能增加信息量,或信息越来越少,内容越新,越多,越复杂,信息量越多.这就是所谓的香农信息论基本思想.2023/2/6

信息工程学院戴永552.2变长码例1.设有4个字符,a1,a2,a3,a4.<1>若它们在数据串中出现的概率均等于0.25,相应的数据熵(实际对应的是2进位数)是4(-0.25Log20.25)=2即每个字符至少需要2位2进制码,这里先给4个字符分别赋予00,01,10,11.4个字符概率相等,R=0,所以数据不能被再压缩,即不能被压缩到低于2位/字符.<2>若出现概率不等,如P1=0.49,P2=0.25,P3=0.25,P4=0.01,对应的数据熵为-(0.49Log20.49+0.25Log20.25+0.25Log20.25+0.01Log20.01)≈-(-0.050-0.5-0.5-0.066)=1.57即每字符的平均最少位数下降到了1.57位.2023/2/6

信息工程学院戴永56如果仍用个2位进行编码,则R=2-1.57=0.43.减少R的方法是采用不定长码或变长码.具体原理:将概率高的对应短码,依次增长,如下表所示.符号概率编码1编码2a10.4911a20.250101a30.25010000a40.01001001变长码计算平均码长的方法:因概率是该字符在整个数字串中出现的概率,赋予变长码后,应该考虑该字符对应的码长在数字串中出现的概率,这里可以把概率看成是比率,即假定输出的数字串长度为Z,第i字符出现的次数为K(累积长度),则第i字符在数字串中出现的概率为K/Z,也是第i字符在Z中占据的长度比率.当给各符号赋予不同的码长时,每个码长在字串长度中占有的份额即为平均码长,计算公式为:码长∙概率所有符号占用的代码长度由下式求得码长1∙概率1+码长2∙概率2+·········+码长n∙概率n对于上表有1∙0.49+2∙0.25+3∙0.25+3∙0.01=1.77

接近最少位数.2023/2/6

信息工程学院戴永57和等长码相比,R=1.77-1.57=0.2.值得注意的是平均位短不一定数字串的编码长度就短,需看采用何种编码.例1.用上述表中符号编一个20符号的字符串(见书P32),每个符号的出现概率与表中相同.显然,按等长编码,1.57位必须用2位,需40位.如果按编码1进行变长码编码则只用了37位,每字符平均占用37/20=1.85位,和平均码长的计算值很接近.编码1存在解码的歧义性.设从左到右进行解码.a1的编码与其它3个有明显区别不会出错.a2~a4均以0开始,解码器遇0后必须再往后查,再查到0肯定可以确定其右必为1,此3位为a4代码.若查到的是1,则要区别a2还是a3,再往下查,如果是1,可以判为a2a1序列;如果是0,那么是a3,还是a2,a4,还是a2a3呢?编码2按上述过程识别不会出现歧义,第2,3位都有独立码.2023/2/6

信息工程学院戴永58设计变长码应遵循的两条规则:(1)把短码赋予出现频率高的字符;(2)遵循前缀性.按上述规则生成字符代码可既短又唯一可译,但未必最佳(未必是平均长度最短的码字).2.3前缀码前缀码就是满足前缀性(区别在前面规定的可变的码长)的变长码.前面介绍的整数2进制编码的码长是已知的,即事先知道这组整数的位数为n,从而决定了码长为1+Log2n;再者不能在代码前加码,即无前缀性.2023/2/6

信息工程学院戴永592.3.1一元前缀码基本一元码定义:设有正整数n,用n-1个1后跟一个0,或用n-1个0后跟一个1构成的代码称为一元码.可见一元码的长度是n位.两种结构如下n0尾一元码1尾一元码101210013110001411100001511110000012023/2/6

信息工程学院戴永60通用一元码定义:对数据字符进行编码的第n个码字由n个1后跟一个0再加上所有的a位码组成,a=开始数+n•步长数.设定一个结束数(STOP),当a=STOP时,丢掉n个1后紧跟的一个0.可见通用一元码形成取决于开始数(START),步长数(STEP)和结束数,常用(START,STEP,STOP)三元组的形式表达通用一元码.例1.设有通用一元码(3,2,9),其对应的码字如下表

na=3+n•2第n个码码字数目表达的整数范围030xxx23=80~7

1510xxxxx25=328~39(将00000定为8)

27

110xxxxxxx27=128

40~(39+128)

3

9

111xxxxxxxxx29=512

168

~(39+128+512)2023/2/6

信息工程学院戴永61例2.通用一元码为(2,1,10)请自阅.注意点:(1)STOP通过步长累加是一定能到达的值.(2)a是符号可添加代码的位数.(3)除STOP对应的码字外,前面符号的已知代码排列服从一元码规则.(4)通用一元码由已知码和待填码两部分组成.(5)通用一元码的数量=(2stop+step-2start)/(2step-1)例3.通用一元码(3,2,9)的码字数=(512•4-8)/3=680=512+128+32+82023/2/6

信息工程学院戴永622.3.2其他前缀码用B(n)代表整数n的2进制表示,|B(n)|为这种表示所占用的位数,用/B(n)表示B(n)去掉最高位后的编码(最高位总是1).以下是基于这种表示的4种前缀码.C1码:前面是通用一元码,后面是/B(n).例如n=16,则B(16)=(10000)2,|B(16)|=5,/B(16)=0000,由于|B(16)|=5,相应的通用一元码选用11110(也可采用00001).相应的C1码表示为11110|0000.|C1(n)|=2Log2n+1C2码:将C1按如下方法重排既得C2.11110|0000→C2(16)=101010100C3码:由前后两部分组成.前部分根据n的2进制位数进行C2编码,如n=16,则|B(16)|=5,C2(5)=10110(C1(5)=110|01);后部分为/B(n).例C3(16)=10110|00002023/2/6

信息工程学院戴永63C4:由多个码位数递减前排构成.基本原理为从B(n)开始,以其|B(n)|-1的2进制编码递归左排,直到位数可用两位代码表示则停止,为便于识别在B(n)右边加一个0.例.C4(16)=10|100|10000|05|B(4)|-1=2|B(16)|-1=4n等于其它值正整数的4种前缀码请参阅P35.表2.6.以下根据码长来计算n的概率对于一元码,设整数为n,则表示n的2进制位数即码长L也为n,L=n=Log22n任意n在L位的组合中出现的概率为P(n)=1/2L=2-L=2-nC1(n)的长度L=1+2Log2n=Log2(2n2)如果也按L等于整数处理,则P(n)=2-L=1/(2n2)C3(n)的码长L=1+Log2n+2(Log2(1+Log2n))2023/2/6

信息工程学院戴永64=Log22+2Log2Log22n+Log2n=Log22n+2Log2Log22n=Log2(2n(Log22n)2)因此在L等于整数的理想状态下,有

P(n)=2-L=1/(2n(Log22n)2)P35表2.7给出了一元码,C1,C3的8个整数的理想概率.对于特定场合正整数编码的前缀码按如下方法设计选择一些相关的正整数vi,进行有序排列,形成表格.2023/2/6

信息工程学院戴永65正整数n按以下步骤确定(1)找一个k,使其满足∑k-1i=1vi

<n≤∑ki=1vi

(2)计算差值d,d=n-∑k-1i=1vi-1nmax=∑ki=1vi

,所以dmax=∑ki=1vi

-∑k-1i=1vi

–1=vk-1dmax是可以用Log2vk位表示的值对d进行标准的2进制编码,有两种码长1)与d相等