第四章数据压缩技术(补充)

1、2022-4-29信息管理系12022-4-29信息管理系2什么是数据压缩 数据压缩就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号信源编码信道编码信道信道译码信源译码信源信宿2022-4-29信息管理系3数据压缩能实现的条件(1)信息集包含冗余信息。计算机内的信息均以二进制形式表示，以一个字节为单位，基本信息集是00-ffh。当某信息集的数据量大于256时，理论上可以判定其中必有冗余，而去掉冗余不会减少信息量，仍可原样恢复数据。如在一份计算机文件中，某些符号耍比其他符号额外高得多地重复出现，或一些字符总在数据块中某一可预见的位置上出现，这些冗余部分便可在数据编码中除去或减少。20

2、22-4-29信息管理系4(2)数据中间尤其是相邻的数据之间常存在着相关性，如图片中常常有色彩均匀的背影，电视信号的相邻两帧之间可能只有少量的变化景物是不同的，声音信号有时具有一定的规律性和周期性等。因此，有可能利用某些变换来尽可能地去掉这些相关性。2022-4-29信息管理系5 (3)人们在欣赏音像节目时，由于人的视觉和听觉的生理特性，耳、日对信旱的时间变化和幅度变化的感受能力都有一定的极限。如人眼对影视节目有视觉暂留效应，对低于某一极限的幅度变化无法感知，故可将信号中这部分感觉不出的分量压缩掉，经过压缩编码的视听信号在复现时仍具有较为满意的主观质量。2022-4-29信息管理系6多媒体信源

3、引起了“数据爆炸”如果不进行数据压缩 传输和存储都难以实用化。多媒体数据数据压缩的必要性2022-4-29信息管理系7数字音数字音频格式频格式频带频带(Hz)带宽带宽(KHz)取样率取样率(KHz)量化量化位数位数存储容存储容量量(MB)电话电话20034003.2880.48会议电会议电视伴音视伴音507000716141.68CD-DACD-DA20200002044.1165.2922DATDAT20200002048165.762数字音数字音频广播频广播20200002048165.766分钟数字音频信号需要的存储空间1 12022-4-29信息管理系8分钟数字视频信号需要的存储空间1

4、 12022-4-29信息管理系9 时间域压缩时间域压缩迅速传输媒体信源迅速传输媒体信源 频率域压缩频率域压缩并行开通更多业务并行开通更多业务 空间域压缩空间域压缩降低存储费用降低存储费用 能量域压缩能量域压缩降低发射功率降低发射功率数据压缩的好处2022-4-29信息管理系10l压缩比要大压缩比要大l恢复后的失真小恢复后的失真小l压缩算法要简单、速度快压缩算法要简单、速度快l压缩能否用硬件实现压缩能否用硬件实现数据压缩技术实现的衡量标准2022-4-29信息管理系112022-4-29信息管理系12 (1)无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据

5、完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。 (2)有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。数据压缩技术的分类2022-4-29信息管理系13 (3)混合压缩。混合压缩是被广泛采用的方法，它吸收了各种无损压缩和有损压缩方法的长处，以求在压缩比、压缩效率及保真度之间取得最佳平衡，如静止图像压缩标准JPEG和活动图像压缩标难MPEG就是采用了混合编码的压缩方法。2022-4-29信息管理系14压缩技术的应用电报、传真(CCITT)通讯(Modem/网络

6、协议)存储(压缩池)文件系统(压缩扇区)图像(GIF/TIFF/JPEG)音频(MP3)视频(MPEG/RM)数据库(B+树)归档(TAR/ZIP)密码学(消除数据的原始特征)全文索引(倒排索引表)编译(JAVA)程序设计(算法/空间和时间效率)人工智能(专家系统/知识树)2022-4-29信息管理系15压缩技术起源信息压缩技术的起源比计算机的发明早几千年2022-4-29信息管理系16一千多年前的中国学者用“班马”这样的缩略语来指代班固和司马迁，这种崇尚简约的风俗一直延续到了今天的 Internet 时代：BBS 上用“ 7456 ”代表“气死我了”，用“ B4 ”代表“ Before ”的

