多媒体技术基础(第3版) 第2章数据无损压缩 张奇 复旦大学 计算机科学技术学院 2015年4月.

Presentation on theme: "多媒体技术基础(第3版) 第2章数据无损压缩 张奇 复旦大学 计算机科学技术学院 2015年4月."— Presentation transcript:

1 多媒体技术基础(第3版) 第2章数据无损压缩 张奇 复旦大学 计算机科学技术学院 2015年4月

2 第2章 数据无损压缩目录 2.1 数据的冗余 2.2 统计编码 2.3 RLE编码 2.4 词典编码 参考文献和站点 2.1.1 冗余概念
2.1.2 决策量 2.1.3 信息量 2.1.4 熵 2.1.5 数据冗余量 2.2 统计编码 2.2.1 香农-范诺编码 2.2.2 霍夫曼编码 2.2.3 算术编码 2.3 RLE编码 2.4 词典编码 2.4.1 词典编码的思想 2.4.2 LZ77算法 2.4.3 LZSS算法 2.4.4 LZ78算法 2.4.5 LZW算法 参考文献和站点 2018年9月22日 第2章 数据无损压缩

3 2.0 数据无损压缩概述 数据可被压缩的依据 三种多媒体数据类型 数据本身存在冗余 听觉系统的敏感度有限 视觉系统的敏感度有限
文字 (text)数据——无损压缩 根据数据本身的冗余(Based on data redundancy) 声音(audio)数据——有损压缩 根据人的听觉系统特性( Based on human hearing system) 图像(image)/视像(video) 数据——有损压缩 根据人的视觉系统特性(Based on human visual system) 2018年9月22日 第2章 数据无损压缩

4 2.0 数据无损压缩概述(续1) 数据无损压缩的理论——信息论(information theory) 数据无损压缩的方法
1948年创建的数学理论的一个分支学科，研究信息的编码、传输和存储 该术语源于Claude Shannon (香农)发表的“A Mathematical Theory of Communication”论文题目，提议用二进制数据对信息进行编码 最初只应用于通信工程领域，后来扩展到包括计算在内的其他多个领域，如信息的存储、信息的检索等。在通信方面，主要研究数据量、传输速率、信道容量、传输正确率等问题。 数据无损压缩的方法 霍夫曼编码(Huffman coding ) 算术编码(arithmetic coding) 行程长度编码(run-length coding) 词典编码(dictionary coding) …… 2018年9月22日 第2章 数据无损压缩

5 2.0 数据无损压缩概述(续2) 信息论之父介绍 The Father of Information Theory—— Claude Elwood Shannon Born: 30 April 1916 in Gaylord, Michigan, USA Died: 24 Feb 2001 in Medford, Massachusetts, USA 2018年9月22日 第2章 数据无损压缩

6 2.0 数据无损压缩概述(续3) Claude Shannon
——The founding father of electronic communications age；American mathematical engineer In 1936~1940, MIT: Master's thesis, A symbolic analysis of relay and switching circuits Doctoral thesis: on theoretical genetics In 1948: A mathematical theory of communication, landmark, climax (An important feature of Shannon's theory: concept of entropy ) 2018年9月22日 第2章 数据无损压缩

7 2.1 数据的冗余 冗余概念 人为冗余 视听冗余 数据冗余 在信息处理系统中，使用两台计算机做同样的工作是提高系统可靠性的一种措施
在数据存储和传输中，为了检测和恢复在数据存储或数据传输过程中出现的错误，根据使用的算法的要求，在数据存储或数据传输之前把额外的数据添加到用户数据中，这个额外的数据就是冗余数据 视听冗余 由于人的视觉系统和听觉系统的局限性，在图像数据和声音数据中，有些数据确实是多余的，使用算法将其去掉后并不会丢失实质性的信息或含义，对理解数据表达的信息几乎没有影响 数据冗余 不考虑数据来源时，单纯数据集中也可能存在多余的数据，去掉这些多余数据并不会丢失任何信息，这种冗余称为数据冗余，而且还可定量表达 2018年9月22日 第2章 数据无损压缩

