《多媒体数据压缩技术》由会员分享，可在线阅读，更多相关《多媒体数据压缩技术（47页珍藏版）》请在金锄头文库上搜索。
1、第四章 数据压缩技术Data Compression TechnologiesData Compression Technologies本章主要介绍目前用得最多和技术最成熟的数据压缩编本章主要介绍目前用得最多和技术最成熟的数据压缩编码技术。数据压缩可分成两种类型，一种叫做无损码技术。数据压缩可分成两种类型，一种叫做无损(lossless)(lossless)压缩，另一种叫做有损压缩，另一种叫做有损( (lossylossy) )压缩。压缩。无损压缩编码技术包括霍夫曼编码、算术编码、无损压缩编码技术包括霍夫曼编码、算术编码、RLERLE编编码和词典编码。码和词典编码。有损压缩技术如离散余弦变换、
2、小波变换等。有损压缩技术如离散余弦变换、小波变换等。2024/8/18第 1 1 页第四章 多媒体数据压缩技术内容提纲4.1数据压缩技术概述4.2霍夫曼( (HuffmanHuffman) )编码算法4.3算术( (ArithmeticArithmetic) )编码算法4.4RLE编码( (Run Length EncodingRun Length Encoding) )算法4.5词典( (DictionaryDictionary) )编码算法参考文献与作业参考文献与作业2024/8/18第 2 2 页第四章 多媒体数据压缩技术回到第一页作业vv运用运用Huffman,Huffman,算术编码
3、，算术编码，LZ77LZ77分别对下段文字进行编解分别对下段文字进行编解码码： ( (HuffmanHuffman编码可设置码表编码可设置码表) )GridcomputingisbecominganimportantframeworkforenablingapplicationstoutilizewidelyGridcomputingisbecominganimportantframeworkforenablingapplicationstoutilizewidelydistributedcollectionsofcomputationalanddataresources,howevercur
4、rentgridsoftwareisstilldistributedcollectionsofcomputationalanddataresources,howevercurrentgridsoftwareisstillimmatureandratherdifficulttouse.Theimmatureandratherdifficulttouse.TheGlobusGlobusGridToolkitisasetoflow-leveltools,protocolsandGridToolkitisasetoflow-leveltools,protocolsandservicesthathasb
5、ecomeadefactostandardforbasicgridcomputinginfrastructure.Theservicesthathasbecomeadefactostandardforbasicgridcomputinginfrastructure.TheGlobusGlobus ResourceAllocationandManagement(GRAM)serviceprovidesforthemanagementandremoteResourceAllocationandManagement(GRAM)serviceprovidesforthemanagementandrem
6、oteexecutionofjobsdefinedusingastandardResourceSpecificationLanguage(RSL).Currently,theexecutionofjobsdefinedusingastandardResourceSpecificationLanguage(RSL).Currently,theGRAMhasverylimitedfunctionality,whichmakesitmoredifficulttodevelopgridapplications.OneGRAMhasverylimitedfunctionality,whichmakesi
7、tmoredifficulttodevelopgridapplications.Onelimitationisthelackofsupportforapplicationsthatrequireaspecialexecutionenvironment,suchaslimitationisthelackofsupportforapplicationsthatrequireaspecialexecutionenvironment,suchasJavaapplicationsthatrunwithinaJavaVirtualMachine.Cumbersomeworkaroundsarenecess
8、arytoJavaapplicationsthatrunwithinaJavaVirtualMachine.Cumbersomeworkaroundsarenecessarytorunsuchapplications.ThecurrentGRAMaddressestheseproblemsinaratheradhocwayforcertainrunsuchapplications.ThecurrentGRAMaddressestheseproblemsinaratheradhocwayforcertainspecificcases,howeverthereisnogeneral,well-de
9、finedmechanismforsupportingarbitraryexecutionspecificcases,howeverthereisnogeneral,well-definedmechanismforsupportingarbitraryexecutionenvironments.Hereweoutlinesomeoftheproblemswiththecurrentenvironments.HereweoutlinesomeoftheproblemswiththecurrentGlobusGlobusGRAMspecificationandGRAMspecificationan
10、dprovideaproposalforhowtheymightbeaddressedbydefiningsomeextensionstothestandardRSLprovideaproposalforhowtheymightbeaddressedbydefiningsomeextensionstothestandardRSLsupportedbytheGRAM,aswellassomemodificationstothedesignoftheGRAMthatwouldenablesupportedbytheGRAM,aswellassomemodificationstothedesigno
11、ftheGRAMthatwouldenableittosupportarbitraryexecutionenvironments.Wegiveexamplesofhowourproposedsystemcanittosupportarbitraryexecutionenvironments.WegiveexamplesofhowourproposedsystemcanprovideimprovedsupportforJavaapplicationsandclustermanagementsystems,anddescribeourprovideimprovedsupportforJavaapp
12、licationsandclustermanagementsystems,anddescribeourongoingworkinimplementingprototypesoftheseproposedGRAMextensions.ongoingworkinimplementingprototypesoftheseproposedGRAMextensions.2024/8/183第四章 多媒体数据压缩技术回到第一页参考文献vv题名：题名：题名：题名：多媒体数据压缩技术多媒体数据压缩技术uu丛编题名丛编题名丛编题名丛编题名：全国高技术重点图书全国高技术重点图书uuISBNISBN号：号：7-50
13、53-2206-07-5053-2206-0uu出版项出版项出版项出版项：北京北京 电子工业出版社电子工业出版社 1994.41994.4uu著者：著者：著者：著者：高文高文vv题名：题名：题名：题名：数据压缩技术及其应用数据压缩技术及其应用uu丛编题名：丛编题名：丛编题名：丛编题名：计算机科学大众丛书计算机科学大众丛书uuISBNISBN号：号：号：号： 7-5053-3253-87-5053-3253-8uu出版项：出版项：出版项：出版项：北京北京 电子工业出版社电子工业出版社 19951995 uu著者：著者：著者：著者：袁玫袁玫, ,袁文袁文vv题名：题名：题名：题名：数据压缩技术原理
14、与范例数据压缩技术原理与范例uuISBNISBN号：号：号：号： 7-03-004846-67-03-004846-6uu出版项：出版项：出版项：出版项：北京北京 科学出版社科学出版社 19951995uu著者：著者：著者：著者：( (美美)MarkNelson)MarkNelsonvv题名：题名：题名：题名：数据压缩技术及其应用数据压缩技术及其应用uuISBNISBN号：号：号：号：7-115-03835-X7-115-03835-Xuu出版项：出版项：出版项：出版项：北京北京 人民邮电出版社人民邮电出版社 1989.61989.6 uu著者：著者：著者：著者：( (美美) )林奇林奇( (
15、Lynch,T.JLynch,T.J.) .)2024/8/184第四章 多媒体数据压缩技术数据压技术缩概述An Introduction to Data CompressionAn Introduction to Data Compressionv 基本概念与定义基本概念与定义v 数据压缩技术的分类数据压缩技术的分类v 常用的数据压缩方法常用的数据压缩方法4.12024/8/18第 5 5 页第四章 多媒体数据压缩技术回到第一页数据压缩的必要性vv数据通信数据通信vv数据存储数据存储vv24BitBitmap(193k)24BitBitmap(193k)JPEG(10k)JPEG(10k)2
16、024/8/186第四章 多媒体数据压缩技术回到第一页考虑的因素vv不能失真不能失真uu磁盘文件磁盘文件uu。vv允许失真允许失真uu在不影响在不影响“ “质量质量” ”的情况下的情况下ABCAACBBCABCAACBBCABCAACBBCABCAACBBC#$%&*#$%&*压缩编码压缩编码数据还原数据还原256color(66k)256color(66k)24bit(193k)24bit(193k)2024/8/187第四章 多媒体数据压缩技术回到第一页基本概念vv无损压缩无损压缩( (Lossless CompressionLossless Compression) )是指使用压缩后的数
17、据进是指使用压缩后的数据进行重构行重构( (或者叫做还原，解压缩或者叫做还原，解压缩) )，重构后的数据与原来的，重构后的数据与原来的数据完全相同。数据完全相同。vv有损压缩有损压缩( (LossyLossy Compression Compression) )是指使用压缩后的数据进行是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。人对原始资料表达的信息造成误解。无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的
18、例无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的文件的数据压缩到原来的文件的数据压缩到原来的文件的数据压缩到原来的1/21/21/41/4。一些常用的无损压缩算法有霍夫曼。一些常用的无损压缩算法有霍夫曼。一些常用的无损压缩算法有
19、霍夫曼。一些常用的无损压缩算法有霍夫曼(Huffman)(Huffman)算法和算法和算法和算法和LZW(Lenpel-ZivLZW(Lenpel-Ziv & Welch) & Welch)压缩算法。压缩算法。压缩算法。压缩算法。 有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的像和声音的压缩就可以采用有损压缩，因为
20、其中包含的数据往往多于我们的像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。像所表达的意思产生误解，但可大大提高压缩比。像所表达的意思产生误解，但可大大提高压缩比。像所表达的意思产生误解，但可大大提高压缩比。
21、 2024/8/188第四章 多媒体数据压缩技术回到第一页数据压缩技术的分类多媒体数据压缩编码PCM量化预测编码基于频率基于统计(熵编码)基于重要性基于模型国际标准DPCM变换编码(DCT)子带编码小波变换HuffmanArithmeticRLE滤波子采样比特分配基于内容(物体)基于语义物体截取物体形状编码运动估计运动补偿纹理编码三维景物建模模型限定参数编码JPEGMPEGH.261MHEG2024/8/189第四章 多媒体数据压缩技术回到第一页统计编码中“熵”的基本概念vv熵熵( (EntropyEntropy) )uu熵是信息量的度量方法，它表示某一事件出现的消息越多，事件熵是信息量的度量
22、方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。发生的可能性就越小，数学上就是概率越小。 uu某个事件的信息量用某个事件的信息量用表示表示 ， 其中其中p pi i为第为第i i个事件的概个事件的概率，率，00p pi i 11。uu信源信源s s的熵的的熵的定义定义：按照香农：按照香农(Shannon)(Shannon)的理论，信源的理论，信源s s的熵定义为的熵定义为 其中：其中： p pi i 为为 s si i 在在 s s中出现的概率，中出现的概率，表示包含在表示包含在 s si i 中的信息量，也就中的信息量，也就是编码所需要的位数，例如，一幅用是编
23、码所需要的位数，例如，一幅用256256级灰度表示的图像，如果每一个象级灰度表示的图像，如果每一个象素点灰度的概率均为素点灰度的概率均为 p pi i=1/256=1/256，编码每一个象素点就需要，编码每一个象素点就需要8 8位位 。2024/8/1810第四章 多媒体数据压缩技术回到第一页常用的压缩方法vv统计编码统计编码uu图像图像uu。vv预测编码预测编码uu音频音频uu。vv变换编码变换编码uu图像图像uu。vv混合编码混合编码uu标准标准量化也是实现数据量化也是实现数据压缩的一种手段压缩的一种手段2024/8/1811第四章 多媒体数据压缩技术霍夫曼编码Huffman Encodi
24、ng SystemHuffman Encoding System霍夫曼霍夫曼(Huffman)(Huffman)在在19521952年提出的一种编码方法，即从年提出的一种编码方法，即从下到上的编码方法。该方法根据待编码信息的统计特下到上的编码方法。该方法根据待编码信息的统计特征征( (熵熵) )，先按出现频率的大小从下到上构建编码树；然，先按出现频率的大小从下到上构建编码树；然后按类似于前序后按类似于前序( (后序后序) )遍历的方法赋予树的每条边一个遍历的方法赋予树的每条边一个码值，码值，“ “0”0”或或“ “1”1”；最后探索根到叶结点，根到叶；最后探索根到叶结点，根到叶所经历边码的序列
25、即为该字符的所经历边码的序列即为该字符的“ “码值码值” ”。霍夫曼编码分为定长编码和变长编码两种。后者的应霍夫曼编码分为定长编码和变长编码两种。后者的应用比较广泛。此外，霍夫曼编码自含同步码，码串中用比较广泛。此外，霍夫曼编码自含同步码，码串中不需要另加标记。不需要另加标记。4.22024/8/18第 12 12 页第四章 多媒体数据压缩技术回到第一页编码算法vv主要步骤主要步骤 ( (可变长编码可变长编码) )uu统计各字符出现的频率统计各字符出现的频率uu根据贪心策略构建编码树根据贪心策略构建编码树uu按类似于前序遍历的方法递归地遍历编码树，对于连接左子树的按类似于前序遍历的方法递归地遍
26、历编码树，对于连接左子树的边赋予边码为边赋予边码为“ “0”0”，连接右树的边码为，连接右树的边码为“ “1”1”。反过来亦可。反过来亦可。uu即算从即算从“ “根根” ”到到“ “叶叶” ”的边码序列，得到某字符的编码。的边码序列，得到某字符的编码。0.12820.15380.15390.17950.38460.28200.33340.61541.00000 01 10 00 01 11 11 10 0A AB BC CD DE EA : “A : “0 0” ”B : “B : “100100” ”C : “C : “101101” ”D : “D : “110110” ”E : “E :
27、 “111111” ”2024/8/1813第四章 多媒体数据压缩技术回到第一页编码方法vvHuffmanHuffman编码举例编码举例符号符号出出现现的次数的次数loglog2 2(1/p(1/pi i) )分配的代分配的代码码需要的位数需要的位数A A15(0.3846)15(0.3846)1.381.380 01515B B7(0.1795)7(0.1795)2.482.481001002121C C6(0.1538)6(0.1538)2.702.701011011818D D6(0.1538)6(0.1538)2.702.701101101818E E5(0.1282)5(0.1282
28、)2.962.9611111115151. 1.从下到上按贪心策略进行选择来构建从下到上按贪心策略进行选择来构建二进制编码树。二进制编码树。2. 2.在进行编码树遍历时规定连接在进行编码树遍历时规定连接“ “左左” ”子数的边码为子数的边码为“ “0”0”，右子树的码为，右子树的码为“ “1”1”。反过来也可以。反过来也可以。3. 3.从根到叶的边码序列为该叶节点的编从根到叶的边码序列为该叶节点的编码，如码，如C C的编码为的编码为“ “101”101”。2024/8/1814第四章 多媒体数据压缩技术回到第一页霍夫曼编码小结vv霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码霍夫曼码的
29、码长虽然是可变的，但却不需要另外附加同步代码( (自含自含同步码，在编码之后的码串中都不须要另外添加标记符号同步码，在编码之后的码串中都不须要另外添加标记符号) )。uu例如，码串中的第例如，码串中的第1 1位为位为0 0，那末肯定是符号，那末肯定是符号A A，因为表示其他符号的代，因为表示其他符号的代码没有一个是以码没有一个是以0 0开始的，因此下一位就表示下一个符号代码的第开始的，因此下一位就表示下一个符号代码的第1 1位。位。同样，如果出现同样，如果出现“ “110”110”，那么它就代表符号，那么它就代表符号D D。uu如果事先编写出一本解释各种代码意义的如果事先编写出一本解释各种代码
30、意义的“ “词典词典” ”，即码簿，那么就可，即码簿，那么就可以根据码簿一个码一个码地依次进行译码以根据码簿一个码一个码地依次进行译码vv采用霍夫曼编码时有两个问题值得注意：采用霍夫曼编码时有两个问题值得注意：uu霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪仅是能一个接一个地正确译出代码。但如果码串中有错误，哪仅是1 1位出现位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误
31、传播现象称为错误传播(errorpropagation)(errorpropagation)。计算机对这种错误也无能为力，。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。说不出错在哪里，更谈不上去纠正它。uu霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。然后再译码，这就需要在存储代码之前加以考虑。2024/8/1815第四章 多媒体数据压缩技术算术编码Arithmetic Encoding SystemArithmetic Encoding System
32、算术编码在图像数据压缩标准算术编码在图像数据压缩标准( (如如JPEGJPEG，JBIG)JBIG)中中扮演了重要的角色。在算术编码中，消息用扮演了重要的角色。在算术编码中，消息用0 0到到1 1之间的实数进行编码，算术编码用到两个基本的之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在源符号的间隔，而这些间隔包含在0 0到到1 1之间。编之间。编码过程中的间隔决定了符号压缩后的输出。码过程中的间隔决定了符
33、号压缩后的输出。4.32024/8/18第 16 16 页第四章 多媒体数据压缩技术回到第一页关于算术编码vv简要历史：简要历史：uu2020世纪世纪6060年代初，年代初，EliasElias提出了算术编码提出了算术编码(ArithmeticCoding)(ArithmeticCoding)概念。概念。19761976年年RissanenRissanen和和PascoPasco首次介绍该实用技术。首次介绍该实用技术。vv基本原理：基本原理：uu将编码的信息用将编码的信息用0 0到到1 1之间的实数区间进行编码之间的实数区间进行编码 uu算术编码用到两个基本的参数：算术编码用到两个基本的参数：
34、 符号的概率：信源符号的概率决定压缩编码的效率，也决定编码过符号的概率：信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在程中信源符号的间隔，而这些间隔包含在0 0到到1 1之间。之间。 编码间隔：编码过程中的间隔决定了符号压缩后的输出。编码间隔：编码过程中的间隔决定了符号压缩后的输出。 2024/8/1817第四章 多媒体数据压缩技术回到第一页算术编码简介vv编码举例编码举例uu假设信源符号、出现的概率和处世间隔如下：假设信源符号、出现的概率和处世间隔如下：uu编码过程：假设消息序列的输入顺序为：编码过程：假设消息序列的输入顺序为：10100000111100
35、00101011110101。 符符 号号0000010110101111概概 率率0.10.10.40.40.20.20.30.3初始初始编码间编码间隔隔0,0.1)0,0.1)0.1,0.5)0.1,0.5)0.5,0.7)0.5,0.7)0.7,1)0.7,1)2024/8/1818第四章 多媒体数据压缩技术回到第一页算法描述vv考虑一个有考虑一个有MM个符号个符号a ai i=(1,2,=(1,2,MM) )的字符表集，假定的字符表集，假定a ai i的概率的概率 p p( (a ai i)=)=p pi i，而，而vv输入的符号用输入的符号用x xn n表示，第表示，第n n个子间隔
36、的范围用个子间隔的范围用表示，其中：表示，其中：l l0 0=0,=0,d d0 0=0,=0,p p0 0=0,=0,l ln n表示间隔左边界的值，表示间隔左边界的值，r rn n表示间隔右边界的值，表示间隔右边界的值，d dn n=r rn n-l ln n表示间隔长度。表示间隔长度。2024/8/1819第四章 多媒体数据压缩技术回到第一页算法描述vv编码步骤如下：编码步骤如下：步骤步骤1 1：首先在：首先在1 1和和0 0之间给每个符号分配一个初始子间隔，子间隔的长度等于之间给每个符号分配一个初始子间隔，子间隔的长度等于它的概率，初始子间隔的范围为它的概率，初始子间隔的范围为I I1
37、 1。令。令 d d1 1=r r1 1- -l l1 1，L L=l l1 1 和和 R R=r r1 1。步骤步骤2 2：L L 和和 R R 的二进制表达式分别表示为：的二进制表达式分别表示为：和和其中其中 u uk k 和和 v vk k 等于等于“ “1”1”或者或者“ “0”0”。比较比较 u u1 1 和和 v v1 1 ： 如果如果，不发送任何数据，转到步骤，不发送任何数据，转到步骤3 3。反之，。反之，发送二进制符号发送二进制符号 u u1 1。比较比较 u u2 2 和和 v v2 2： 如果如果，不发送任何数据，转到步骤，不发送任何数据，转到步骤3 3；反之，；反之，发送
38、二进制符号发送二进制符号u u2 2。这种比较一直进行到两个符号不相同为止。这种比较一直进行到两个符号不相同为止。步骤步骤3 3：令：令 n = n = n n+1+1，读下一个符号。假设第，读下一个符号。假设第 n n 个输入符号为个输入符号为 x xn n =a ai i ，按照以，按照以前的步骤把这个间隔分成子间隔前的步骤把这个间隔分成子间隔 I In n；并令；并令 L L=I In n ，R R=r rn n 和和 d dn n=r rn n-l ln n， 转步骤转步骤2 2。2024/8/1820第四章 多媒体数据压缩技术回到第一页算法描述vv编码过程：编码过程：步步骤骤 输输入
39、入符号符号编码间编码间隔隔 编码编码判决判决1 110100.5,0.7)0.5,0.7)符号的间隔范围符号的间隔范围0.5,0.7)0.5,0.7)2 200000.5,0.52)0.5,0.52)0.5,0.7)0.5,0.7)间隔的第一个间隔的第一个1/101/103 311110.514,0.52)0.514,0.52)0.5,0.52)0.5,0.52)间隔的最后一个间隔的最后一个1/101/104 400000.514,0.5146)0.514,0.5146)0.514,0.52)0.514,0.52)间隔的第一个间隔的第一个1/101/105 510100.5143,0.5144
40、2)0.5143,0.51442)0.514,0.5146)0.514,0.5146)间隔的第五个间隔的第五个1/101/10开始，二个开始，二个1/101/106 611110.514384,0.51442)0.514384,0.51442)0.5143,0.51442)0.5143,0.51442)间隔的最后间隔的最后3 3个个1/101/107 701010.5143836,0.514402)0.5143836,0.514402)0.514384,0.51442)0.514384,0.51442)间隔的间隔的4 4个个1/101/10，从第，从第1 1个个1/101/10开始开始8 8从
41、从0.5143876,0.5144020.5143876,0.514402中选择一个数作为输出：中选择一个数作为输出：0.51438760.51438762024/8/1821第四章 多媒体数据压缩技术回到第一页算法描述vv译码过程译码过程步步骤骤 间间隔隔译码译码符号符号 译码译码判决判决 1 10.5,0.7)0.5,0.7)10100.514390.51439在间隔在间隔 0.5,0.7)0.5,0.7)2 20.5,0.52)0.5,0.52)00000.514390.51439在间隔在间隔 0.5,0.7)0.5,0.7)的第的第1 1个个1/101/103 30.514,0.52)
42、0.514,0.52)11110.514390.51439在间隔在间隔0.5,0.52)0.5,0.52)的第的第7 7个个1/101/104 40.514,0.5146)0.514,0.5146)00000.514390.51439在间隔在间隔0.514,0.52)0.514,0.52)的第的第1 1个个1/101/105 50.5143,0.51442)0.5143,0.51442)10100.514390.51439在间隔在间隔0.514,0.5146)0.514,0.5146)的第的第5 5个个1/101/106 60.514384,0.51442)0.514384,0.51442)1
43、1110.514390.51439在间隔在间隔0.5143,0.51442)0.5143,0.51442)的第的第7 7个个1/101/107 70.51439,0.5143948)0.51439,0.5143948)01010.514390.51439在间隔在间隔0.51439,0.5143948)0.51439,0.5143948)的第的第1 1个个1/101/107 7译码的消息：译码的消息：10001100101101100011001011012024/8/1822第四章 多媒体数据压缩技术回到第一页算术编码小结vv在算术编码中需要注意的几个问题：在算术编码中需要注意的几个问题：uu
44、由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有问题，但多数机器都有1616位、位、3232位或者位或者6464位的精度，因此这个问题可使位的精度，因此这个问题可使用比例缩放方法解决。用比例缩放方法解决。uu算术编码器对整个消息只产生一个码字，这个码字是在间隔算术编码器对整个消息只产生一个码字，这个码字是在间隔0,1)0,1)中的一中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。uu算术编码也是一种对错误很敏感的编
45、码方法，如果有一位发生错误就会算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。导致整个消息译错。vv算术编码可以是静态的或者自适应的。算术编码可以是静态的或者自适应的。uu在静态算术编码中，信源符号的概率是固定的。在静态算术编码中，信源符号的概率是固定的。uu在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改。动态地进行修改。2024/8/1823第四章 多媒体数据压缩技术RLE编码Run Length Encoding SystemRun Length Encoding S
46、ystem现实中有许多这样的图像，在一幅图像中具有许多颜现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。在这种情况下就不需要存储每一个象素的的颜色值。在这种情况下就不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值，以及具有相颜色值，而仅仅存储一个象素的颜色值，以及具有相同颜色的象素数目就可以，或者存储一个象素的颜色同颜色的象素数目就可以，或者存储一个象素的颜色值，以及具有相同颜色值的行数。这种压缩
47、编码称为值，以及具有相同颜色值的行数。这种压缩编码称为行程编码，常用行程编码，常用( (r rununl lengthengthe encodingncoding，RLE)RLE)表示，具有表示，具有相同颜色并且是连续的象素数目称为行程长度。相同颜色并且是连续的象素数目称为行程长度。4.42024/8/18第 2424 页第四章 多媒体数据压缩技术回到第一页RLE简介vv设有一幅灰度图像设有一幅灰度图像uu第第n n行的象素值为：行的象素值为：uu用用RLERLE编码方法得到的代码为：编码方法得到的代码为：8 80 03 31 150508 84 41 18 80 0。代码中用黑体表示的数字是
48、行程长度，黑体字后面的数字代表象代码中用黑体表示的数字是行程长度，黑体字后面的数字代表象素的颜色值。例如黑体字素的颜色值。例如黑体字5050代表有连续代表有连续5050个象素具有相同的颜色个象素具有相同的颜色值，它的颜色值是值，它的颜色值是8 8。2024/8/1825第四章 多媒体数据压缩技术回到第一页RLE简介(cont.)(cont.)vv问题：问题：uu编码如何处理多行图像数据呢？编码如何处理多行图像数据呢？vvRLERLE编码小结编码小结uuRLERLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。存储空间非
49、常有效。uu然而，然而，RLERLE对颜色丰富的自然图像就显得力不从心，在同一行上对颜色丰富的自然图像就显得力不从心，在同一行上具有相同颜色的连续象素往往很少，而连续几行都具有相同颜色具有相同颜色的连续象素往往很少，而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用值的连续行数就更少。如果仍然使用RLERLE编码方法，不仅不能压编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。缩图像数据，反而可能使原来的图像数据变得更大。uu请注意，这并不是说请注意，这并不是说RLERLE编码方法不适用于自然图像的压缩，相编码方法不适用于自然图像的压缩，相反，在自然图像的压缩中还真少不了
50、反，在自然图像的压缩中还真少不了RLERLE，只不过是不能单纯使，只不过是不能单纯使用用RLERLE一种编码方法，需要和其他的压缩编码技术联合应用。一种编码方法，需要和其他的压缩编码技术联合应用。2024/8/1826第四章 多媒体数据压缩技术词典编码Dictionary Encoding SystemDictionary Encoding System4.5.1词典编码的思想词典编码的思想4.5.2LZ77LZ77 (Lempel(LempelZivZiv) )算法算法4.5.3LZSSLZSS (Lempel(LempelZivZivStorerStorerSzymanski)Szyman
51、ski)算算法法4.5.4LZ78LZ78 (Lempel(LempelZivZiv) )算法算法4.5.5LZWLZW (Lempel(LempelZivZivWaltchWaltch) )算法算法4.52024/8/18第 2727 页第四章 多媒体数据压缩技术回到第一页词典编码的思想vv第一类词典编码第一类词典编码企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的符串的“指针指针
52、”。 这里所指的这里所指的“ “词典词典” ”是指用以前处理过的数据来表示编码过程中遇到的重是指用以前处理过的数据来表示编码过程中遇到的重复部分。复部分。2024/8/1828第四章 多媒体数据压缩技术回到第一页词典编码的思想(cont.)(cont.)vv第二类词典编码第二类词典编码企图从输入的数据中创建一个企图从输入的数据中创建一个“ “短语词典短语词典(dictionaryofthephrases)”(dictionaryofthephrases)”，这种，这种短语不一定是具有具体含义的短语，它可以是任意字符的组合。编码数据短语不一定是具有具体含义的短语，它可以是任意字符的组合。编码数据
53、过程中当遇到已经在词典中出现的过程中当遇到已经在词典中出现的“ “短语短语” ”时，编码器就输出这个词典中时，编码器就输出这个词典中的短语的的短语的“ “索引号索引号” ”，而不是短语本身。，而不是短语本身。 2024/8/1829第四章 多媒体数据压缩技术回到第一页LZ77算法vv几个术语几个术语1. 1.输入数据流输入数据流(inputstream)(inputstream)：要被压缩的字符序列。：要被压缩的字符序列。 2. 2.字符字符(character)(character)：输入数据流中的基本单元。：输入数据流中的基本单元。 3. 3.编码位置编码位置(codingposition
54、)(codingposition)：输入数据流中当前要编码的字符位：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。置，指前向缓冲存储器中的开始字符。 4. 4.前向缓冲存储器前向缓冲存储器( (LookaheadLookaheadbuffer)buffer)：存放从编码位置到输入数：存放从编码位置到输入数据流结束的字符序列的存储器。据流结束的字符序列的存储器。 5. 5.窗口窗口(window)(window)：指包含：指包含WW个字符的窗口，字符是从编码位置开个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。始向后数也就是最后处理的字符数。 6. 6.指针指针
55、(pointer)(pointer)：指向窗口中的匹配串且含长度的指针。：指向窗口中的匹配串且含长度的指针。 2024/8/1830第四章 多媒体数据压缩技术回到第一页LZ77算法(cont.)(cont.)vvLZ77LZ77编码算法的核心是查找从前向缓冲存储器开始的最编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行步骤如下：长的匹配串。编码算法的具体执行步骤如下：1. 1.把编码位置设置到输入数据流的开始位置。把编码位置设置到输入数据流的开始位置。 2. 2.查找窗口中最长的匹配串。查找窗口中最长的匹配串。 3. 3.以以“ “(Pointer,Length)Ch
56、aracters”(Pointer,Length)Characters”的格式输出，其中的格式输出，其中PointerPointer是指是指向窗口中匹配串的指针，向窗口中匹配串的指针，LengthLength表示匹配字符的长度，表示匹配字符的长度，CharactersCharacters是前向缓冲存储器中的不匹配的第是前向缓冲存储器中的不匹配的第1 1个字符。个字符。 4. 4.如果前向缓冲存储器不是空的，则把编码位置和窗口向前移如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)(Length+1)个字符，然后返回到步骤个字符，然后返回到步骤2 2。 2024/8/183
57、1第四章 多媒体数据压缩技术回到第一页LZ77算法(cont.)(cont.)vvLZ77LZ77算法举例算法举例位置位置1 12 23 34 45 56 67 78 89 9字符字符 A AA AB BC CB BB BA AB BC C步步骤骤位置位置匹配串匹配串 字符字符 输输出出 1 11 1- -A A(0,0)A(0,0)A2 22 2A AB B(1,1)B(1,1)B3 34 4- -C C(0,0)C(0,0)C4 45 5B BB B(2,1)B(2,1)B5 57 7ABABC C(5,2)C(5,2)C步步骤：表示编码步骤。骤：表示编码步骤。 位位置：表示编码位置，输入
58、数据流中的第置：表示编码位置，输入数据流中的第1 1个字符为编码位置个字符为编码位置1 1。 匹配串：栏表示窗口中找到的最长的匹配串。匹配串：栏表示窗口中找到的最长的匹配串。 字字符：表示匹配之后在前向缓冲存储器中的第符：表示匹配之后在前向缓冲存储器中的第1 1个字符。个字符。 输输出：以出：以“ “( (Back_charsBack_chars, ,Chars_lengthChars_length) )Explicit_characterExplicit_character” ”格式输出。格式输出。2024/8/1832第四章 多媒体数据压缩技术回到第一页LZ77算法(cont.)(cont
59、.)vvLZ77LZ77算法小结算法小结vv存在的缺点存在的缺点uuLZ77LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。但这个解决方案包含有冗余信息。uu冗余信息表现在如下两个方面：冗余信息表现在如下两个方面： 一是空指针一是空指针 二是编码器可能输出额外的字符，这种字符是指可能包含在下一个二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。匹配串中的字符。2024/8/1833第四章 多媒体数据压缩技术回到第一页LZSS算法vvLZSSLZSS编码算法的具体执行步骤如下：编
60、码算法的具体执行步骤如下：1. 1.把编码位置置于输入数据流的开始位置。把编码位置置于输入数据流的开始位置。 2. 2.在前向缓冲存储器中查找与窗口中最长的匹配串在前向缓冲存储器中查找与窗口中最长的匹配串PointerPointer：=匹配串指针。匹配串指针。LengthLength：=匹配串长度。匹配串长度。 3. 3.判断匹配串长度判断匹配串长度LengthLength是否大于等于最小匹配串长度是否大于等于最小匹配串长度(Length(Length MIN_LENGTH)MIN_LENGTH)，如果如果“ “是是” ”：输出指针，然后把编码位置向前移动：输出指针，然后把编码位置向前移动Le
61、ngthLength个字符。个字符。如果如果“ “否否” ”：输出前向缓冲存储器中的第：输出前向缓冲存储器中的第1 1个字符，然后把编码个字符，然后把编码位置向前移动一个字符。位置向前移动一个字符。 4. 4.如果前向缓冲存储器不是空的，就返回到步骤如果前向缓冲存储器不是空的，就返回到步骤2 2。 2024/8/1834第四章 多媒体数据压缩技术回到第一页LZSS算法(cont.)(cont.)vvLZSSLZSS算法举例算法举例uu设有下列字符串设有下列字符串uu编码步骤如下：编码步骤如下：位置位置1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7
62、 78 8 8 89 9 9 91010101011111111字符字符 A AA AB BB BC CB BB BA AA AB BC C步步骤骤位置位置 匹配串匹配串输输出出1 11 1- -A A2 22 2A AA A3 33 3- -B B4 44 4B BB B5 55 5- -C C6 66 6B BB B(3,2)(3,2)7 78 8A A BA A B(7,3)(7,3)8 81111C CC C2024/8/1835第四章 多媒体数据压缩技术回到第一页LZSS算法(cont.)(cont.)vvLZSSLZSS算法小结算法小结uu在相同的计算机环境下，在相同的计算机环境下
63、，LZSSLZSS算法比算法比LZ77LZ77可获得比较高的压缩可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了的基础，许多后来开发的文档压缩程序都使用了LZSSLZSS的思想。的思想。例如，例如，PKZipPKZip,ARJ,ARJ,LHArcLHArc和和ZOOZOO等等，其差别仅仅是指针的长等等，其差别仅仅是指针的长短和窗口的大小等有所不同。短和窗口的大小等有所不同。uuLZSSLZSS同样可以和熵编码联合使用，例如同样可以和熵编码联合使用，例如ARJARJ就与霍夫
64、曼编码联用，就与霍夫曼编码联用，而而PKZipPKZip则与则与Shannon-Shannon-FanoFano联用，它的后续版本也采用霍夫曼编联用，它的后续版本也采用霍夫曼编码。码。2024/8/1836第四章 多媒体数据压缩技术回到第一页LZ78算法vv几个术语符号几个术语符号1. 1.字符流字符流( (CharstreamCharstream) )：要被编码的数据序列。：要被编码的数据序列。 2. 2.字符字符(Character)(Character)：字符流中的基本数据单元。：字符流中的基本数据单元。 3. 3.前缀前缀(Prefix)(Prefix)： 在一个字符之前的字符序列。在
65、一个字符之前的字符序列。 4. 4.缀缀- -符串符串(String)(String)：前缀字符。：前缀字符。 5. 5.码字码字(Codeword)(Codeword)：码字流中的基本数据单元，代表词典中的一串字符。：码字流中的基本数据单元，代表词典中的一串字符。6. 6.码字流码字流( (CodestreamCodestream) )： 码字和字符组成的序列，是编码器的输出。码字和字符组成的序列，是编码器的输出。 7. 7.词典词典(Dictionary)(Dictionary)： 缀缀- -符串表。按照词典中的索引号对每条缀符串表。按照词典中的索引号对每条缀- -符串符串(String)
66、(String)指定一个码字指定一个码字(Codeword)(Codeword)。 8. 8.当前前缀当前前缀(Currentprefix)(Currentprefix)：在编码算法中使用，指当前正在处理的前缀，：在编码算法中使用，指当前正在处理的前缀，用符号用符号P P表示。表示。 9. 9.当前字符当前字符(Currentcharacter)(Currentcharacter)：在编码算法中使用，指当前前缀之后的字：在编码算法中使用，指当前前缀之后的字符，用符号符，用符号C C表示。表示。 10.10.当前码字当前码字(Currentcodeword)(Currentcodeword)：
67、在译码算法中使用，指当前处理的码字，在译码算法中使用，指当前处理的码字，用用WW表示当前码字，表示当前码字，String.WString.W表示当前码字的缀表示当前码字的缀- -符串。符串。 2024/8/1837第四章 多媒体数据压缩技术回到第一页LZ78算法(cont.)(cont.)vvLZ78LZ78编码算法编码算法步骤步骤1 1：在开始时，词典和当前前缀：在开始时，词典和当前前缀P P都是空的。都是空的。步骤步骤2 2：当前字符：当前字符CC：=字符流中的下一个字符。字符流中的下一个字符。步骤步骤3 3：判断：判断P+CP+C是否在词典中：是否在词典中：(1)(1)如果如果“ “是是
68、” ”：用：用C C扩展扩展P P，让，让PP：=P+C=P+C；(2)(2)如果如果“ “否否” ”： 输出与当前前缀输出与当前前缀P P相对应的码字和当前字符相对应的码字和当前字符C C； 把字符串把字符串P+CP+C添加到词典中。添加到词典中。 令令PP：=空值。空值。(3)(3)判断字符流中是否还有字符需要编码判断字符流中是否还有字符需要编码 如果如果“ “是是” ”：返回到步骤：返回到步骤2 2。 如果如果“ “否否” ”：若当前前缀：若当前前缀P P不是空的，输出相应于当前前缀不是空的，输出相应于当前前缀P P的码字，的码字，然后结束编码。然后结束编码。LZ78LZ78编码器的输出
69、是码字编码器的输出是码字 字符字符(W,C)(W,C)对，每次输出一对到码字流中，与码字对，每次输出一对到码字流中，与码字WW相对相对应的缀应的缀- -符串符串(String)(String)用字符用字符C C进行扩展生成新的缀进行扩展生成新的缀- -符串符串(String)(String)，然后添加到词典中。，然后添加到词典中。LZ78LZ78编码的具体算法如下：编码的具体算法如下： 2024/8/1838第四章 多媒体数据压缩技术回到第一页LZ78算法(cont.)(cont.)vvLZ78LZ78译码算法译码算法uuLZ78LZ78编码器的输出是码字编码器的输出是码字- -字符字符(W,
70、C)(W,C)对，每次输出一对到码字流对，每次输出一对到码字流中，与码字中，与码字WW相对应的缀相对应的缀- -符串符串(String)(String)用字符用字符C C进行扩展生成新的进行扩展生成新的缀缀- -符串符串(String)(String)，然后添加到词典中。，然后添加到词典中。uuLZ78LZ78编码的具体算法如下：编码的具体算法如下：步骤步骤1 1： 在开始时词典是空的。在开始时词典是空的。步骤步骤2 2： 当前码字当前码字WW：=码字流中的下一个码字。码字流中的下一个码字。步骤步骤3 3： 当前字符当前字符CC：=紧随码字之后的字符。紧随码字之后的字符。步骤步骤4 4： 把当
71、前码字的缀把当前码字的缀- -符串符串( (string.Wstring.W) )输出到字符流输出到字符流( (CharstreamCharstream) )，然后输，然后输出字符出字符C C。步骤步骤5 5： 把把string.Wstring.W+C+C添加到词典中。添加到词典中。步骤步骤6 6： 判断码字流中是否还有码字要译判断码字流中是否还有码字要译(1)(1)如果如果“ “是是” ”，就返回到步骤，就返回到步骤2 2。(2)(2)如果如果“ “否否” ”，则结束。，则结束。2024/8/1839第四章 多媒体数据压缩技术回到第一页LZ78算法(cont.)(cont.)vvLZ78LZ
72、78算法举例算法举例uu假设有下列编码字符串：假设有下列编码字符串：uu编码过程如下：编码过程如下：位置位置1 12 23 34 45 56 67 78 89 9字符字符 A AB BB BC CB BC CA AB BA A步步骤骤位置位置 词词典典输输出出 1 11 1A A(0,A)(0,A)2 22 2B B(0,B)(0,B)3 33 3B CB C(2,C)(2,C)4 45 5B C AB C A(3,A)(3,A)5 58 8B AB A(2,A)(2,A)步骤：步骤：步骤：步骤： 编码步骤。编码步骤。编码步骤。编码步骤。 位置：位置：位置：位置： 在输入数据中的当前位置。在输
73、入数据中的当前位置。在输入数据中的当前位置。在输入数据中的当前位置。 词典：词典：词典：词典： 添加到词典中的缀添加到词典中的缀添加到词典中的缀添加到词典中的缀- -符串，缀符串，缀符串，缀符串，缀- -符串的索引等于符串的索引等于符串的索引等于符串的索引等于“ “步骤步骤步骤步骤” ”序号。序号。序号。序号。输出：输出：输出：输出： 以以以以( (当前码字当前码字当前码字当前码字W, W, 当前字符当前字符当前字符当前字符C)C)简化为简化为简化为简化为(W, C)(W, C)的形式输出。的形式输出。的形式输出。的形式输出。 与与与与LZ77LZ77相比，相比，相比，相比，LZ78LZ78的
74、最大优点是的最大优点是的最大优点是的最大优点是在每个编码步骤中减少了缀在每个编码步骤中减少了缀在每个编码步骤中减少了缀在每个编码步骤中减少了缀- -符串符串符串符串(String)(String)比较的数目，而压缩率与比较的数目，而压缩率与比较的数目，而压缩率与比较的数目，而压缩率与LZ77LZ77类似。类似。类似。类似。 2024/8/1840第四章 多媒体数据压缩技术回到第一页LZW算法vvLZWLZW算法中使用的术语与算法中使用的术语与LZ78LZ78使用的相同，仅增加了一使用的相同，仅增加了一个术语个术语前缀根前缀根(Root)(Root)，它是由单个字符串组成的缀，它是由单个字符串组
75、成的缀- -符符串串(String)(String)。vv在编码原理上，在编码原理上，LZWLZW与与LZ78LZ78相比有如下差别：相比有如下差别：uuLZWLZW只输出代表词典中的缀只输出代表词典中的缀- -符串符串(String)(String)的码字的码字(codeword)(codeword)。这。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根中的所有单个字符，即前缀根(Root)(Root)。uu由于所有可能出现的单个字符都事先包含在词典中，每个编码步由于所有可能出现的单个字符都事先包含在
76、词典中，每个编码步骤开始时都使用一字符前缀骤开始时都使用一字符前缀(one-characterprefix)(one-characterprefix)，因此在词典中，因此在词典中搜索的第搜索的第1 1个缀个缀- -符串有两个字符。符串有两个字符。2024/8/1841第四章 多媒体数据压缩技术回到第一页LZW算法(cont.)(cont.)vvLZWLZW编码算法编码算法码字码字码字码字( (Code wordCode word) )前缀前缀前缀前缀( (PrefixPrefix) )1 1193193A A194194B B25525513051305abcdefxyF01234abcdef
77、xyF012342024/8/1842第四章 多媒体数据压缩技术回到第一页LZW算法(cont.)(cont.)vvLZWLZW编码算法编码算法uuLZWLZW编码算法的具体执行步骤如下：编码算法的具体执行步骤如下：步骤步骤1： 开始时的词典包含所有可能的根开始时的词典包含所有可能的根(Root)，而当前前缀，而当前前缀P是空的；是空的；步骤步骤2： 当前字符当前字符(C) ：=字符流中的下一个字符；字符流中的下一个字符；步骤步骤3： 判断缀判断缀-符串符串P+C是否在词典中是否在词典中 (1) 如果如果“是是”：P ：= P+C/ 用用C扩展扩展P ； (2) 如果如果“否否” 把代表当前前
78、缀把代表当前前缀P的码字输出到码字流的码字输出到码字流; 把缀把缀-符串符串P+C添加到词典添加到词典; 令令P ：= C/ 现在的现在的P仅包含一个字符仅包含一个字符C;步骤步骤4： 判断码字流中是否还有码字要译判断码字流中是否还有码字要译 (1) 如果如果“是是”，就返回到步骤，就返回到步骤2； (2) 如果如果“否否” 把代表当前前缀把代表当前前缀P的码字输出到码字流的码字输出到码字流; 结束。结束。2024/8/1843第四章 多媒体数据压缩技术回到第一页LZW算法(cont.)(cont.)vvLZWLZW编码算法编码算法uu开始时假设编码词典包含若干个已经定义的单个码字。例如，开始
79、时假设编码词典包含若干个已经定义的单个码字。例如，256256个字符的码字。个字符的码字。uu用伪码可以表示成：用伪码可以表示成：DictionaryjDictionaryjallnsingle-characterallnsingle-character， j j1,21,2， ，n njn+1jn+1PrefixreadfirstCharacterinPrefixreadfirstCharacterinCharstreamCharstreamwhile(Cwhile(CnextCharacter)!=NULL)nextCharacter)!=NULL)BeginBeginIfIfPrefix
80、.CPrefix.CisinDictionaryisinDictionaryPrefixPrefixPrefix.CPrefix.CelseelseCodestreamCodestreamcWcWforPrefixforPrefixDictionaryjDictionaryjPrefix.CPrefix.Cjn+1jn+1PrefixCPrefixCendendCodestreamCodestreamcWcWforPrefixforPrefix2024/8/1844第四章 多媒体数据压缩技术回到第一页LZW算法(cont.)(cont.)vvLZWLZW译码算法译码算法uuLZWLZW译码算法
81、中还用到译码算法中还用到另外两个术语：另外两个术语：DictionaryjDictionaryj allnsingle-characterallnsingle-character， j j1,21,2， ，n njn+1jn+1cWcWfirstcodefromfirstcodefromCodestreamCodestreamCharstreamCharstreamDictionarycWDictionarycW pWpWcWcWWhile(cWWhile(cWnextCodeword)!=NULL)nextCodeword)!=NULL)BeginBeginIfIfcWcWisinDicti
82、onaryisinDictionaryCharstreamCharstreamDictionarycWDictionarycW PrefixPrefixDictionarypWDictionarypW cWcWfirstCharacteroffirstCharacterofDictionarycWDictionarycW DictionaryjDictionaryjPrefix.cWPrefix.cWjn+1jn+1pWpWcWcWelseelsePrefixPrefixDictionarypWDictionarypW cWcWfirstCharacterofPrefixfirstCharac
83、terofPrefixCharstreamCharstreamPrefix.cWPrefix.cWDictionaryjDictionaryjPrefix.CPrefix.CpWpWcWcWjn+1jn+1endend2024/8/1845第四章 多媒体数据压缩技术回到第一页LZW算法(cont.)(cont.)vvLZWLZW算法举例算法举例uu假设有下列编码字符串：假设有下列编码字符串：uu编编 / /译码过程如下：译码过程如下：位置位置1 12 23 34 45 56 67 78 89 9字符字符 A AB BB BA AB BA AB BA AC C步步骤骤位置位置 词词典典输输出出(
84、1)(1)(1)(1)A A A A(2)(2)(2)(2)B B B B(3)(3)(3)(3)C C C C1 1 1 1(1)(1)(1)(1)- A A A A2 2 2 2(2)(2)(2)(2)(4)(4)(4)(4)A BA BA BA BB B B B3 3 3 3(2)(2)(2)(2)(5)(5)(5)(5)B BB BB BB BB B B B4 4 4 4(4)(4)(4)(4)(6)(6)(6)(6)B AB AB AB AA BA BA BA B5 5 5 5(7)(7)(7)(7)(7)(7)(7)(7)A B AA B AA B AA B AA B AA B A
85、A B AA B A6 6 6 6(3)(3)(3)(3)(8)(8)(8)(8)A B A CA B A CA B A CA B A CC C C C步步骤骤位置位置 词词典典输输出出(1)(1)(1)(1)A A A A(2)(2)(2)(2)B B B B(3)(3)(3)(3)C C C C1 1 1 11 1 1 1(4)(4)(4)(4)A BA BA BA B(1)(1)(1)(1)2 2 2 22 2 2 2(5)(5)(5)(5)B BB BB BB B(2)(2)(2)(2)3 3 3 33 3 3 3(6)(6)(6)(6)B AB AB AB A(2)(2)(2)(2)
86、4 4 4 44 4 4 4(7)(7)(7)(7)A B AA B AA B AA B A(4)(4)(4)(4)5 5 5 56 6 6 6(8)(8)(8)(8)A B A CA B A CA B A CA B A C(7)(7)(7)(7)6 6 6 6-(3)(3)(3)(3)2024/8/1846第四章 多媒体数据压缩技术回到第一页LZW算法(cont.)(cont.)vvLZWLZW算法小结算法小结uuLZWLZW算法得到普遍采用，它的速度比使用算法得到普遍采用，它的速度比使用LZ77LZ77算法的速度快，算法的速度快，因为它不需要执行那么多的缀因为它不需要执行那么多的缀- -符
87、串比较操作。对符串比较操作。对LZWLZW算法进一算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀步的改进是增加可变的码字长度，以及在词典中删除老的缀- -符符串。在串。在GIFGIF图像格式和图像格式和UNIXUNIX的压缩程序中已经采用了这些改进措的压缩程序中已经采用了这些改进措施之后的施之后的LZWLZW算法。算法。uuLZWLZW算法取得了专利，专利权的所有者是美国的一个大型计算机算法取得了专利，专利权的所有者是美国的一个大型计算机公司公司Unisys(Unisys(优利系统公司优利系统公司) )，除了商业软件生产公司之外，可，除了商业软件生产公司之外，可以免费使用以免费使用LZWLZW算法。算法。2024/8/1847第四章 多媒体数据压缩技术