7、时候，这就是一种最简单的数据压缩。2022-4-29信息管理系17在计算机出现之前，著名的 Morse 电码就已经成功地实践了这一准则。在 Morse 码表中，每个字母都对应于一个唯一的点划组合，出现概率最高的字母 e 被编码为一个点“ . ”，而出现概率较低的字母 z 则被编码为“ -. ”。显然，这可以有效缩短最终的电码长度。 2022-4-29信息管理系18信息论信息存在冗余信息存在冗余通过采用一定通过采用一定的模型和编码方法，的模型和编码方法，可以降低这种冗余度可以降低这种冗余度贝尔实验室的 Claude Shannon 和 MIT 的 R.M.Fano几乎同时提出了最早的对符号进行有

8、效编码从而实现数据压缩的 Shannon-Fano 编码方法。2022-4-29信息管理系19D.A.Huffman1952 年 发表论文：“最小冗余度代码的构造方法”A Method for the Construction of Minimum Redundancy CodesUNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT 就是 Huffman 0 阶自适应编码的具体实现 80 年代初，Huffman 编码又在 CP/M 和 DOS 系统中实现，其代表程序叫 SQHuffman时代：时代：60 年代、年代、70 年代乃至年代乃至 80 年代的早期年代的早期2022-4-29

9、信息管理系20接近极限熵80年代早期，数学家们设计出算术编码方法(Arithmetic Coding)可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容 q 但是，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，却要消耗也许几十倍的计算时间 算术编码是部分匹配预测(Predication by Partial matching, PPM)技术的变体2022-4-29信息管理系21以色列人1978 年 发表论文：“通过可变比率编码的独立序列的压缩”Compression of Individual Sequences via Variable

10、-Rate Coding字典编码时代：字典编码时代：LZ77和和LZ78压缩算法压缩算法1977 年 发表论文：“顺序数据压缩的一个通用算法”A Universal Algorithm for Sequential Data Compression2022-4-29信息管理系22LZW算法Welch 实现了 LZ78 算法的一个变种 UNIX：使用 LZW 算法的 Compress 程序MS-DOS：ARC 程序，以及PKWare、PKARC 等仿制品。 1984 年 发表论文：“高性能数据压缩技术”A Technique for High-Performance Data Compressi

11、on 2022-4-29信息管理系23通用数据压缩80年代中期以后，对LZ77算法进行改进Haruyasu Yoshizaki(Yoshi) 的 LHarcRobert Jung 的 ARJ 从PKZip到WinZip：通用数据压缩格式标准 ZIPLZ77、LZ78、LZW 一起垄断当今的通用数据压缩领域一起垄断当今的通用数据压缩领域2022-4-29信息管理系24多媒体数据压缩q国际电报电话咨询委员会( CCITT ) ：针对二值图像的一系列压缩标准，如 CCITT Group3、CCITT Group4 等 (此外还包括CCITT与ISO共同制订的JBIG标准) 。q70 年代末 80 年

12、代初：数学家们提出了损失压缩精度以换取压缩损失压缩精度以换取压缩率的崭新思路率的崭新思路。国际标准化组织( ISO )和 CCITT 联合组成了两个委员会：静态图像联合专家小组( JPEG )和动态图像联合专家小组( MPEG )。诞生了 JPEG、MPEG-1、MPEG-2、MPEG-4、MPEG-7 等系列标准。qPostScript矢量图形格式：起源于 1976 年的 Evans & Sutherland 计算机公司，当时的名字是 Design System。1978 年，John Warnock 和 Martin Newel 将其演变为 JAM 语言。1982 年，John Warno

