多媒体技术基础(林福宗)-02数据无损压缩资料课件.ppt

1、第第2章章 数据无损压缩数据无损压缩2023年9月9日第2章 数据无损压缩2 of 65第第2章章 数据无损压缩目录数据无损压缩目录2.0数据压缩概述数据压缩概述(补补)2.1 数据的冗余数据的冗余2.1.1 冗余概念2.1.2 决策量2.1.3 信息量2.1.4 熵2.1.5 数据冗余量2.2 统计编码统计编码2.2.1 香农-范诺编码2.2.2 霍夫曼编码2.2.3 算术编码2.3 RLE编码编码2.4 词典编码词典编码2.4.1 词典编码的思想2.4.2 LZ77算法2.4.3 LZSS算法2.4.4 LZ78算法2.4.5 LZW算法2023年9月9日第2章 数据无损压缩3 of 65

2、2.0 多媒体数据压缩概述多媒体数据压缩概述2023年9月9日第2章 数据无损压缩4 of 652.0 多媒体数据压缩概述多媒体数据压缩概述n数据压缩的必要性数据压缩的必要性数据量大数据量大BGR图像：图像：一张一张640640480480真彩真彩(24(24位位)的的图像需：图像需：64064048048024247372800(bit)=7372800(bit)=900KB900KB (1Byte=8bit)(1Byte=8bit)相当于约相当于约4646万万汉字汉字2023年9月9日第2章 数据无损压缩5 of 652.0 数据压缩概述数据压缩概述n数据压缩必要性数据压缩必要性数据量大数

3、据量大视频：视频：以这样的图像构成视频，以每秒以这样的图像构成视频，以每秒3030帧帧进行播放，所需数据量为：进行播放，所需数据量为：737280073728003026.37MB3026.37MB一张一张650MB(5200Mb)650MB(5200Mb)的光盘的光盘 只能存储约只能存储约2525秒秒的视频节目的视频节目很难满足计算机处理多媒体的要求很难满足计算机处理多媒体的要求2023年9月9日第2章 数据无损压缩6 of 652.0 数据压缩概述数据压缩概述n数据压缩必要性数据压缩必要性数据量大数据量大音频：音频：以以44.1KHz44.1KHz采样频率，量化为采样频率，量化为16bit

4、16bit双通道立体双通道立体声，每秒数据量为：声，每秒数据量为：441004410016162 21411200(bit)172.3KB1411200(bit)172.3KB一张一张650MB650MB的光盘能存放：的光盘能存放：6506501024/172.31024/172.36464分钟分钟很难满足计算机处理多媒体的要求很难满足计算机处理多媒体的要求2023年9月9日第2章 数据无损压缩7 of 652.0 数据概述数据概述n数据可被压缩的依据数据可被压缩的依据数据本身存在冗余听觉系统的敏感度有限视觉系统的敏感度有限n数据压缩类型数据压缩类型无损压缩有损压缩2023年9月9日第2章 数

5、据无损压缩8 of 652.0 数据压缩概述数据压缩概述n数据无损压缩的理论数据无损压缩的理论信息论信息论(information theory)1948年创建的数学理论的一个分支学科，研究信息的编码、传输和存储Claude Shannon(香农)发表的“A Mathematical Theory of Communication”论文题目，提议用二进制数据对信息进行编码最初只应用于通信工程领域，后来扩展到包括计算在内的其他多个领域，如信息的存储、信息的检索等。在通信方面，主要研究数据量、传输速率、信道容量、传输正确率等问题。2023年9月9日第2章 数据无损压缩9 of 652.0 数据压缩

6、概述数据压缩概述 n数据压缩的可能性数据压缩的可能性数字化的多媒体数据可以进行数据压缩是基于两种事实n信息的冗余度信息的冗余度：多媒体数据中存在大量的冗余，如：30000(后跟100个0)，可以表示为30(100)，表示3后跟100个0，从而避免大量的重复0。(科学记数法)数据数据(文字、图形、声音、视频等文字、图形、声音、视频等)在计算机中都是以二进制值在计算机中都是以二进制值0 0、1 1来表达、存储和传输，其数值之间有空间相关和时间相关来表达、存储和传输，其数值之间有空间相关和时间相关性。利用相关性可以进行压缩。性。利用相关性可以进行压缩。2023年9月9日第2章 数据无损压缩10 of

7、 652.0 数据压缩概述数据压缩概述n数据压缩的可能性数据压缩的可能性数字化的多媒体数据可以进行数据压缩是基于以下两种事实n人的视觉及听觉等感官特性人的视觉及听觉等感官特性n视觉特征视觉特征表现为对亮度信息很敏感而对边缘的急剧变化不敏感n听觉特征听觉特征表现出对部分音频信号不敏感,如人的听觉具有一个强音能抑制一个同时存在的弱音现象,而且人耳对低频端比较敏感，而对高频端不太敏感因此，完全可以利用这些特性去除一些多余及不敏因此，完全可以利用这些特性去除一些多余及不敏感的信息，从而实现对数据的压缩感的信息，从而实现对数据的压缩2023年9月9日第2章 数据无损压缩11 of 652.1 数据的冗余

8、数据的冗余n冗余概念冗余概念人为冗余人为冗余n在信息处理系统中，使用两台计算机做同样的工作是提高系统可靠性的一种措施n在数据存储和传输中，为了检测和恢复在数据存储或数据传输过程中出现的错误，根据使用的算法的要求，在数据存储或数据传输之前把额外的数据添加到用户数据中，这个额外的数据就是冗余数据视听冗余视听冗余n由于人的视觉系统和听觉系统的局限性，在图像数据和声音数据中，有些数据确实是多余的，使用算法将其去掉后并不会丢失实质性的信息或含义，对理解数据表达的信息几乎没有影响数据冗余数据冗余n不考虑数据来源时，单纯数据集中也可能存在多余的数据，去掉这些多余数据并不会丢失任何信息，这种冗余称为数据冗余，

9、而且还可定量表达 2023年9月9日第2章 数据无损压缩12 of 652.1 数据的冗余数据的冗余n例：信息量、数据量与冗余量例：信息量、数据量与冗余量多媒体数据的数据量远远大于其所携带的信息量 例：180个汉字，文本数据量为360B。广播员朗读使用1分钟，数字化时采样频率8000Hz，单声道，8位量化，则数据量为800060480KB。可见，传递同样信息，语音数据有1300倍冗余 数学描述：IDdu I：信息量 D：数据量 du：冗余量2023年9月9日第2章 数据无损压缩13 of 652.1 数据的冗余数据的冗余n信息量信息量(information content)信源发出的消息是不

10、确定的，与概率有关。事件发生的概率越小，猜测它有没有发生的困难程度就越大，不确定性就越大，一旦它出现必然使人感到意外，给人的信息量就越大，当消息的概率很小，即几乎不可能的消息出现了，则会给人以巨大的信息量。对于发生概率等于1的必然事件，就不存在不确定性，不具任何信息量。例例2023年9月9日第2章 数据无损压缩14 of 652.1 数据的冗余数据的冗余信息量信息量信息论中常用的对数底是2，则信息量的单位是比特(bit)。如果p(ui)0.5,I(ui)=1bit。所以1bit信息量就是两个互不相容的等概率事件之一发生时所提供的信息量。1.若取自然对数e为底，则信息量的单位为(nat)。2.若

11、以10为对数底，则信息量的单位为(hart)。2023年9月9日第2章 数据无损压缩15 of 652.1 数据的冗余数据的冗余(续续2)n信息量信息量(information content)具有确定概率事件的信息的定量度量在数学上定义为 其中，是事件出现的概率 举例：假设X=a,b,c是由3个事件构成的集合，p(a)=0.5，p(b)=0.25，p(b)=0.25分别是事件a,b和c出现的概率，这些事件的信息量分别为，I(a)=log2(1/0.50)=1 sh I(b)=log2(1/0.25)=2 sh I(c)=log2(1/0.25)=2 sh一个等概率事件的集合，每个事件的信息量

12、等于该集合的决策量(依据定义可得)22()log 1/()log()I xp xp x()p x2023年9月9日第2章 数据无损压缩16 of 652.1 数据的冗余数据的冗余n决策量决策量(decision content)特殊的信息量特殊的信息量在有限数目的互斥事件集合中，决策量是事件数的对数值在数学上表示为 H0=log(n)其中，n是事件数决策量的单位由对数的底数决定nSh(Shannon):用于以2为底的对数nNat(natural unit):用于以e为底的对数nHart(hartley)：用于以10为底的对数2023年9月9日第2章 数据无损压缩17 of 652.1 数据的冗

13、余数据的冗余(续续3)n熵熵(entropy)按照香农(Shannon)的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量(mean information content)用数学表示为2023年9月9日第2章 数据无损压缩18 of 652.1 数据的冗余数据的冗余(续续4)n数据的冗余量数据的冗余量2023年9月9日第2章 数据无损压缩19 of 652.2 统计编码统计编码n统计编码统计编码给已知统计信息的符号分配代码的数据无损压缩方法n编码方法编码方法香农-范诺编码霍夫曼编码算术编码n编码特性编码特性香农-范诺编码和霍夫曼编码的原理相同，都是根据

14、符号集中各个符号出现的频繁程度来编码，出现次数越多的符号，给它分配的代码位数越少算术编码使用0和1之间的实数的间隔长度代表概率大小，概率越大间隔越长，编码效率可接近于熵2023年9月9日第2章 数据无损压缩20 of 652.2.1香农香农-范诺范诺(Shannon-Fano)编码编码n最早阐述和实现这种编码的是最早阐述和实现这种编码的是Shannon(1948年年)和和Fano(1949年年)，采用从上到下的方法进行编，采用从上到下的方法进行编码。码。n按照符号出现的频度或概率排序按照符号出现的频度或概率排序n使用递归方法分成两个部分，每一部分具有近使用递归方法分成两个部分，每一部分具有近似

15、相同的次数似相同的次数2023年9月9日第2章 数据无损压缩21 of 652.2.1香农香农-范诺范诺(Shannon-Fano)编码编码(例例1)n香农范诺算法香农范诺算法采用从上到下的方法进行编码1.按符号出现的频率或概率排序;2.按递归方法分成两部分，每部分具有近似相同的次数;H E L O符号符号数目数目1 1 2 1假设对单词HELLO中字符进行编码，每个字符出现的频率如右：2023年9月9日第2章 数据无损压缩22 of 65n例如，例如，A，B，C，D和和E符号符号出现的次数出现的次数(Pi)log2(1/Pi)分配的代码分配的代码需要的位数需要的位数A15(0.375)1.4

16、1500030B7(0.175)2.51450114C7(0.175)2.51451014D6(0.150)2.736911018E5(0.125)3.000011115ABCDE00111102.2.1香农香农-范诺范诺(Shannon-Fano)编码编码(例例2)2023年9月9日第2章 数据无损压缩23 of 652.2.1香农香农-范诺范诺(Shannon-Fano)编码编码(Quiz)2023年9月9日第2章 数据无损压缩24 of 65Huffman编码的理论基础是Huffman定理；HuffmanHuffman定理（定理（1952年Huffman提出的）在变长编码中,对出现概率大

17、的信源符号赋于短码字,而对于出现概率小的信源符号赋于长码字。如果码字长度严格按照所对应符号出现概率大小逆序排列,则编码结果平均码字长度一定小于任何其它排列方式。也称为最佳编码，平均码长最短。2.2.2 Huffman编码编码n霍夫曼编码理论霍夫曼编码理论2023年9月9日第2章 数据无损压缩25 of 65霍夫曼(Huffman)1952年，从下到上的编码方法。1.初始化,根据概率大小由大到小顺序对符号进行排序2.概率最小的两个符号组成节点3.重复步骤24.从根节点到页节点,分别进行编码霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。几个问题值得注意：1.霍夫曼码没有错误保护功能；2.

18、霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码;3.接收端需保存一个与发送端相同的霍夫曼码表。n霍夫曼编码方法2.2.2 Huffman编码编码2023年9月9日第2章 数据无损压缩26 of 65例：设有例：设有7个符号：个符号：a1,a2,a3,a4,a5,a6,a7 它们出现概率是它们出现概率是:0.2,0.19,0.18,0.17,0.15,0.1,0.01a2(0.19)a1(0.2)a3(0.18)a4(0.17)a5(0.15)a6(0.1)0.390.350.110.260.611.010010101010110110000010100110a7(0

19、.01)0111平均码字长度平均码字长度:R=Pii=2.72n该信源的信息熵：该信源的信息熵：H=Pilog2Pi=2.61n霍夫曼编码举例2.2.2 Huffman编码编码(举例举例)2023年9月9日第2章 数据无损压缩27 of 65每个编码均非其它码的前缀，因此唯一可译(a1=10,a2=11,a3=000,a4=001,a5=010,a6=0110,a7=0111)11 010 10 001 10 11 10 0111 a2 a5 a1 a4 a1 a2 a1 a71.编码方案不唯一，码表必须存储（传输）2.简单易实现3.编码效率较高4.必须预先知道信源的统计特性2.2.2 Huf

20、fman编码（分析）编码（分析）2023年9月9日第2章 数据无损压缩28 of 65Huffman编码中每个符号都用整数个bits来表示，影响编码效率。若能把一串符号作为编码单位，则效率还可提高。符号串的区间表示法设符号串为：S1,S2,Sm 则它可以映射成为0.1中的唯一的一个子区间来表示基本原理：将编码的信息表示成实数0和1之间的一个间隔，信息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。n算术编码思想2.2.3 算术编码算术编码2023年9月9日第2章 数据无损压缩29 of 65消息用0到1之间的实数进行编码，两个基本的参数：符号的概率和编码间隔。信源符号的概率决定

21、编码的效率，及信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。步骤：步骤：1.在0,1)之间给每个符号分配一个初始子间隔,其长度为等于它的概率，初始子间隔的范围用表示.2.用递归方法读下一个符号。),),iiinniiinnnnnpdIpdIrlI1 11 11 11 11 11 11 1),),iiiiiipprlI1 11 11 11 11 11 1n算术编码步骤2.2.3 算术编码算术编码2023年9月9日第2章 数据无损压缩30 of 65假设信源符号为假设信源符号为00,00,01,10,1101,10,11，这些，这些符号的概率分别为符号的概率分

