dd数据压缩技术概论

1、王咏刚 2001年2月数据压缩技术概论 压缩技术简史 压缩技术基础 Huffman编码 算术编码 LZ77和LZW算法 JPEG算法 通用压缩工具比较1压缩技术分类通用数据压缩（均为无损压缩）多媒体数据压缩（无损和有损压缩）基于统计模型的压缩技术基于字典模型的压缩技术Huffman编码算术编码LZ77LZ78LZW图像压缩音频和视频压缩MPEG等二值图像CCITTJBIG等灰度图像FELICSJPEG等彩色图像RLE编码JPEG等矢量图像PostScriptWMFCAD等2压缩技术的应用电报、传真(CCITT)通讯(Modem/网络协议)存储(压缩池)文件系统(压缩扇区)图像(GIF/TIFF

2、/JPEG)音频(MP3)视频(MPEG/RM)数据库(B+树)归档(TAR/ZIP)密码学(消除数据的原始特征)全文索引(倒排索引表)编译(JAVA)程序设计(算法/空间和时间效率)人工智能(专家系统/知识树)3压缩技术起源信息压缩技术的起源比计算机的发明早几千年4信息论信息存在冗余通过采用一定的模型和编码方法，可以降低这种冗余度贝尔实验室的 Claude Shannon 和 MIT 的 R.M.Fano几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的 Shannon-Fano 编码方法。5D.A.Huffman1952 年 发表论文：“最小冗余度代码的构造方法”A Method f

3、or the Construction of Minimum Redundancy CodesUNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT 就是 Huffman 0 阶自适应编码的具体实现 80 年代初，Huffman 编码又在 CP/M 和 DOS 系统中实现，其代表程序叫 SQHuffman时代：60 年代、70 年代乃至 80 年代的早期6接近极限熵80年代早期，数学家们设计出算术编码方法(Arithmetic Coding)可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容 但是，在同样的计算机系统上，算术编码虽然可以得到最

4、好的压缩效果，却要消耗也许几十倍的计算时间 算术编码是部分匹配预测(Predication by Partial matching, PPM)技术的变体7以色列人Jacob Ziv 和 Abraham Lempel1978 年 发表论文：“通过可变比率编码的独立序列的压缩”Compression of Individual Sequences via Variable-Rate Coding字典编码时代：LZ77和LZ78压缩算法1977 年 发表论文：“顺序数据压缩的一个通用算法”A Universal Algorithm for Sequential Data Compression8LZ

5、W算法Terry Welch Welch 实现了 LZ78 算法的一个变种 LZW算法UNIX：使用 LZW 算法的 Compress 程序MS-DOS：ARC 程序，以及PKWare、PKARC 等仿制品。 1984 年 发表论文：“高性能数据压缩技术”A Technique for High-Performance Data Compression 9通用数据压缩80年代中期以后，对LZ77算法进行改进Haruyasu Yoshizaki(Yoshi) 的 LHarcRobert Jung 的 ARJ 从PKZip到WinZip：通用数据压缩格式标准 ZIPLZ77、LZ78、LZW 一起

6、垄断当今的通用数据压缩领域10多媒体数据压缩国际电报电话咨询委员会( CCITT ) ：针对二值图像的一系列压缩标准，如 CCITT Group3、CCITT Group4 等 (此外还包括CCITT与ISO共同制订的JBIG标准) 。70 年代末 80 年代初：数学家们提出了损失压缩精度以换取压缩率的崭新思路。国际标准化组织( ISO )和 CCITT 联合组成了两个委员会：静态图像联合专家小组( JPEG )和动态图像联合专家小组( MPEG )。诞生了 JPEG、MPEG-1、MPEG-2、MPEG-4、MPEG-7 等系列标准。PostScript矢量图形格式：起源于 1976 年的

7、Evans & Sutherland 计算机公司，当时的名字是 Design System。1978 年，John Warnock 和 Martin Newel 将其演变为 JAM 语言。1982 年，John Warnock 和 Chuck Geschke 创建了著名的 Adobe System 公司，第三次设计和实现了这个语言，并称其为 PostScript。11技术准备：什么是熵熵来源于40年代由Claude Shannon创立的信息论中的一条定理，这一定理借用了热力学中的名词“熵”( Entropy )来表示一条信息中真正需要编码的信息量：考虑用 0 和 1 组成的二进制数码为含有 n

8、 个符号的某条信息编码，假设符号 Fn 在整条信息中重复出现的概率为 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位12技术准备：模型使用模型：得到字符或单词在信息中出现的概率静态/半静态