13、ck 和 Chuck Geschke 创建了著名的 Adobe System 公司，第三次设计和实现了这个语言，并称其为 PostScript。2022-4-29信息管理系25技术准备：什么是熵熵熵来源于40年代由Claude Shannon创立的信息论中的一条定理，这一定理借用了热力学中的名词“熵”( Entropy )来表示一条信息中真正需要编码的信息量：考虑用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码，假设符号 Fn 在整条信息中重复出现的概率为 Pn，则该符号的熵也即表示该符号所需的二进制位数为：En = - log2( Pn )整条信息的熵也即表示整条信息所需的二

14、进制位数为：E = knEn例：对信息aabbaccbaa，字符串长度为 10，字符a、b、c分别出现了5、3、2次，则Ea=-log2(0.5)=1 Eb=-log2(0.3)=1.737 Ec=-log2(0.2)=2.322E= 5Ea + 3Eb + 2Ec =14.855 位对比一下，我们用ASCII编码表示该信息需要80位2022-4-29信息管理系26技术准备：模型使用模型：得到字符或单词在信息中出现的概率静态/半静态模型自适应模型Claude Shannon的“聚会游戏”(party game)：他每次向听众公布一条被他隐藏起一个字符的消息，让听众来猜下一个字符，一次猜一个，直

15、到猜对为止。然后，Shannon 使用猜测次数来确定整个信息的熵。（人的语言经验）静态字典模型自适应字典模型统计模型字典模型2022-4-29信息管理系27技术准备：编码通过模型，我们可以确定对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。前缀编码规则：任何一个符号的编码都不是另一个符号编码的前缀。最简单的前缀编码字符字符编码编码A0B10C110D1110E111101110010101110110111100010 D A B B D C E A A B 反过来说就是，任何一个字符的编码，都不是由另一个字符的编码加

16、上若干位 0 或 1 组成 2022-4-29信息管理系28二叉树可以实现前缀编码规则root01011abcde0102022-4-29信息管理系29技术准备：压缩=模型+编码输入模型编码输出符号概率代码2022-4-29信息管理系30Shannon-Fano编码cabcedeacacdeddaaabaababaaabbacdebaceada a 16b 7c 6d 6e - 5 a 16b 7-c 6-d 6e - 5 例子中的信息编码为：例子中的信息编码为：10 00 01 10 111 110 111 00 10 00 10 .码长共码长共91位，位，而使用而使用ASCII编码表示上述

17、信息共需要编码表示上述信息共需要240位位a 00b 01c 10d 110e 111root0010111abcde2022-4-29信息管理系31Shannon-Fano编码步骤:1) 将给定符号按照其频率从大到小排序。对上面的例子，应该得到：a - 16 b - 7 c - 6 d - 6 e - 52022-4-29信息管理系32Shannon-Fano编码步骤2) 将序列分成上下两部分，使得上部频率总和尽可能接近下部频率总和.a - 16 b - 7 - c 6 d - 6 e - 52022-4-29信息管理系33Shannon-Fano编码步骤3) 我们把第二步中划分出的上部作为

18、二叉树的左子树，记 0，下部作为二叉树的右子树，记 1。2022-4-29信息管理系34Shannon-Fano编码步骤4) 分别对左右子树重复 2 3 两步，直到所有的符号都成为二叉树的树叶为止。现在我们有如下的二叉树.root01011abcde0012022-4-29信息管理系35 1952 年时，年轻的 Huffman 是麻省理工学院的一名学生，他为了向老师证明自己可以不参加某门功课的期末考试，才设计了这个看似简单，但却影响深远的Huffman编码方法。1、Huffman故事Huffman编码2022-4-29信息管理系362、Huffman编码过程2022-4-29信息管理系3720

19、22-4-29信息管理系382022-4-29信息管理系392022-4-29信息管理系402022-4-29信息管理系412022-4-29信息管理系4271161050030111010Huffman码2022-4-29信息管理系43Huffman编码cabcedeacacdeddaaabaababaaabbacdebaceada a 16b 7c 6d 6e - 5 例子中的信息编码为：例子中的信息编码为：101 0 100 101 111 110 111 0 101 0 101 .码长码长88位位，比，比Shannon-Fano编码略短一些编码略短一些a 0b 100c 101d 11

