无损数据压缩

1、第4章无损数据压缩数据压缩可分成两种类型，一种叫做无损压缩，另一种叫做有损压缩。无损压缩是指使用压缩后的数据进行重构（或者叫做还原，解压缩），重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩 到原来的1/21/4。一些常用的无损压缩算法有霍夫曼（Huffman）算法和LZW（Lenpel-Ziv &Welch）压缩算法。有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和

2、原始信号完全相 同的场合。例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。本章主要介绍目前用得最多和技术最成熟的无损压缩编码技术，包括包含霍夫曼编码、算术编码、RLE编码和词典编码。对于不打算开发压缩技术和编写压缩程序的读者可不必深究 编译码的详细过程。香农-范诺与霍夫曼编码香农-范诺编码算法需要用到下面两个基本概念：Entropy（ 嫡）的概念.嫡是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越 小，数学上就是概率越小。.某个事件的信息

3、量用4 =7整3巧表示， 其中乌为第，个事件的概率， 。工吊4 12.信源S的嫡的定义按照仙农（Shannon）的理论，信源S的嫡定义为耳=疗=黑吊腌式15）其中用是符号苗在S中出现的概率；叫式”为）表示包含在戋中的信息量，也就是编码苫 所需要的位数。例如，一幅用256级灰度表示的图像，如果每一个象素点灰度的概率均为PC 256 ,编码每一个象素点就需要8位。例4.1有一幅40个象素组成的灰度图像，灰度共有 5级，分别用符号 A、B、C D和E 表示，40个象素中出现灰度 A的象素数有15个，出现灰度B的象素数有7个，出现灰度 C的象素数有7个等等，如表4-01所示。如果用3个位表示5个等级的

4、灰度值，也就是每个象素用3位表示，编码这幅图像总共需要120位。表4-01符号在图像中出现的数目符号ABCDE出现的次数157765按照仙农理论，这幅图像的嫡为+ (5/40)(40/5)HS) = (15/40)二(40/15) + (7/40)、二二(40/7) + =2.196这就是说每个符号用 2.196位表示，40个象素需用87.84位。最早阐述和实现这种编码的是Shannon（1948年）和Fano（1949年），因此被称为仙农-范诺（Shannon- Fano）算法。这种方法采用从上到下的方法进行编码。首先按照符号出现的频度或概率排序，例如， 力，3, 和如表4-02所示。然后使

5、用递归方法分成两个部分，每一部分具有近似相同的次数，如图 4-01所示。按照这种方法进行编码得到的总位 数为91。压缩比约为1.3 : 1 。表4-02 Shannon-Fano算法举例表符号出现的次数（71 ）loSafl/jPi)分配的代码需要的位数A15 (0.375)1.41500030B7 (0.175)2.51450114C7 (0.175)2.51451014D6 (0.150)2.736911018E5 (0.125)3.000011115图4-01香农-范诺算法编码举例4.1.2 霍夫曼编码霍夫曼（Huffman）在1952年提出了另一种编码方法，即从下到上的编码方法。现仍以

6、一个具体的例子说明它的编码步骤：.初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如表4-03和图4-02所示。.把概率最小的两个符号组成一个节点，如图 4-02中的D和E组成节点P1。.重复步骤2,得到节点P2、P3和P4,形成一棵 树”，其中的P4称为根节点。.从根节点P4开始到相应于每个符号的树叶”，从上到下标上 0上技）或者“11（枝），至于哪个为“1哪个为“0则无关紧要，最后的结果仅仅是分配的代码不同，而 代码的平均长度是相同的。.从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码，如表 4-03所示。.按照仙农理论，这幅图像的嫡为H：S) = (15/39)二二(39

7、/15) + (7/39) ”二:(39/7) + (5/39) ;二二(39/5)=2.1859压缩比1.37:1表4-03霍夫曼编码举例符号出现的次数log 2(1/p i)分配的代码需要的位数A15(0.3846)1.38015B7(0.1795)2.4810021C6(0.1538)2.7010118D6(0.1538)2.7011018E5(0.1282)2.9611115 TOC o 1-5 h z A(0.3846)-0BQ1795) oC(0 1538) 1_ b D(0 1538)P3E(0.1282)图4-02霍夫曼编码方法霍夫曼码的码长虽然是可变的，但却不需要另外附加同步