9、模型自适应模型Claude Shannon的“聚会游戏”(party game)：他每次向听众公布一条被他隐藏起一个字符的消息，让听众来猜下一个字符，一次猜一个，直到猜对为止。然后，Shannon 使用猜测次数来确定整个信息的熵。（人的语言经验）静态字典模型自适应字典模型统计模型字典模型13技术准备：编码通过模型，我们可以确定对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。前缀编码规则：任何一个符号的编码都不是另一个符号编码的前缀。最简单的前缀编码字符编码A0B10C110D1110E11110111101111000

10、10 D A B B D C E A A B 14技术准备：压缩=模型+编码输入模型编码输出符号概率代码15Shannon-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 111root0010111abcde16Huffman编码cabcedeacacdeddaaabaababa

11、aabbacdebaceada 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 111root00111abcde00117整数位编码与信息熵cabcedeacacdeddaaabaababaaabbacdebaceada 该信息的熵经计算可知为86.601位符号理想位数（熵）S-F编码需要位数Huffman编码需要位数a1.32221b2.51523c2.73723d2.73733e3.00033总计86.60191

12、8818另：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 that a child dont know anyt

13、hing.“- Gadsby by E.V.Wright, 1939.19算术编码假设某个字符的出现概率为 80%，该字符事实上只需要 -log2(0.8) = 0.322 个二进制位进行编码难道真的能只输出 0.322 个 0 或 0.322 个 1 吗？算术编码的输出是：一个小数算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于0和1之间的二进制小数。例如算术编码对某条信息的输出为1010001111，那么它表示小数0.1010001111，也即十进制数0.6420算术编码例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb第

14、一步：在没有开始压缩进程之前，假设我们对 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/321算术编码第二步：现在我们拿到第一个字符b，让我们把目光投向b对应的区间0.3333-0.6667。这时由于多了字符b，三个字符的概率分布变成：Pa=1/4，Pb=2/4，Pc=1/4。

15、好，让我们按照新的概率分布比例划分0.3333-0.6667这一区间，划分的结果可以用图形表示为：0.66670.58340.41670.3333Pc = 1/4Pb = 2/4Pa = 1/4例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb22算术编码第三步：接着我们拿到字符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/5Pb = 2

16、/5Pa = 1/5例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb23算术编码第四步：现在输入下一个字符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 三种，我们要压缩保存的原始信息为 bccb24算术编码第五步：输入最后一个字符b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的b的区间为0.6390-0.6501，好，让我们在

17、这个区间内随便选择一个容易变成二进制的数，例如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)225自适应模型的阶h(t)(t)gh(t)igh(t)例文：the weight of .0阶1阶2阶3阶问题：半静态模型和自适应

18、模型转义码的使用存储空间问题26LZ77算法字典模型：现代汉语词典以及下面的例子27LZ77算法LZ77算法的基本流程：“滑动的窗口”1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。2、输出三元符号组(off,len,c)。其中off为窗口中匹配字符串相对窗口边界的偏移，len为可匹配的长度，c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤 1。3、输出三元符号组(0,0,c)。其中c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤 1。28LZ77算法应用实例：窗口大小为10个字符，刚编码过的

19、10个字符为“abcdbbccaa”，即将编码的10个字符为 “abaeaaabaee”。我们首先发现，可以和待编码字符匹配的最长串为ab(off=0,len=2), ab的下一个字符为a，我们输出三元组：(0,2,a)现在窗口向后滑动3个字符，窗口中的内容为：dbbccaaaba下一个字符e在窗口中没有匹配，我们输出三元组：(0,0,e)窗口向后滑动1个字符，其中内容变为：bbccaaabae我们马上发现，要编码的aaabae在窗口中存在(off=4,len=6)，其后的字符为e，我们可以输出：(4,6,e)这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。

20、解压缩时，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符c输出（如果off和len都为0则只输出后继字符c)即可还原出原始数据。29LZ77算法三元组的编码方法（编码方式取决于数据的分布概率）：对于第一个分量窗口内的偏移，通常的经验是，偏移接近窗口尾部的情况要多于接近窗口头部的情况。但对于普通的窗口大小来说，这一差别可以忽略不计，我们用固定的位数来表示它：即编码off需要的位数为upper_bound(log2(MAX_WND_SIZE)对于第二个分量字符串长度，它的值在大多数时候不会太大，大字符串的匹配的发生概率很小。显然可以使用一种变

21、长的编码方式来表示该长度值。我们已经知道，要输出变长的编码，该编码必须满足前缀编码的条件。其实 Huffman 编码也可以在此处使用，但却不是最好的选择。适用于此处的好的编码方案很多，我们将在稍后介绍其中两种应用非常广泛的编码：Golomb编码和编码。对三元组的最后一个分量字符 c，因为其分布并无规律可循，我们只能老老实实地用 8 个二进制位对其编码。30假设对正整数x进行Golomb编码，选择参数m，令b = 2mq = INT(x - 1)/b)r = x - qb 1则x可以被编码为两部分，第一部分是由q个1加1个0组成，第二部分为m位二进制数，其值为 r。Golomb编码31假设对x编