20、0e 111root00111abcde0012022-4-29信息管理系44整数位编码与信息熵cabcedeacacdeddaaabaababaaabbacdebaceada 该信息的熵经计算可知为86.601位符号符号理想位数理想位数（熵）（熵）S-F编码需编码需要位数要位数Huffman编编码需要位数码需要位数a1.32221b2.51523c2.73723d2.73733e3.00033总计总计86.60191882022-4-29信息管理系45另：Huffman编码还有一个变种范式Huffman编码，可以有效减少编码字典的存储空间。Huffman编码的模型选择奇怪的段落奇怪的段落If

21、 Youth，throughout all history，had 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.2022-4-29信息管理系46算术编码假设某个字符的出现概率为 80

22、%，该字符事实上只需要 -log2(0.8) = 0.322 个二进制位进行编码难道真的能只输出 0.322 个 0 或 0.322 个 1 吗？算术编码的输出是：一个小数算术编码的输出是：一个小数算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于0和1之间的二进制小数。例如算术编码对某条信息的输出为1010001111，那么它表示小数0.1010001111，也即十进制数0.642022-4-29信息管理系47算术编码例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb第一步第一步：在没有开始压缩进程之前，假设我们对 a b c

23、 三者在信息中的出现概率一无所知（我们采用的是自适应模型），即认为三者的出现概率相等，也就是都为1/3，我们将0-1区间按照概率的比例分配给三个字符，即a从0.0000到0.3333，b从0.3333到0.6667，c从0.6667到1.0000。用图形表示就是：1.00000.66670.33330.0000Pc = 1/3Pb = 1/3Pa = 1/32022-4-29信息管理系48算术编码第二步第二步：现在我们拿到第一个字符b，让我们把目光投向b对应的区间0.3333-0.6667。这时由于多了字符b，三个字符的概率分布变成：Pa=1/4，Pb=2/4，Pc=1/4。好，让我们按照新的

24、概率分布比例划分0.3333-0.6667这一区间，划分的结果可以用图形表示为：0.66670.58340.41670.3333Pc = 1/4Pb = 2/4Pa = 1/4例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb2022-4-29信息管理系49算术编码第三步第三步：接着我们拿到字符c，我们现在要关注上一步中得到的c的区间 0.5834-0.6667。新添了c以后，三个字符的概率分布变成Pa=1/5，Pb=2/5，Pc=2/5。我们用这个概率分布划分区间0.5834-0.6667：0.66670.63340.60010.5834Pc = 2

25、/5Pb = 2/5Pa = 1/5例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb2022-4-29信息管理系50算术编码第四步第四步：现在输入下一个字符c，三个字符的概率分布为：Pa=1/6，Pb=2/6，Pc=3/6。我们来划分c的区间0.6334-0.6667：0.66670.65010.63900.6334Pc = 3/6Pb = 2/6Pa = 1/6例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb2022-4-29信息管理系51算术编码第五步第五步：输入最后一个字符b，因为是最后一个字符，不用

26、再做进一步的划分了，上一步中得到的b的区间为0.6390-0.6501，好，让我们在这个区间内随便选择一个容易变成二进制的数，例如0.64，将它变成二进制0.1010001111，去掉前面没有太多意义的0和小数点，我们可以输出1010001111，这就是信息被压缩后的结果，我们完成了一次最简单的算术压缩过程0.66670.65010.63900.6334Pc = 3/6Pb = 2/6Pa = 1/6例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb输出输出:(0.64)10 = (0.1010001111)22022-4-29信息管理系52自适应模型

