饮食文化与中国传统节日.ppt

1
行程编码适合于对二值图像的编码,如果
图像是由很多块颜色或灰度相同的大面积区域
组成的,采用行程编码可以达到很大的压缩比。
通常,为了达到比较好的压缩效果,一般
不单独使用行程编码,而是和其他编码方法结合
使用。如:在JPEG中,就综合使用了行程编码以及哈夫曼编码。
2
1977年,以色列人Lempel和Ziv共同提出了查找冗余字符
和用较短的符号标记替代冗余字符的概念,简称LZ压缩技术。
1985年,美国人Welch将LZ压缩技术从概念发展到实用阶段,简称LZW压缩技术。广泛用于图象压缩领域。
LZW(Lempel-Ziv & Welch)编码又称字串表编码,属于一种无损编码,LZW编码与行程编码类似,也是对字符串进行编码从而实现压缩,但它在编码的同时还生成了特定字符串以及与之对应的索引字符串表。
LZW编码
3
压缩的数据并与一个字典库(库开始是空的)中
字符串插入字典中。
字符串数据在字典库中的位置索引,
的字符串对比,
LZW压缩使用字典库查找方案。
它读入待
如有匹配的字符串,则输出该
否则将该
4
步骤1:将词典初始化为包含所有可能的单字
步骤2:当前字符C:=字符流中的下一个字符。
字符,当前前缀P初始化为空。
LZW编码算法
5
令P:=C,现在的P仅包含一个字符C
步骤3:判断P+C是否在词典中
(1)如果“是”,则用C扩展P,即让P:=P+C
(2)如果“否”,则
输出与当前前缀P相对应的码字;
将P+C添加到词典中;
6
步骤4:判断码字流中是否还有码字要译
(1)如果“是”,就返回到步骤2;
(2)如果“否”
把代表当前前缀P的码字输出到码字流;
结束。
7
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
6
3
输入数据流:
编码过程:
8
初始化字符串表
字符串
索引
a
0 H
b
1 H
c
2 H
d
3 H
LZW_CLEAR
4 H
LZW_EOI
5 H
LZW编码实例 aabcabbbbd
9
输入数据S2
S1+S2
输出结果
S1
生成的新字符串及索引
NULL
a
a
b
c
a
b
b
b
b
d
NULL
NULL
a
a
a
aa
4H
0H
0H
ab
bc
ca
ab
abb
bb
bb
bbd
1H
2H
7H
1H
BH
3H
5H
b
c
a
ab
b
b
bb
d
aa <6H>
ab <7H>
bc <8H>
ca <9H>
abb <AH>
bb <BH>
bbd <CH>
S1为NULL,故输出结果为空
S1+S2在字符表中,S1=S1+S2
aa不存在,故输出S1=“a”的索引0H
S1+S2不在字符表中,S1=S2=“a”
ab不存在,故输出S1=“a”的索引0H
S1+S2不在字符表中,S1=S2=“b”
S1+S2结果已存在,故输出结果为空
S1+S2在字符表中,S1=S1+S2
此时已无输入
输出S1的索引3H
输出LZW_EOI标志的索引
10