8、代码。例如，码串中的第1位为0,那末肯定是符号 A,因为表示其他符号的彳t码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“ 110”，那么它就代表符号D=如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码。采用霍夫曼编码时有两个问题值得注意： 霍夫曼码没有错误保护功能， 在译码时，如果码 串中没有错误，那么就能一个接一个地正确译出代码。 但如果码串中有错误， 哪仅是1位出 现错误，不但这个码本身译错， 更糟糕的是一错一大串， 全乱了套，这种现象称为错误传播(error propagation) 。计算机对这种错误也

9、无能为力，说不出错在哪里，更谈不上去纠正它。霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。尽管如此，霍夫曼码还是得到广泛应用。与仙农-范诺编码相比，这两种方法都自含同步码，在编码之后的码串中都不须要另外添加标记符号，即在译码时分割符号的特殊代码。此外，霍夫曼编码方法的编码效率比仙农-范诺编码效率高一些。请读者自行验证。4.2算术编码算术编码在图像数据压缩标准(如JPEG JBIG)中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，

10、也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。算术编码器的编码过程可用下面的例子加以解释。例4.2假设信源符号为00, 01, 10, 11,这些符号的概率分别为 0.1, 0.4, 0.2, 0.3 , 根据这些概率可把间隔0, 1)分成4个子间隔：0, 0.1), 0.1, 0.5), 0.5, 0.7), 0.7, 1),其中【兀田)表示半开放间隔，即包含 X不包含丁。上面的信息可综合在表4-04中。表4-04信源符号，概率和初始编码间隔符号00011011概率0.10.40.20.3初始编码同 隔0, 0.1)0.1,0.5)0.5

11、, 0.7)0.7, 1)如果二进制消息序列的输入为：10 00 11 00 10 11 01。编码时首先输入的符号是10,找到它的编码范围是0.5, 0.7)。由于消息中第二个符号00的编码范围是0, 0.1),因此它的间隔就取0.5, 0.7)的第一个十分之一作为新间隔0.5, 0.52)。依此类推，编码第 3个符号11时取新间隔为0.514, 0.52),编码第4个符号00时，取新间隔为0.514, 0.5146),。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图4-03所示。编码间隔输入 10 00 1100101101图4-03算术编码过程举例这个例子的编码和译码的全过

12、程分别表示在表4-05和表4-06中。根据上面所举的例子，可把计算过程总结如下。考虑一个有M个符号由=02-3此的字符表集，假设概率%，而工办（/）=Pi+p士+ PM）=1,。输入符号用 餐表示，第犀个子间隔的范围用=超=3:a-1 + *2Jx=1 + :制-i.Pi）J n1n J白 表示。其中，。=Q ,%=i和外=o d表示间隔左边界的值,弓表示间隔右边界的值，*=*表示间隔长度。编码步骤如下：步骤1：首先在i和0之间给每个符号分配一个初始子间隔，子间隔的长度等于它的概率，初始子间隔的范围用A =儿为）=川）表示。令心=尸4 ,=八和衣=%。步骤2: L和R的二进制表达式分别表示为：

13、 g0t-l 和其中也和咋等于“1”或者“0” 。比较为和巧：如果以】H巧，不发送任何数据，转到步骤3；如果以】=叫，就发送二进制符号为。比较肛和冷：如果% f ,不发送任何数据，转到步骤 3;如果%=吗就发送二 进制符号叫。 TOC o 1-5 h z 这种比较一直进行到两个符号不相同为止，然后进入步骤3,步骤3:为加1,读下一个符号。假设第 两个输入符号为 & = % ,按照以前的步骤把这个间 隔分成如下所示的子间隔：1a=丑，8)=M_1 4-1 j-1I令 =(，氏=q和=/一4，然后转到步骤2。表4-05编码过程步骤输入 符号编码间隔编码判决1100.5, 0.7)符号的间隔范围0.