27、的阶h(t)(t)gh(t)igh(t)例文：例文：the weight of .0阶阶1阶阶2阶阶3阶阶问题：1. 半静态模型和自适应模型2. 转义码的使用3. 存储空间问题2022-4-29信息管理系53阶概念例: 对一篇英文文本进行编码，已经编码了 10000 个英文字符，刚刚编码的字符是 t，下一个要编码的字符是 h。在前面的编码过程中已经统计出前 10000 个字符中出现了 113 次字母 t，其中有 47 个 t 后面跟着字母 h。我们得出字符 h 在字符 t 后的出现频率是 47/113，我们使用这一频率对字符 h 进行编码，需要 -log2(47/113) = 1.266 位。

28、2022-4-29信息管理系54阶概念 对比 0 阶自适应模型，如果前 10000 个字符中 h 的出现次数为 82 次，则字符 h 的概率是 82/10000，我们用此概率对 h 进行编码，需要 -log2(82/10000) = 6.930 位。考虑上下文因素的优势显而易见。2022-4-29信息管理系55阶概念例: 要编码字符 h 的前两个字符是 gt，而在已经编码的文本中 gt 后面出现 h 的概率是 80%，那么我们只需要 0.322 位就可以编码输出字符 h。此时，我们使用的模型叫做 2 阶上下文自适应模型. 同样对于3阶一样.2022-4-29信息管理系56字典压缩日常生活: 我

29、们常常跟人说“奥运会”、“IBM”、“TCP”之类的词汇，说者和听者都明白它们指的是“奥林匹克运动会”、“国际商业机器公司”和“传输控制协议”，这实际就是信息的压缩。我们之所以可以顺利使用这种压缩方式而不产生语义上的误解，是因为在说者和听者的心中都有一个事先定义好的缩略语字典，我们在对信息进行压缩（说）和解压缩（听）的过程中都对字典进行了查询操作。字典压缩模型正是基于这一思路设计实现的.2022-4-29信息管理系57字典压缩最简单的情况: 我们拥有一本预先定义好的字典。例如，我们要对一篇中文文章进行压缩，我们手中已经有一本现代汉语词典。那么，我们扫描要压缩的文章，并对其中的句子进行分词操作，

30、对每一个独立的词语，我们在现代汉语词典查找它的出现位置，如果找到，我们就输出页码和该词在该页中的序号，如果没有找到，我们就输出一个新词。这就是静态字典模型的基本算法.2022-4-29信息管理系58字典压缩静态缺点:(1)静态模型的适应性不强，我们必须为每类不同的信息建立不同的字典；(2)对静态模型，我们必须维护信息量并不算小的字典，这一额外的信息量影响了最终的压缩效果。自适应的方式: 将已经编码过的信息作为字典，如果要编码的字符串曾经出现过，就输出该字符串的出现位置及长度，否则输出新的字符串。2022-4-29信息管理系59字典压缩例:2022-4-29信息管理系60LZ77算法 LZ77

31、算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。2022-4-29信息管理系61LZ77算法LZ77算法的基本流程：“滑动的窗口”1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到

32、，则进行步骤 2，否则进行步骤 3。2、输出三元符号组(off,len,c)。其中off为窗口中匹配字符串相对窗口边界的偏移，len为可匹配的长度，c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤 1。3、输出三元符号组(0,0,c)。其中c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤 1。2022-4-29信息管理系62LZ77算法应用实例：窗口大小为10个字符，刚编码过的10个字符为“abcdbbccaa”，即将编码的10个字符为 “abaeaaabaee”。1. 我们首先发现，可以和待编码字符匹配的最长串为ab(off=0,len=2), ab的下一个字符为a，

33、我们输出三元组：(0,2,a)2. 现在窗口向后滑动3个字符，窗口中的内容为：dbbccaaaba3. 下一个字符e在窗口中没有匹配，我们输出三元组：(0,0,e)4. 窗口向后滑动1个字符，其中内容变为：bbccaaabae5. 我们马上发现，要编码的aaabae在窗口中存在(off=4,len=6)，其后的字符为e，我们可以输出：(4,6,e)6. 这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。7. 解压缩时，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符c输出（如果off和len都为0则只输出后