22、别为 0.1,0.4,0.2,0.1,0.4,0.2,0.3 0.3，根据这些概，根据这些概率可把间隔率可把间隔0,1)0,1)分成分成4 4个子间隔：个子间隔：0,0,0.1),0.1,0.5),0.1),0.1,0.5),0.5,0.7),0.7,0.5,0.7),0.7,1)1)，二进制消息序，二进制消息序列的输入为：列的输入为：10 00 10 00 11 00 10 11 0111 00 10 11 012.2.3 算术编码（例算术编码（例1）2023年9月9日第2章 数据无损压缩31 of 65可用伪代码描述如下可用伪代码描述如下：set Low to 0 set High to

23、1 while there are input symbols do take a symbol CodeRange=High Low High=Low+CodeRange*HighRange(symbol)Low=Low+CodeRange*LowRange(symbol)end of while output Low n算术编码算法描述2.2.3 算术编码算术编码2023年9月9日第2章 数据无损压缩32 of 65例例:设符号串为设符号串为AABA,编码过程如下编码过程如下:0101013/43/49/169/1627/649/1627/64135/256(27/64)0.011011

24、0.10000111(135/256)0.1AAAABAABA01A2.2.3 算术编码（例算术编码（例2）2023年9月9日第2章 数据无损压缩33 of 65输入序列为：输入序列为：bcc.cba1.00000.66670.33330.00000.66670.58340.41670.33330.66670.63340.60010.58340.66670.65010.63900.6334c1/31/42/53/6b1/32/42/52/6a1/31/41/51/62.2.3 算术编码（算术编码（补充：自适应算术编码）2023年9月9日第2章 数据无损压缩34 of 65子区间的大小对应于符号

