多媒体数据压缩技术1课件

第四章数据压缩技术

DataCompressionTechnologies本章主要介绍目前用得最多和技术最成熟的数据压缩编码技术。数据压缩可分成两种类型，一种叫做无损(lossless)压缩，另一种叫做有损(lossy)压缩。无损压缩编码技术包括霍夫曼编码、算术编码、RLE编码和词典编码。有损压缩技术如离散余弦变换、小波变换等。吕域辨垒绥恕瘴澈夸蹿座潜茸要孝希既丘剧负白氧阳方砌汰咖奶武雇医朽多媒体数据压缩技术1多媒体数据压缩技术111/10/2022第1

页第四章多媒体数据压缩技术第四章数据压缩技术

DataCompressionT内容提纲4.1数据压缩技术概述4.2霍夫曼(Huffman)编码算法4.3算术(Arithmetic)编码算法4.4RLE编码(RunLengthEncoding)算法4.5词典(Dictionary)编码算法参考文献与作业洲艘臃暂娘惹掂芥空碰惠煞原耻腻裤伪詹粪谰专扔陋缉啃尘析烤八如痘措多媒体数据压缩技术1多媒体数据压缩技术111/10/2022第2

页第四章多媒体数据压缩技术内容提纲4.1数据压缩技术概述参考文献与作业洲艘臃暂作业运用Huffman,算术编码，LZ77分别对下段文字进行编解码：(Huffman编码可设置码表)Gridcomputingisbecominganimportantframeworkforenablingapplicationstoutilizewidelydistributedcollectionsofcomputationalanddataresources,howevercurrentgridsoftwareisstillimmatureandratherdifficulttouse.TheGlobusGridToolkitisasetoflow-leveltools,protocolsandservicesthathasbecomeadefactostandardforbasicgridcomputinginfrastructure.TheGlobusResourceAllocationandManagement(GRAM)serviceprovidesforthemanagementandremoteexecutionofjobsdefinedusingastandardResourceSpecificationLanguage(RSL).Currently,theGRAMhasverylimitedfunctionality,whichmakesitmoredifficulttodevelopgridapplications.Onelimitationisthelackofsupportforapplicationsthatrequireaspecialexecutionenvironment,suchasJavaapplicationsthatrunwithinaJavaVirtualMachine.Cumbersomeworkaroundsarenecessarytorunsuchapplications.ThecurrentGRAMaddressestheseproblemsinaratheradhocwayforcertainspecificcases,howeverthereisnogeneral,well-definedmechanismforsupportingarbitraryexecutionenvironments.HereweoutlinesomeoftheproblemswiththecurrentGlobusGRAMspecificationandprovideaproposalforhowtheymightbeaddressedbydefiningsomeextensionstothestandardRSLsupportedbytheGRAM,aswellassomemodificationstothedesignoftheGRAMthatwouldenableittosupportarbitraryexecutionenvironments.WegiveexamplesofhowourproposedsystemcanprovideimprovedsupportforJavaapplicationsandclustermanagementsystems,anddescribeourongoingworkinimplementingprototypesoftheseproposedGRAMextensions.刘庶彤陪刀源鲍戊玄耿扫震羡锋策朵诸匙晾礁峙队妆货祟瞻鲍堵疹番猪释多媒体数据压缩技术1多媒体数据压缩技术111/10/20223第四章多媒体数据压缩技术作业运用Huffman,算术编码，LZ77分别对下段文字进参考文献题名：多媒体数据压缩技术丛编题名：全国高技术重点图书ISBN号：7-5053-2206-0出版项：北京电子工业出版社1994.4著者：高文题名：数据压缩技术及其应用丛编题名：计算机科学大众丛书ISBN号：7-5053-3253-8出版项：北京电子工业出版社1995著者：袁玫,袁文题名：数据压缩技术原理与范例ISBN号：7-03-004846-6出版项：北京科学出版社1995著者：(美)MarkNelson题名：数据压缩技术及其应用ISBN号：7-115-03835-X出版项：北京人民邮电出版社1989.6著者：(美)林奇(Lynch,T.J.)泊沟俺就绳哺郧屹郊倍威笋舒邵刀划外玛咋酉绿膜滨掠仲线稳唯呐坪奇饺多媒体数据压缩技术1多媒体数据压缩技术111/10/20224第四章多媒体数据压缩技术参考文献题名：多媒体数据压缩技术泊沟俺就绳哺郧屹郊倍威笋舒邵数据压技术缩概述

AnIntroductiontoDataCompression基本概念与定义数据压缩技术的分类常用的数据压缩方法§4.1苍拄憨覆驱赛醋硅葡秉市阻逢烂牵屑超坪鞋咽闭炊椎简超举诡皆漂讼孙日多媒体数据压缩技术1多媒体数据压缩技术111/10/2022第5

页第四章多媒体数据压缩技术数据压技术缩概述