8 2.1 数据的冗余(续1) 决策量(decision content) 在有限数目的互斥事件集合中，决策量是事件数的对数值 在数学上表示为
H0=log(n) 其中，n是事件数 决策量的单位由对数的底数决定 Sh (Shannon): 用于以2为底的对数 Nat (natural unit): 用于以e为底的对数 Hart (hartley)：用于以10为底的对数 2018年9月22日 第2章 数据无损压缩

9 2.1 数据的冗余(续2) 信息量(information content) 具有确定概率事件的信息的定量度量 在数学上定义为
其中， 是事件出现的概率 举例：假设X={a,b,c}是由3个事件构成的集合，p(a)=0.5，p(b)=0.25，p(b)=0.25分别是事件a, b和c出现的概率，这些事件的信息量分别为， I(a)=log2(1/0.50)=1 sh I(b)=log2(1/0.25)=2 sh I(c)=log2(1/0.25)=2 sh 一个等概率事件的集合，每个事件的信息量等于该集合的决策量 2018年9月22日 第2章 数据无损压缩

10 2.1 数据的冗余(续3) 熵(entropy) 按照香农(Shannon)的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量(mean information content) 用数学表示为 2018年9月22日 第2章 数据无损压缩

11 2.1 数据的冗余(续4) 数据的冗余量 2018年9月22日 第2章 数据无损压缩

12 2.2 统计编码 统计编码 编码方法 编码特性 给已知统计信息的符号分配代码的数据无损压缩方法 香农-范诺编码 霍夫曼编码 算术编码
香农-范诺编码和霍夫曼编码的原理相同，都是根据符号集中各个符号出现的频繁程度来编码，出现次数越多的符号，给它分配的代码位数越少 算术编码使用0和1之间的实数的间隔长度代表概率大小，概率越大间隔越长，编码效率可接近于熵 2018年9月22日 第2章 数据无损压缩

13 2.2.1 统计编码——香农-范诺编码 香农-范诺编码(Shannon–Fano coding)
在香农的源编码理论中，熵的大小表示非冗余的不可压缩的信息量 在计算熵时，如果对数的底数用2，熵的单位就用“香农(Sh)”，也称“位(bit)” 。“位”是1948年Shannon首次使用的术语。例如 最早阐述和实现“从上到下”的熵编码方法的人是Shannon(1948年)和Fano(1949年)，因此称为香农-范诺(Shannon- Fano)编码法 2018年9月22日 第2章 数据无损压缩

14 2.2.1 香农-范诺编码 香农-范诺编码举例 有一幅40个像素组成的灰度图像，灰度共有5级，分别用符号A，B，C，D和E表示。40个像素中出现灰度A的像素数有15个，出现灰度B的像素数有7个，出现灰度C的像素数有7个，其余情况见表2-1 (1) 计算该图像可能获得的压缩比的理论值 (2) 对5个符号进行编码 (3) 计算该图像可能获得的压缩比的实际值 表2-1 符号在图像中出现的数目 符号 A B C D E 出现的次数 15 7 6 5 出现的概率 15/40 7/40 6/40 5/40 2018年9月22日 第2章 数据无损压缩

15 2.2.1 香农-范诺编码(续1) (1) 压缩比的理论值 按照常规的编码方法，表示5个符号最少需要3位，如用000表示A，001表示B，…，100表示E，其余3个代码 (101，110，111)不用。这就意味每个像素用3位，编码这幅图像总共需要120位。按照香农理论，这幅图像的熵为 这个数值表明，每个符号不需要用3位构成的代码表示，而用2.196位就可以，因此40个像素只需用87.84位就可以，因此在理论上，这幅图像的的压缩比为120:87.84≈1.37:1，实际上就是3:2.196≈1.37 2018年9月22日 第2章 数据无损压缩

