《王咏刚2001年2月.ppt》由会员分享，可在线阅读，更多相关《王咏刚2001年2月.ppt（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、王咏刚2001年2月 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望压缩技术分类通用数据压缩（均为无损压缩）通用数据压缩（均为无损压缩）多媒体数据压缩（无损和有损压缩）多媒体数据压缩（无损和有损压缩）基于统计模型基于统计模型的压缩技术的压缩技术基于字典模型基于字典模型的压缩技术的压缩技术HuffmanHuffman编码编码算术编码算术编码LZ77LZ77LZ78LZ78LZWLZW图像压缩图像压缩音频和视频压缩音频和视频压缩MPEGMPEG等等二值图像二值图像CC
2、ITTCCITTJBIGJBIG等等灰度图像灰度图像FELICSFELICSJPEGJPEG等等彩色图像彩色图像RLERLE编码编码JPEGJPEG等等矢量图像矢量图像PostScriptPostScriptWMFWMFCADCAD等等压缩技术的应用电报、传真(CCITT)通讯(Modem/网络协议)存储(压缩池)文件系统(压缩扇区)图像(GIF/TIFF/JPEG)音频(MP3)视频(MPEG/RM)数据库(B+树)归档(TAR/ZIP)密码学(消除数据的原始特征)全文索引(倒排索引表)编译(JAVA)程序设计(算法/空间和时间效率)人工智能(专家系统/知识树)压缩技术起源信息压缩技术的起源
3、比计算机的发明早几千年信息论信息存在冗余信息存在冗余通过采用一定通过采用一定的模型和编码方法，的模型和编码方法，可以降低这种冗余度可以降低这种冗余度贝尔实验室的 Claude Shannon 和 MIT 的 R.M.Fano几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的 Shannon-Fano 编码方法。D.A.Huffman1952 年 发表论文：“最小冗余度代码的构造方法”A Method for the Construction of Minimum Redundancy CodesUNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT 就是 Huffman 0 阶自
4、适应编码的具体实现 80 年代初，Huffman 编码又在 CP/M 和 DOS 系统中实现，其代表程序叫 SQHuffman时代：时代：60 年代、年代、70 年代乃至年代乃至 80 年代的早期年代的早期接近极限熵80年代早期，数学家们设计出算术编码方法(Arithmetic Coding)可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容 q但是，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，却要消耗也许几十倍的计算时间 算术编码是部分匹配预测(Predication by Partial matching,PPM)技术的变体以色列人
5、Jacob ZivJacob Ziv 和和 Abraham LempelAbraham Lempel1978 年 发表论文：“通过可变比率编码的独立序列的压缩”Compression of Individual Sequences via Variable-Rate Coding字典编码时代：字典编码时代：LZ77和和LZ78压缩算法压缩算法1977 年 发表论文：“顺序数据压缩的一个通用算法”A Universal Algorithm for Sequential Data CompressionLZW算法Terry Welch Welch 实现了 LZ78 算法的一个变种 LZW算法UNI
6、X：使用 LZW 算法的 Compress 程序MS-DOS：ARC 程序，以及PKWare、PKARC 等仿制品。1984 年 发表论文：“高性能数据压缩技术”A Technique for High-Performance Data Compression 通用数据压缩80年代中期以后，对LZ77算法进行改进Haruyasu Yoshizaki(Yoshi)的 LHarcRobert Jung 的 ARJ 从PKZip到WinZip：通用数据压缩格式标准 ZIPLZ77、LZ78、LZW 一起垄断当今的通用数据压缩领域一起垄断当今的通用数据压缩领域多媒体数据压缩q国际电报电话咨询委员会(C
7、CITT)：针对二值图像的一系列压缩标准，如 CCITT Group3、CCITT Group4 等(此外还包括CCITT与ISO共同制订的JBIG标准)。q70 年代末 80 年代初：数学家们提出了损失压缩精度以换取压缩损失压缩精度以换取压缩率的崭新思路率的崭新思路。国际标准化组织(ISO)和 CCITT 联合组成了两个委员会：静态图像联合专家小组(JPEG)和动态图像联合专家小组(MPEG)。诞生了 JPEG、MPEG-1、MPEG-2、MPEG-4、MPEG-7 等系列标准。qPostScript矢量图形格式：起源于 1976 年的 Evans&Sutherland 计算机公司，当时的名
8、字是 Design System。1978 年，John Warnock 和 Martin Newel 将其演变为 JAM 语言。1982 年，John Warnock 和 Chuck Geschke 创建了著名的 Adobe System 公司，第三次设计和实现了这个语言，并称其为 PostScript。技术准备：什么是熵熵熵来源于40年代由Claude Shannon创立的信息论中的一条定理，这一定理借用了热力学中的名词“熵”(Entropy)来表示一条信息中真正需要编码的信息量：考虑用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码，假设符号 Fn 在整条信息中重复出现的概
9、率为 Pn，则该符号的熵也即表示该符号所需的二进制位数为：En=-log2(Pn)整条信息的熵也即表示整条信息所需的二进制位数为：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位技术准备：模型使用模型：得到字符或单词在信息中出现的概率静态/半静态模型自适应模型Claude Shannon的“聚会游戏”(party game)：他每次向听众
10、公布一条被他隐藏起一个字符的消息，让听众来猜下一个字符，一次猜一个，直到猜对为止。然后，Shannon 使用猜测次数来确定整个信息的熵。（人的语言经验）静态字典模型自适应字典模型统计模型字典模型技术准备：编码通过模型，我们可以确定对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。前缀编码规则：任何一个符号的编码都不是另一个符号编码的前缀。最简单的前缀编码字符字符编码编码A0B10C110D1110E111101110010101110110111100010 D A B B D C E A A B 技术准备：压缩=模型+
11、编码输入模型编码输出符号概率代码Shannon-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编码表示上述信息共需要编码表示上述信息共需要240位位a 00b 01c 10d 110e 111root0010111abcdeHuffman编码cabcedeacacdeddaaabaababaaabbacdebaceada
12、 a 16b 7c 6d 6e-5 例子中的信息编码为：例子中的信息编码为：101 0 100 101 111 110 111 0 101 0 101.码长码长88位，比位，比Shannon-Fano编码略短一些编码略短一些a 0b 100c 101d 110e 111root00111abcde001整数位编码与信息熵cabcedeacacdeddaaabaababaaabbacdebaceada 该信息的熵经计算可知为86.601位符号符号理想位数理想位数（熵）（熵）S-F编码需编码需要位数要位数Huffman编编码需要位数码需要位数a1.32221b2.51523c2.73723d2.7
13、3733e3.00033总计总计86.6019188另：Huffman编码还有一个变种范式Huffman编码，可以有效减少编码字典的存储空间。Huffman编码的模型选择奇怪的段落奇怪的段落If 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
14、that a child dont know anything.“-Gadsby by E.V.Wright,1939.算术编码假设某个字符的出现概率为 80%，该字符事实上只需要-log2(0.8)=0.322 个二进制位进行编码难道真的能只输出 0.322 个 0 或 0.322 个 1 吗？算术编码的输出是：一个小数算术编码的输出是：一个小数算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于0和1之间的二进制小数。例如算术编码对某条信息的输出为1010001111，那么它表示小数0.1010001111，也即十进制数0.64算术编码例：考虑某条信息中可能出现的字符
15、仅有 a b c 三种，我们要压缩保存的原始信息为 bccb第一步第一步：在没有开始压缩进程之前，假设我们对 a b c 三者在信息中的出现概率一无所知（我们采用的是自适应模型），即认为三者的出现概率相等，也就是都为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/3算术编码第二步第二步：现在我们拿到第一个字符b，让我们把目光投向b对应的区间0.3333-0.6667。这时由于多了字符b，三个字符
16、的概率分布变成：Pa=1/4，Pb=2/4，Pc=1/4。好，让我们按照新的概率分布比例划分0.3333-0.6667这一区间，划分的结果可以用图形表示为：0.66670.58340.41670.3333Pc=1/4Pb=2/4Pa=1/4例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb算术编码第三步第三步：接着我们拿到字符c，我们现在要关注上一步中得到的c的区间 0.5834-0.6667。新添了c以后，三个字符的概率分布变成Pa=1/5，Pb=2/5，Pc=2/5。我们用这个概率分布划分区间0.5834-0.6667：0.66670.63340.
17、60010.5834Pc=2/5Pb=2/5Pa=1/5例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb算术编码第四步第四步：现在输入下一个字符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 三种，我们要压缩保存的原始信息为 bccb算术编码第五步第五步：输入最后一个字符b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的b的区间为0.6390
18、-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)2自适应模型的阶h(t)(t)gh(t)igh(t)例文：例文：the weight of.0阶阶1阶阶2阶阶3阶阶
19、问题：1.半静态模型和自适应模型2.转义码的使用3.存储空间问题LZ77算法字典模型：现代汉语词典以及下面的例子LZ77算法LZ77算法的基本流程：“滑动的窗口”1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。2、输出三元符号组(off,len,c)。其中off为窗口中匹配字符串相对窗口边界的偏移，len为可匹配的长度，c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤 1。3、输出三元符号组(0,0,c)。其中c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤 1。LZ77算法应用实例：窗口大小
20、为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.这样，我们将可以匹配的字符串都变成了指向
21、窗口内的指针，并由此完成了对上述数据的压缩。7.解压缩时，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符c输出（如果off和len都为0则只输出后继字符c)即可还原出原始数据。LZ77算法三元组的编码方法（编码方式取决于数据的分布概率）：1.对于第一个分量窗口内的偏移，通常的经验是，偏移接近窗口尾部的情况要多于接近窗口头部的情况。但对于普通的窗口大小来说，这一差别可以忽略不计，我们用固定的位数来表示它：即编码off需要的位数为upper_bound(log2(MAX_WND_SIZE)2.对于第二个分量字符串长度，它的值在大多数时候不会太
22、大，大字符串的匹配的发生概率很小。显然可以使用一种变长的编码方式来表示该长度值。我们已经知道，要输出变长的编码，该编码必须满足前缀编码的条件。其实 Huffman 编码也可以在此处使用，但却不是最好的选择。适用于此处的好的编码方案很多，我们将在稍后介绍其中两种应用非常广泛的编码：Golomb编码和编码。3.对三元组的最后一个分量字符 c，因为其分布并无规律可循，我们只能老老实实地用 8 个二进制位对其编码。假设对正整数x进行Golomb编码，选择参数m，令b=2mq=INT(x-1)/b)r=x-qb 1则x可以被编码为两部分，第一部分是由q个1加1个0组成，第二部分为m位二进制数，其值为 r
23、。值值 xm=0m=1m=2m=3100 00 000 0002100 10 010 001311010 00 100 0104111010 10 110 011511110110 010 000 1006111110110 110 010 101711111101110 010 100 1108111111101110 110 110 111911111111011110 0110 0010 000Golomb编码假设对x编码，令q=int(log2x)则编码的前一部分是q个1加一个0，后一部分是q位长的二进制数，其值等于(x-2q)值值 x编码编码10210 0310 14110 0051
24、10 016110 107110 1181110 00091110 001编码LZ77算法的其他问题其他的编码方式：1.输出匹配串时不输出后续字符2.输出0表示下面是一个匹配串，输出1表示下面是一个单个字符3.对匹配串长度加以限制如何查找匹配串：1.限制匹配串的长度，在内存中组织二叉有序树2.将窗口中每个长度为3的字符串建立字典索引3.使用Hash表建立索引4.使用字符树建立索引窗口滑动时内存中的索引重建问题：1.建立环状偏移2.以环状偏移为基础建立窗口索引内存词典：内存词典：第二步：压缩串第二步：压缩串“AD.”在内存词典中仍无法找到匹配串，则输出二元组在内存词典中仍无法找到匹配串，则输出二
25、元组(0，“A”)并将字串并将字串“A”置入内存词典置入内存词典第一步：压缩串第一步：压缩串“DAD.”在内存词典中无法找到匹配串，则输出二元组在内存词典中无法找到匹配串，则输出二元组(0，“D”)二元组中第一个元素表示词典的索引，第二个元素表示后续字符。二元组中第一个元素表示词典的索引，第二个元素表示后续字符。并将字串并将字串“D”置入内存词典置入内存词典内存词典：内存词典：LZW算法LZW算法是LZ78的改进，其基本思路是在内存中维护一个动态的字典，输出的代码是该字典的索引例：待压缩的信息为例：待压缩的信息为 DAD DADA DADDY DADO.索引索引0词条词条null索引索引01词
26、条词条null“D”第三步：压缩串第三步：压缩串“D D.”在内存词典中可以找到最大匹配串在内存词典中可以找到最大匹配串“D”，输出输出二元组二元组(1，“”)以此对字串以此对字串“D”进行了编码，然后将进行了编码，然后将“D”置入内存词典置入内存词典内存词典：内存词典：内存词典：内存词典：第四步：压缩串第四步：压缩串“DAD.”在内存词典中可以找到最大匹配串在内存词典中可以找到最大匹配串“D”，则输则输出出二元组二元组(1，“A”)以此对字串以此对字串“DA”进行了编码，然后将进行了编码，然后将“DA”置入内存词典置入内存词典LZW算法例：待压缩的信息为例：待压缩的信息为 DAD DADA
27、DADDY DADO.索引索引012词条词条null“D”“A”索引索引0123词条词条null“D”“A”“D”LZW算法例：待压缩的信息为例：待压缩的信息为 DAD DADA DADDY DADO.第九步后，内存词典的情况如下：第九步后，内存词典的情况如下：索引索引01234词条词条null“D”“A”“D”“DA”索引索引56789词条词条“DA”“DAD”“DY”“”“DADO”每一步的输出如下（每一步输出均为二元组）：每一步的输出如下（每一步输出均为二元组）：步骤步骤12345输出输出(0,”D”)(0,”A”)(1,”)(1,”A”)(4,”)步骤步骤6789输出输出(4,”D”)
28、(1,”Y”)(0,”)(6,”O”)JPEG图像压缩算法qJPEG 是有损压缩算法qJPEG 核心是“离散余弦变换(Discrete Cosine Transform,DCT)”qJPEG 压缩算法的基本步骤为：1、离散余弦变换DCT Transformation2、系数量子化Coefficient Quantization 3、无损压缩Lossless Compression一维波二维波离散余弦变换 DCTDCT操作X、Y、Z坐标轴上的三维信号。X、Y坐标轴是平面图像的两个维度，Z轴表示图象的象素值。对N*N的象素矩阵进行DCT变换的公式如下：离散余弦变换(Discrete Cosine
29、Transform,DCT)公式：反向离散余弦变换(Inverse Discrete Cosine Transform,IDCT)公式：其中：但是：按照上述基本公式写出的程序实现存在一个严重的问题时间复杂度太高使用矩阵运算的DCT替代公式q实现上面的替代公式的程序代码的时间复杂度就大大降低了。进一步的改进还包括将余弦函数由浮点运算改为整数运算、改进傅立叶变换技术等。量子化 QuantizationDCT变换的输入是8位的象素值（0255，JPEG实现时将其减去128，范围变成-128127），但输出范围是从1024到1023，占11位。量子化即通过整除运算减少输出值的存储位数。使用量子化矩阵（
30、Quantization Matrix）来实现量子化。量子化公式为：量化后的值(i,j)=ROUND(DCT(i,j)/量子(i,j)逆量子化公式为：DCT(i,j)=量化后的值(i,j)*量子(i,j)量子化是JPEG算法中损失图像精度的根源，也是产生压缩效果的源泉量子表Quantum Table4 7 1013161922257 101316192225281013161922252831131619222528313416192225283134371922252831343740222528313437404325283134374043461019283746556473192837
31、4655647382283746556473829137465564738291100465564738291100109556473829110010911864738291100109118127738291100109118127136quality=4quality=9Quantumij=1+(1+i+j)*quality)Zig-Zag编码(0,0)-(0,1)-(1,0)-(2,0)-q将量子化的矩阵按Zig-Zag顺序排列q将原始数列转换为差值数列q对差值数列进行编码，可以使用Huffman编码、算术编码或熵编码等方法一个真实的编码和解码过程一个真实的编码和解码过程JPEG的其他
32、问题qq将原始图像划分成多个将原始图像划分成多个 8 8 X 8 X 8 或或 16 16 X 16 X 16 的矩阵进行处理的矩阵进行处理qq要求矩阵中每个点的像素值范围是要求矩阵中每个点的像素值范围是 0255 0255qq二值、二值、1616级灰度等均转换为级灰度等均转换为256256级灰度图像进行处理级灰度图像进行处理qq对非对非256256色的彩色图象，先转换成真彩色图像，然后使用分色色的彩色图象，先转换成真彩色图像，然后使用分色法将图像分成红、蓝、绿三个法将图像分成红、蓝、绿三个256256级灰度图像，再进行处理级灰度图像，再进行处理Independent JPEG GroupIn
33、dependent JPEG Grouphttp:/www.ijg.org/http:/www.ijg.org/通用压缩工具性能比较 文件格式文件格式测试指标测试指标文本文本图像图像程序程序游戏游戏音频音频最高压缩率最高压缩率82.2%76.0%68.2%53.0%34.5%压缩比最高压缩比最高RK 1.02b5ARHANGEL 1.40RK 1.02b5RK 1.02b4RK 1.02b4压缩速度最快压缩速度最快LZOP 1.00wLZOP 1.00wLZOP 1.00wLZOP 1.00wLZOP 1.00w解压速度最快解压速度最快LZOP 1.00wLZOP 1.00wLZOP 1.00wLZOP 1.00wLZOP 1.00w综合得分最高综合得分最高PPMD vEERI32 4.4freCOOLZIP 1.01RAR32 2.60WAVARC 1.1资料来源：资料来源：资料来源：资料来源：Archive Compression Test by Jeff Gilchrist Nov.1,2000 EditionArchive Compression Test by Jeff Gilchrist Nov.1,2000 Edition主页地址：主页地址：主页地址：主页地址：http:/