数据压缩技术概论 压缩技术简史 压缩技术基础 Huffman编码 算术编码 LZ77和LZW算法 JPEG算法 通用压缩工具比较

Presentation on theme: "数据压缩技术概论 压缩技术简史 压缩技术基础 Huffman编码 算术编码 LZ77和LZW算法 JPEG算法 通用压缩工具比较"— Presentation transcript:

1 数据压缩技术概论 压缩技术简史 压缩技术基础 Huffman编码 算术编码 LZ77和LZW算法 JPEG算法 通用压缩工具比较
王咏刚 2001年2月

2 压缩技术分类 通用数据压缩（均为无损压缩） 多媒体数据压缩（无损和有损压缩） 基于统计模型 的压缩技术 基于字典模型 的压缩技术 图像压缩
音频和视频压缩 MPEG等 Huffman 编码 算术编码 二值图像 CCITT JBIG等 彩色图像 RLE编码 JPEG等 矢量图像 PostScript WMF CAD等 LZ77 LZ78 LZW 灰度图像 FELICS JPEG等

3 压缩技术的应用 人工智能(专家系统/知识树) 编译(JAVA) 程序设计(算法/空间和时间效率) 全文索引(倒排索引表)
密码学(消除数据的原始特征) 文件系统(压缩扇区) 音频(MP3) 视频(MPEG/RM) 数据库(B+树) 归档(TAR/ZIP) 图像(GIF/TIFF/JPEG) 存储(压缩池) 电报、传真(CCITT) 通讯(Modem/网络协议)

4 压缩技术起源 信息压缩技术的起源…… 比计算机的发明早几千年……

5 信息论 贝尔实验室的 Claude Shannon 和 MIT 的 R.M.Fano 几乎同时提出了最早的对符号进行有效编码
信息存在冗余 通过采用一定 的模型和编码方法， 可以降低这种冗余度 贝尔实验室的 Claude Shannon 和 MIT 的 R.M.Fano 几乎同时提出了最早的对符号进行有效编码 从而实现数据压缩的 Shannon-Fano 编码方法。

6 D.A.Huffman 1952 年 发表论文：“最小冗余度代码的构造方法”
A Method for the Construction of Minimum Redundancy Codes UNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT 就是 Huffman 0 阶自适应编码的具体实现 80 年代初，Huffman 编码又在 CP/M 和 DOS 系统 中实现，其代表程序叫 SQ Huffman时代：60 年代、70 年代乃至 80 年代的早期

7 接近极限——熵 80年代早期，数学家们设计出算术编码方法(Arithmetic Coding)
算术编码是部分匹配预测(Predication by Partial matching, PPM)技术的变体 可以证明，算术编码得到的压缩效果可以最大地减小 信息的冗余度，用最少量的符号精确表达原始信息内容 但是，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，却要消耗也许几十倍的计算时间

8 以色列人 Jacob Ziv 和 Abraham Lempel 1977 年 发表论文：“顺序数据压缩的一个通用算法”
A Universal Algorithm for Sequential Data Compression 1978 年 发表论文：“通过可变比率编码的独立序列的压缩” Compression of Individual Sequences via Variable-Rate Coding 字典编码时代：LZ77和LZ78压缩算法

9 LZW算法 Terry Welch 1984 年 发表论文：“高性能数据压缩技术”
A Technique for High-Performance Data Compression Welch 实现了 LZ78 算法的一个变种 —— LZW算法 UNIX：使用 LZW 算法的 Compress 程序 MS-DOS：ARC 程序，以及PKWare、PKARC 等仿制品。

10 通用数据压缩 80年代中期以后，对LZ77算法进行改进 从PKZip到WinZip： 通用数据压缩格式标准 —— ZIP
Haruyasu Yoshizaki(Yoshi) 的 LHarc Robert Jung 的 ARJ 从PKZip到WinZip： 通用数据压缩格式标准 —— ZIP LZ77、LZ78、LZW 一起垄断当今的通用数据压缩领域