16 2.2.1 香农-范诺编码(续2) (2) 符号编码 对每个符号进行编码时采用“从上到下”的方法。首先按照符号出现的频度或概率排序，如A，B，C，D和E，见表2-2。然后使用递归方法分成两个部分，每一部分具有近似相同的次数，如图2-1所示 2018年9月22日 第2章 数据无损压缩

17 2.2.1 香农-范诺编码(续3) （3）压缩比的实际值 图2-1 香农-范诺算法编码举例
按照这种方法进行编码需要的总位数为 ＝91，实际的压缩比为120:91≈1.32 : 1 2018年9月22日 第2章 数据无损压缩

18 2.2.2 统计编码——霍夫曼编码 霍夫曼编码(Huffman coding)
霍夫曼(D.A. Huffman)在1952年提出和描述的“从下到上”的熵编码方法 根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少 广泛用在JPEG, MPEG, H.26X等各种信息编码标准中 2018年9月22日 第2章 数据无损压缩

19 2.2.2 霍夫曼编码— Case Study 1 霍夫曼编码举例1
现有一个由5个不同符号组成的30个符号的字符串：BABACACADADABBCBABEBEDDABEEEBB 计算 (1) 该字符串的霍夫曼码 (2) 该字符串的熵 (3) 该字符串的平均码长 (4) 编码前后的压缩比 2018年9月22日 第2章 数据无损压缩

