数据压缩技术概论
压缩技术简史
压缩技术基础
Huffman编码
算术编码
LZ77和 LZW算法
JPEG算法
通用压缩工具比较压缩技术分类通用数据压缩（均为无损压缩） 多媒体数据压缩（无损和有损压缩）
基于统计模型的压缩技术基于字典模型的压缩技术
Huffman
编码算术编码
LZ77 LZ78 LZW
图像压缩 音频和视频压缩
MPEG等二值图像
CCITT
JBIG等灰度图像
FELICS
JPEG等彩色图像
RLE编码
JPEG等矢量图像
PostScript
WMF
CAD等压缩技术的应用电报、传真 (CCITT)
通讯 (Modem/网络协议 )
存储 (压缩池 )
文件系统 (压缩扇区 )
图像 (GIF/TIFF/JPEG)
音频 (MP3)
视频 (MPEG/RM)数据库 (B+树 )
归档 (TAR/ZIP)
密码学 (消除数据的原始特征 )
全文索引 (倒排索引表 )
编译 (JAVA)
程序设计 (算法 /空间和时间效率 )
人工智能 (专家系统 /知识树 )
压缩技术起源信息压缩技术的起源 ……
比计算机的发明早几千年 ……
信息论信息存在冗余通过采用一定的模型和编码方法，
可以降低这种冗余度贝尔实验室的 Claude Shannon 和 MIT 的 R.M.Fano
几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的 Shannon-Fano 编码方法。
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 年代的早期接近极限 ——熵
80年代早期，数学家们设计出算术编码方法 (Arithmetic
Coding)
可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容
但是，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，却要消耗也许几十倍的计算时间算术编码是部分匹配预测 (Predication by Partial matching,
PPM)技术的变体以色列人
Jacob Ziv 和 Abraham Lempel
1978 年 发表论文：“通过可变比率编码的独立序列的压缩”
Compression of Individual Sequences via Variable-Rate Coding
字典编码时代,LZ77和 LZ78压缩算法
1977 年 发表论文：“顺序数据压缩的一个通用算法”
A Universal Algorithm for Sequential Data Compression
LZW算法
Terry Welch
Welch 实现了 LZ78 算法的一个变种 —— LZW算法
UNIX：使用 LZW 算法的 Compress 程序
MS-DOS,ARC 程序,以及 PKWare,PKARC 等仿制品。
1984 年 发表论文：“高性能数据压缩技术”
A Technique for High-Performance Data Compression
通用数据压缩
80年代中期以后，对 LZ77算法进行改进
Haruyasu Yoshizaki(Yoshi) 的 LHarc
Robert Jung 的 ARJ
从 PKZip到 WinZip：
通用数据压缩格式标准 —— ZIP
LZ77,LZ78,LZW 一起垄断当今的通用数据压缩领域多媒体数据压缩
国际电报电话咨询委员会 ( 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。
技术准备：什么是熵熵 ——来源于 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)=1.737 Ec=-log2(0.2)=2.322
E= 5Ea + 3Eb + 2Ec =14.855 位对比一下，我们用 ASCII编码表示该信息需要 80位技术准备：模型使用模型：得到字符或单词在信息中出现的概率静态 /半静态模型自适应模型
Claude Shannon的“聚会游戏” (party game)：
他每次向听众公布一条被他隐藏起一个字符的消息，让听众来猜下一个字符，一次猜一个，直到猜对为止。然后,Shannon 使用猜测次数来确定整个信息的熵。（人的语言经验）
静态字典模型自适应字典模型统计模型字典模型技术准备：编码通过模型，我们可以确定对某一个符号该用多少位二进制数进行编码。
现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。
前缀编码规则：任何一个符号的编码都不是另一个符号编码的前缀。
最简单的前缀编码字符 编码
A 0
B 10
C 110
D 1110
E 11110
1110010101110110111100010
D A B B D C E A A B
技术准备：压缩 =模型 +编码输入 模型 编码 输出符号 概率 代码
Shannon-Fano编码
cabcedeacacdeddaaabaababaaabbacdebaceada
a – 16
b – 7
c – 6
d – 6
e - 5
a – 16
b – 7
---------
c – 6
-----
d – 6
e - 5
例子中的信息编码为：
10 00 01 10 111 110 111 00 10 00 10,.....
码长共 91位，而使用 ASCII编码表示上述信息共需要 240位
a – 00
b – 01
c – 10
d – 110
e – 111
root
0
0 1
0
1
1
1
a b c
d e
Huffman编码
cabcedeacacdeddaaabaababaaabbacdebaceada
a – 16
b – 7
c – 6
d – 6
e - 5
例子中的信息编码为：
101 0 100 101 111 110 111 0 101 0 101,.....
码长 88位，比 Shannon-Fano编码略短一些
a – 0
b – 100
c – 101
d – 110
e – 111
root
0
0
1
1
1a
b c d e
0
01
整数位编码与信息熵
cabcedeacacdeddaaabaababaaabbacdebaceada
该信息的熵经计算可知为 86.601位符号 理想位数
（熵）
S-F编码需要位数
Huffman编码需要位数
a 1.322 2 1
b 2.515 2 3
c 2.737 2 3
d 2.737 3 3
e 3.000 3 3
总计 86.601 91 88
另,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 wouldn't constantly run across
folks today who claim that "a child don't 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
算术编码例：考虑某条信息中可能出现的字符仅有 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
0.6667
0.3333
0.0000
Pc = 1/3
Pb = 1/3
Pa = 1/3
算术编码第二步,现在我们拿到第一个字符 b,让我们把目光投向 b对应的区间
0.3333-0.6667。这时由于多了字符 b,三个字符的概率分布变成：
Pa=1/4,Pb=2/4,Pc=1/4。 好，让我们按照新的概率分布比例划分
0.3333-0.6667这一区间，划分的结果可以用图形表示为：
0.6667
0.5834
0.4167
0.3333
Pc = 1/4
Pb = 2/4
Pa = 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.6667
0.6334
0.6001
0.5834
Pc = 2/5
Pb = 2/5
Pa = 1/5
例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb
算术编码第四步,现在输入下一个字符 c,三个字符的概率分布为,Pa=1/6，
Pb=2/6,Pc=3/6。 我们来划分 c的区间 0.6334-0.6667：
0.6667
0.6501
0.6390
0.6334
Pc = 3/6
Pb = 2/6
Pa = 1/6
例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb
算术编码第五步,输入最后一个字符 b,因为是最后一个字符，不用再做进一步的划分了，上一步中得到的 b的区间为 0.6390-0.6501，好，让我们在这个区间内随便选择一个容易变成二进制的数，例如 0.64，将它变成二进制 0.1010001111，去掉前面没有太多意义的 0和小数点，我们可以输出
1010001111，这就是信息被压缩后的结果，我们完成了一次最简单的算术压缩过程
0.6667
0.6501
0.6390
0.6334
Pc = 3/6
Pb = 2/6
Pa = 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阶问题：
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算法应用实例：窗口大小为 10个字符，刚编码过的 10个字符为,abcdbbccaa”,
即将编码的 10个字符为,abaeaaabaee” 。
1,我们首先发现，可以和待编码字符匹配的最长串为 ab(off=0,len=2),
ab的下一个字符为 a,我们输出三元组,(0,2,a)
2,现在窗口向后滑动 3个字符，窗口中的内容为,dbbccaaaba
3,下一个字符 e在窗口中没有匹配，我们输出三元组,(0,0,e)
4,窗口向后滑动 1个字符，其中内容变为,bbccaaabae
5,我们马上发现，要编码的 aaabae在窗口中存在 (off=4,len=6),其后的字符为 e,我们可以输出,(4,6,e)
6,这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。
7,解压缩时，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符 c输出（如果 off和 len都为 0则只输出后继字符 c)即可还原出原始数据。
LZ77算法三元组的编码方法（编码方式取决于数据的分布概率）：
1,对于第一个分量 ——窗口内的偏移，通常的经验是，偏移接近窗口尾部的情况要多于接近窗口头部的情况。但对于普通的窗口大小来说，这一差别可以忽略不计，我们用固定的位数来表示它：即编码 off需要的位数为
upper_bound(log2(MAX_WND_SIZE))
2,对于第二个分量 ——字符串长度，它的值在大多数时候不会太大，大字符串的匹配的发生概率很小。显然可以使用一种变长的编码方式来表示该长度值。我们已经知道，要输出变长的编码，该编码必须满足前缀编码的条件。其实 Huffman 编码也可以在此处使用，但却不是最好的选择。适用于此处的好的编码方案很多，我们将在稍后介绍其中两种应用非常广泛的编码：
Golomb编码和 γ 编码。
3,对三元组的最后一个分量 ——字符 c,因为其分布并无规律可循，我们只能老老实实地用 8 个二进制位对其编码。
假设对正整数 x进行 Golomb编码，选择参数 m,令
b = 2m
q = INT((x - 1)/b)
r = x - qb – 1
则 x可以被编码为两部分，第一部分是由 q个 1加 1个 0组成，第二部分为 m位二进制数，其值为 r。
值 x m = 0 m = 1 m = 2 m = 3
1 0 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 1111110 1110 0 10 10 0 110
8 11111110 1110 1 10 11 0 111
9 111111110 11110 0 110 00 10 000
Golomb编码假设对 x编码，令
q = int( log2x )
则编码的前一部分是 q个 1加一个 0，
后一部分是 q位长的二进制数，
其值等于 (x-2q )值 x 编码
1 0
2 10 0
3 10 1
4 110 00
5 110 01
6 110 10
7 110 11
8 1110 000
9 1110 001
γ 编码
LZ77算法的其他问题其他的编码方式：
1,输出匹配串时不输出后续字符
2,输出 0表示下面是一个匹配串，输出 1表示下面是一个单个字符
3,对匹配串长度加以限制如何查找匹配串：
1,限制匹配串的长度，在内存中组织二叉有序树
2,将窗口中每个长度为 3的字符串建立字典索引
3,使用 Hash表建立索引
4,使用字符树建立索引窗口滑动时内存中的索引重建问题：
1,建立环状偏移
2,以环状偏移为基础建立窗口索引内存词典：
第二步：压缩串,AD,..”在内存词典中仍无法找到匹配串，则输出二元组
(0，,A”)
并将字串,A”置入内存词典第一步：压缩串,DAD...”在内存词典中无法找到匹配串，则输出二元组
(0，,D”)
二元组中第一个元素表示词典的索引，第二个元素表示后续字符。
并将字串,D”置入内存词典内存词典：
LZW算法 LZW算法是 LZ78的改进，其基本思路是在内存中维护一个动态的字典，输出的代码是该字典的索引例：待压缩的信息为 "DAD DADA DADDY DADO..."
索引 0
词条 null
索引 0 1
词条 null,D”
第三步：压缩串,D D...”在内存词典中可以找到最大匹配串,D”,输出二元组 (1，,”)
以此对字串,D,进行了编码，然后将,D,置入内存词典内存词典：
内存词典：
第四步：压缩串,DAD...”在内存词典中可以找到最大匹配串,D”,则输出二元组 (1,“A”)
以此对字串,DA”进行了编码，然后将,DA”置入内存词典
LZW算法例：待压缩的信息为 "DAD DADA DADDY DADO..."
索引 0 1 2
词条 null,D”,A”
索引 0 1 2 3
词条 null,D”,A”,D,
LZW算法例：待压缩的信息为 "DAD DADA DADDY DADO..."
第九步后，内存词典的情况如下：
索引 0 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”)
JPEG图像压缩算法
JPEG 是有损压缩算法
JPEG 核心是“离散余弦变换 (Discrete Cosine Transform,DCT)”
JPEG 压缩算法的基本步骤为：
1、离散余弦变换
DCT Transformation
2、系数量子化
Coefficient Quantization
3、无损压缩
Lossless Compression
一维波二维波离散余弦变换 DCT
DCT操作 X,Y,Z坐标轴上的三维信号。 X,Y坐标轴是平面图像的两个维度，
Z轴表示图象的象素值。对 N * N的象素矩阵进行 DCT变换的公式如下：
1
0
1
0
]}2 )12([]2 )12([),({)()(21),( N
x
N
y N
jyC o s
N
ixC o syxP i xeljCiC
NjiD C T
1
0
1
0
]}2 )12([]2 )12([),()()({21),( N
i
N
j N
jyCo s
N
ixCo sjiD CTjCiC
NyxP i xel
离散余弦变换 (Discrete Cosine Transform,DCT)公式：
反向离散余弦变换 (Inverse Discrete Cosine Transform,IDCT)公式：
)0(1
)0(
2
1
)(
x
x
xC
其中：
但是：按照上述基本公式写出的程序实现存在一个严重的问题 ——时间复杂度太高使用矩阵运算的 DCT替代公式
实现上面的替代公式的程序代码的时间复杂度就大大降低了。进一步的改进还包括将余弦函数由浮点运算改为整数运算、改进傅立叶变换技术等。
量子化 Quantization
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算法中损失图像精度的根源，
也是产生压缩效果的源泉量子表 Quantum Table
4 7 10 13 16 19 22 25
7 10 13 16 19 22 25 28
10 13 16 19 22 25 28 31
13 16 19 22 25 28 31 34
16 19 22 25 28 31 34 37
19 22 25 28 31 34 37 40
22 25 28 31 34 37 40 43
25 28 31 34 37 40 43 46
10 19 28 37 46 55 64 73
19 28 37 46 55 64 73 82
28 37 46 55 64 73 82 91
37 46 55 64 73 82 91 100
46 55 64 73 82 91 100 109
55 64 73 82 91 100 109 118
64 73 82 91 100 109 118 127
73 82 91 100 109 118 127 136
quality = 4
quality = 9
Quantum[i][j] = 1 + ( ( 1 + i + j ) * quality )
Zig-Zag编码
(0,0)->(0,1)->(1,0)->(2,0)->……
将量子化的矩阵按 Zig-Zag顺序排列
将原始数列转换为差值数列
对差值数列进行编码，可以使用 Huffman编码、算术编码或熵编码等方法一个真实的编码和解码过程
JPEG的其他问题
将原始图像划分成多个 8 X 8 或 16 X 16 的矩阵进行处理
要求矩阵中每个点的像素值范围是 0~255
二值,16级灰度等均转换为 256级灰度图像进行处理
对非 256色的彩色图象，先转换成真彩色图像，然后使用分色法将图像分成红、蓝、绿三个 256级灰度图像，再进行处理
Independent JPEG Group
http://www.ijg.org/
通用压缩工具性能比较文件格式测试指标文本 图像 程序 游戏 音频最高压缩率 82.2% 76.0% 68.2% 53.0% 34.5%
压缩比最高 RK 1.02b5 ARHANGEL 1.40 RK 1.02b5 RK 1.02b4 RK 1.02b4
压缩速度最快 LZOP 1.00w LZOP 1.00w LZOP 1.00w LZOP 1.00w LZOP 1.00w
解压速度最快 LZOP 1.00w LZOP 1.00w LZOP 1.00w LZOP 1.00w LZOP 1.00w
综合得分最高 PPMD vE ERI32 4.4fre COOLZIP 1.01 RAR32 2.60 WAVARC 1.1
资料来源,Archive Compression Test by Jeff Gilchrist Nov,1,2000 Edition
主页地址,http://act.by.net/
谢谢，再见！
压缩技术简史
压缩技术基础
Huffman编码
算术编码
LZ77和 LZW算法
JPEG算法
通用压缩工具比较压缩技术分类通用数据压缩（均为无损压缩） 多媒体数据压缩（无损和有损压缩）
基于统计模型的压缩技术基于字典模型的压缩技术
Huffman
编码算术编码
LZ77 LZ78 LZW
图像压缩 音频和视频压缩
MPEG等二值图像
CCITT
JBIG等灰度图像
FELICS
JPEG等彩色图像
RLE编码
JPEG等矢量图像
PostScript
WMF
CAD等压缩技术的应用电报、传真 (CCITT)
通讯 (Modem/网络协议 )
存储 (压缩池 )
文件系统 (压缩扇区 )
图像 (GIF/TIFF/JPEG)
音频 (MP3)
视频 (MPEG/RM)数据库 (B+树 )
归档 (TAR/ZIP)
密码学 (消除数据的原始特征 )
全文索引 (倒排索引表 )
编译 (JAVA)
程序设计 (算法 /空间和时间效率 )
人工智能 (专家系统 /知识树 )
压缩技术起源信息压缩技术的起源 ……
比计算机的发明早几千年 ……
信息论信息存在冗余通过采用一定的模型和编码方法，
可以降低这种冗余度贝尔实验室的 Claude Shannon 和 MIT 的 R.M.Fano
几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的 Shannon-Fano 编码方法。
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 年代的早期接近极限 ——熵
80年代早期，数学家们设计出算术编码方法 (Arithmetic
Coding)
可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容
但是，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，却要消耗也许几十倍的计算时间算术编码是部分匹配预测 (Predication by Partial matching,
PPM)技术的变体以色列人
Jacob Ziv 和 Abraham Lempel
1978 年 发表论文：“通过可变比率编码的独立序列的压缩”
Compression of Individual Sequences via Variable-Rate Coding
字典编码时代,LZ77和 LZ78压缩算法
1977 年 发表论文：“顺序数据压缩的一个通用算法”
A Universal Algorithm for Sequential Data Compression
LZW算法
Terry Welch
Welch 实现了 LZ78 算法的一个变种 —— LZW算法
UNIX：使用 LZW 算法的 Compress 程序
MS-DOS,ARC 程序,以及 PKWare,PKARC 等仿制品。
1984 年 发表论文：“高性能数据压缩技术”
A Technique for High-Performance Data Compression
通用数据压缩
80年代中期以后，对 LZ77算法进行改进
Haruyasu Yoshizaki(Yoshi) 的 LHarc
Robert Jung 的 ARJ
从 PKZip到 WinZip：
通用数据压缩格式标准 —— ZIP
LZ77,LZ78,LZW 一起垄断当今的通用数据压缩领域多媒体数据压缩
国际电报电话咨询委员会 ( 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。
技术准备：什么是熵熵 ——来源于 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)=1.737 Ec=-log2(0.2)=2.322
E= 5Ea + 3Eb + 2Ec =14.855 位对比一下，我们用 ASCII编码表示该信息需要 80位技术准备：模型使用模型：得到字符或单词在信息中出现的概率静态 /半静态模型自适应模型
Claude Shannon的“聚会游戏” (party game)：
他每次向听众公布一条被他隐藏起一个字符的消息，让听众来猜下一个字符，一次猜一个，直到猜对为止。然后,Shannon 使用猜测次数来确定整个信息的熵。（人的语言经验）
静态字典模型自适应字典模型统计模型字典模型技术准备：编码通过模型，我们可以确定对某一个符号该用多少位二进制数进行编码。
现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。
前缀编码规则：任何一个符号的编码都不是另一个符号编码的前缀。
最简单的前缀编码字符 编码
A 0
B 10
C 110
D 1110
E 11110
1110010101110110111100010
D A B B D C E A A B
技术准备：压缩 =模型 +编码输入 模型 编码 输出符号 概率 代码
Shannon-Fano编码
cabcedeacacdeddaaabaababaaabbacdebaceada
a – 16
b – 7
c – 6
d – 6
e - 5
a – 16
b – 7
---------
c – 6
-----
d – 6
e - 5
例子中的信息编码为：
10 00 01 10 111 110 111 00 10 00 10,.....
码长共 91位，而使用 ASCII编码表示上述信息共需要 240位
a – 00
b – 01
c – 10
d – 110
e – 111
root
0
0 1
0
1
1
1
a b c
d e
Huffman编码
cabcedeacacdeddaaabaababaaabbacdebaceada
a – 16
b – 7
c – 6
d – 6
e - 5
例子中的信息编码为：
101 0 100 101 111 110 111 0 101 0 101,.....
码长 88位，比 Shannon-Fano编码略短一些
a – 0
b – 100
c – 101
d – 110
e – 111
root
0
0
1
1
1a
b c d e
0
01
整数位编码与信息熵
cabcedeacacdeddaaabaababaaabbacdebaceada
该信息的熵经计算可知为 86.601位符号 理想位数
（熵）
S-F编码需要位数
Huffman编码需要位数
a 1.322 2 1
b 2.515 2 3
c 2.737 2 3
d 2.737 3 3
e 3.000 3 3
总计 86.601 91 88
另,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 wouldn't constantly run across
folks today who claim that "a child don't 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
算术编码例：考虑某条信息中可能出现的字符仅有 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
0.6667
0.3333
0.0000
Pc = 1/3
Pb = 1/3
Pa = 1/3
算术编码第二步,现在我们拿到第一个字符 b,让我们把目光投向 b对应的区间
0.3333-0.6667。这时由于多了字符 b,三个字符的概率分布变成：
Pa=1/4,Pb=2/4,Pc=1/4。 好，让我们按照新的概率分布比例划分
0.3333-0.6667这一区间，划分的结果可以用图形表示为：
0.6667
0.5834
0.4167
0.3333
Pc = 1/4
Pb = 2/4
Pa = 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.6667
0.6334
0.6001
0.5834
Pc = 2/5
Pb = 2/5
Pa = 1/5
例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb
算术编码第四步,现在输入下一个字符 c,三个字符的概率分布为,Pa=1/6，
Pb=2/6,Pc=3/6。 我们来划分 c的区间 0.6334-0.6667：
0.6667
0.6501
0.6390
0.6334
Pc = 3/6
Pb = 2/6
Pa = 1/6
例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb
算术编码第五步,输入最后一个字符 b,因为是最后一个字符，不用再做进一步的划分了，上一步中得到的 b的区间为 0.6390-0.6501，好，让我们在这个区间内随便选择一个容易变成二进制的数，例如 0.64，将它变成二进制 0.1010001111，去掉前面没有太多意义的 0和小数点，我们可以输出
1010001111，这就是信息被压缩后的结果，我们完成了一次最简单的算术压缩过程
0.6667
0.6501
0.6390
0.6334
Pc = 3/6
Pb = 2/6
Pa = 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阶问题：
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算法应用实例：窗口大小为 10个字符，刚编码过的 10个字符为,abcdbbccaa”,
即将编码的 10个字符为,abaeaaabaee” 。
1,我们首先发现，可以和待编码字符匹配的最长串为 ab(off=0,len=2),
ab的下一个字符为 a,我们输出三元组,(0,2,a)
2,现在窗口向后滑动 3个字符，窗口中的内容为,dbbccaaaba
3,下一个字符 e在窗口中没有匹配，我们输出三元组,(0,0,e)
4,窗口向后滑动 1个字符，其中内容变为,bbccaaabae
5,我们马上发现，要编码的 aaabae在窗口中存在 (off=4,len=6),其后的字符为 e,我们可以输出,(4,6,e)
6,这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。
7,解压缩时，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符 c输出（如果 off和 len都为 0则只输出后继字符 c)即可还原出原始数据。
LZ77算法三元组的编码方法（编码方式取决于数据的分布概率）：
1,对于第一个分量 ——窗口内的偏移，通常的经验是，偏移接近窗口尾部的情况要多于接近窗口头部的情况。但对于普通的窗口大小来说，这一差别可以忽略不计，我们用固定的位数来表示它：即编码 off需要的位数为
upper_bound(log2(MAX_WND_SIZE))
2,对于第二个分量 ——字符串长度，它的值在大多数时候不会太大，大字符串的匹配的发生概率很小。显然可以使用一种变长的编码方式来表示该长度值。我们已经知道，要输出变长的编码，该编码必须满足前缀编码的条件。其实 Huffman 编码也可以在此处使用，但却不是最好的选择。适用于此处的好的编码方案很多，我们将在稍后介绍其中两种应用非常广泛的编码：
Golomb编码和 γ 编码。
3,对三元组的最后一个分量 ——字符 c,因为其分布并无规律可循，我们只能老老实实地用 8 个二进制位对其编码。
假设对正整数 x进行 Golomb编码，选择参数 m,令
b = 2m
q = INT((x - 1)/b)
r = x - qb – 1
则 x可以被编码为两部分，第一部分是由 q个 1加 1个 0组成，第二部分为 m位二进制数，其值为 r。
值 x m = 0 m = 1 m = 2 m = 3
1 0 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 1111110 1110 0 10 10 0 110
8 11111110 1110 1 10 11 0 111
9 111111110 11110 0 110 00 10 000
Golomb编码假设对 x编码，令
q = int( log2x )
则编码的前一部分是 q个 1加一个 0，
后一部分是 q位长的二进制数，
其值等于 (x-2q )值 x 编码
1 0
2 10 0
3 10 1
4 110 00
5 110 01
6 110 10
7 110 11
8 1110 000
9 1110 001
γ 编码
LZ77算法的其他问题其他的编码方式：
1,输出匹配串时不输出后续字符
2,输出 0表示下面是一个匹配串，输出 1表示下面是一个单个字符
3,对匹配串长度加以限制如何查找匹配串：
1,限制匹配串的长度，在内存中组织二叉有序树
2,将窗口中每个长度为 3的字符串建立字典索引
3,使用 Hash表建立索引
4,使用字符树建立索引窗口滑动时内存中的索引重建问题：
1,建立环状偏移
2,以环状偏移为基础建立窗口索引内存词典：
第二步：压缩串,AD,..”在内存词典中仍无法找到匹配串，则输出二元组
(0，,A”)
并将字串,A”置入内存词典第一步：压缩串,DAD...”在内存词典中无法找到匹配串，则输出二元组
(0，,D”)
二元组中第一个元素表示词典的索引，第二个元素表示后续字符。
并将字串,D”置入内存词典内存词典：
LZW算法 LZW算法是 LZ78的改进，其基本思路是在内存中维护一个动态的字典，输出的代码是该字典的索引例：待压缩的信息为 "DAD DADA DADDY DADO..."
索引 0
词条 null
索引 0 1
词条 null,D”
第三步：压缩串,D D...”在内存词典中可以找到最大匹配串,D”,输出二元组 (1，,”)
以此对字串,D,进行了编码，然后将,D,置入内存词典内存词典：
内存词典：
第四步：压缩串,DAD...”在内存词典中可以找到最大匹配串,D”,则输出二元组 (1,“A”)
以此对字串,DA”进行了编码，然后将,DA”置入内存词典
LZW算法例：待压缩的信息为 "DAD DADA DADDY DADO..."
索引 0 1 2
词条 null,D”,A”
索引 0 1 2 3
词条 null,D”,A”,D,
LZW算法例：待压缩的信息为 "DAD DADA DADDY DADO..."
第九步后，内存词典的情况如下：
索引 0 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”)
JPEG图像压缩算法
JPEG 是有损压缩算法
JPEG 核心是“离散余弦变换 (Discrete Cosine Transform,DCT)”
JPEG 压缩算法的基本步骤为：
1、离散余弦变换
DCT Transformation
2、系数量子化
Coefficient Quantization
3、无损压缩
Lossless Compression
一维波二维波离散余弦变换 DCT
DCT操作 X,Y,Z坐标轴上的三维信号。 X,Y坐标轴是平面图像的两个维度，
Z轴表示图象的象素值。对 N * N的象素矩阵进行 DCT变换的公式如下：
1
0
1
0
]}2 )12([]2 )12([),({)()(21),( N
x
N
y N
jyC o s
N
ixC o syxP i xeljCiC
NjiD C T
1
0
1
0
]}2 )12([]2 )12([),()()({21),( N
i
N
j N
jyCo s
N
ixCo sjiD CTjCiC
NyxP i xel
离散余弦变换 (Discrete Cosine Transform,DCT)公式：
反向离散余弦变换 (Inverse Discrete Cosine Transform,IDCT)公式：
)0(1
)0(
2
1
)(
x
x
xC
其中：
但是：按照上述基本公式写出的程序实现存在一个严重的问题 ——时间复杂度太高使用矩阵运算的 DCT替代公式
实现上面的替代公式的程序代码的时间复杂度就大大降低了。进一步的改进还包括将余弦函数由浮点运算改为整数运算、改进傅立叶变换技术等。
量子化 Quantization
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算法中损失图像精度的根源，
也是产生压缩效果的源泉量子表 Quantum Table
4 7 10 13 16 19 22 25
7 10 13 16 19 22 25 28
10 13 16 19 22 25 28 31
13 16 19 22 25 28 31 34
16 19 22 25 28 31 34 37
19 22 25 28 31 34 37 40
22 25 28 31 34 37 40 43
25 28 31 34 37 40 43 46
10 19 28 37 46 55 64 73
19 28 37 46 55 64 73 82
28 37 46 55 64 73 82 91
37 46 55 64 73 82 91 100
46 55 64 73 82 91 100 109
55 64 73 82 91 100 109 118
64 73 82 91 100 109 118 127
73 82 91 100 109 118 127 136
quality = 4
quality = 9
Quantum[i][j] = 1 + ( ( 1 + i + j ) * quality )
Zig-Zag编码
(0,0)->(0,1)->(1,0)->(2,0)->……
将量子化的矩阵按 Zig-Zag顺序排列
将原始数列转换为差值数列
对差值数列进行编码，可以使用 Huffman编码、算术编码或熵编码等方法一个真实的编码和解码过程
JPEG的其他问题
将原始图像划分成多个 8 X 8 或 16 X 16 的矩阵进行处理
要求矩阵中每个点的像素值范围是 0~255
二值,16级灰度等均转换为 256级灰度图像进行处理
对非 256色的彩色图象，先转换成真彩色图像，然后使用分色法将图像分成红、蓝、绿三个 256级灰度图像，再进行处理
Independent JPEG Group
http://www.ijg.org/
通用压缩工具性能比较文件格式测试指标文本 图像 程序 游戏 音频最高压缩率 82.2% 76.0% 68.2% 53.0% 34.5%
压缩比最高 RK 1.02b5 ARHANGEL 1.40 RK 1.02b5 RK 1.02b4 RK 1.02b4
压缩速度最快 LZOP 1.00w LZOP 1.00w LZOP 1.00w LZOP 1.00w LZOP 1.00w
解压速度最快 LZOP 1.00w LZOP 1.00w LZOP 1.00w LZOP 1.00w LZOP 1.00w
综合得分最高 PPMD vE ERI32 4.4fre COOLZIP 1.01 RAR32 2.60 WAVARC 1.1
资料来源,Archive Compression Test by Jeff Gilchrist Nov,1,2000 Edition
主页地址,http://act.by.net/
谢谢，再见！