11 多媒体数据压缩 国际电报电话咨询委员会( 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 年的 Evans & Sutherland 计算机公司，当时的名字是 Design System。1978 年，John Warnock 和 Martin Newel 将其演变为 JAM 语言。1982 年，John Warnock 和 Chuck Geschke 创建了著名的 Adobe System 公司，第三次设计和实现了这个语言，并称其为 PostScript。

12 Ea=-log2(0.5)=1 Eb=-log2(0.3)=1.737 Ec=-log2(0.2)=2.322
技术准备：什么是熵 熵——来源于40年代由Claude Shannon创立的信息论中的一条定理，这一定理借用了热力学中的名词“熵”( Entropy )来表示一条信息中真正需要编码的信息量： 考虑用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码，假设符号 Fn 在整条信息中重复出现的概率为 Pn，则该符号的熵也即表示该符号所需的二进制位数为： En = - log2( Pn ) 整条信息的熵也即表示整条信息所需的二进制位数为： E = ∑knEn 例：对信息aabbaccbaa，字符串长度为 10，字符a、b、c分别出现了5、3、2次，则 Ea=-log2(0.5)=1 Eb=-log2(0.3)= Ec=-log2(0.2)=2.322 E= 5Ea + 3Eb + 2Ec = 位 对比一下，我们用ASCII编码表示该信息需要80位

13 技术准备：模型 使用模型：得到字符或单词在信息中出现的概率 静态/半静态模型 统计模型 自适应模型 静态字典模型 字典模型 自适应字典模型
Claude Shannon的“聚会游戏”(party game)： 他每次向听众公布一条被他隐藏起一个字符的消息，让听众来猜下一个字符，一次猜一个，直到猜对为止。然后，Shannon 使用猜测次数来确定整个信息的熵。（人的语言经验）

14 前缀编码规则：任何一个符号的编码都不是另一个符号编码的前缀。
技术准备：编码 通过模型，我们可以确定对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。 前缀编码规则：任何一个符号的编码都不是另一个符号编码的前缀。 最简单的前缀编码 字符 编码 A B 10 C 110 D 1110 E 11110 D A B B D C E A A B

15 技术准备：压缩=模型+编码 符号 概率 代码 输入 模型 编码 输出

16 Shannon-Fano编码 cabcedeacacdeddaaabaababaaabbacdebaceada a – 16 b – 7
c – 6 ----- d – 6 e - 5 root a – 16 b – 7 c – 6 d – 6 e - 5 a – 00 b – 01 c – 10 d – 110 e – 111 1 1 1 1 a b c d e 例子中的信息编码为： 码长共91位，而使用ASCII编码表示上述信息共需要240位

17 Huffman编码 cabcedeacacdeddaaabaababaaabbacdebaceada root a – 16 b – 7
a – 0 b – 100 c – 101 d – 110 e – 111 1 1 a 1 1 b c d e 例子中的信息编码为： 码长88位，比Shannon-Fano编码略短一些

18 整数位编码与信息熵 cabcedeacacdeddaaabaababaaabbacdebaceada 该信息的熵经计算可知为86.601位
符号 理想位数（熵） S-F编码需要位数 Huffman编码需要位数 a 1.322 2 1 b 2.515 3 c 2.737 d e 3.000 总计 86.601 91 88

19 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 wouldn't constantly run across folks today who claim that "a child don't know anything.“ - Gadsby by E.V.Wright, 1939. 另：Huffman编码还有一个变种——范式Huffman编码，可以有效减少编码字典的存储空间。

20 算术编码 假设某个字符的出现概率为 80%，该字符事实上只需要 -log2(0.8) = 个二进制位进行编码 难道真的能只输出 个 0 或 个 1 吗？ 算术编码的输出是：一个小数 算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于0和1之间的二进制小数。 例如算术编码对某条信息的输出为 ，那么它表示小数 ，也即十进制数0.64

21 算术编码 例：考虑某条信息中可能出现的字符仅有 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.0000 Pc = 1/3 0.6667 Pb = 1/3 0.3333 Pa = 1/3 0.0000

22 算术编码 例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb
第二步：现在我们拿到第一个字符b，让我们把目光投向b对应的区间 。这时由于多了字符b，三个字符的概率分布变成：Pa=1/4，Pb=2/4，Pc=1/4。好，让我们按照新的概率分布比例划分 这一区间，划分的结果可以用图形表示为： 0.6667 Pc = 1/4 0.5834 Pb = 2/4 0.4167 Pa = 1/4 0.3333

23 算术编码 例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb
第三步：接着我们拿到字符c，我们现在要关注上一步中得到的c的区间 。新添了c以后，三个字符的概率分布变成Pa=1/5，Pb=2/5，Pc=2/5。我们用这个概率分布划分区间 ： 0.6667 Pc = 2/5 0.6334 Pb = 2/5 0.6001 Pa = 1/5 0.5834

24 算术编码 例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb
第四步：现在输入下一个字符c，三个字符的概率分布为：Pa=1/6，Pb=2/6，Pc=3/6。我们来划分c的区间 ： 0.6667 Pc = 3/6 0.6501 Pb = 2/6 0.6390 Pa = 1/6 0.6334

25 算术编码 例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb 第五步：输入最后一个字符b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的b的区间为 ，好，让我们在这个区间内随便选择一个容易变成二进制的数，例如0.64，将它变成二进制 ，去掉前面没有太多意义的0和小数点，我们可以输出 ，这就是信息被压缩后的结果，我们完成了一次最简单的算术压缩过程 0.6667 Pc = 3/6 输出:(0.64)10 = ( )2 0.6501 Pb = 2/6 0.6390 Pa = 1/6 0.6334

26 自适应模型的阶 例文：the weight of ... 0阶 1阶 2阶 3阶 (t) h(t) gh(t) igh(t) 问题：
半静态模型和自适应模型 转义码的使用 存储空间问题

27 LZ77算法 字典模型：《现代汉语词典》以及下面的例子

28 LZ77算法 LZ77算法的基本流程：“滑动的窗口”
1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。 2、输出三元符号组(off,len,c)。其中off为窗口中匹配字符串相对窗口边界的偏移，len为可匹配的长度，c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤 1。 3、输出三元符号组(0,0,c)。其中c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤 1。

29 LZ77算法 应用实例：窗口大小为10个字符，刚编码过的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) 这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。 解压缩时，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符c输出（如果off和len都为0则只输出后继字符c)即可还原出原始数据。