14、5, 0.7)2000.5, 0.52)0.5, 0.7)间隔的 A个 1/103110.514, 0.52)0.5, 0.52) 间隔的最舟-个 1/104000.514, 0.5146)0.514, 0.52) 间隔的第一个 1/105100.5143, 0.51442)0.514, 0.5146)间隔的第五个1/10开始，二个1/106110.514384, 0.51442)0.5143, 0.51442) 间隔的最后 3 个 1/107010.5143836, 0.514402)0.514384, 0.51442) 间隔的 4 个 1/10,从第 1 个1/10开始8从0.514387

15、6, 0.514402中选择一个数作为输出：0.5143876表4-06译码过程步 骤间隔译码符号译码判决10.5, 0.7)100.51439 在间隔0.5, 0.7)20.5, 0.52)000.51439 在间隔0.5, 0.7) 的第 1 个 1/1030.514, 0.52)110.51439 在间隔0.5, 0.52)的第 7 个 1/1040.514, 0.5146)000.51439 在间隔0.514, 0.52) 的第 1 个 1/1050.5143, 0.51442)100.51439 在间隔0.514, 0.5146) 的第 5 个 1/1060.514384, 0.51

16、442)110.51439 在间隔0.5143, 0.51442)的第 7 个 1/1070.51439, 0.5143948)010.51439 在间隔0.51439, 0.5143948) 的第 1 个 1/107译码的消息：10 00 11 00 10 11 01例3假设有4个符号的信源，它门的概率如表4-07所示:表4-07符号概率信源符号ai%概率仍Pi = 0同为=0253 = 0.125|P4 =025初始编码同 隔0, 0.5)0.5, 0.75)0.75, 0.875)0.875, 1)输入序列为/ : 曲，与，。它的编码过程如图4-04所示，现说明如下。输入第1个符号是为可

17、知=2 ,定义初始间隔21r;、 工必-1E必4小丹)1,)=0.5, 0.75),由此可知H1 =口25 ,左右边界的二进制数分别表示为：L=0.5=0.1(B) , R = 0.7 =0.11(B)。按照步骤2,叫=叫，发送1。因:！二& ,因此转到步骤3。输入第2个字符强1=,它的子间隔仃-L外切一 I勺1, I )= 0.5, 0.625),由此可得 心=0.125。左右边界的二进制数分别表示为：L= 0.5=0.1003。工“ - a , I =I4+义工Pl叼 %,& = ?,它的子间隔 气-, R= 0.101(B)。按照步骤2, % =2=0,发送0,而和当不相同，因此在发送

18、0之后就转到步骤输入第3个字符， i h +a立为-)=0.59375, 0.609375),由此可得 分=0.015625。左右边界的二进制数分别表示为： = 0.59375=0.10011 (B),氏=0.609375=0.100111 (B)。按照步骤 2 产3=0= 以4 ”4 =1,町=马=1 ,但小和也不相同，因此在发送011之后转到步骤3。发送的符号是：10011- O被编码的最后的符号是结束符号符号 十进制0 二进制0.010.750.110.S75 1.0All 1.0十进制二进制0.6250.1010.6875 0.71875 0.75D.1011 0-10111 0.11

19、号制制0.5方%吗 吗%与比”40.56250.59375 0.609375 0.6250.10010.10011 0.100111 0.101图4-04算术编码概念就这个例子而言，算术编码器接受的第1位是“1”，它的间隔范围就限制在0.5, 1)，但在这个范围里有3种可能的码符 3,和口4,因此第1位没有包含足够的译码信息。在 接受第2位之后就变成“ 10”，它落在0.5, 0.75) 的间隔里，由于这两位表示的符号都指向阳开始的间隔，因此就可断定第一个符号是 “之。在接受每位信息之后的译码情况如下表4-08所示。表4-08译码过程表接受的数字间隔译码输出10,5, 1)一00.5, 0.7