20 2.2.2 霍夫曼编码— Case Study 1 (续1) 符号出现的概率 符号 出现的次数 log2(1/pi） 分配的代码 需要的位数
B 10 1.585 ? A 8 1.907 C 3 3.322 D 4 2.907 E 5 2.585 合计 30 2018年9月22日 第2章 数据无损压缩

21 2.2.2 霍夫曼编码— Case Study 1 (续2) (1) 计算该字符串的霍夫曼码
步骤①：按照符号出现概率大小的顺序对符号进行排序 步骤②：把概率最小的两个符号组成一个节点P1 步骤③：重复步骤②，得到节点P2，P3，P4，……， PN，形成一棵树，其中的PN称为根节点 步骤④：从根节点PN开始到每个符号的树叶，从上到下 标上0(上枝)和1(下枝)，至于哪个为1哪个为0则 无关紧要，但通常把概率大的标成1，概率小的 标成0 步骤⑤：从根节点PN开始顺着树枝到每个叶子分别写出 每个符号的代码 2018年9月22日 第2章 数据无损压缩

22 2.2.2 霍夫曼编码— Case Study 1 (续3) 代码 1 B(11) B (10) 1 A(10) A (8) E(00)
符号 B (10) A (8) E (5) D (4) C (3) 1 1 P3 (18) P4 (30) 1 1 P2 (12) P1 (7) 2018年9月22日 第2章 数据无损压缩

23 2.2.2 霍夫曼编码— Case Study 1 (续4) 5个符号的代码 30个字符组成的字符串需要67位 符号 出现的次数
log2(1/pi） 分配的代码 需要的位数 B 10 1.585 11 20 A 8 1.907 16 C 3 3.322 010 9 D 4 2.907 011 12 E 5 2.585 00 合计 30 1.0 67 30个字符组成的字符串需要67位 2018年9月22日 第2章 数据无损压缩

24 2.2.2 霍夫曼编码— Case Study 1 (续5) (2) 计算该字符串的熵 H(S) 其中， 是事件 的集合， 并满足
其中， 是事件 的集合， 并满足 H(S) =(8/30)×log2(30/8) + (10/30)×log2(30/10) (3/30)×log2(30/3) + (4/30)×log2(30/4) (5/30)×log2(30/5) = [30lg30 – (8×lg8 ＋ 10×lg10 ＋ 3×lg3 ＋ ×lg4 ＋5 lg5)] / (30×log22) = ( － )/ ＝ (Sh) 2018年9月22日 第2章 数据无损压缩

25 2.2.2 霍夫曼编码— Case Study 1 (续6) (3) 计算该字符串的平均码长 (4) 计算编码前后的压缩比
平均码长： ＝(2×8＋2×10＋3×3＋3×4＋2×5)/ ＝2.233 位/符号 平均码长：67/30=2.233位 (4) 计算编码前后的压缩比 编码前：5个符号需3位，30个字符，需要90位 编码后：共67位 压缩比: 90/67=1.34:1 2018年9月22日 第2章 数据无损压缩

26 2.2.2 霍夫曼编码— Case Study 2 霍夫曼编码举例2 计算 编码前
N = 8 symbols: {a,b,c,d,e,f,g,h}, 3 bits per symbol (N =23=8) P(a) = 0.01, P(b)=0.02, P(c)=0.05, P(d)=0.09, P(e)=0.18, P(f)=0.2, P(g)=0.2, P(h)=0.25 计算 (1) 该字符串的霍夫曼码 (2) 该字符串的熵 (3) 该字符串的平均码长 (4) 编码效率 2018年9月22日 第2章 数据无损压缩

27 2.2.2 霍夫曼编码— Case Study 2 (续1) 2018年9月22日 第2章 数据无损压缩

28 2.2.2 霍夫曼编码— Case Study 2 (续2) Average length per symbol (before coding): (2) Entropy: (3) Average length per symbol (with Huffman coding): (4) Efficiency of the code: 2018年9月22日 第2章 数据无损压缩

29 2.2.3 统计编码——算术编码 算术编码(arithmetic coding) 给已知统计信息的符号分配代码的数据无损压缩技术
基本思想是用0和1之间的一个数值范围表示输入流中的一个字符，而不是给输入流中的每个字符分别指定一个码字 实质上是为整个输入字符流分配一个“码字”，因此它的编码效率可接近于熵 2018年9月22日 第2章 数据无损压缩

30 2.2.3 算术编码举例 [例2.3]（取自教材） 假设信源符号为{00, 01, 10, 11}，它们的概率分别为{ 0.1, 0.4, 0.2, 0.3 } 对二进制消息序列 … 进行算术编码 2018年9月22日 第2章 数据无损压缩

31 2.2.3 算术编码举例(续1) 初始化 根据信源符号的概率把间隔[0, 1)分成如表2-4所示的4个子间隔：[0, 0.1), [0.1, 0.5), [0.5, 0.7), [0.7, 1)。其中[x, y)的表示半开放间隔，即包含x不包含y，x称为低边界或左边界，y称为高边界或右边界 表2-4 例2.3的信源符号概率和初始编码间隔 符号 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] 2018年9月22日 第2章 数据无损压缩

32 2.2.3 算术编码举例(续2) 确定符号的编码范围 整个编码过程如图2-3所示 编码和译码的全过程分别见表2-5和表2-6
编码时输入第1个符号是10，找到它的编码范围是[0.5, 0.7] 消息中第2个符号00的编码范围是[0, 0.1)，它的间隔就取[0.5, 0.7)的第一个十分之一作为新间隔[0.5, 0.52) 编码第3个符号11时，取新间隔为[0.514, 0.52) 编码第4个符号00时，取新间隔为[0.514, ) 依此类推…… 消息的编码输出可以是最后一个间隔中的任意数 整个编码过程如图2-3所示 编码和译码的全过程分别见表2-5和表2-6 2018年9月22日 第2章 数据无损压缩

33 2.2.3 算术编码举例(续3) 图2-3 例2.3的算术编码过程 2018年9月22日 第2章 数据无损压缩

34 2.2.3 算术编码举例(续4) 2018年9月22日 第2章 数据无损压缩

35 2.2.3 算术编码举例(续5) 2018年9月22日 第2章 数据无损压缩

36 2.3 RLE编码 行程长度编码(Run-Length Coding)
一种无损压缩数据编码技术，它利用重复的数据单元有相同的数值这一特点对数据进行压缩。对相同的数值只编码一次，同时计算出相同值重复出现的次数。在JPEG，MPEG，H.261和H.263等压缩方法中，RLE用来对图像数据变换和量化后的系数进行编码 例: 假设有一幅灰度图像第n行的像素值如图2-5所示。用RLE编码方法得到的代码为： 图2-5 RLE编码概念 2018年9月22日 第2章 数据无损压缩

37 2.3 RLE编码(续) Assumption: Long sequences of identical symbols. Example,
2018年9月22日 第2章 数据无损压缩

38 2.4 词典编码 词典编码(dictionary coding) 具体算法
文本中的词用它在词典中表示位置的号码代替的一种无损数据压缩方法。采用静态词典编码技术时，编码器需要事先构造词典，解码器要事先知道词典。采用动态辞典编码技术时, 编码器将从被压缩的文本中自动导出词典，解码器解码时边解码边构造解码词典 两种类型的编码算法 具体算法 LZ77算法 LZSS算法 LZ78算法 LZW算法 2018年9月22日 第2章 数据无损压缩

39 2.4 词典编码(续1) 第一类编码算法 用已经出现过的字符串替代重复的部分 编码器的输出仅仅是指向早期出现过的字符串的“指针”
图2-6 第一类词典编码概念 2018年9月22日 第2章 数据无损压缩

40 2.4 词典编码(续2) 第二类编码算法 从输入的数据中创建一个“短语词典(dictionary of the phrases)”
编码器输出词典中的短语“索引号”，而不是短语 图2-7 第二类词典编码概念 2018年9月22日 第2章 数据无损压缩

41 LZ77算法 第一类词典编码里：所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。
这类编码中的所有算法都是以Abraham Lempel和Jakob Ziv在1977年开发和发表的称为LZ77算法为基础的 Jacob Ziv, Abraham Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory, 23(3): , May 1977.

42 LZ77算法 LZ77 算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。

43 LZ77 首先介绍算法中用到的几个术语： 输入数据流(input stream)：要被压缩的字符序列。
字符(character)：输入数据流中的基本单元。 编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。 前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器。 窗口(window)：指包含W个字符的窗口，字符从编码位置开始向后数，也就是最后处理的字符数。 指针(pointer)：指向窗口中的匹配串，一般含有长度。 已编码 未编码 A B C W=5 B=4

44 图例 输入数据流

45 LZ77算法核心 LZ77编码算法的核心：查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行步骤如下：
把编码位置设置到输入数据流的开始位置。 查找窗口中最长的匹配串。 以“(Pointer, Length) Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。 如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2。

46 指针表示 (Pointer, Length) Characters 表示匹配的（字符位置，长度）下一个不匹配的字符
指针可以以“(Back_chars, Chars_length) Explicit_character”格式输出。 其中，(Back_chars, Chars_length)是指向匹配串的指针，告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”，Explicit_character是真实字符。

47 例子 W=5,B=2 每次移动窗口和编码位置Len+1 C B A Len=0 Len=1 Len=0 Len=1 位置 1 2 3 4 5
6 7 8 9 字符 A B C C B A Len=0 Len=1 Len=0 Len=1 编码步骤 编码位置 匹配串 前向缓冲中第一个字符 输出 (ptr,len) ch 1 -- A (0,0) A 2 B (1,1) B 3 4 C (0,0) C 5 (2,1) B 7 A B (5,2) C

48 LZ77的问题 LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，
一是空指针 例如前一个例子中 (0,0) C 二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。

49 LZSS算法 1982年由Storer和Szymanski改进LZ77 LZSS算法以比较有效的方法解决这个问题，
它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。由于输出的压缩数据流中包含有指针和字符本身，为了区分它们就需要有额外的标志位，即ID位。

50 LZSS编码算法步骤 把编码位置置于输入数据流的开始位置。
在前向缓冲存储器中查找与窗口中最长的匹配串 ① Pointer ：=匹配串指针。 ② Length ：=匹配串长度。 判断匹配串长度Length是否大于等于最小匹配串长度(Length≥MIN_LENGTH) ， 如果“是”：输出指针，然后把编码位置向前移动Length个字符。 如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。 如果前向缓冲存储器不是空的，就返回到步骤2

51 例子 位置 1 2 3 4 5 6 7 8 9 10 11 字符 A B C 编码过程(MIN_LENGTH = 2，W=10, B=3)
步骤 位置 匹配串 输出 1 -- A 2 3 B 4 5 C 6 B B (3,2) 7 8 A A B (7,3) 11 Len=1<2

52 LZSS与LZ77比较 在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip, GZip, ARJ, LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。 LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。

53 LZ78原理 LZ78的编码思想是不断地从字符流中提取新的字符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流(Char stream)，生成码字流(Code stream)，从而达到压缩数据的目的。

54 LZ77与LZ78比较 LZ77利用滑动窗口里的内容作为字典，找最长子串 LZ78动态构建字典

55 LZ78编码 在编码开始时词典是空的，不包含任何字符串(string)。在这种情况下编码器就输出一个表示空字符串的特殊码字(例如“0”)和字符流中(Charstream)的第一个字符C，并把这个字符C添加到词典中作为一个由一个字符组成的字符串(string)。在编码过程中，如果出现类似没有任何匹配的情况，也照此办理。 在词典中已经包含某些字符串(String)之后，如果“当前前缀P +当前字符C”已经在词典中，就用字符C来扩展这个前缀，这样的扩展操作一直重复到获得一个在词典中没有的字符串(String)为止。 此时就输出表示当前前缀P的码字(Code word)和字符C，并把P+C添加到词典中，然后开始处理字符流(Charstream)中的下一个字符。

56 算法 在开始时，词典和当前前缀P都是空的。 当前字符C ：=字符流中的下一个字符。 判断P+C是否在词典中：
(1) 如果“是”：用C扩展P，让P ：= P+C ； (2) 如果“否”： ① 输出与当前前缀P相对应的码字和当前字符C； ② 把字符串P+C 添加到词典中。 ③ 令P ：=空值。 (3) 判断字符流中是否还有字符需要编码 ① 如果“是”：返回到步骤2。 ② 如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。

57 LZ78编码输出 LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的字符串(String)用字符C进行扩展生成新的字符串(String)，然后添加到词典中。

58 例子 位置 1 2 3 4 5 6 7 8 9 字符 A B C 步骤 位置 当前字符C 当前前缀P 添加词典 输出 1 A －，－
BCA，－ B C A (3,A) 8 BA，－ B A (2,A)

59 LZ78与LZ77 LZ78在每个编码步骤中减少了string比较数目 LZ77需要找最长匹配子串 压缩率与LZ77类似。

60 LZW Terry A.Weltch在1984年发表了改进LZ78的文章，因此把这种编码方法称为LZW (Lempel-Ziv Walch)

61 LZW与LZ78编码原理差别 ①LZW只输出代表词典中的字符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。 ②由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)，因此至少可以在词典中找到长度为1的匹配串。

