四川大学计算机学院 多媒体技术 4

语义依赖（semantic-dependent）的DC方法应用背景： 对于“局部冗余”的特殊类型。 主要应用于图象表达、处理。原因：数字化的image有大量的“局部冗余”占空间大 （一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。）语义依赖（semantic-dependent）的DC方法典型：行程编码（run-lengthencoding:RLE）差异映射(differencemapping)词典编码(DictionaryEncoding)语义依赖（semantic-dependent）的DC方法差异映射：算法思想：图象表示为相邻像素在亮度/颜色上的差异阵列，而不是像素本身的亮度/颜色值例[Laeseretal.1986]8bits/pixel(256brightness)

3bits/pixel语义依赖（semantic-dependent）的DC方法词典编码词典：全部词语（words）常用词语+词语结束符号编码方法：指向词典的指针表指向词典的指针表（常用词语）+编码（不常用词语）语义依赖（semantic-dependent）的数据压缩方法缺点：实用性有限可以用其他更一般的编码方法获得相同效果如huffman编码、Lempel-Ziv编码RLE编码行程编码(RLE）算法:x1,x2,……

xn

---->(

c1,l1),(

c2,l2),……

(

ck,lk

)

ci:亮度/颜色li:第i行程（相同亮度/颜色的像素的序列）的长度不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值，以及具有相同颜色的象素数目就可以；或者存储一个象素的颜色值，以及具有相同颜色值的行数。具有相同颜色并且是连续的象素数目称为行程长度。RLE编码例：代码字为：（0，8),（1，3),（8，50),（1，4),(0，8）RLE编码RLE所能获得的压缩比——主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。RLE是无损压缩技术。RLE编码应用：尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。（对颜色丰富的自然图像不能单纯使用RLE一种编码方法，需要和其他的压缩编码技术联合应用。）商业数据处理（如连续多个0，空格）分解与编码源信息代码（长度）：block->blockblock->variablevariable->blockvariable->variable例：“aa

bbb

cccc

ddddd

eeeeee

fffffffgggggggg”

block->block(120)Sourcemassage codeworda 000b 001c 010d 011e 100f 101g 110space 111例：“aa

bbb

cccc

ddddd

eeeeee

fffffffgggggggg”

variable->variable(30)

Sourcemassage codewordaa 0bbb 1ccccc 10ddddd 11eeeeeee 100fffffff 101gggggggg 110space 111分解与编码“定义字”与“自由分解”方法定义字（defined-word）方式源信息分解的长度在编码调用之前已确定自由分解（free-parse）方式编码算法本身决定源信息分解的长度（变长）分解与编码典型算法定义字方式的：Shannon-FanocodingHuffmancodingUniversalcodes(通用码)Arithmeticcoding(算术编码)自由分解方式的：Lempel-ZivcodesAlgorithmBSTWLempel-Ziv编码variable->block自由分解算法：一规则：从一个有限字母表分解出不超过规定长度的子串或词；一编码方法：将子串顺序地映射成固定长度、可辨认的代码字。Lempel-Ziv编码策略：选出几乎必定出现的字串。使得概率大的字符，组成较长串；概率小的字符，组成较短串。

对有效利用冗余，因为符号的频繁出现字母重复高使用模式Lempel-Ziv编码不断增长长度的语法分析策略：在编码的每一步，分解出剩余源信息集合中与现有表的某项∞匹配的最长前缀，追加上源信息集合中该前缀的后一字符c,将∞c加入编码表中，编为（i,c):i——现有表项的代码字；c——追加的字符Lempel-Ziv编码例：“010100010”分解：{0，1，01，00，010}编码：{(0,0),(0,1),(1,1),(1,0),(3,0)}例：“aa

bbb

cccc

ddddd

eeeeee

fffffffgggggggg”

（3-bits:a~g,

,5-bits:tableindexes,码长=173）a 1 e 121

2 12e 13b 3 13e 143b 4 5f 15

5 f 16c 6 16f 17 6c 7 17f 186

8 g 19d 9 19g 209d 10 20g 2110

11 20 22Lempel-Ziv编码评价：简单，且贪心（每步找最长识别串）渐近最优Hash查找实际应用：UNIX资源压缩，50~60%的压缩率

LZ78算法

例：输入为“ABBCBCABA”步骤位置词典输出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)

LZW算法

例：输入为“ABBABABAC”步骤位置(序号)词典输出(1)A(2)B(3)C11(4)AB122(5)BB233(6)BA244(7)ABA456(8)ABAC763

LZ77算法

例：输入为“AABCBBABC”步骤位置匹配串字符输出11A(0,0)A22AB(1,1)