20、5)%00,5, 0.609375)1110,5625, 0,609375)一10,59375, 0,609375)在上面的例子中，我们假定编码器和译码器都知道消息的长度，因此译码器的译码过程不会无限制地运行下去。 实际上在译码器中需要添加一个专门的终止符，当译码器看到终止符时就停止译码。在算术编码中需要注意的几个问题：1,由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多 数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。.算术编码器对整个消息只产生一个码字，这个码字是在间隔0,1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能

21、进行译码。.算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消 息译错。算术编码可以是静态的或者自适应的。在静态算术编码中， 信源符号的概率是固定的。 在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。需要开开发态算术编码的原因是因为事先知道精确的信源概率是很难的， 而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获 得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键RLE编码现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图

22、块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。在这种情况下就不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值，以及具有相同颜色的象素数目就可以，或者存储一个象素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为行程编码，常用(r un l ength encoding , RLE)表示，具有相同颜色并且是连续的象素数目 称为行程长度。为了叙述方便，假定一幅灰度图像，第n行的象素值为：00000000 111 8888881111 00000000I i i wn ii i8个0 3个1 50个8I个1 X40图4-05 RLE编码的概念用RLE编码方

23、法得到的代码为：803150841800代码中用黑体表示的数字是行程长度，黑体字后面的数字代表象素的颜色值。例如黑体字50代表有连续50个象素具有相同的颜色值，它的颜色值是8。对比RLE编码前后的代码数可以发现，在编码前要用73个代码表示这一行的数据，而编码后只要用11个代码表示代表原来的 73个代码，压缩前后的数据量之比约为7:1 ,即压缩比为7:1。这说明RLE确实是一种压缩技术，而且这种编码技术相当直观，也非常经济。RLE所能获得的压缩比有多大，这主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。译码时按照与编码时采用

24、的相同规则进行，还原后得到的数据与压缩前的数据完全相同。因此，RLE是无损压缩技术。RLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。然而， RLE对颜色丰富的自然图像就显得力不从心，在同一行上具有相同颜色的连续象素往往很 少，而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用 RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。请注意，这并不是说RLE编码方法不适用于自然图像的压缩，相反，在自然图像的压缩中还真少不了RLE,只不过是不能单纯使用RLE一种编码方法，需要和其他的压缩编码技术联合应用。词典编码有许多场合，开始时不知道要编码数据的

25、统计特性，也不一定允许你事先知道它们的统计特性。因此，人们提出了许许多多的数据压缩方法，企图用来对这些数据进行压缩编码，在实际编码过程中以尽可能获得最大的压缩比。这些技术统称为通用编码技术。词典编码 (Dictionary Encoding)技术就是属于这一类，这种技术属于无损压缩技术。词典编码的思想词典编码(dictionary encoding)的根据是数据本身包含有重复代码这个特性。例如文本文件和光栅图像就具有这种特性。词典编码法的种类很多，归纳起来大致有两类。第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅

26、是指向早期出现过的字符串的“指 针”。这种编码概念如图 4-06所示。图4-06第一类词典法编码概念这里所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。这类编码中的所有算法都是以 Abraham Lempel和Jakob Ziv 在1977年开发和发表的称为 LZ77算法 为基础的，例如1982年由Storer和Szymanski改进的称为LZSS算法就是属于这种情况。第二类算法的想法是企图从输入的数据中创建一个“短语词典(dictionary of thephrases); 这种短语不一定是像“严谨勤奋求实创新”和“国泰民安是坐稳总统宝座的根本”这类具有具体含义的短语，它

27、可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。这个概念如图4-07所示。图4-07第二类词典法编码概念J.Ziv和A.Lempel在1978年首次发表了介绍这种编码方法的文章。在他们的研究基础上， Terry A.Weltch 在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为 LZW(Lempel-Ziv Walch)压缩编码，首先在高速硬盘控制器上应用了这种算法。LZ77 算法为了更好地说明LZ77算法的原理，首先介绍算法中用到的几个术语：.输入数据流(input stream)：要被压缩的字