25、串中各符号概率的乘积大小子区间的位置对应着 符号串中符号的排列顺序子区间的头尾均用二进制数表示该符号串的编码是满足下列条件的、最短的数F:头=F H1o1h1a1i1除非经常遇到 n“Ahhhhhhhhhhhhhhhhh!”,n“Noooooooooo!”.n“Gooooooooooooooooooooooogle”2023年9月9日第2章 数据无损压缩48 of 65n通用编码技术通用编码技术许多场合，开始时不知道要编码数据的统计特性，也不一定允许你事先知道它们的统计特性。词典编码：不需要知道统计特性n利用数据本身包含许多重复字符串利用数据本身包含许多重复字符串 例：“吃葡萄不吐葡萄皮,不吃

26、葡萄倒吐葡萄皮”，“我们是祖国的花朵，我们是祖国的未来”。用一些简单的代号代替这些字符串,实现压缩。字符串与代号的对应表就是词典。n实用的词典编码算法的核心就是如何动实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式态地形成词典，以及如何选择输出格式以减小冗余以减小冗余2.4词典编码词典编码2023年9月9日第2章 数据无损压缩49 of 65 第一类词典法的想法是企图查找查找正在压缩的字符序列是否在以前输以前输入入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。输入数据流输入数据流输出数据流输出数据流a ab bc c