62 LZW的词典 LZW编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀(Prefix)的字符序列，并且为每个表项分配一个码字(Code word)，或者叫做序号。 Welch的论文中用了12位码字，12位可以有4096个不同的12位代码，这就是说，转换表有4096个表项，其中256个表项用来存放已定义的字符，剩下3840个表项用来存放前缀(Prefix)。

63 例子 码字(Code word) 前缀(Prefix) 1 … 193 A 194 B 255 1305 abcdefxyF01234

64 LZW编码 LZW编码器就是通过管理这个词典完成输入与输出之间的转换。
LZW编码器的输入是字符流(Char stream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流 (Code stream)，码字代表单个字符或多个字符组成的字符串(String)。LZ78输出是码字+字符 C B A 193…

65 贪婪分析算法 LZW采用greedy parsing algorithm
每一次分析都要串行地检查来自字符流(Charstream)的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀(Prefix)。 用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Current character)作为该前缀的扩展字符，形成新的扩展字符串。 判断新的串是否在词典中 是：继续输入C 否：加入词典，分配码字

66 具体执行步骤 开始时词典包含所有可能的根(Root)，当前前缀P是空的； 当前字符(C) ：=字符流中的下一个字符；
如果“是”：P ：= P+C // (用C扩展P) ； 如果“否” ① 把代表当前前缀P的码字输出到码字流; ② 把缀-符串P+C添加到词典; ③ 令P ：= C //(现在的P仅包含一个字符C);