28、符序列。.字符(character)：输入数据流中的基本单元。.编码位置(coding position):输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。.前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结束的字符序列 的存储器。.窗口(window)：指包含 W个字符的窗口，字符是从编码位置开始向后数也就是最后 处理的字符数。.指针(pointer)：指向窗口中的匹配串且含长度的指针。LZ77编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行 步骤如下：.把编码位置设置到输入数据流的开始位置。.查找窗口中最长的匹配串。.

29、以“(Pointer, Length) Characters的格式输出，其中 Pointer是指向窗口中匹配串的指 针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。.如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2。例4.4待编码的数据流如表4-09所示，编码过程如表4-10所示。现作如下说明：“步骤”栏表示编码步骤。“位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。“匹配串”栏表示窗口中找到的最长的匹配串。“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。输出栏以(Back_cha

30、rs, Chars_length) Explicit_character 格式输出。其中， (Back_chars, Chars_length)是指向匹配串的指针，告诉译码器”在这个窗口中向后退 Back_chars个字符然后拷贝 Chars_length个字符到输出，Explicit_character是真实 字符。例如，表4-10中的输出(5,2) C”告诉译码器回退5个字符，然后拷贝2个字 符AB”表4-09待编码的数据流123456789字符AABCBBABC表4-10编码过程步骤匹配串字符输出11-A(0,0) A22AB(1,1)B34-C(0,0) C45BB(2,1)57 A

31、B C (5,2)C4.4.3 LZSS 算法LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗 余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。LZSS算法以比较有效的方法解决这个问题，它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。由于输出的压缩数据流中包含有指针和字符本身，为了区分它们就需要有额外的标志位，即ID位。LZSS编码算法的具体执行步骤如下：.把编码位置置于输入数据流的开始位置。.在前向缓冲存储器中查找与窗口中最长的匹配串Pointer :=匹配串指

32、针。Length :=匹配串长度。.判断匹配串长度 Length是否大于等于最小匹配串长度(Length之MIN_LENGTH),如果“是：输出指针，然后把编码位置向前移动Length个字符。如果“否”：输出前向缓冲存储器中的 第1个字符，然后把编码位置向前移动一个字 符。.如果前向缓冲存储器不是空的，就返回到步骤 2。4-12所示。现说明如下:例4.5编码字符串如表 4-11所不，编码过程如表“步骤”栏表示编码步骤。“位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。“匹配”栏表示窗口中找到的最长的匹配串。“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。“输出”栏的输出为：

33、如果匹配串本身的长度Length之MIN_LENGTH ,输出指向匹配串的指针，格式为(Back_chars, Chars_length)。该指针告诉译码器”在这个窗口中向后退Back_chars个字符然后拷贝 Chars_length个字符到输出”。如果匹配串本身的长度Length MIN_LENGTH，则输出真实的匹配串。表4-11输入数据流立置12345617891011字符AABBCB|BAABC表 4-12 编码过程(MIN_LENGTH= 2)步 骤位置匹配 串输出11-A22AA33-B44BB55-C66B B(3,2)78A A B(7,3)811CC在相同的计算机环境下，L