30 LZ77算法 三元组的编码方法（编码方式取决于数据的分布概率）：
对于第一个分量——窗口内的偏移，通常的经验是，偏移接近窗口尾部的情况要多于接近窗口头部的情况。但对于普通的窗口大小来说，这一差别可以忽略不计，我们用固定的位数来表示它：即编码off需要的位数为upper_bound(log2(MAX_WND_SIZE)) 对于第二个分量——字符串长度，它的值在大多数时候不会太大，大字符串的匹配的发生概率很小。显然可以使用一种变长的编码方式来表示该长度值。我们已经知道，要输出变长的编码，该编码必须满足前缀编码的条件。其实 Huffman 编码也可以在此处使用，但却不是最好的选择。适用于此处的好的编码方案很多，我们将在稍后介绍其中两种应用非常广泛的编码：Golomb编码和γ编码。 对三元组的最后一个分量——字符 c，因为其分布并无规律可循，我们只能老老实实地用 8 个二进制位对其编码。

31 Golomb编码 假设对正整数x进行Golomb编码，选择参数m，令 b = 2m q = INT((x - 1)/b)
r = x - qb – 1 则x可以被编码为两部分，第一部分是由q个1加1个0组成，第二部分为m位二进制数，其值为 r。 Golomb编码 值 x m = 0 m = 1 m = 2 m = 3 1 0 0 0 00 0 000 2 10 0 1 0 01 0 001 3 110 10 0 0 10 0 010 4 1110 10 1 0 11 0 011 5 11110 110 0 10 00 0 100 6 111110 110 1 10 01 0 101 7 1110 0 10 10 0 110 8 1110 1 10 11 0 111 9 110 00 10 000

32 则编码的前一部分是q个1加一个0，后一部分是q位长的二进制数，其值等于(x-2q )
γ编码 假设对x编码，令 q = int( log2x ) 则编码的前一部分是q个1加一个0，后一部分是q位长的二进制数，其值等于(x-2q ) 值 x 编码 1 2 10 0 3 10 1 4 110 00 5 110 01 6 110 10 7 110 11 8 9

33 LZ77算法的其他问题 其他的编码方式： 输出匹配串时不输出后续字符 输出0表示下面是一个匹配串，输出1表示下面是一个单个字符
对匹配串长度加以限制 如何查找匹配串： 限制匹配串的长度，在内存中组织二叉有序树 将窗口中每个长度为3的字符串建立字典索引 使用Hash表建立索引 使用字符树建立索引 窗口滑动时内存中的索引重建问题： 建立环状偏移 以环状偏移为基础建立窗口索引

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

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

