XIDIAN
西安电子科技大学多媒体研究所
http://www.mti.xidian.edu.cn
多媒体数据压缩基础
多媒体系统对人类获取信息的作用
扩大了范围、
加快了速度、
增加了存储、
更易于接受。
计算机对多媒体系统的研究
通过学习媒体本质,更贴切表现视觉,听觉,
触觉等媒体
通过学习人类思维,更好模拟对环境的思维能力媒体及媒体技术多媒体表现
更贴切表现多媒体可以通过增加采样精度，加大量化位数，消除信道噪声等途径来取得，但是也带来新的问题－数据量过大
多媒体数据压缩的必要性
数据存储
传输带宽
数据压缩 就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号。
数据压缩原理
去除数据之间的相关性和冗余性采集的多媒体数据信息具有相关性，可以用数学的方法来消除数据之间的这些相关性
统计编码
变换方法
感官误差允许人们在感知各种媒体对象时，往往对一些细节信息没有很强的感知，而且存在各种隐蔽效应。
量化方法
变换方法
压缩比要大
恢复后的失真小
压缩算法要简单,速度快
硬件实现的可能性数据压缩技术实现的衡量标准无损压缩 是指使用压缩后的数据进行重构
(或者叫做还原，解压缩 )，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。
有损压缩 是指使用压缩后的数据进行重构，
重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。
数据压缩技术的分类统计编码方法（信息论）
信源被抽象为一个随机变量序列（随机过程）。
如果信源输出的随机变量取值于某一连续区间，就叫做连续信源。比如语音信号 X(t)。
如果信源输出的随机变量取值于某一离散符号集合，就叫做离散信源。比如平面图像 X(x，
y)和电报。
信源 X1,X2,X3,X4……
统计编码理论（信息量和熵）
香农信息论把一个随机事件（字符 a1） 所携带的信息量定义为：
I(a1) = log2 (1/p) = -log2 p (bit)
其中 p为事件发生（字符出现）的概率
I(a1)即随机变量 X取值为 a1时所携带的信息量，也是编码 a1所需要的位数
各个随机事件组成的序列的信息量也是一个随机变量，所以要研究它的统计特性。其数学期望为：
称 H(X)为一阶信息熵或者简称为熵 (Entropy)
m
j
m
j
jjjj ppaIpxH
1 1
l o g)()(
信源的概率分布与熵的关系
熵的大小与信源的概率模型有着密切的关系。
最大离散熵定理,当与信源对应的字符集中的各个字符为等概率分布时，熵具有极大值
log2m。 m为字符集中字符个数。
m
j
jj ppxH
1
l o g)(
平均码长与熵
如果对字符 aj的编码长度为 Lj,则 X的平均码长为：
根据前面对二进制信源的分析，有：
m
j
jj LpL
1
)(1)( XHLL XH
m
j
jjj
m
j
j ppLp
1
2
1
l o g
在 Lj ＝ － log2pj时，平均码长取得极小值 H(X)
熵编码理论
编码长度等于熵，肯定是最优编码
数据量与信息量的区别
信息量等于数据量与冗余量的差值
压缩编码就是去除冗余的过程熵编码
熵编码 包括香农－范诺编码,霍夫曼编码 和算术编码，其宗旨在于找到一种编码使得平均码长到达熵极限，基本思想就是对出现概率较大的符号取较短的码长，而对出现概率较小的符号取较大的码长。
霍夫曼编码
1952年问世，依据变字长编码理论
具体步骤：
（ 1）初始化
（ 2）合并概率最小的两个事件
（ 3）排序
（ 4）如果事件个数大于 2则重复（ 2）和（ 3）
（ 5）赋值
（ 6）编码霍夫曼编码举例符号 S1 S2 S3 S4
出现概率 1/2 1/4 1/8 1/8
等长编码 00 01 10 11
霍夫曼 0 10 110 111
H(X) = 1.75 L1=2 L2=1.75
源 S1 S2 S1 S3 S2 S1 S1 S4
等 00 01 00 10 01 00 00 11
霍 0 10 0 110 10 0 0 111
霍夫曼编码的局限性
如果源符号集的概率分布不是 2负 n次方形式，编码是否可以达到最佳？原因 …
是否具有错误保护机制？
事先无法得知概率分布怎么办？
优点是不需要同步码算术编码
基本思想：算术编码不是将单个信源符号映射成一个码字,而是把整个信源表示为实数线上的 0到 1之间的一个区间，其长度等于该序列的概率，再在该区间内选择一个代表性的小数，
转化为二进制作为实际的编码输出 。消息序列中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。
采用算术编码每个符号的平均编码长度可以为小数。
算术编码举例（一）
符号 00 01 10 11
概率 0.1 0.4 0.2 0.3
初始区间 [0,0.1) [0.1,0.5) [0.5,0.7) [0.7,1)
算术编码举例（二）
最后的子区间起始位置＝ 85/256 = 0.01010101
子区间长度 ＝ 27/256 = 0.00011011
子区间尾 ＝ 7/16 = 0.0111
取编码区间中的一个值，最后编码为,011
符号 0 1
频度 1/4 3/4
消息序列 1 0 1 1
区间起始 1/4 1/4 19/64 85/256
区间长度 3/4 3/16 9/64 27/256
信源分布：
算术编码的具体实现
因为实际只能用有限长的寄存器，这就要求将已编码的高位码字及时输出，但又不能输出过早，
以免后续运算还要调整已输出的码位。（具体算法见相关参考书）
算术编码每次递推都要做乘法，所以效率比较低。
二进制算术编码 是一种实用的编码算法，用移位代替了乘法，使效率大大提高。
自适应算术编码 可以在编码过程中根据符号出现的频繁程度动态的修改分布概率，这样可以避免在编码之前必须精确求出信源概率的难题。
自适应算术编码举例
c
b
a
1.0000
0.6667
0.3333
0.0000
0.6667
0.5834
0.4167
0.3333
0.6667
0.6334
0.6001
0.5834
0.6667
0.6501
0.6390
0.6334
c 1/3 1/4 2/5 3/6
b 1/3 2/4 2/5 2/6
a 1/3 1/4 1/5 1/6
输入序列为,bcc……….
一个简单示例熵编码的典型应用霍夫曼编码和算术编码一个字符序列
AAAAABBBBBAAAAABBBBB
求取其最佳编码为
00000111110000011111
这种方式是否能找到其最佳编码长度？
高阶熵（相关性）
以 N个象素作为组成子像块进行编码，其对应的熵为高阶熵。高阶熵与其可能达到的最大值之间的差值反映了该有记忆信源所含的冗余度，这种冗余是由于随机变量序列之间的相关性造成的。
)()|( XHYXH?
)()()|()(),( YHXHXYHXHYXH
行程编码（ RLE）
行程编码（ Run-Length Encoding）,它通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。
例如,RTTTTTTTTABBCDG被转换为,R#8TABBCDG，
其中,＃,作为转义字符，表明其后所跟的字符表示长度。
行程编码多用于黑白二值图像的压缩中。例如
00000000111111111111000001111111被转化为一系列黑串和白串长度的编码,81257。因为串长度并非等概率分布，所以一般要配合以统计编码
（ Huffman编码）。
词典编码
词典编码主要利用数据本身包含许多 重复的字符串 的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。
实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。
第一类词典编码
第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的,指针,。
第二类词典编码
第二类算法的想法是企图从输入的数据中创建一个,短语词典 (dictionary of the phrases)”，
这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的,短语,时，编码器就输出这个词典中的短语的,索引号,,而不是短语本身。
LZ77算法
LZ77 算法在某种意义上又可以称为,滑动窗口压缩,,该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位臵和长度。
使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；
LZ77编码的基本流程
1、从当前压缩位臵开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。
2、输出三元符号组 ( off,len,c )。 其中 off
为窗口中匹配字符串相对窗口右边界的偏移，
len 为可匹配的长度,c 为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动 len + 1
个字符，继续步骤 1。
3、输出三元符号组 ( 0,0,c )。 其中 c 为下一个字符。然后将窗口向后滑动 1 个字符，继续步骤 1。
LZ77算法
LZ77编码举例
A A B C B B A B C A
步骤 位置 匹配串 输出
1 1 －－ 0,0,A
2 2 A 1,1,B
3 4 －－ 0,0,C
4 5 B 2,1,B
5 7 AB 5,2,C
LZSS算法
LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面,一是空指针,
二是 编码器可能输出额外的字符,这种字符是指可能包含在下一个匹配串中的字符。
LZSS算法的思想是如果匹配串的长度比指针本身的长度长就输出指针（匹配串长度大于等于
MIN_LENGTH）,否则就输出真实字符。另外要输出额外的标志位区分是指针还是字符。
LZSS编码的基本流程
1、从当前压缩位臵开始，考察未编码的字符，并试图在滑动窗口中找出最长的匹配字符串，如果匹配串长度 len大于等于最小匹配串长度
（ len >= MIN_LENGTH）,则进行步骤 2，否则进行步骤 3。
2、输出指针二元组 ( off,len)。 其中 off 为窗口中匹配字符串相对窗口边界的偏移,len
为匹配串的长度，然后将窗口向后滑动 len 个字符，继续步骤 1。
3、输出当前字符 c,然后将窗口向后滑动 1 个字符，继续步骤 1。
LZSS编码举例位置 1 2 3 4 5 6 7 8 9 10 11
字符 A A B B C B B A A B C
步骤 位置 匹配串 输出
1 1 －－ A
2 2 A A
3 3 －－ B
4 4 B B
5 5 －－ C
6 6 BB （ 3,2）
7 8 AAB （ 7,3）
8 11 C C
输入数据流：
编码过程
MIN_LEN
=2
LZSS算法
在相同的计算机环境下,LZSS算法比 LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了 LZSS的思想。例如，
PKZip,GZip,ARJ,LHArc和 ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。
LZSS同样可以和熵编码联合使用，例如 ARJ就与霍夫曼编码联用，而 PKZip则与 Shannon-Fano联用，它的后续版本也采用霍夫曼编码。
LZ78算法
LZ78的编码思想是不断地从字符流中提取新的字符串 (String),通俗地理解为新,词条,,然后用,代号,也就是码字 (Code word)表示这个
,词条,。这样一来，对字符流的编码就变成了用码字 (Code word)去替换字符流 (Char stream)，
生成码字流 (Code stream),从而达到压缩数据的目的。
LZ78编码器的输出是码字 -字符 (W,C)对，每次输出一对到码字流中，与码字 W相对应的字符串
(String)用字符 C进行扩展生成新的字符串
(String),然后添加到词典中。
LZ78编码算法步骤 1,将词典和当前前缀 P都初始化为空。
步骤 2,当前字符 C:=字符流中的下一个字符。
步骤 3,判断 P＋ C是否在词典中
（ 1）如果,是,,则用 C扩展 P,即让 P:=P＋ C，
返回到步骤 2。
（ 2）如果,否,,则输出与当前前缀 P相对应的码字 W和当前字符 C,即（ W,C）；
将 P＋ C添加到词典中；
令 P:=空值，并返回到步骤 2
LZ78编码举例位置 1 2 3 4 5 6 7 8 9
字符 A B B C B C A B A
步骤 位置 词典 输出
1 1 A (0,A)
2 2 B (0,B)
3 3 BC (2,C)
4 5 BCA (3,A)
5 8 BA (2,A)
输入数据流：
编码过程：
LZW算法
J.Ziv和 A.Lempel在 1978年首次发表了介绍第二类词典编码算法的文章。在此基础上,Terry A.Welch
在 1984年发表了改进这种编码算法的文章，因此把这种编码方法称为 LZW(Lempel-Ziv Walch)压缩编码。
在编码原理上,LZW与 LZ78相比有如下差别：
LZW只输出代表词典中的字符串 (String)的码字
(code word)。 这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符 。 即在编码匹配时，至少可以在词典中找到长度为 1的匹配串。
LZW编码是围绕称为词典的转换表来完成的。
LZW算法的词典
LZW编码器 (软件编码器或硬件编码器 )就是通过管理这个词典完成输入与输出之间的转换。
LZW编码器的输入是字符流 (Char stream),字符流可以是用 8位 ASCII字符组成的字符串，而输出是用
n位 (例如 12位 )表示的码字流 (Code stream),码字代表单个字符或多个字符组成的字符串 (String)。
LZW编码算法步骤 1,将词典初始化为包含所有可能的单字符，
当前前缀 P初始化为空。
步骤 2,当前字符 C:=字符流中的下一个字符。
步骤 3,判断 P＋ C是否在词典中
（ 1）如果,是,,则用 C扩展 P,即让 P:=P＋ C，
返回到步骤 2。
（ 2）如果,否,,则输出与当前前缀 P相对应的码字 W；
将 P＋ C添加到词典中；
令 P:=C，并返回到步骤 2
LZW编码举例位置 1 2 3 4 5 6 7 8 9
字符 A B B A B A B A C
步骤 位置 码字 词典 输出
1 A
2 B
3 C
1 1 4 AB 1
2 2 5 BB 2
3 3 6 BA 2
4 4 7 ABA 4
5 6 8 ABAC 7
输入数据流：
编码过程：
LZW算法
LZW算法得到普遍采用，它的速度比使用 LZ78
算法的速度快，因为它不需要执行那么多的缀 -符串比较操作。对 LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀 -符串。在 GIF图像格式和 UNIX的压缩程序中已经采用了这些改进措施之后的 LZW算法。
LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司 — Unisys(优利系统公司 )，除了商业软件生产公司之外，可以免费使用 LZW算法。
小结
理解无损压缩和常用无损压缩算法。
信息论方面的知识给出了数据压缩的理论基础。
熵是一种具有统计特性的平均信息量。
算术编码具有比哈夫曼编码更好的压缩率
几种典型的无损压缩算法在多媒体数据压缩中都有应用。
高阶熵编码应用
RLE（行程编码）和词典编码一个例子
1111222244448888
行程编码为
1＃ 4 2#4 4#4 8#4
是否消除了所有的数据相关性？
西安电子科技大学多媒体研究所
http://www.mti.xidian.edu.cn
多媒体数据压缩基础
多媒体系统对人类获取信息的作用
扩大了范围、
加快了速度、
增加了存储、
更易于接受。
计算机对多媒体系统的研究
通过学习媒体本质,更贴切表现视觉,听觉,
触觉等媒体
通过学习人类思维,更好模拟对环境的思维能力媒体及媒体技术多媒体表现
更贴切表现多媒体可以通过增加采样精度，加大量化位数，消除信道噪声等途径来取得，但是也带来新的问题－数据量过大
多媒体数据压缩的必要性
数据存储
传输带宽
数据压缩 就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号。
数据压缩原理
去除数据之间的相关性和冗余性采集的多媒体数据信息具有相关性，可以用数学的方法来消除数据之间的这些相关性
统计编码
变换方法
感官误差允许人们在感知各种媒体对象时，往往对一些细节信息没有很强的感知，而且存在各种隐蔽效应。
量化方法
变换方法
压缩比要大
恢复后的失真小
压缩算法要简单,速度快
硬件实现的可能性数据压缩技术实现的衡量标准无损压缩 是指使用压缩后的数据进行重构
(或者叫做还原，解压缩 )，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。
有损压缩 是指使用压缩后的数据进行重构，
重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。
数据压缩技术的分类统计编码方法（信息论）
信源被抽象为一个随机变量序列（随机过程）。
如果信源输出的随机变量取值于某一连续区间，就叫做连续信源。比如语音信号 X(t)。
如果信源输出的随机变量取值于某一离散符号集合，就叫做离散信源。比如平面图像 X(x，
y)和电报。
信源 X1,X2,X3,X4……
统计编码理论（信息量和熵）
香农信息论把一个随机事件（字符 a1） 所携带的信息量定义为：
I(a1) = log2 (1/p) = -log2 p (bit)
其中 p为事件发生（字符出现）的概率
I(a1)即随机变量 X取值为 a1时所携带的信息量，也是编码 a1所需要的位数
各个随机事件组成的序列的信息量也是一个随机变量，所以要研究它的统计特性。其数学期望为：
称 H(X)为一阶信息熵或者简称为熵 (Entropy)
m
j
m
j
jjjj ppaIpxH
1 1
l o g)()(
信源的概率分布与熵的关系
熵的大小与信源的概率模型有着密切的关系。
最大离散熵定理,当与信源对应的字符集中的各个字符为等概率分布时，熵具有极大值
log2m。 m为字符集中字符个数。
m
j
jj ppxH
1
l o g)(
平均码长与熵
如果对字符 aj的编码长度为 Lj,则 X的平均码长为：
根据前面对二进制信源的分析，有：
m
j
jj LpL
1
)(1)( XHLL XH
m
j
jjj
m
j
j ppLp
1
2
1
l o g
在 Lj ＝ － log2pj时，平均码长取得极小值 H(X)
熵编码理论
编码长度等于熵，肯定是最优编码
数据量与信息量的区别
信息量等于数据量与冗余量的差值
压缩编码就是去除冗余的过程熵编码
熵编码 包括香农－范诺编码,霍夫曼编码 和算术编码，其宗旨在于找到一种编码使得平均码长到达熵极限，基本思想就是对出现概率较大的符号取较短的码长，而对出现概率较小的符号取较大的码长。
霍夫曼编码
1952年问世，依据变字长编码理论
具体步骤：
（ 1）初始化
（ 2）合并概率最小的两个事件
（ 3）排序
（ 4）如果事件个数大于 2则重复（ 2）和（ 3）
（ 5）赋值
（ 6）编码霍夫曼编码举例符号 S1 S2 S3 S4
出现概率 1/2 1/4 1/8 1/8
等长编码 00 01 10 11
霍夫曼 0 10 110 111
H(X) = 1.75 L1=2 L2=1.75
源 S1 S2 S1 S3 S2 S1 S1 S4
等 00 01 00 10 01 00 00 11
霍 0 10 0 110 10 0 0 111
霍夫曼编码的局限性
如果源符号集的概率分布不是 2负 n次方形式，编码是否可以达到最佳？原因 …
是否具有错误保护机制？
事先无法得知概率分布怎么办？
优点是不需要同步码算术编码
基本思想：算术编码不是将单个信源符号映射成一个码字,而是把整个信源表示为实数线上的 0到 1之间的一个区间，其长度等于该序列的概率，再在该区间内选择一个代表性的小数，
转化为二进制作为实际的编码输出 。消息序列中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。
采用算术编码每个符号的平均编码长度可以为小数。
算术编码举例（一）
符号 00 01 10 11
概率 0.1 0.4 0.2 0.3
初始区间 [0,0.1) [0.1,0.5) [0.5,0.7) [0.7,1)
算术编码举例（二）
最后的子区间起始位置＝ 85/256 = 0.01010101
子区间长度 ＝ 27/256 = 0.00011011
子区间尾 ＝ 7/16 = 0.0111
取编码区间中的一个值，最后编码为,011
符号 0 1
频度 1/4 3/4
消息序列 1 0 1 1
区间起始 1/4 1/4 19/64 85/256
区间长度 3/4 3/16 9/64 27/256
信源分布：
算术编码的具体实现
因为实际只能用有限长的寄存器，这就要求将已编码的高位码字及时输出，但又不能输出过早，
以免后续运算还要调整已输出的码位。（具体算法见相关参考书）
算术编码每次递推都要做乘法，所以效率比较低。
二进制算术编码 是一种实用的编码算法，用移位代替了乘法，使效率大大提高。
自适应算术编码 可以在编码过程中根据符号出现的频繁程度动态的修改分布概率，这样可以避免在编码之前必须精确求出信源概率的难题。
自适应算术编码举例
c
b
a
1.0000
0.6667
0.3333
0.0000
0.6667
0.5834
0.4167
0.3333
0.6667
0.6334
0.6001
0.5834
0.6667
0.6501
0.6390
0.6334
c 1/3 1/4 2/5 3/6
b 1/3 2/4 2/5 2/6
a 1/3 1/4 1/5 1/6
输入序列为,bcc……….
一个简单示例熵编码的典型应用霍夫曼编码和算术编码一个字符序列
AAAAABBBBBAAAAABBBBB
求取其最佳编码为
00000111110000011111
这种方式是否能找到其最佳编码长度？
高阶熵（相关性）
以 N个象素作为组成子像块进行编码，其对应的熵为高阶熵。高阶熵与其可能达到的最大值之间的差值反映了该有记忆信源所含的冗余度，这种冗余是由于随机变量序列之间的相关性造成的。
)()|( XHYXH?
)()()|()(),( YHXHXYHXHYXH
行程编码（ RLE）
行程编码（ Run-Length Encoding）,它通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。
例如,RTTTTTTTTABBCDG被转换为,R#8TABBCDG，
其中,＃,作为转义字符，表明其后所跟的字符表示长度。
行程编码多用于黑白二值图像的压缩中。例如
00000000111111111111000001111111被转化为一系列黑串和白串长度的编码,81257。因为串长度并非等概率分布，所以一般要配合以统计编码
（ Huffman编码）。
词典编码
词典编码主要利用数据本身包含许多 重复的字符串 的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。
实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。
第一类词典编码
第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的,指针,。
第二类词典编码
第二类算法的想法是企图从输入的数据中创建一个,短语词典 (dictionary of the phrases)”，
这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的,短语,时，编码器就输出这个词典中的短语的,索引号,,而不是短语本身。
LZ77算法
LZ77 算法在某种意义上又可以称为,滑动窗口压缩,,该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位臵和长度。
使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；
LZ77编码的基本流程
1、从当前压缩位臵开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。
2、输出三元符号组 ( off,len,c )。 其中 off
为窗口中匹配字符串相对窗口右边界的偏移，
len 为可匹配的长度,c 为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动 len + 1
个字符，继续步骤 1。
3、输出三元符号组 ( 0,0,c )。 其中 c 为下一个字符。然后将窗口向后滑动 1 个字符，继续步骤 1。
LZ77算法
LZ77编码举例
A A B C B B A B C A
步骤 位置 匹配串 输出
1 1 －－ 0,0,A
2 2 A 1,1,B
3 4 －－ 0,0,C
4 5 B 2,1,B
5 7 AB 5,2,C
LZSS算法
LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面,一是空指针,
二是 编码器可能输出额外的字符,这种字符是指可能包含在下一个匹配串中的字符。
LZSS算法的思想是如果匹配串的长度比指针本身的长度长就输出指针（匹配串长度大于等于
MIN_LENGTH）,否则就输出真实字符。另外要输出额外的标志位区分是指针还是字符。
LZSS编码的基本流程
1、从当前压缩位臵开始，考察未编码的字符，并试图在滑动窗口中找出最长的匹配字符串，如果匹配串长度 len大于等于最小匹配串长度
（ len >= MIN_LENGTH）,则进行步骤 2，否则进行步骤 3。
2、输出指针二元组 ( off,len)。 其中 off 为窗口中匹配字符串相对窗口边界的偏移,len
为匹配串的长度，然后将窗口向后滑动 len 个字符，继续步骤 1。
3、输出当前字符 c,然后将窗口向后滑动 1 个字符，继续步骤 1。
LZSS编码举例位置 1 2 3 4 5 6 7 8 9 10 11
字符 A A B B C B B A A B C
步骤 位置 匹配串 输出
1 1 －－ A
2 2 A A
3 3 －－ B
4 4 B B
5 5 －－ C
6 6 BB （ 3,2）
7 8 AAB （ 7,3）
8 11 C C
输入数据流：
编码过程
MIN_LEN
=2
LZSS算法
在相同的计算机环境下,LZSS算法比 LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了 LZSS的思想。例如，
PKZip,GZip,ARJ,LHArc和 ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。
LZSS同样可以和熵编码联合使用，例如 ARJ就与霍夫曼编码联用，而 PKZip则与 Shannon-Fano联用，它的后续版本也采用霍夫曼编码。
LZ78算法
LZ78的编码思想是不断地从字符流中提取新的字符串 (String),通俗地理解为新,词条,,然后用,代号,也就是码字 (Code word)表示这个
,词条,。这样一来，对字符流的编码就变成了用码字 (Code word)去替换字符流 (Char stream)，
生成码字流 (Code stream),从而达到压缩数据的目的。
LZ78编码器的输出是码字 -字符 (W,C)对，每次输出一对到码字流中，与码字 W相对应的字符串
(String)用字符 C进行扩展生成新的字符串
(String),然后添加到词典中。
LZ78编码算法步骤 1,将词典和当前前缀 P都初始化为空。
步骤 2,当前字符 C:=字符流中的下一个字符。
步骤 3,判断 P＋ C是否在词典中
（ 1）如果,是,,则用 C扩展 P,即让 P:=P＋ C，
返回到步骤 2。
（ 2）如果,否,,则输出与当前前缀 P相对应的码字 W和当前字符 C,即（ W,C）；
将 P＋ C添加到词典中；
令 P:=空值，并返回到步骤 2
LZ78编码举例位置 1 2 3 4 5 6 7 8 9
字符 A B B C B C A B A
步骤 位置 词典 输出
1 1 A (0,A)
2 2 B (0,B)
3 3 BC (2,C)
4 5 BCA (3,A)
5 8 BA (2,A)
输入数据流：
编码过程：
LZW算法
J.Ziv和 A.Lempel在 1978年首次发表了介绍第二类词典编码算法的文章。在此基础上,Terry A.Welch
在 1984年发表了改进这种编码算法的文章，因此把这种编码方法称为 LZW(Lempel-Ziv Walch)压缩编码。
在编码原理上,LZW与 LZ78相比有如下差别：
LZW只输出代表词典中的字符串 (String)的码字
(code word)。 这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符 。 即在编码匹配时，至少可以在词典中找到长度为 1的匹配串。
LZW编码是围绕称为词典的转换表来完成的。
LZW算法的词典
LZW编码器 (软件编码器或硬件编码器 )就是通过管理这个词典完成输入与输出之间的转换。
LZW编码器的输入是字符流 (Char stream),字符流可以是用 8位 ASCII字符组成的字符串，而输出是用
n位 (例如 12位 )表示的码字流 (Code stream),码字代表单个字符或多个字符组成的字符串 (String)。
LZW编码算法步骤 1,将词典初始化为包含所有可能的单字符，
当前前缀 P初始化为空。
步骤 2,当前字符 C:=字符流中的下一个字符。
步骤 3,判断 P＋ C是否在词典中
（ 1）如果,是,,则用 C扩展 P,即让 P:=P＋ C，
返回到步骤 2。
（ 2）如果,否,,则输出与当前前缀 P相对应的码字 W；
将 P＋ C添加到词典中；
令 P:=C，并返回到步骤 2
LZW编码举例位置 1 2 3 4 5 6 7 8 9
字符 A B B A B A B A C
步骤 位置 码字 词典 输出
1 A
2 B
3 C
1 1 4 AB 1
2 2 5 BB 2
3 3 6 BA 2
4 4 7 ABA 4
5 6 8 ABAC 7
输入数据流：
编码过程：
LZW算法
LZW算法得到普遍采用，它的速度比使用 LZ78
算法的速度快，因为它不需要执行那么多的缀 -符串比较操作。对 LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀 -符串。在 GIF图像格式和 UNIX的压缩程序中已经采用了这些改进措施之后的 LZW算法。
LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司 — Unisys(优利系统公司 )，除了商业软件生产公司之外，可以免费使用 LZW算法。
小结
理解无损压缩和常用无损压缩算法。
信息论方面的知识给出了数据压缩的理论基础。
熵是一种具有统计特性的平均信息量。
算术编码具有比哈夫曼编码更好的压缩率
几种典型的无损压缩算法在多媒体数据压缩中都有应用。
高阶熵编码应用
RLE（行程编码）和词典编码一个例子
1111222244448888
行程编码为
1＃ 4 2#4 4#4 8#4
是否消除了所有的数据相关性？