34、继字符c)即可还原出原始数据。2022-4-29信息管理系63LZ77算法三元组的编码方法（编码方式取决于数据的分布概率）：1. 对于第一个分量窗口内的偏移，通常的经验是，偏移接近窗口尾部的情况要多于接近窗口头部的情况。但对于普通的窗口大小来说，这一差别可以忽略不计，我们用固定的位数来表示它：即编码off需要的位数为upper_bound(log2(MAX_WND_SIZE)2. 对于第二个分量字符串长度，它的值在大多数时候不会太大，大字符串的匹配的发生概率很小。显然可以使用一种变长的编码方式来表示该长度值。我们已经知道，要输出变长的编码，该编码必须满足前缀编码的条件。其实 Huffman 编

35、码也可以在此处使用，但却不是最好的选择。适用于此处的好的编码方案很多，我们将在稍后介绍其中两种应用非常广泛的编码：Golomb编码和编码。3. 对三元组的最后一个分量字符 c，因为其分布并无规律可循，我们只能老老实实地用 8 个二进制位对其编码。2022-4-29信息管理系64假设对正整数x进行Golomb编码，选择参数m，令b = 2mq = INT(x - 1)/b)r = x - qb 1则x可以被编码为两部分，第一部分是由q个1加1个0组成，第二部分为m位二进制数，其值为 r。值值 xm = 0m = 1m = 2m = 3100 00 000 0002100 10 010 00131

36、1010 00 100 0104111010 10 110 011511110110 010 000 1006111110110 110 010 101711111101110 010 100 1108111111101110 110 110 111911111111011110 0110 0010 0002022-4-29信息管理系65假设对x编码，令q = int( log2x )则编码的前一部分是q个1加一个0，后一部分是q位长的二进制数，其值等于(x-2q )值值 x编码编码10210 0310 14110 005110 016110 107110 1181110 00091110 0

37、012022-4-29信息管理系66LZ77算法的其他问题其他的编码方式：1. 输出匹配串时不输出后续字符2. 输出0表示下面是一个匹配串，输出1表示下面是一个单个字符3. 对匹配串长度加以限制如何查找匹配串：1. 限制匹配串的长度，在内存中组织二叉有序树2. 将窗口中每个长度为3的字符串建立字典索引3. 使用Hash表建立索引4. 使用字符树建立索引窗口滑动时内存中的索引重建问题：1. 建立环状偏移2. 以环状偏移为基础建立窗口索引2022-4-29信息管理系67LZSS算法 LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一

38、是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。 LZSS算法的思想是如果匹配串的长度比指针本身的长度长就输出指针（匹配串长度大于等于MIN_LENGTH），否则就输出真实字符。另外要输出额外的标志位区分是指针还是字符。2022-4-29信息管理系68LZSS编码的基本流程1、从当前压缩位置开始，考察未编码的字符，并试图在滑动窗口中找出最长的匹配字符串，如果匹配串长度len大于等于最小匹配串长度（len = MIN_LENGTH），则进行步骤 2，否则进行步骤 3。2、输出指针二元组 ( off, len)。其中 off 为窗口中匹配字符串相对窗口边界的偏移

39、，len 为匹配串的长度，然后将窗口向后滑动 len 个字符，继续步骤 1。3、输出当前字符c，然后将窗口向后滑动 1 个字符，继续步骤 1。2022-4-29信息管理系69LZSS编码举例位置位置1234567891011字符字符AABBCBBAABC步骤步骤位置位置匹配串匹配串输出输出11A22AA33B44BB55C66BB（3，2）78AAB（1，3）811CC输入数据流：输入数据流：编码过程编码过程MIN_LEN =22022-4-29信息管理系70LZSS算法 在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基