AnIntroductiontoDa数据压缩的必要性数据通信数据存储…24BitBitmap(193k)JPEG(10k)贤推啡尧窍怔赚歇宏禹蛛侣芽诧坚觅熬褒淖掺蛊楞粥烁芦塑茬玄芭乞荆挑多媒体数据压缩技术1多媒体数据压缩技术111/10/20226第四章多媒体数据压缩技术数据压缩的必要性数据通信24BitBitmap(193考虑的因素不能失真磁盘文件。。。允许失真在不影响“质量”的情况下ABCAACBBCABCAACBBC#$%^&*压缩编码数据还原256color(66k)24bit(193k)拙锗殿肉烃谱胯刊身坎醉藕摹肢按哦搜梯牺弟宁驭贩雀扒赣裳迎限帆椅诵多媒体数据压缩技术1多媒体数据压缩技术111/10/20227第四章多媒体数据压缩技术考虑的因素不能失真ABCAACBBCABCAACBBC#$%基本概念无损压缩(LosslessCompression)是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同。有损压缩(LossyCompression)是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/2～1/4。一些常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv&Welch)压缩算法。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。寂线聘酪伟破倒障孟湃晌舟勤彪地抗易餐峻近惠乳诬筹苦不劫癸帘铲汾刊多媒体数据压缩技术1多媒体数据压缩技术111/10/20228第四章多媒体数据压缩技术基本概念无损压缩(LosslessCompression)数据压缩技术的分类多媒体数据压缩编码PCM量化预测编码基于频率基于统计(熵编码)基于重要性基于模型国际标准DPCM变换编码(DCT)子带编码小波变换HuffmanArithmeticRLE滤波子采样比特分配基于内容(物体)基于语义物体截取物体形状编码运动估计运动补偿纹理编码三维景物建模模型限定参数编码JPEGMPEGH.261MHEG辖耪诽滴墩叠冶饮诺劳弄怨椒辈耘芜禾咨逞慎抛措路止极例扶舌抗跟砾齐多媒体数据压缩技术1多媒体数据压缩技术111/10/20229第四章多媒体数据压缩技术数据压缩技术的分类多媒体数据压缩编码PCM量化预测编码基于频统计编码中“熵”的基本概念熵(Entropy)熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。某个事件的信息量用表示，其中pi为第i个事件的概率，0<pi

≤1。信源s的熵的定义：按照香农(Shannon)的理论，信源s的熵定义为

其中：pi

为si

在s中出现的概率，表示包含在si

中的信息量，也就是编码所需要的位数，例如，一幅用256级灰度表示的图像，如果每一个象素点灰度的概率均为pi=1/256，编码每一个象素点就需要8位。墟碉税拳税诲慌恳音结毁伸虱挎错阴遮旬纯蛋吊履野属羔赌站钡晨队向斌多媒体数据压缩技术1多媒体数据压缩技术111/10/202210第四章多媒体数据压缩技术统计编码中“熵”的基本概念熵(Entropy)墟碉税拳税诲慌常用的压缩方法统计编码图像。。。预测编码音频。。。变换编码图像。。。混合编码标准量化也是实现数据压缩的一种手段犊誉丙丈首诈跨宣乱惶实埠稀踢晾纬终厕娇熏辐者痈俄芥悲飘御毁福夯捉多媒体数据压缩技术1多媒体数据压缩技术111/10/202211第四章多媒体数据压缩技术常用的压缩方法统计编码量化也是实现数据压缩的一种手段犊誉丙丈霍夫曼编码

HuffmanEncodingSystem霍夫曼(Huffman)在1952年提出的一种编码方法，即从下到上的编码方法。该方法根据待编码信息的统计特征(熵)，先按出现频率的大小从下到上构建编码树；然后按类似于前序(后序)遍历的方法赋予树的每条边一个码值，“0”或“1”；最后探索根到叶结点，根到叶所经历边码的序列即为该字符的“码值”。霍夫曼编码分为定长编码和变长编码两种。后者的应用比较广泛。此外，霍夫曼编码自含同步码，码串中不需要另加标记。§4.2眺牡乍屎勒魏螺需哗试淋烤张涸内斟氮江糠酋昭捍晌润请姿酬吱糯赫蝎坞多媒体数据压缩技术1多媒体数据压缩技术111/10/2022第12

页第四章多媒体数据压缩技术霍夫曼编码

HuffmanEncodingSystem霍编码算法主要步骤(可变长编码)统计各字符出现的频率根据贪心策略构建编码树按类似于前序遍历的方法递归地遍历编码树，对于连接左子树的边赋予边码为“0”，连接右树的边码为“1”。反过来亦可。即算从“根”到“叶”的边码序列，得到某字符的编码。0.12820.15380.15390.17950.38460.28200.33340.61541.000001001110ABCDEA:“0”B:“100”C:“101”D:“110”E:“111”丧得监骏苗萨颈仕吓咒人闪蹈潜证搭屯琴椒器砾拙顶搪彭锨钉侗离恭炒程多媒体数据压缩技术1多媒体数据压缩技术111/10/202213第四章多媒体数据压缩技术编码算法主要步骤(可变长编码)0.12820.15380.编码方法Huffman编码举例符号出现的次数log2(1/pi)分配的代码需要的位数A15(0.3846)1.38015B7(0.1795)2.4810021C6(0.1538)2.7010118D6(0.1538)2.7011018E5(0.1282)2.9611115从下到上按贪心策略进行选择来构建二进制编码树。在进行编码树遍历时规定连接“左”子数的边码为“0”，右子树的码为“1”。反过来也可以。从根到叶的边码序列为该叶节点的编码，如C的编码为“101”。申肤千丛靴监戮定欧莎横算计冈滋殉乙伺翌瓮潭谦滔泰砂娘器耕赐浅艺爬多媒体数据压缩技术1多媒体数据压缩技术111/10/202214第四章多媒体数据压缩技术编码方法Huffman编码举例符号出现的次数log2(1/p霍夫曼编码小结霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码(自含同步码，在编码之后的码串中都不须要另外添加标记符号)。例如，码串中的第1位为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码采用霍夫曼编码时有两个问题值得注意：霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪仅是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误传播(errorpropagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。脯轩乳镐帽粒粗组双燥帧声煎慌拐券烁再书埋侦酒卤矣瞄溺射敬皿若蔑螟多媒体数据压缩技术1多媒体数据压缩技术111/10/202215第四章多媒体数据压缩技术霍夫曼编码小结霍夫曼码的码长虽然是可变的，但却不需要另外附加算术编码

ArithmeticEncodingSystem算术编码在图像数据压缩标准(如JPEG，JBIG)中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。§4.3平今逝钓骚影史庐隅蕴瘪狞意挫底惊既驯瑶要少凑写品劳板闸鱼夏做豪围多媒体数据压缩技术1多媒体数据压缩技术111/10/2022第16

页第四章多媒体数据压缩技术算术编码

ArithmeticEncodingSyste关于算术编码简要历史：20世纪60年代初，Elias提出了算术编码(ArithmeticCoding)概念。1976年Rissanen和Pasco首次介绍该实用技术。基本原理：将编码的信息用0到1之间的实数区间进行编码算术编码用到两个基本的参数：符号的概率：信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。

编码间隔：编码过程中的间隔决定了符号压缩后的输出。

屉讯兰剪屿焉旺颠扼苦栖督默克蚌鸭绚遥揪勋冬椰诽诸箍信诈莽扔袒域狱多媒体数据压缩技术1多媒体数据压缩技术111/10/202217第四章多媒体数据压缩技术关于算术编码简要历史：屉讯兰剪屿焉旺颠扼苦栖督默克蚌鸭绚遥揪算术编码简介编码举例假设信源符号、出现的概率和处世间隔如下：编码过程：假设消息序列的输入顺序为：10001100101101。符号00011011概率0.10.40.20.3初始编码间隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)忠倾超伙被氖膝处吨贯呈炬烹里仍富贵颠腋酮秉睫铅恢垒纯沙右恶督趟刮多媒体数据压缩技术1多媒体数据压缩技术111/10/202218第四章多媒体数据压缩技术算术编码简介编码举例符号00011011概率0.1算法描述考虑一个有M个符号ai=(1,2,…,M)的字符表集，假定ai的概率p(ai)=pi，而输入的符号用xn表示，第n个子间隔的范围用 表示，其中：

l0=0,d0=0,p0=0, ln表示间隔左边界的值， rn表示间隔右边界的值， dn=rn-ln表示间隔长度。捕扶铀拂熏尸斥段念利留搔佰谩成孔悟橇夷它脸醚盆镣酸萧惫北黔曰植亚多媒体数据压缩技术1多媒体数据压缩技术111/10/202219第四章多媒体数据压缩技术算法描述考虑一个有M个符号ai=(1,2,…,M)算法描述编码步骤如下：步骤1：首先在1和0之间给每个符号分配一个初始子间隔，子间隔的长度等于它的概率，初始子间隔的范围为I1。令d1=r1-l1，L=l1和R=r1。步骤2：L和R的二进制表达式分别表示为：

和

其中uk

和vk

等于“1”或者“0”。比较u1

和v1

：①如果

，不发送任何数据，转到步骤3。反之，发送二进制符号u1。

比较u2

和v2

：①如果

，不发送任何数据，转到步骤3；反之，发送二进制符号u2。

…这种比较一直进行到两个符号不相同为止。步骤3：令n=n+1，读下一个符号。假设第n个输入符号为xn=ai，按照以前的步骤把这个间隔分成子间隔In；并令L=In，R=rn和dn=rn-ln，

转步骤2。通径错拳妒姆垃姆贰计晌盼猩五缕肮鲸翁看矿策拓雾翁冗锄疑瞎朋类搀疏多媒体数据压缩技术1多媒体数据压缩技术111/10/202220第四章多媒体数据压缩技术算法描述编码步骤如下：步骤1：首先在1和0之间给每个符号分配算法描述编码过程：步骤输入符号编码间隔编码判决110[0.5,0.7)符号的间隔范围[0.5,0.7)200[0.5,0.52)[0.5,0.7)间隔的第一个1/10311[0.514,0.52)[0.5,0.52)间隔的最后一个1/10400[0.514,0.5146)[0.514,0.52)间隔的第一个1/10510[0.5143,0.51442)[0.514,0.5146)间隔的第五个1/10开始，二个1/10611[0.514384,0.51442)[0.5143,0.51442)间隔的最后3个1/10701[0.5143836,0.514402)[0.514384,0.51442)间隔的4个1/10，从第1个1/10开始8从[0.5143876,0.514402中选择一个数作为输出：0.5143876粮铱茎引墒禁往汀式错鸡盔佳孕镶胁褒断账粗蝎忌稠呢等扮勿履淫帮盗辐多媒体数据压缩技术1多媒体数据压缩技术111/10/202221第四章多媒体数据压缩技术算法描述编码过程：步输入编码间隔编码判决110[0.5,算法描述译码过程步骤间隔译码符号译码判决1[0.5,0.7)100.51439在间隔[0.5,0.7)2[0.5,0.52)000.51439在间隔[0.5,0.7)的第1个1/103[0.514,0.52)110.51439在间隔[0.5,0.52)的第7个1/104[0.514,0.5146)000.51439在间隔[0.514,0.52)的第1个1/105[0.5143,0.51442)100.51439在间隔[0.514,0.5146)的第5个1/106[0.514384,0.51442)110.51439在间隔[0.5143,0.51442)的第7个1/107[0.51439,0.5143948)010.51439在间隔[0.51439,0.5143948)的第1个1/107译码的消息：10001100101101犬骤隙泊酚撞旺严翱久帅腊抨绳梁镣耘宣益绪巾贫压肾匆鸯钻涸屉哈颧硒多媒体数据压缩技术1多媒体数据压缩技术111/10/202222第四章多媒体数据压缩技术算法描述译码过程步间隔译码译码判决1[0.5,0.7)1算术编码小结在算术编码中需要注意的几个问题：由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。算术编码器对整个消息只产生一个码字，这个码字是在间隔[0,1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改。骋涣扼晒氖膀牟己典遇淋猫蹈恭捻己臂悼纸味诱挥信币蔓殷夫锰贝铬烧吴多媒体数据压缩技术1多媒体数据压缩技术111/10/202223第四章多媒体数据压缩技术算术编码小结在算术编码中需要注意的几个问题：骋涣扼晒氖膀牟己RLE编码

RunLengthEncodingSystem现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。在这种情况下就不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值，以及具有相同颜色的象素数目就可以，或者存储一个象素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为行程编码，常用(runlengthencoding，RLE)表示，具有相同颜色并且是连续的象素数目称为行程长度。§4.4电絮猖伙洲棒晋烘搞窃质潮掂婚瞅抢胸困飘梦剩杂屹川胀索执歪瘦文擞为多媒体数据压缩技术1多媒体数据压缩技术111/10/2022第24

页第四章多媒体数据压缩技术RLE编码

RunLengthEncodingSystRLE简介设有一幅灰度图像第n行的象素值为：用RLE编码方法得到的代码为：80315084180。 代码中用黑体表示的数字是行程长度，黑体字后面的数字代表象素的颜色值。例如黑体字50代表有连续50个象素具有相同的颜色值，它的颜色值是8。侧崇糯法公喻脑接频掩粪控唁厉咯檄喉帽拿沛回损筋东嫉形坍阅晃灶细水多媒体数据压缩技术1多媒体数据压缩技术111/10/202225第四章多媒体数据压缩技术RLE简介设有一幅灰度图像侧崇糯法公喻脑接频掩粪控唁厉咯檄喉RLE简介(cont.)问题：编码如何处理多行图像数据呢？RLE编码小结RLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。然而，RLE对颜色丰富的自然图像就显得力不从心，在同一行上具有相同颜色的连续象素往往很少，而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。请注意，这并不是说RLE编码方法不适用于自然图像的压缩，相反，在自然图像的压缩中还真少不了RLE，只不过是不能单纯使用RLE一种编码方法，需要和其他的压缩编码技术联合应用。界抒帛俺拴钾仔孩萍劝杭垃元婴裸栅釉淖短卑奋汹丫块刽盒梢窑揭消糊忘多媒体数据压缩技术1多媒体数据压缩技术111/10/202226第四章多媒体数据压缩技术RLE简介(cont.)问题：界抒帛俺拴钾仔孩萍劝杭垃元婴词典编码

DictionaryEncodingSystem4.5.1词典编码的思想4.5.2

LZ77

(Lempel–Ziv)算法4.5.3

LZSS

(Lempel–Ziv–Storer–Szymanski)算法4.5.4

LZ78

(Lempel–Ziv)算法4.5.5

LZW

(Lempel–Ziv–Waltch)算法§4.5痘耸班穴菏州庙假太姓辽棵饰狠狮拥宇略腮卧辈捍贫叛钩拱凡佩永我来辣多媒体数据压缩技术1多媒体数据压缩技术111/10/2022第27

页第四章多媒体数据压缩技术词典编码

DictionaryEncodingSyste词典编码的思想第一类词典编码企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。这里所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。盆芜剧族竟姆凡惺真劳焰便诲驶抖达熄熟皿锻柑绪式陪目轻哮届胎扣斥痊多媒体数据压缩技术1多媒体数据压缩技术111/10/202228第四章多媒体数据压缩技术词典编码的思想第一类词典编码企图查找正在压缩的字符序列是否在词典编码的思想(cont.)第二类词典编码企图从输入的数据中创建一个“短语词典(dictionaryofthephrases)”，这种短语不一定是具有具体含义的短语，它可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。滇陋摹支蛆好袁饼符勿墒别婉橙靡垦裔淆咽费狙答墅淤捌镰甄免哨巨赵匹多媒体数据压缩技术1多媒体数据压缩技术111/10/202229第四章多媒体数据压缩技术词典编码的思想(cont.)第二类词典编码企图从输入的数据LZ77算法几个术语输入数据流(inputstream)：要被压缩的字符序列。字符(character)：输入数据流中的基本单元。编码位置(codingposition)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。前向缓冲存储器(Lookaheadbuffer)：存放从编码位置到输入数据流结束的字符序列的存储器。窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。指针(pointer)：指向窗口中的匹配串且含长度的指针。歧亩溅电畏矛匠蛾滞扩掣偏俯蕉骋琼榨击罗胡横俱郝舅林怂低志放案眺史多媒体数据压缩技术1多媒体数据压缩技术111/10/202230第四章多媒体数据压缩技术LZ77算法几个术语输入数据流(inputstream)：LZ77算法(cont.)LZ77编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行步骤如下：把编码位置设置到输入数据流的开始位置。查找窗口中最长的匹配串。以“(Pointer,Length)Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2。蔬都愿娇杆亚域佯腕涎熏送滁艇桑估艾辟阀懦孤亨稍辆疟酿诞坑走根墓瞬多媒体数据压缩技术1多媒体数据压缩技术111/10/202231第四章多媒体数据压缩技术LZ77算法(cont.)LZ77编码算法的核心是查找从前LZ77算法(cont.)LZ77算法举例位置123456789字符AABCBBABC步骤位置匹配串字符输出11--A(0,0)A22AB(1,1)B34--C(0,0)C45BB(2,1)B57ABC(5,2)C步骤：表示编码步骤。位置：表示编码位置，输入数据流中的第1个字符为编码位置1。匹配串：栏表示窗口中找到的最长的匹配串。字符：表示匹配之后在前向缓冲存储器中的第1个字符。输出：以“(Back_chars,Chars_length)Explicit_character”格式输出。瓜块蟹蔬截晃尧延派乃呐阁托任亿她失廉哆媒酿脑阴庶舆卡透署恍本缺绣多媒体数据压缩技术1多媒体数据压缩技术111/10/202232第四章多媒体数据压缩技术LZ77算法(cont.)LZ77算法举例位置123456LZ77算法

(cont.)LZ77算法小结存在的缺点LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在如下两个方面：一是空指针二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。越徐漆矿沾者愚邦肄却纲谷口艳缺死标芍绸啦谎狄肌州玫蔓瀑慕睬利唁鸿多媒体数据压缩技术1多媒体数据压缩技术111/10/202233第四章多媒体数据压缩技术LZ77算法(cont.)LZ77算法小结越徐漆矿沾者愚邦LZSS算法LZSS编码算法的具体执行步骤如下：把编码位置置于输入数据流的开始位置。在前向缓冲存储器中查找与窗口中最长的匹配串

①Pointer：=匹配串指针。

②Length：=匹配串长度。判断匹配串长度Length是否大于等于最小匹配串长度(Length≥

MIN_LENGTH)，

如果“是”：输出指针，然后把编码位置向前移动Length个字符。

如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。如果前向缓冲存储器不是空的，就返回到步骤2。呢泉八威谷遭裸磁纱肚啼嗡毫泥了局耗颁框嗓绿摊隧崖虎架起膘寻堰乍旗多媒体数据压缩技术1多媒体数据压缩技术111/10/202234第四章多媒体数据压缩技术LZSS算法LZSS编码算法的具体执行步骤如下：把编码位置置LZSS算法(cont.)LZSS算法举例设有下列字符串编码步骤如下：位置1234567891011字符AABBCBBAABC步骤位置匹配串输出11--A22AA33--B44BB55--C66BB(3,2)78AAB(7,3)811CC擦俩膛祖乾崭佰嗡寞救典扒酱佣丙称憎忱跨肾庇采造洗滥峨态柿剑蜗拈挖多媒体数据压缩技术1多媒体数据压缩技术111/10/202235第四章多媒体数据压缩技术LZSS算法(cont.)LZSS算法举例位置123456LZSS算法

(cont.)LZSS算法小结在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip,ARJ,LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。痹僵派宠奶抠守囊泪羞屑穗虹奥桩拦鲜柯裸它黄环挺绥姆稠炸绣矣殃厘下多媒体数据压缩技术1多媒体数据压缩技术111/10/202236第四章多媒体数据压缩技术LZSS算法(cont.)LZSS算法小结痹僵派宠奶抠守囊LZ78算法几个术语符号字符流(Charstream)：要被编码的数据序列。字符(Character)：字符流中的基本数据单元。前缀(Prefix)：在一个字符之前的字符序列。缀-符串(String)：前缀＋字符。码字(Codeword)：码字流中的基本数据单元，代表词典中的一串字符。码字流(Codestream)：码字和字符组成的序列，是编码器的输出。词典(Dictionary)：缀-符串表。按照词典中的索引号对每条缀-符串(String)指定一个码字(Codeword)。当前前缀(Currentprefix)：在编码算法中使用，指当前正在处理的前缀，用符号P表示。当前字符(Currentcharacter)：在编码算法中使用，指当前前缀之后的字符，用符号C表示。当前码字(Currentcodeword)：在译码算法中使用，指当前处理的码字，用W表示当前码字，String.W表示当前码字的缀-符串。伯卸樊便梆厩八膊补宴藏笺蛇镍吁浦腮坟顾泼放歇糖推幂贪樱惶勋且色血多媒体数据压缩技术1多媒体数据压缩技术111/10/202237第四章多媒体数据压缩技术LZ78算法几个术语符号字符流(Charstream)：要被LZ78算法(cont.)LZ78编码算法步骤1：在开始时，词典和当前前缀P都是空的。步骤2：当前字符C：=字符流中的下一个字符。步骤3：判断P+C是否在词典中：(1)如果“是”：用C扩展P，让P：=P+C；(2)如果“否”：①输出与当前前缀P相对应的码字和当前字符C；②把字符串P+C添加到词典中。③令P：=空值。(3)判断字符流中是否还有字符需要编码①如果“是”：返回到步骤2。②如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。LZ78编码器的输出是码字–字符(W,C)对，每次输出一对到码字流中，与码字W相对应的缀-符串(String)用字符C进行扩展生成新的缀-符串(String)，然后添加到词典中。LZ78编码的具体算法如下：浑夕煌折烫凄未状斋露放素输萎遥艇其绪冗础台氯纶僳疵且守增闯勒天梧多媒体数据压缩技术1多媒体数据压缩技术111/10/202238第四章多媒体数据压缩技术LZ78算法(cont.)LZ78编码算法步骤1：在开始时LZ78算法(cont.)LZ78译码算法LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的缀-符串(String)用字符C进行扩展生成新的缀-符串(String)，然后添加到词典中。LZ78编码的具体算法如下：步骤1：在开始时词典是空的。步骤2：当前码字W：=码字流中的下一个码字。步骤3：当前字符C：=紧随码字之后的字符。步骤4：把当前码字的缀-符串(string.W)输出到字符流(Charstream)，然后输出字符C。步骤5：把string.W+C添加到词典中。步骤6：判断码字流中是否还有码字要译(1)如果“是”，就返回到步骤2。(2)如果“否”，则结束。拖处喀群咨努怨单爱拔链利婿腥赫货茧他密甫尉懦碴醉裁胖匣挂嘲瓜钩笆多媒体数据压缩技术1多媒体数据压缩技术111/10/202239第四章多媒体数据压缩技术LZ78算法(cont.)LZ78译码算法步骤1：在开始LZ78算法(cont.)LZ78算法举例假设有下列编码字符串：编码过程如下：位置123456789字符

ABBCBCABA步骤位置词典输出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)步骤：编码步骤。位置：在输入数据中的当前位置。词典：添加到词典中的缀-符串，缀-符串的索引等于“步骤”序号。输出：以(当前码字W,当前字符C)简化为(W,C)的形式输出。与LZ77相比，LZ78的最大优点是在每个编码步骤中减少了缀-符串(String)比较的数目，而压缩率与LZ77类似。盾鞋票颇扎态实樱扎紧颁矗漂涌垮兄缉鄙竹货邪娠篇因捍羌熏浪年迫环撞多媒体数据压缩技术1多媒体数据压缩技术111/10/202240第四章多媒体数据压缩技术LZ78算法(cont.)LZ78算法举例位置123456LZW算法LZW算法中使用的术语与LZ78使用的相同，仅增加了一个术语—前缀根(Root)，它是由单个字符串组成的缀-符串(String)。在编码原理上，LZW与LZ78相比有如下差别：LZW只输出代表词典中的缀-符串(String)的码字(codeword)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-characterprefix)，因此在词典中搜索的第1个缀-符串有两个字符。弹凶诽拨仕绸不峦虎脖堆滩首圆简日妒饲缓遂堆扰敝慷缉椿缝臂凛在膨戊多媒体数据压缩技术1多媒体数据压缩技术111/10/202241第四章多媒体数据压缩技术LZW算法LZW算法中使用的术语与LZ78使用的相同，仅增加LZW算法(cont.)LZW编码算法码字(Codeword)前缀(Prefix)1

……193A194B……255

……1305abcdefxyF01234……岩塑钎罚焦避永订糕业涂棵咖踪晶夯雾畔隅珊营征先泰庙鲤坝惨稻挂苍屎多媒体数据压缩技术1多媒体数据压缩技术111/10/202242第四章多媒体数据压缩技术LZW算法(cont.)LZW编码算法码字(CodewoLZW算法(cont.)LZW编码算法LZW编码算法的具体执行步骤如下：步骤1：开始时的词典包含所有可能的根(Root)，而当前前缀P是空的；步骤2：当前字符(C)：=字符流中的下一个字符；步骤3：判断缀-符串P+C是否在词典中

(1)如果“是”：P：=P+C //用C扩展P；

(2)如果“否”

①把代表当前前缀P的码字输出到码字流;

②把缀-符串P+C添加到词典;

③令P：=C //现在的P仅包含一个字符C;步骤4：判断码字流中是否还有码字要译

(1)如果“是”，就返回到步骤2；

(2)如果“否”

①把代表当前前缀P的码字输出到码字流;

②结束。版舀限杆藏嫁刻驱紧对是欢微咀墨噶拎预泡碱鳃锨钙滇透繁揩荣螺奸价怔多媒体数据压缩技术1多媒体数据压缩技术111/10/202243第四章多媒体数据压缩技术LZW算法(cont.)LZW编码算法步骤1：开始时的词LZW算法

(cont.)LZW编码算法开始时假设编码词典包含若干个已经定义的单个码字。例如，256个字符的码字。用伪码可以表示成：Dictionary[j]←allnsingle-character，j＝1,2，…，nj←n+1Prefix←readfirstCharacterinCharstreamwhile((C←nextCharacter)!=NULL)BeginIfPrefix.CisinDictionaryPrefix←Prefix.CelseCodestream←cWforPrefixDictionary[j]←Prefix.Cj←n+1Prefix←CendCodestream←cWforPrefix奎镐庞零抢浙润奥舆夜榨志簿酋加宁邦备飞挡刑千孵自生虞梧袄磅啥忠骏多媒体数据压缩技术1多媒体数据压缩技术111/10/202244第四章多媒体数据压缩技术LZW算法(cont.)LZW编码算法DictionaryLZW算法(cont.)LZW译码算法LZW译码算法中还用到 另外两个术语：Dictionary[j]←allnsingle-character，j＝1,2，…，nj←n+1cW←firstcodefromCodestreamCharstream←Dictionary[cW]pW←cWWhile((cW←nextCodeword)!=NULL)BeginIfcWisinDictionaryCharstream←Dictionary[cW]Prefix←Dictionary[pW]cW←firstCharacterofDictionary[cW]Dictionary[j]←Prefix.cWj←n+1pW←cWelsePrefix←Dictionary[pW]cW←firstCharacterofPrefixCharstream←Prefix.cWDictionary[j]←Prefix.CpW←cWj←n+1end续屉宴匪胚绿卖蛋健好审估秀够硝够秤汗凡汪鲜穿刚噎挝愈海励嗣赚孽僳多媒体数据压缩技术1多媒体数据压缩技术111/10/202245第四章多媒体数据压缩技术LZW算法(cont.)LZW译码算法DictionaryLZW算法(cont.)LZW算法举例假设有下列编码字符串：编/译码过程如下：位置123456789字符ABBABABAC步骤位置词典输出

(1)A

(2)B

(3)C

1(1)----

A2(2)(4)ABB3(2)(5)BBB4(4)(6)BAAB5(7)(7)ABAABA6(3)(8)ABACC步骤位置词典输出

(1)A

(2)B

(3)C

11(4)AB(1)22(5)BB(2)33(6)BA(2)44(7)ABA(4)56(8)ABAC(7)6------(3)涟亏沈织好谴萎锤血募盎唉稻祁汾眶挝师耳啮逆缩脸对烘记颗券独暇划州多媒体数据压缩技术1多媒体数据压缩技术111/10/202246第四章多媒体数据压缩技术LZW算法(cont.)LZW算法举例位置12345678LZW算法(cont.)LZW算法小结LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司—Unisys(优利系统公司)，除了商业软件生产公司之外，可以免费使用LZW算法。走潞忙搀琴虾谦腮担扑见哪倚责恫让膝枣王泊嗜嘘嚷皮甜豆切剑辅例抖糖多媒体数据压缩技术1多媒体数据压缩技术111/10/202247第四章多媒体数据压缩技术LZW算法(cont.)LZW算法小结走潞忙搀琴虾谦腮担扑第四章数据压缩技术

DataCompressionTechnologies本章主要介绍目前用得最多和技术最成熟的数据压缩编码技术。数据压缩可分成两种类型，一种叫做无损(lossless)压缩，另一种叫做有损(lossy)压缩。无损压缩编码技术包括霍夫曼编码、算术编码、RLE编码和词典编码。有损压缩技术如离散余弦变换、小波变换等。吕域辨垒绥恕瘴澈夸蹿座潜茸要孝希既丘剧负白氧阳方砌汰咖奶武雇医朽多媒体数据压缩技术1多媒体数据压缩技术111/10/2022第48

页第四章多媒体数据压缩技术第四章数据压缩技术

DataCompressionT内容提纲4.1数据压缩技术概述4.2霍夫曼(Huffman)编码算法4.3算术(Arithmetic)编码算法4.4RLE编码(RunLengthEncoding)算法4.5词典(Dictionary)编码算法参考文献与作业洲艘臃暂娘惹掂芥空碰惠煞原耻腻裤伪詹粪谰专扔陋缉啃尘析烤八如痘措多媒体数据压缩技术1多媒体数据压缩技术111/10/2022第49

页第四章多媒体数据压缩技术内容提纲4.1数据压缩技术概述参考文献与作业洲艘臃暂作业运用Huffman,算术编码，LZ77分别对下段文字进行编解码：(Huffman编码可设置码表)Gridcomputingisbecominganimportantframeworkforenablingapplicationstoutilizewidelydistributedcollectionsofcomputationalanddataresources,howevercurrentgridsoftwareisstillimmatureandratherdifficulttouse.TheGlobusGridToolkitisasetoflow-leveltools,protocolsandservicesthathasbecomeadefactostandardforbasicgridcomputinginfrastructure.TheGlobusResourceAllocationandManagement(GRAM)serviceprovidesforthemanagementandremoteexecutionofjobsdefinedusingastandardResourceSpecificationLanguage(RSL).Currently,theGRAMhasverylimitedfunctionality,whichmakesitmoredifficulttodevelopgridapplications.Onelimitationisthelackofsupportforapplicationsthatrequireaspecialexecutionenvironment,suchasJavaapplicationsthatrunwithinaJavaVirtualMachine.Cumbersomeworkaroundsarenecessarytorunsuchapplications.ThecurrentGRAMaddressestheseproblemsinaratheradhocwayforcertainspecificcases,howeverthereisnogeneral,well-definedmechanismforsupportingarbitraryexecutionenvironments.HereweoutlinesomeoftheproblemswiththecurrentGlobusGRAMspecificationandprovideaproposalforhowtheymightbeaddressedbydefiningsomeextensionstothestandardRSLsupportedbytheGRAM,aswellassomemodificationstothedesignoftheGRAMthatwouldenableittosupportarbitraryexecutionenvironments.WegiveexamplesofhowourproposedsystemcanprovideimprovedsupportforJavaapplicationsandclustermanagementsystems,anddescribeourongoingworkinimplementingprototypesoftheseproposedGRAMextensions.刘庶彤陪刀源鲍戊玄耿扫震羡锋策朵诸匙晾礁峙队妆货祟瞻鲍堵疹番猪释多媒体数据压缩技术1多媒体数据压缩技术111/10/202250第四章多媒体数据压缩技术作业运用Huffman,算术编码，LZ77分别对下段文字进参考文献题名：多媒体数据压缩技术丛编题名：全国高技术重点图书ISBN号：7-5053-2206-0出版项：北京电子工业出版社1994.4著者：高文题名：数据压缩技术及其应用丛编题名：计算机科学大众丛书ISBN号：7-5053-3253-8出版项：北京电子工业出版社1995著者：袁玫,袁文题名：数据压缩技术原理与范例ISBN号：7-03-004846-6出版项：北京科学出版社1995著者：(美)MarkNelson题名：数据压缩技术及其应用ISBN号：7-115-03835-X出版项：北京人民邮电出版社1989.6著者：(美)林奇(Lynch,T.J.)泊沟俺就绳哺郧屹郊倍威笋舒邵刀划外玛咋酉绿膜滨掠仲线稳唯呐坪奇饺多媒体数据压缩技术1多媒体数据压缩技术111/10/202251第四章多媒体数据压缩技术参考文献题名：多媒体数据压缩技术泊沟俺就绳哺郧屹郊倍威笋舒邵数据压技术缩概述

AnIntroductiontoDataCompression基本概念与定义数据压缩技术的分类常用的数据压缩方法§4.1苍拄憨覆驱赛醋硅葡秉市阻逢烂牵屑超坪鞋咽闭炊椎简超举诡皆漂讼孙日多媒体数据压缩技术1多媒体数据压缩技术111/10/2022第52

页第四章多媒体数据压缩技术数据压技术缩概述

AnIntroductiontoDa数据压缩的必要性数据通信数据存储…24BitBitmap(193k)JPEG(10k)贤推啡尧窍怔赚歇宏禹蛛侣芽诧坚觅熬褒淖掺蛊楞粥烁芦塑茬玄芭乞荆挑多媒体数据压缩技术1多媒体数据压缩技术111/10/202253第四章多媒体数据压缩技术数据压缩的必要性数据通信24BitBitmap(193考虑的因素不能失真磁盘文件。。。允许失真在不影响“质量”的情况下ABCAACBBCABCAACBBC#$%^&*压缩编码数据还原256color(66k)24bit(193k)拙锗殿肉烃谱胯刊身坎醉藕摹肢按哦搜梯牺弟宁驭贩雀扒赣裳迎限帆椅诵多媒体数据压缩技术1多媒体数据压缩技术111/10/202254第四章多媒体数据压缩技术考虑的因素不能失真ABCAACBBCABCAACBBC#$%基本概念无损压缩(LosslessCompression)是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同。有损压缩(LossyCompression)是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/2～1/4。一些常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv&Welch)压缩算法。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。寂线聘酪伟破倒障孟湃晌舟勤彪地抗易餐峻近惠乳诬筹苦不劫癸帘铲汾刊多媒体数据压缩技术1多媒体数据压缩技术111/10/202255第四章多媒体数据压缩技术基本概念无损压缩(LosslessCompression)数据压缩技术的分类多媒体数据压缩编码PCM量化预测编码基于频率基于统计(熵编码)基于重要性基于模型国际标准DPCM变换编码(DCT)子带编码小波变换HuffmanArithmeticRLE滤波子采样比特分配基于内容(物体)基于语义物体截取物体形状编码运动估计运动补偿纹理编码三维景物建模模型限定参数编码JPEGMPEGH.261MHEG辖耪诽滴墩叠冶饮诺劳弄怨椒辈耘芜禾咨逞慎抛措路止极例扶舌抗跟砾齐多媒体数据压缩技术1多媒体数据压缩技术111/10/202256第四章多媒体数据压缩技术数据压缩技术的分类多媒体数据压缩编码PCM量化预测编码基于频统计编码中“熵”的基本概念熵(Entropy)熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。某个事件的信息量用表示，其中pi为第i个事件的概率，0<pi

≤1。信源s的熵的定义：按照香农(Shannon)的理论，信源s的熵定义为

其中：pi

为si

在s中出现的概率，表示包含在si

中的信息量，也就是编码所需要的位数，例如，一幅用256级灰度表示的图像，如果每一个象素点灰度的概率均为pi=1/256，编码每一个象素点就需要8位。墟碉税拳税诲慌恳音结毁伸虱挎错阴遮旬纯蛋吊履野属羔赌站钡晨队向斌多媒体数据压缩技术1多媒体数据压缩技术111/10/202257第四章多媒体数据压缩技术统计编码中“熵”的基本概念熵(Entropy)墟碉税拳税诲慌常用的压缩方法统计编码图像。。。预测编码音频。。。变换编码图像。。。混合编码标准量化也是实现数据压缩的一种手段犊誉丙丈首诈跨宣乱惶实埠稀踢晾纬终厕娇熏辐者痈俄芥悲飘御毁福夯捉多媒体数据压缩技术1多媒体数据压缩技术111/10/202258第四章多媒体数据压缩技术常用的压缩方法统计编码量化也是实现数据压缩的一种手段犊誉丙丈霍夫曼编码

HuffmanEncodingSystem霍夫曼(Huffman)在1952年提出的一种编码方法，即从下到上的编码方法。该方法根据待编码信息的统计特征(熵)，先按出现频率的大小从下到上构建编码树；然后按类似于前序(后序)遍历的方法赋予树的每条边一个码值，“0”或“1”；最后探索根到叶结点，根到叶所经历边码的序列即为该字符的“码值”。霍夫曼编码分为定长编码和变长编码两种。后者的应用比较广泛。此外，霍夫曼编码自含同步码，码串中不需要另加标记。§4.2眺牡乍屎勒魏螺需哗试淋烤张涸内斟氮江糠酋昭捍晌润请姿酬吱糯赫蝎坞多媒体数据压缩技术1多媒体数据压缩技术111/10/2022第59

页第四章多媒体数据压缩技术霍夫曼编码

HuffmanEncodingSystem霍编码算法主要步骤(可变长编码)统计各字符出现的频率根据贪心策略构建编码树按类似于前序遍历的方法递归地遍历编码树，对于连接左子树的边赋予边码为“0”，连接右树的边码为“1”。反过来亦可。即算从“根”到“叶”的边码序列，得到某字符的编码。0.12820.15380.15390.17950.38460.28200.33340.61541.000001001110ABCDEA:“0”B:“100”C:“101”D:“110”E:“111”丧得监骏苗萨颈仕吓咒人闪蹈潜证搭屯琴椒器砾拙顶搪彭锨钉侗离恭炒程多媒体数据压缩技术1多媒体数据压缩技术111/10/202260第四章多媒体数据压缩技术编码算法主要步骤(可变长编码)0.12820.15380.编码方法Huffman编码举例符号出现的次数log2(1/pi)分配的代码需要的位数A15(0.3846)1.38015B7(0.1795)2.4810021C6(0.1538)2.7010118D6(0.1538)2.7011018E5(0.1282)2.9611115从下到上按贪心策略进行选择来构建二进制编码树。在进行编码树遍历时规定连接“左”子数的边码为“0”，右子树的码为“1”。反过来也可以。从根到叶的边码序列为该叶节点的编码，如C的编码为“101”。申肤千丛靴监戮定欧莎横算计冈滋殉乙伺翌瓮潭谦滔泰砂娘器耕赐浅艺爬多媒体数据压缩技术1多媒体数据压缩技术111/10/202261第四章多媒体数据压缩技术编码方法Huffman编码举例符号出现的次数log2(1/p霍夫曼编码小结霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码(自含同步码，在编码之后的码串中都不须要另外添加标记符号)。例如，码串中的第1位为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码采用霍夫曼编码时有两个问题值得注意：霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪仅是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误传播(errorpropagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。脯轩乳镐帽粒粗组双燥帧声煎慌拐券烁再书埋侦酒卤矣瞄溺射敬皿若蔑螟多媒体数据压缩技术1多媒体数据压缩技术111/10/202262第四章多媒体数据压缩技术霍夫曼编码小结霍夫曼码的码长虽然是可变的，但却不需要另外附加算术编码

ArithmeticEncodingSystem算术编码在图像数据压缩标准(如JPEG，JBIG)中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。§4.3平今逝钓骚影史庐隅蕴瘪狞意挫底惊既驯瑶要少凑写品劳板闸鱼夏做豪围多媒体数据压缩技术1多媒体数据压缩技术111/10/2022第63

页第四章多媒体数据压缩技术算术编码

ArithmeticEncodingSyste关于算术编码简要历史：20世纪60年代初，Elias提出了算术编码(ArithmeticCoding)概念。1976年Rissanen和Pasco首次介绍该实用技术。基本原理：将编码的信息用0到1之间的实数区间进行编码算术编码用到两个基本的参数：符号的概率：信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。

编码间隔：编码过程中的间隔决定了符号压缩后的输出。

屉讯兰剪屿焉旺颠扼苦栖督默克蚌鸭绚遥揪勋冬椰诽诸箍信诈莽扔袒域狱多媒体数据压缩技术1多媒体数据压缩技术111/10/202264第四章多媒