27、d dx xm ma ab bc cd dx xp pm ma ab bc cp 第一类词典编码思想2.4词典编码词典编码(分类分类)2023年9月9日第2章 数据无损压缩50 of 65 第二类算法的想法是企图从输入的数据中创建一个创建一个“短语词典短语词典(dictionary of the phrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。输输 入入数据流数据流输输 出出数据流数据流a ac cb ba ax xy y1 1b b4 4a ad dy yx xa ad d编编 码码

28、词词 典典1 1a ac c2 2a ax x3 3e ec c5 5c ca a4 4a ax xx xx xp 第二类词典编码思想2.4词典编码词典编码(分类分类)2023年9月9日第2章 数据无损压缩51 of 65核心核心：查找从前向缓冲存储器开始的最长的匹配串1.1.输入数据流输入数据流：要被压缩的字符序列2.2.字符字符：输入数据流的基本单元3.3.编码位置编码位置：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符4.前向缓冲存储器前向缓冲存储器：存放从编码位置到输入数据流结束的字符序列的存储器。5.窗口窗口：指包含W个字符的窗口6.指针指针：指向窗口窗口中的匹配串且

29、含长度的指针。(Point,Length)CharactersYN编码位置输入数据流开始位置编码位置输入数据流开始位置查找窗口中最长的匹配串查找窗口中最长的匹配串前 向 缓 冲前 向 缓 冲存 储 器 空存 储 器 空？编码位置、编码位置、窗 口 前 移窗 口 前 移Length1个字符个字符stop2.4词典编码词典编码(第一类词典编码_LZ77)2023年9月9日第2章 数据无损压缩52 of 652.4词典编码词典编码(第一类词典编码_ LZ77)2023年9月9日第2章 数据无损压缩53 of 65位位置置 1 2 3 4 5 6 7 8 9 10 字字符符 A A B C B B A

30、 B C A 步步骤骤 位位置置 匹匹配配串串 字字符符 输输出出 1 1 A(0,0)A 2 2 A B(1,1)B 3 4 C(0,0)C 4 5 B B(2,1)B 5 7 ABC A(5,3)A 2.4词典编码词典编码(第一类词典编码_ LZ77例)2023年9月9日第2章 数据无损压缩54 of 65 LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。LZSS算法以比较有效的方法解决这个问题，它的思想是如果匹配串的长度比指针本身的长度长

31、就输出指针，否则就输出真实字符。另外要输出额外的标志位区分是指针另外要输出额外的标志位区分是指针还是字符。还是字符。2.4词典编码词典编码(第一类词典编码_ LZ77分析分析)2023年9月9日第2章 数据无损压缩55 of 65CharacterYPointYN编码位置输入数据流开始位置编码位置输入数据流开始位置查找窗口中最长的匹配串查找窗口中最长的匹配串L e n g t h L e n g t h MIN_LENGTH?MIN_LENGTH?N前向缓冲存前向缓冲存储器空？储器空？stop2.4词典编码词典编码(第一类词典编码_ LZSS)2023年9月9日第2章 数据无损压缩56 of

32、65MIN_LENGTH2LengthLength MIN_LENGTH MIN_LENGTH？位置位置1 12 23 34 45 56 67 78 89 9 1010 1111字符字符A A B B C B B A A B C步骤步骤位置位置匹配串匹配串输出输出1 11 1A2 22 2AA3 33 3B4 44 4BB5 55 5C6 66 6BB(3,2)7 78 8AAB(7,3)8 81111CC2.4词典编码词典编码(第一类词典编码_ LZSS举例举例)2023年9月9日第2章 数据无损压缩57 of 65 第二类算法的想法是企图从输入的数据中创建一个创建一个“短语词典短语词典(d

33、ictionary of the phrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。输输 入入数据流数据流输输 出出数据流数据流a ac cb ba ax xy y1 1b b4 4a ad dy yx xa ad d编编 码码词词 典典1 1a ac c2 2a ax x3 3e ec c5 5c ca a4 4a ax xx xx x2.4词典编码词典编码(第二类词典编码思想第二类词典编码思想)2023年9月9日第2章 数据无损压缩58 of 652.4词典编码词典编码(第二类词典编

34、码历史第二类词典编码历史)nJ.Ziv和和A.Lempel在在1978年首次发表了介年首次发表了介绍这种编码方法的文章。绍这种编码方法的文章。(LZ78)n在他们的研究基础上，在他们的研究基础上，Terry A.Weltch在在1984年发表了改进这种编码算法的文章，年发表了改进这种编码算法的文章，因此把这种编码方法称为因此把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码，首先在高速硬盘控压缩编码，首先在高速硬盘控制器上应用了这种算法。制器上应用了这种算法。2023年9月9日第2章 数据无损压缩59 of 652.4词典编码词典编码(第二类词典编码例子第二类词典编码例子)2

35、023年9月9日第2章 数据无损压缩60 of 652.4词典编码词典编码(第二类词典编码第二类词典编码_LZ78)nLZ78的编码思想是不断地从字符流中提的编码思想是不断地从字符流中提取新的字符串取新的字符串(String)，通俗地理解为新，通俗地理解为新“词条词条”，然后用，然后用“代号代号”也就是码字也就是码字(Code word)表示这个表示这个“词条词条”。这样一。这样一来，对字符流的编码就变成了用码字来，对字符流的编码就变成了用码字(Code word)去替换字符流去替换字符流(Char stream)，生成码字流生成码字流(Code stream)，从而达到压，从而达到压缩数据的

36、目的。缩数据的目的。2023年9月9日第2章 数据无损压缩61 of 652.4词典编码词典编码(LZ78&LZ77)nLZ77利用滑动窗口里的内容作为字典，利用滑动窗口里的内容作为字典，找最长子串找最长子串nLZ78动态构建字典动态构建字典2023年9月9日第2章 数据无损压缩62 of 65术语：术语：1.1.字符流字符流(input stream)(input stream)：要被编码的数据序列。：要被编码的数据序列。2.2.字符字符(character)(character)：输入数据流中的基本单元。：输入数据流中的基本单元。3.3.前缀（前缀（prefixprefix）：在一个字符之

37、前的字符序列）：在一个字符之前的字符序列4.4.缀缀-符串符串(String)(String)：前缀：前缀+字符字符5.5.码字码字(code word):(code word):码字流中的基本数据单元码字流中的基本数据单元,代表词典中代表词典中的一串字符的一串字符6.6.码字流码字流(codestream(codestream)：码字和字符组成的序列：码字和字符组成的序列,是编码器是编码器的输出的输出7.7.词典词典(dictionary):(dictionary):缀缀-符串表符串表8.8.当前前缀当前前缀(current prefix):(current prefix):当前正在处理的前

38、缀当前正在处理的前缀(P)(P)9.9.当前字符当前字符(current character):(current character):当前前缀之后的字符当前前缀之后的字符(C)(C)10.10.当前码字当前码字(current code word):(current code word):当前处理的码字当前处理的码字(W)(W)2.4词典编码词典编码(术语术语)2023年9月9日第2章 数据无损压缩63 of 65 LZ78LZ78的编码思想是不断地从字符流中提取新的缀的编码思想是不断地从字符流中提取新的缀-符串符串(String)(String)，通俗地理解为新，通俗地理解为新“词条词条”

39、，然后用，然后用“代号代号”也就是码字也就是码字(Code word)(Code word)表示这个表示这个“词条词条”。这样，对字。这样，对字符流的编码就变成了用码字符流的编码就变成了用码字(Code word)(Code word)去替换字符流去替换字符流(Char stream)(Char stream)，生成码字流，生成码字流(Code stream)(Code stream)，从而达到，从而达到压缩数据的目的。压缩数据的目的。LZ78LZ78编码器的输出是码字编码器的输出是码字-字符字符(W,C)(W,C)对，每次输出一对，每次输出一对到码字流中，与码字对到码字流中，与码字W W相对

40、应的缀相对应的缀-符串符串(String)(String)用字用字符符C C进行扩展生成新的缀进行扩展生成新的缀-符串符串(String)(String)，然后添加到词，然后添加到词典中。典中。2.4词典编码词典编码(第二类词典编码第二类词典编码_ LZ78)2023年9月9日第2章 数据无损压缩64 of 65位置1 2 3 4 5 6 78 9字符A B B C B C A B A步骤位置词典输出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)PP+CYNP对应的码字对应的码字+CNY词典空，当前前缀词典空，当前前缀P空空当前字符当前字符C字符流中字

41、符流中next字符字符P PC C 词典词典Y字符流空？字符流空？PP+C加入词典；加入词典；P空空NP P空？空？PStopStop2.4词典编码词典编码(第二类词典编码第二类词典编码_ LZ78 例例)2023年9月9日第2章 数据无损压缩65 of 65nTerry A.Weltch在在1984年发表了改进年发表了改进LZ78的文章，因此把这种编码方法称为的文章，因此把这种编码方法称为LZW(Lempel-Ziv Walch)2.4词典编码词典编码(第二类词典编码第二类词典编码_ LZW）2023年9月9日第2章 数据无损压缩66 of 652.4词典编码词典编码(第二类词典编码第二类词

42、典编码_ LZ78&LZW)LZW只输出代表词典中的字符串只输出代表词典中的字符串(String)的码的码字字(code word)。这就意味在开始时词典不能是。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根单个字符，即前缀根(Root)。由于所有可能出现的单个字符都事先包含在词由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)，因此至少可以在词典，因此至少可以在词典中找到长度为中找到长度为1的匹配串。的

43、匹配串。2023年9月9日第2章 数据无损压缩67 of 652.4词典编码词典编码(第二类词典编码第二类词典编码_ LZW)nLZW编码是围绕称为词典的转换表来完编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀成的。这张转换表用来存放称为前缀(Prefix)的字符序列，并且为每个表项分的字符序列，并且为每个表项分配一个码字配一个码字(Code word)，或者叫做序号。，或者叫做序号。nWelch的论文中用了的论文中用了12位码字，位码字，12位可以位可以有有4096个不同的个不同的12位代码，这就是说，位代码，这就是说，转换表有转换表有4096个表项，其中个表项，其中256个

44、表项用个表项用来存放已定义的字符，剩下来存放已定义的字符，剩下3840个表项个表项用来存放前缀用来存放前缀(Prefix)。2023年9月9日第2章 数据无损压缩68 of 65PP+CYYP对应的码字对应的码字NY词典所有根，当前前缀词典所有根，当前前缀P空空当前字符当前字符C字符流中字符流中next字符字符P PC C 词典词典N字符流空？字符流空？PP+C加入词典；加入词典；P空空NP P空？空？PStopStop2.4词典编码词典编码(第二类词典编码第二类词典编码_ LZW)2023年9月9日第2章 数据无损压缩69 of 65位置123456789字符ABBABABAC步骤步骤位置位置词典词典输出输出（1）A（2）B（3）C11（4）AB（1）22（5）BB（2）33（6）BA（2）44（7）ABA（4）56（8）ABAC（7）6（3）2.4词典编码词典编码(第二类词典编码第二类词典编码_ LZW例子例子)ENDEND第第2章章 数据无损压缩数据无损压缩