40、础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip, GZip, ARJ, LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。 LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。2022-4-29信息管理系71第二类词典编码 第二类算法的想法是企图从输入的数据中创建一个“短语词典 (dictionary of the phrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短

41、语本身。2022-4-29信息管理系72LZ78算法 LZ78的编码思想是不断地从字符流中提取新的字符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流(Char stream)，生成码字流(Code stream)，从而达到压缩数据的目的。 LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的字符串(String)用字符C进行扩展生成新的字符串(String)，然后添加到词典中。2022-4-29信息管理系73算法中用到的几个术语

42、: 字符流(Charstream)：待编码的数据序列。 字符(Character)：字符流中的基本数据单元。 前缀(Prefix)：在一个字符之前的字符序列。 缀-符串(String)：前缀字符。 码字(Code word)：码字流中的基本数据单元，代表词典中的一串字符。 2022-4-29信息管理系74码流(Codestream)：码字和字符组成的序列，是编码器的输出。 词典(Dictionary)：缀-符串表。按照词典中的索引号对每条缀-符串(String)指定一个码字(Code word)。 当前前缀(Current prefix)：在编码算法中使用，指当前正在处理的前缀，用符号P表示。

43、 当前字符(Current character)：在编码算法中使用，指当前前缀之后的字符，用符号C表示。 当前码字(Current code word)：在译码算法中使用，指当前处理的码字，用W表示当前码字，String.W表示当前码字的缀-符串。2022-4-29信息管理系75LZ78编码算法步骤1：在开始时，词典和当前前缀P都是空的； 步骤2：当前字符C：=字符流中的下一个字符； 步骤3：判断P+C是否在词典中 (1) 如果“是”：用C扩展P，让P：= P+C ； (2) 如果“否”： 输出与当前前缀P相对应的码字和当前字符C； 把字符串P+C添加到词典中； 令P：=空值； (3) 判断字

44、符流中是否还有字符需要编码 如果“是”：返回到步骤2； 如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。 2022-4-29信息管理系76LZ78编码举例位置位置123456789字符字符ABBCBCABA步骤步骤位置位置词典词典输出输出11A(0, A)22B(0, B)33BC(2, C)45BCA(3, A)58BA(2, A)输入数据流：输入数据流：编码过程：编码过程：2022-4-29信息管理系77LZ78译码的具体算法如下： 步骤1：在开始时词典是空的； 步骤2：当前码字W：=码字流中的下一个码字； 步骤3：当前字符C：= 紧随码字之后的字符； 步骤4：

45、把当前码字的缀-符串(string.W)输出到字符流，然后输出字符C； 步骤5：把string.W+C添加到词典中； 步骤6：判断码字流中是否还有码字要译 (1) 如果“是”，就返回到步骤2； (2) 如果“否”，则结束。2022-4-29信息管理系78LZW算法 J.Ziv和A.Lempel在1978年首次发表了介绍第二类词典编码算法的文章。在他们的研究基础上，Terry A.Welch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码。 2022-4-29信息管理系79在编码原理上，LZW与LZ78相比有如下差别： LZW只输

46、出代表词典中的字符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符。即在编码匹配时，至少可以在词典中找到长度为1的匹配串。 LZW编码是围绕称为词典的转换表来完成的。2022-4-29信息管理系80LZW算法的词典算法的词典 LZW编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流(Char stream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流 (Code stream)，码字代表单个字符或多个字符组成的字符串(Str

47、ing)。2022-4-29信息管理系81LZW编码算法步骤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的码字输出到码字流; 结束。2022-4-29信息管理系82LZW编码举例位

48、置位置123456789字符字符ABBABABAC步骤步骤位置位置码字码字词典词典输出输出1A2B3C114AB1225BB2336BA2447ABA4558ABAC763输入数据流：输入数据流：2022-4-29信息管理系83LZW算法 LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。 LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司Unisys(优利系统公司)，除了商业软

49、件生产公司之外，可以免费使用LZW算法。2022-4-29信息管理系84LZW特点如下： l)LZW压缩技术对于可预测性不大的数据具有较好的处理效果，常用于GIF格式的图像压缩，其平均压缩比在2)1以上，最高压缩比可达到3：1。 2)对于数据流中连续重复出现的字节和字串，LZW压缩技术具有很高的压缩比。 3)除了用于图像数据处理以外，LZW压缩技术还被用于文本程序等数据压缩领域。2022-4-29信息管理系85 4)LZW压缩技术有很多变体，例如常见的ARC、RKARC、PKZIP高效压缩程序。 5)对于任意宽度和像素位长度的图像，都具有稳定的压缩过程。压缩和解压缩速度较快。 6)对机器硬件条

