LZ编码

编辑:礼节网互动百科 时间:2019-11-14 09:16:29
编辑 锁定
1965年苏联数学家Kolmogolov提出利用信源序列的结构特性来编码。而两位以色列研究者J.Ziv和A.Lempel独辟蹊径,完全脱离Huffman及算术编码的设计思路,创造出了一系列比Huffman编码更有效,比算术编码更快捷的通用压缩算法。将这些算法统称为LZ系列算法。
中文名
LZ编码
时    间
1965年
提    出
Kolmogolov
性    质
更快捷的通用压缩算

目录

LZ编码算法举例

编辑
设信源符号集A={a1,a2,…,aK}共K个符号,设输入信源符号序列为u=(u1,u2,…,uL)编码是将此序列分成不同的段。分段的规范为:尽可能取最少个相连的信源符号,并保证各段都不相同。
开始时,先取一个符号作为第一段,然后继续分段。若出现与前面相同的符号时,就再取紧跟后面的一个符号一起组成一个段,使之与前面的段不同。这些分段构成字典。当字典达到一定大小后,再分段时就应查看有否与字典中的短语相同,若有重复就添加符号,以便与字典中短语不同,直至信源序列结束。
编码的码字由段号加一个符号组成。设u构成的字典中的短语共有M(u)个。若编码为二元码,段号所需码长n=「log M(u)「(注:代表上取整符号),每个符号需要的码长为「log K「。单符号的码字段号为0,非单字符的码字段号为除最后一个符号外字典中相同短语的段号。
例如,设U={a1,a2,a3,a4},信源序列为a1,a3,a2,a3,a2,a4,a3,a2,a1,a4,a3,a2,a1,共13位,字典如表所示:
表1 编码字典
段号
短语
编码
1
a1
00000
2
a3
00010
3
a2
00001
4
a3a2
01001
5
a4
00011
6
a3a2a1
10000
7
a4a3
10110
8
a2a1
01100
表2 符号编码表
a1
a2
a3
a4
00
01
10
11
表1中,8个短语使用3bit可以表示段号。每个信源符号使用2bit表示,因此,一个短语使用5bit。
LZ编码的编码方法非常简捷,译码也很简单,可以一边译码一边建立字典,只要传输字典的大小,无需传输字典本身。当编码的信源序列增长时,编码效率会提高,平均码长会逼近信源熵。

LZ编码改进

编辑
Ziv和Lempel于1977年提出了LZ77算法[Ziv & Lempel (1977)]。1978年,二人又提出了改进算法,后被命名为LZ78[Ziv & Lempel (1978)]。1984年,T.A.Welch提出了LZ78算法的一个变种,即LZW算法[ Welch (1984)]。1990年后,T.C.Bell等人又陆续提出了许多LZ系列算法的变体或改进版本[ Bell 等(1990)]。
LZ系列算法用一种巧妙的方式将字典技术应用于通用数据压缩领域,而且,可以从理论上证明LZ系列算法同样可以逼近信息熵的极限。
词条标签:
计算机术语 计算机学