67 注意：每个输出的码字对应于词典中的一个词条，因为只有当出现新的字符串的时候才输出码字。
4. 判断字符流中是否还有字符需要编码 (1) 如果“是”，就返回到步骤2； (2) 如果“否” ① 把代表当前前缀P的码字输出到码字流; ② 结束。 注意：每个输出的码字对应于词典中的一个词条，因为只有当出现新的字符串的时候才输出码字。

68 位置 1 2 3 4 5 6 7 8 9 字符 A B C 步骤 位置 词典 当前字符C 当前前缀P 输出 (1) A － (2) B (3) C 1 (4) A B AB, B 2 (5) B B BB, B 3 (6) B A BA, A 4 (7) A B A AB ABA, A 5 6 (8) A B A C ABA ABAC, C --

69 LZW的特点 1) 对于一段短语，它只输出一个数字，即字典中的序号。（这个数字的位数决定了字典的最大容量，当它的位数取得太大时，比如 24 位以上，对于短匹配占多数的情况，压缩率可能很低。取得太小时，比如 8 位，字典的容量受到限制。所以同样需要取舍。） 2) 对于一个短语，比如 abcd ，当它在待压缩文件中第一次出现时，ab 被加入字典，第二次出现时，abc 被加入字典，第三次出现时，abcd 才会被加入字典，对于一些长匹配，它必须高频率地出现，并且字典有较大的容量，才会被最终完整地加入字典。相应地，lz77 只要匹配在“字典区域”中存在，马上就可以直接使用。 3) 一个长匹配被加入字典的过程，是从两个字节开始，逐次增长一个字节，确定了字典的最大容量，也就间接确定了匹配的可能的最大长度。