50、件要求不高，在 Intel 80386的计算机上即可进行压缩和解压缩。2022-4-29信息管理系86比较：LZ77算法LZ77算法的基本流程：“滑动的窗口”1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。2、输出三元符号组(off,len,c)。其中off为窗口中匹配字符串相对窗口边界的偏移，len为可匹配的长度，c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤 1。3、输出三元符号组(0,0,c)。其中c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤 1。2022-4-29信息管理系87L

51、Z77算法应用实例：窗口大小为10个字符，刚编码过的10个字符为“abcdbbccaa”，即将编码的10个字符为 “abaeaaabaee”。1. 我们首先发现，可以和待编码字符匹配的最长串为ab(off=0,len=2), ab的下一个字符为a，我们输出三元组：(0,2,a)2. 现在窗口向后滑动3个字符，窗口中的内容为：dbbccaaaba3. 下一个字符e在窗口中没有匹配，我们输出三元组：(0,0,e)4. 窗口向后滑动1个字符，其中内容变为：bbccaaabae5. 我们马上发现，要编码的aaabae在窗口中存在(off=4,len=6)，其后的字符为e，我们可以输出：(4,6,e)6

52、. 这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。7. 解压缩时，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符c输出（如果off和len都为0则只输出后继字符c)即可还原出原始数据。2022-4-29信息管理系88LZ78编码算法步骤1：在开始时，词典和当前前缀P都是空的； 步骤2：当前字符C：=字符流中的下一个字符； 步骤3：判断P+C是否在词典中 (1) 如果“是”：用C扩展P，让P：= P+C ； (2) 如果“否”： 输出与当前前缀P相对应的码字和当前字符C； 把字符串P+C添加到词典中；

53、令P：=空值； (3) 判断字符流中是否还有字符需要编码 如果“是”：返回到步骤2； 如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。 2022-4-29信息管理系89LZ78编码举例位置位置123456789字符字符ABBCBCABA步骤步骤位置位置词典词典输出输出11A(0, A)22B(0, B)33BC(2, C)45BCA(3, A)58BA(2, A)输入数据流：输入数据流：编码过程：编码过程：2022-4-29信息管理系90LZW编码算法步骤1： 开始时的词典包含所有可能的根(Root)，而当前前缀P是空的；步骤2： 当前字符(C) :=字符流中的下一

54、个字符；步骤3： 判断缀-符串P+C是否在词典中(1) 如果“是”：P := P+C / (用C扩展P)；(2) 如果“否” 把代表当前前缀P的码字输出到码字流; 把缀-符串P+C添加到词典; 令P := C /(现在的P仅包含一个字符C);步骤4： 判断码字流中是否还有码字要译(1) 如果“是”，就返回到步骤2；(2) 如果“否” 把代表当前前缀P的码字输出到码字流; 结束。2022-4-29信息管理系91LZW编码举例位置位置123456789字符字符ABBABABAC步骤步骤位置位置码字码字词典词典输出输出1A2B3C114AB1225BB2336BA2447ABA4558ABAC763输入数据流：输入数据流：2022-4-29信息管理系92行程编码（RLE） 行程编码（Run-Length Encoding）：它通过将信源中相同符号序列转换成一个计数字段再