36 LZW算法 例：待压缩的信息为 "DAD DADA DADDY DADO..." 第九步后，内存词典的情况如下：
索引 1 2 3 4 词条 null “D” “A” “D ” “DA” 5 6 7 8 9 “DA ” “DAD” “DY” “ ” “DADO” 每一步的输出如下（每一步输出均为二元组）： 步骤 1 2 3 4 5 输出 (0,”D”) (0,”A”) (1,” ”) (1,”A”) (4,” ”) 6 7 8 9 (4,”D”) (1,”Y”) (0,” ”) (6,”O”)

37 Coefficient Quantization
JPEG图像压缩算法 JPEG 是有损压缩算法 JPEG 核心是“离散余弦变换(Discrete Cosine Transform,DCT)” JPEG 压缩算法的基本步骤为： 1、离散余弦变换 DCT Transformation 2、系数量子化 Coefficient Quantization 3、无损压缩 Lossless Compression

38 一维波

39 二维波

40 离散余弦变换 DCT 离散余弦变换(Discrete Cosine Transform,DCT)公式：
DCT操作X、Y、Z坐标轴上的三维信号。X、Y坐标轴是平面图像的两个维度，Z轴表示图象的象素值。对N * N的象素矩阵进行DCT变换的公式如下： 离散余弦变换(Discrete Cosine Transform,DCT)公式： 反向离散余弦变换(Inverse Discrete Cosine Transform,IDCT)公式： 其中： 但是：按照上述基本公式写出的程序实现存在一个严重的问题——时间复杂度太高

41 使用矩阵运算的DCT替代公式 实现上面的替代公式的程序代码的时间复杂度就大大降低了。进一步的改进还包括将余弦函数由浮点运算改为整数运算、改进傅立叶变换技术等。

42 量子化 Quantization 量子化是JPEG算法中损失图像精度的根源，也是产生压缩效果的源泉
DCT变换的输入是8位的象素值（0~255，JPEG实现时将其减去128，范围变成-128~127），但输出范围是从–1024到1023 ，占11位。 量子化即通过整除运算减少输出值的存储位数。 使用量子化矩阵（Quantization Matrix）来实现量子化。 量子化公式为： 量化后的值( i, j ) = ROUND( DCT(i, j) / 量子(i, j) ) 逆量子化公式为： DCT(i, j) = 量化后的值( i, j ) * 量子(i, j) 量子化是JPEG算法中损失图像精度的根源，也是产生压缩效果的源泉

43 量子表Quantum Table quality = 4 quality = 9
Quantum[i][j] = 1 + ( ( 1 + i + j ) * quality ) quality = 4 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 quality = 9 10 19 28 37 46 55 64 73 82 91 100 109 118 127 136

44 Zig-Zag编码 将量子化的矩阵按Zig-Zag顺序排列 将原始数列转换为差值数列
对差值数列进行编码，可以使用Huffman编码、算术编码或熵编码等方法 (0,0)->(0,1)->(1, 0)->(2,0)->……

45 一个真实的编码和解码过程

46 Independent JPEG Group
将原始图像划分成多个 8 X 8 或 16 X 16 的矩阵进行处理 要求矩阵中每个点的像素值范围是 0~255 二值、16级灰度等均转换为256级灰度图像进行处理 对非256色的彩色图象，先转换成真彩色图像，然后使用分色法将图像分成红、蓝、绿三个256级灰度图像，再进行处理 Independent JPEG Group

47 通用压缩工具性能比较 文本 图像 程序 游戏 音频 最高压缩率 压缩比最高 压缩速度最快 解压速度最快 综合得分最高
文件格式 测试指标 文本 图像 程序 游戏 音频 最高压缩率 82.2% 76.0% 68.2% 53.0% 34.5% 压缩比最高 RK 1.02b5 ARHANGEL 1.40 RK 1.02b4 压缩速度最快 LZOP 1.00w 解压速度最快 综合得分最高 PPMD vE ERI32 4.4fre COOLZIP 1.01 RAR WAVARC 1.1 资料来源：Archive Compression Test by Jeff Gilchrist Nov. 1, 2000 Edition 主页地址：

48 谢谢，再见！