22、码，令q = int( log2x )则编码的前一部分是q个1加一个0，后一部分是q位长的二进制数，其值等于(x-2q )值 x编码10210 0310 14110 005110 016110 107110 1181110 00091110 001编码32LZ77算法的其他问题其他的编码方式：输出匹配串时不输出后续字符输出0表示下面是一个匹配串，输出1表示下面是一个单个字符对匹配串长度加以限制如何查找匹配串：限制匹配串的长度，在内存中组织二叉有序树将窗口中每个长度为3的字符串建立字典索引使用Hash表建立索引使用字符树建立索引窗口滑动时内存中的索引重建问题：建立环状偏移以环状偏移为基础建立窗口

23、索引33内存词典：第二步：压缩串“AD .”在内存词典中仍无法找到匹配串，则输出二元组(0，“A”)并将字串“A”置入内存词典第一步：压缩串“DAD.”在内存词典中无法找到匹配串，则输出二元组(0，“D”)二元组中第一个元素表示词典的索引，第二个元素表示后续字符。并将字串“D”置入内存词典内存词典：LZW算法LZW算法是LZ78的改进，其基本思路是在内存中维护一个动态的字典，输出的代码是该字典的索引例：待压缩的信息为 DAD DADA DADDY DADO. 索引0词条null索引01词条null“D”34第三步：压缩串“D D.”在内存词典中可以找到最大匹配串“D”，输出二元组 (1，“ ”

24、)以此对字串“D ”进行了编码，然后将“D ”置入内存词典内存词典：内存词典：第四步：压缩串“DAD.”在内存词典中可以找到最大匹配串“D”，则输出二元组(1，“A”)以此对字串“DA”进行了编码，然后将“DA”置入内存词典LZW算法例：待压缩的信息为 DAD DADA DADDY DADO. 索引012词条null“D”“A”索引0123词条null“D”“A”“D ”35LZW算法例：待压缩的信息为 DAD DADA DADDY DADO. 第九步后，内存词典的情况如下：索引01234词条null“D”“A”“D ”“DA”索引56789词条“DA ”“DAD”“DY”“ ”“DADO”每

25、一步的输出如下（每一步输出均为二元组）：36JPEG图像压缩算法JPEG 是有损压缩算法JPEG 核心是“离散余弦变换(Discrete Cosine Transform,DCT)”JPEG 压缩算法的基本步骤为：1、离散余弦变换DCT Transformation2、系数量子化Coefficient Quantization 3、无损压缩Lossless Compression37一维波38二维波39离散余弦变换 DCTDCT操作X、Y、Z坐标轴上的三维信号。X、Y坐标轴是平面图像的两个维度，Z轴表示图象的象素值。对N * N的象素矩阵进行DCT变换的公式如下：离散余弦变换(Discrete

26、 Cosine Transform,DCT)公式：反向离散余弦变换(Inverse Discrete Cosine Transform,IDCT)公式：其中：但是：按照上述基本公式写出的程序实现存在一个严重的问题时间复杂度太高40使用矩阵运算的DCT替代公式实现上面的替代公式的程序代码的时间复杂度就大大降低了。进一步的改进还包括将余弦函数由浮点运算改为整数运算、改进傅立叶变换技术等。41量子化 QuantizationDCT变换的输入是8位的象素值（0255，JPEG实现时将其减去128，范围变成-128127），但输出范围是从1024到1023 ，占11位。量子化即通过整除运算减少输出值的存储位数。使用量子化矩阵（Quantization Matrix）来实现量子化。量子化公式为：量化后的值( i, j ) = ROUND( DCT(i, j) / 量子(i, j) )逆量子化公式为：DCT(i, j) = 量化后的值( i, j ) * 量子(i, j) 量子化是JPEG算法中损失图像精度的根源，也是产生压缩效果的源泉42量子表Quantum Table471013161922257101316192225281013161922252831131619222528313416192225283134371922252831