34、ZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip, ARJ, LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等 有所不同。LZSS同样可以和嫡编码联合使用，例如ARJ就与霍夫曼编码联用，而 PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。4.4.4 LZ78 算法在介绍LZ78算法之前，首先说明在算法中用到的几个术语和符号：.字符流(Charstream):要被编码的数据序列。.字符(Character)：字符流中的基本数据单元。.前缀(

35、Prefix):在一个字符之前的字符序列。.缀-符串(String)：前缀十字符。.码字(Code word)：码字流中的基本数据单元，代表词典中的一串字符。.码字流(Codestream):码字和字符组成的序列，是编码器的输出。.词典(Dictionary ):缀-符串表。按照词典中的索引号对每条缀-符串(String)指定一个码字(Code word)。.当前前缀(Current prefix )：在编码算法中使用，指当前正在处理的前缀，用符号 P表 示。.当前字符(Current character)：在编码算法中使用，指当前前缀之后的字符，用符号C表不。.当前码字(Current co

36、de word )：在译码算法中使用，指当前处理的码字，用 W表示 当前码字，String.W表示当前码字的缀-符串。.编码算法LZ78的编码思想是不断地从字符流中提取新的缀-符串(String ),通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word )去替换字符流(Charstream ),生成码字流(Codestream), 从而达到压缩数据的目的。在编码开始时词典是空的，不包含任何缀-符串(string )。在这种情况下编码器就输出一个表示空字符串的特殊码字 (例如“0”)和字符流中(Char

37、stream )的第一个字符 C,并把这个 字符C添加到词典中作为一个由一个字符组成的缀-符串(string )。在编码过程中，如果出现类似的情况，也照此办理。在词典中已经包含某些缀-符串(String )之后，如果“当前前缀P +当前字符C”已经在词典中，就用字符 C来扩展这个前缀，这样的扩展操作一直重复 到获得一个在词典中没有的缀-符串(String )为止。此时就输出表示当前前缀P的码字(Code word)和字符C,并把P+C添加到词典中作为前缀(Pre巾x )，然后开始处理字符流(Charstream) 中的下一个前缀。LZ78编码器的输出是码字-字符(WQ对，每次输出一对到码字流中

38、，与码字Wt目对应的缀-符串(String )用字符C进行扩展生成新的缀-符串(String ),然后添加到词典中。LZ78编码 的具体算法如下： 步骤1：在开始时，词典和当前前缀P都是空的。步骤2:当前字符C :二字符流中的下一个字符。 步骤3:判断P+C是否在词典中：(1)如果“是：用 C扩展P,让P : = P+C ; (2)如果“否”：输出与当前前缀P相对应的码字和当前字符C;把字符串P+C添加到词典中。 令P :=空值。(3)判断字符流中是否还有字符需要编码如果“是：返回到步骤2。 如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。2.译码算法在译码开始时译

39、码词典是空的，它将在译码过程中从码字流中重构。每当从码字流中读入一对码字-字符(W,C)对时，码字就参考已经在词典中的缀-符串，然后把当前码字的缀 -符串string.W 和字符C输出到字符流(Charstream ),而把当前缀-符串(string.W+C )添加到词典 中。在译码结束之后，重构的词典与编码时生成的词典完全相同。LZ78译码的具体算法如下： 步骤1:在开始时词典是空的。 步骤2:当前码字 W:二码字流中的下一个码字。步骤3:当前字符C :=紧随码字之后的字符。步骤4：把当前码字的缀-符串(string.W )输出到字符流(Charstream ),然后输出字符 C 步骤5:把

40、string.W+C 添加到词典中。步骤6:判断码字流中是否还有码字要译 如果“是，就返回到步骤 2。 (2)如果“否，则结束。例4.6编码字符串如表 4-13所示，编码过程如表 4-14所示。现说明如下：“步骤”栏表示编码步骤。“位置”栏表示在输入数据中的当前位置。“词典”栏表示添加到词典中的缀-符串，缀-符串的索引等于 步骤”序号。“输出”栏以(当前码字 W,当前字符C)简化为(W, C)的形式输出。表4-13编码字符串1234516789字符ABBCBCABA表4-14编码过程步II位置1词典输出与LZ77相比，LZ78的最大优点是在每个编码步骤中减少了缀-符串（String ）比较的数

41、目,而压缩率与LZ77类似。4.4.5 LZW 算法在LZW算法中使用的术语与LZ78使用的相同，仅增加了一个术语一前缀根（Root）,它是由单个字符串组成的缀-符串（String）。在编码原理上，LZW与LZ78相比有如下差别：LZW只输出代表词典中的缀-符串（String）的码字（code word）。这就意味在开始时词典不能是空的， 它必须包含可能在字符流出现中的所有单个字符，即前缀根（Root）。由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀（one-characterprefix）,因此在词典中搜索的第1个缀-符串有两个字符。现将LZW编码算法和译码算法介绍如下。 1.编码算法LZW编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀（Pr