70 LZW与LZ77 相对于 lz77 用两个数字来表示一个短语，lzw 只用一个数字来表示一个短语，因此，“字典序号”的位数可以取得多一点（二进制数多一位，意味着数值大一倍），也就是说最长匹配可以比 lz77 更长，当某些超长匹配高频率地出现，直到被完整地加入字典后，lzw将开始弥补初期的低效，逐渐显出自己的优势。 在多数情况下，lz77 拥有更高的压缩率，而在待压缩文件中占绝大多数的是些超长匹配，并且相同的超长匹配高频率地反复出现时，lzw 更具优势，GIF 就是采用了 lzw 算法来压缩背景单一、图形简单的图片。zip 是用来压缩通用文件的，这就是它采用对大多数文件有更高压缩率的 lz77 算法的原因。

71 第2章 数据无损压缩 参考文献和站点 David Salomon, Data Compression, ISBN , Third Edition, Springer-Verlag, 2004 Data Compression Reference Center， Timothy C.Bell, John G.Cleary, Ian H.Witten. Text Compression. Prentice-Hall, Inc.,1990 Ziv, J. and Lempel, A.. A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory, May 1977 Terry A. Welch, A Technique for High-Performance Data Compression. Computer, June 1984 Nelson, M.R. LZW Data Compression. Dr. Dobb's Journal, October 1989， R.Hunter and A.H.Robison. International Digital Facsimile Coding Standards. Proceedings of the IEEE, Vol.68, No.7，July, 1980，pp854～867 2018年9月22日 第2章 数据无损压缩

72 END 第2章 数据无损压缩