多媒体技术Chapter04-B.ppt

第4章 无损数据压缩,1,多媒体信源引起了“数据爆炸”如果不进行数据压缩 传输和存储都难以实用化。,多媒体数据,Facebook每天上传1亿张图片，130TB日志量,数据压缩就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号。,第4章 无损数据压缩,2,第4章 无损数据压缩,3,时间域压缩迅速传输媒体信源频率域压缩并行开通更多业务空间域压缩降低存储费用能量域压缩降低发射功率,多媒体数据压缩的必要性 数据存储 传输带宽,第4章 无损数据压缩,4,压缩比要大恢复后的失真小压缩算法要简单、速度快压缩能否用硬件实现,数据压缩技术实现的衡量标准,第4章 无损数据压缩,5,信息冗余 采集的多媒体数据信息具有相关性，可以用数学的方法来表示这些重复数据或相关数据。感官误差允许 人们在感知各种媒体对象时，往往对一些细节信息没有很强的感知，而且存在各种隐蔽效应。,多媒体数据压缩的可能性,第4章 无损数据压缩,数据压缩可分成两种类型，一种叫做无损压缩，另一种叫做有损压缩。无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/21/4。一些常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv&Welch)压缩算法。,6,有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不会让人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。(数字水印),第4章 无损数据压缩,7,本章主要介绍目前用得最多，技术最成熟的无损压缩编码技术，包含：霍夫曼编码算术编码RLE编码词典编码 对于不打算开发压缩技术和编写压缩程序的读者可不必深究编译码的详细过程。,第4章 无损数据压缩,8,香农-范诺编码算法需要用到下面两个基本概念1.Entropy(熵)的概念(1)熵是信息量的度量方法，它表示某一事件出现的消息越多，不确定性事件发生的可能性就越小，数学上就是概率越小。(2)某个事件的信息量用Ii=-log2pi表示，其中pi为第i个事件的概率，0pi=1,4.1.1 香农-范诺编码,4.1 香农-范诺与霍夫曼编码,9,2.信源S的熵的定义按照香农(Shannon)的理论，信源S的熵定义为,4.1.1 香农-范诺编码,其中pi是符号si在S中出现的概率；log2(1/pi)表示包含在si中的信息量，也就是编码si所需要的位数。例如，一幅用256级灰度表示的图像，如果每一个象素点灰度的概率均为pi=1/256，编码每一个象素点就需要8位。,10,例4.1 有一幅40个象素组成的灰度图像，灰度共有5级，分别用符号A、B、C、D和E表示，40个象素中出现灰度A的象素数有15个，出现灰度B的象素数有7个，出现灰度C的象素数有7个等等，如表4-01所示。如果用3个位表示5个等级的灰度值，也就是每个象素用3位表示，编码这幅图像总共需要120位（31537373635）。表4-01 符号在图像中出现的数目符 号ABCDE出现的次数157765,4.1.1 香农-范诺编码,11,按照香农理论，这幅图像的熵为H(S)=(15/40)log2(40/15)+(7/40)log2(40/7)+(5/40)log2(40/5)=2.196这就是说每个符号用2.196位表示，40个象素需用87.84位（2.19640）。,4.1.1 香农-范诺编码,12,最早阐述和实现这种编码的是Shannon(1948年)和Fano(1949年)，因此被称为香农-范诺(Shannon-Fano)算法。这种方法采用从上到下的方法进行编码。首先按照符号出现的频度或概率排序，例如，A，B，C，D和E，如表4-02所示。然后使用递归方法分成两个部分，使两个部分的概率和接近于相等。直至不可再分，即每一个叶子对应一个字符。如图4-01所示。按照这种方法进行编码得到的总位数为91，实际的压缩比约为1.3:1。,4.1.1 香农-范诺编码,13,表4-02 Shannon-Fano算法举例表,4.1.1 香农-范诺编码,14,图4-01香农-范诺算法编码举例,4.1.1 香农-范诺编码,15,霍夫曼(Huffman)在1952年提出了另一种编码方法，即从下到上的编码方法。现仍以一个具体的例子说明它的编码步骤：(1)初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如表4-03和图4-02所示。表4-03霍夫曼编码举例,4.1.2 霍夫曼编码,4.1 香农-范诺与霍夫曼编码,16,图4-02霍夫曼编码方法,4.1.2 霍夫曼编码,17,(2)把概率最小的两个符号组成一个节点，如图4-02中的D和E组成节点P1。(3)重复步骤2，得到节点P2、P3和P4，形成一棵“树”，其中的P4称为根节点。(4)从根节点P4开始到相应于每个符号的“树叶”，从上到下标上“0”(上枝)或者“1”(下枝)，至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。,4.1.2 霍夫曼编码,18,(5)从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码，如表4-03所示。(6)按照香农理论，这幅图像的熵为H(S)=(15/39)log2(39/15)+(7/39)log2(39/7)+(5/39)log2(39/5)=2.1859压缩比1.34:1。,4.1.2 霍夫曼编码,19,霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。例如，码串中的第1位为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码。,4.1.2 霍夫曼编码,20,采用霍夫曼编码时有两个问题值得注意：霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅仅是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误传播(error propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。尽管如此，霍夫曼码还是得到广泛应用。,4.1.2 霍夫曼编码,21,与香农-范诺编码相比，这两种方法都自含同步码，在编码之后的码串中都不需要另外添加标记符号，即在译码时分割符号的特殊代码。此外，霍夫曼编码方法的编码效率比香农-范诺编码效率高一些。,4.1.2 霍夫曼编码,22,算术编码在图像数据压缩标准(如JPEG，JBIG)中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。算术编码器的编码过程可用下面的例子加以解释。,4.2 算术编码,23,例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,y)表示半开放间隔，即包含x不包含y。上面的信息可综合在表4-04中。表4-04 信源符号、概率和初始编码间隔,4.2 算术编码,24,如果二进制消息序列的输入为：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所示。,4.2 算术编码,25,图4-03 算术编码过程举例,4.2 算术编码,26,这个例子的编码和译码的全过程分别表示在表4-05和表4-06中。根据上面所举的例子，可把计算过程总结如下。考虑一个有M个符号 ai=(1,2,M)的字符表集，假设概率p(ai)=pi，而。输入符号用xn表示，第n个子间隔的范围用 表示。其中 l0=0，d0=1和p0=0，ln表示间隔左边界的值,rn 表示间隔右边界的值，dn=rn-ln表示间隔长度。编码步骤如下：,4.2 算术编码,27,步骤1：首先在1和0之间给每个符号分配一个初始子间隔，子间隔的长度等于它的概率，初始子间隔的范围用I1=l1，r1)=，)表示。令d1=r1-l1，L=l1和R=r1。,4.2 算术编码,28,步骤2：L和R的二进制表达式分别表示为：和 其中ui 和vi 等于“1”或者“0”。比较u1和v1：如果u1v1，不发送任何数据，转到步骤3；如果u1=v1，就发送二进制符号u1。比较u2和v2：如果u2v2，不发送任何数据，转到步骤3；如果u2=v2，就发送二进制符号u2。,4.2 算术编码,29,这种比较一直进行到两个符号不相同为止，然后进入步骤3。步骤3：n加1，读下一个符号。假设第n个输入符号为xn=ai，按照以前的步骤把这个间隔分成如下所示的子间隔：令L=In，R=rn和dn=rn-In，然后转到步骤2。,4.2 算术编码,30,表4-05 编码过程,4.2 算术编码,31,表4-06 译码过程,4.2 算术编码,32,例4.3 假设有4个符号的信源，它们的概率如表4-07所示：表4-07 符号概率,4.2 算术编码,33,输入序列为xn：a2，a1，a3，。它的编码过程如图4-04所示，现说明如下。输入第1个符号是x1=a2，可知i=2，定义初始间隔 0.5,0.75)，由此可知 d1=0.25，左右边界的二进制数分别表示为：L0.5=0.1(B)，R0.70.11(B)。按照步骤2，u1=v1，发送1。因u2v2，因此转到步骤3。,4.2 算术编码,34,输入第2个字符x2=a1，i=1，它的子间隔 0.5,0.625)，由此可得d2=0.125。左右边界的二进制数分别表示为：L0.5=0.100(B)，R0.101(B)。按照步骤2，u2=v2=0，发送0，而u3和v3不相同，因此在发送0之后就转到步骤3。,4.2 算术编码,35,输入第3个字符，x3=a3，i=3，它的子间隔 0.59375,0.609375)，由此可得d3=0.015625。左右边界的二进制数分别表示为：L0.59375=0.10011(B)，R0.609375=0.100111(B)。按照步骤2，u3=v3=0，u4=v4=1，u5=v5=1，但u6和v6不相同，因此在发送011之后转到步骤3。发送的符号是：10011。被编码的最后的符号是结束符号。,4.2 算术编码,36,图4-04 算术编码概念,4.2 算术编码,37,就这个例子而言，算术解码器接受的第1位是“1”，它的间隔范围就限制在0.5,1)，但在这个范围里有3种可能的码符 a2，a3和 a4，因此第1位没有包含足够的译码信息。在接受第2位之后就变成“10”，它落在0.5,0.75)的间隔里，由于这两位表示的符号都指向a2开始的间隔，因此就可断定第一个符号是 a2。在接受每位信息之后的译码情况如下表4-08所示。,4.2 算术编码,38,表4-08 译码过程表,4.2 算术编码,39,在上面的例子中，我们假定编码器和译码器都知道消息的长度，因此译码器的译码过程不会无限制地运行下去。实际上在译码器中需要添加一个专门的终止符，当译码器看到终止符时就停止译码。在算术编码中需要注意的几个问题：,4.2 算术编码,40,(1)由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。(2)算术编码器对整个消息只产生一个码字，这个码字是在间隔0,1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。(3)算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。,4.2 算术编码,41,算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。需要开发动态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键。,4.2 算术编码,42,练习：设英文元音字母采用固定模式符号概率分配如下：字符：A E IOU概率：0.2 0.30.10.20.2试用算术编码对字符串EAIO进行编码。,4.2 算术编码,43,EAIO的编码为：0.2336,0.2348),现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的像素都具有相同的颜色值。在这种情况下就不需要存储每一个像素的颜色值，而仅仅存储一个像素的颜色值，以及具有相同颜色的像素数目就可以，或者存储一个像素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为行程编码(run length encoding，RLE)，具有相同颜色并且是连续的像素数目称为行程长度。,4.3 RLE编码,44,为了叙述方便，假定有一幅灰度图像，第n行的像素值如图4-05所示：,图4-05 RLE编码的概念,4.3 RLE编码,45,用RLE编码方法得到的代码为：80315084180。代码中用黑体表示的数字是行程长度，黑体字后面的数字代表像素的颜色值。例如黑体字50代表有连续50个像素具有相同的颜色值，它的颜色值是8。,4.3 RLE编码,46,对比RLE编码前后的代码数可以发现，在编码前要用73个代码表示这一行的数据，而编码后只要用11个代码表示代表原来的73个代码，压缩前后的数据量之比约为7:1，即压缩比为7:1。这说明RLE确实是一种压缩技术，而且这种编码技术相当直观，也非常经济。RLE所能获得的压缩比有多大，这主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。,4.3 RLE编码,47,译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。因此，RLE是无损压缩技术。RLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。,4.3 RLE编码,48,然而，RLE对颜色丰富的自然图像就显得力不从心，在同一行上具有相同颜色的连续像素往往很少，而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。请注意，这并不是说RLE编码方法不适用于自然图像的压缩，相反，在自然图像的压缩中还真少不了RLE，只不过是不能单纯使用RLE一种编码方法，需要和其他的压缩编码技术联合应用。,4.3 RLE编码,49,4.4.1 词典编码的思想,4.4 词典编码,有许多场合，开始时不知道要编码数据的统计特性，也不一定允许你事先知道它们的统计特性。因此，人们提出了许许多多的数据压缩方法，企图用来对这些数据进行压缩编码，在实际编码过程中以尽可能获得最大的压缩比。这些技术统称为通用编码技术。词典编码(Dictionary Encoding)技术就是属于这一类，这种技术属于无损压缩技术。,50,4.4.1 词典编码的思想,词典编码(dictionary encoding)的根据是数据本身包含有重复代码这个特性。例如文本文件和光栅图像就具有这种特性。词典编码法的种类很多，归纳起来大致有两类。第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅是指向早期出现过的字符串的“指针”。这种编码概念如图4-06所示。,51,图4-06 第一类词典法编码概念,4.4.1 词典编码的思想,52,这里所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。这类编码中的所有算法都是以Abraham Lempel和Jakob Ziv在1977年开发和发表的称为LZ77算法为基础的，例如1982年由Storer和Szymanski改进的称为LZSS算法就是属于这种情况。,4.4.1 词典编码的思想,53,第二类算法的想法是企图从输入的数据中创建一个“短语词典(dictionary of the phrases)”，这种短语不一定是像“严谨勤奋求实创新”和“国泰民安是坐稳总统宝座的根本”这类具有具体含义的短语，它可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。这个概念如图4-07所示。,4.4.1 词典编码的思想,54,图4-07 第二类词典法编码概念,4.4.1 词典编码的思想,55,J.Ziv和A.Lempel在1978年首次发表了介绍这种编码方法的文章LZ78算法。在他们的研究基础上，Terry A.Weltch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码，首先在高速硬盘控制器上应用了这种算法。,4.4.1 词典编码的思想,56,为了更好地说明LZ77算法的原理，首先介绍算法中用到的几个术语：(1)输入数据流(input stream)：要被压缩的字符序列。(2)字符(character)：输入数据流中的基本单元。(3)编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。,4.4.2 LZ77算法,4.4 词典编码,57,(4)前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器。(5)窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。(6)指针(pointer)：指向窗口中的匹配串且含长度的指针。,4.4.2 LZ77算法,58,LZ77编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行步骤如下：(1)把编码位置设置到输入数据流的开始位置。(2)查找窗口中最长的匹配串。(3)以“(Pointer,Length)Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。(4)如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2。,4.4.2 LZ77算法,59,例4.4 待编码的数据流如表4-09所示，编码过程如表4-10所示。现作如下说明:(1)“步骤”栏表示编码步骤。(2)“位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。(3)“匹配串”栏表示窗口中找到的最长的匹配串。(4)“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。(5)“输出”栏以“(Back_chars,Chars_length)Explicit_character”格式输出。,4.4.2 LZ77算法,60,其中，(Back_chars,Chars_length)是指向匹配串的指针，告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”，Explicit_character是真实字符。例如，表4-10中的输出“(5,2)C”告诉译码器回退5个字符，然后拷贝2个字符“AB”,4.4.2 LZ77算法,61,表4-10 编码过程,4.4.2 LZ77算法,表4-09待编码的数据流,62,4.4.2 LZ77算法,练 习,63,LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。LZSS算法以比较有效的方法解决这个问题，它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。由于输出的压缩数据流中包含有指针和字符本身，为了区分它们就需要有额外的标志位，即ID位。,4.4.3 LZSS算法,4.4 词典编码,64,LZSS编码算法的具体执行步骤如下：(1)把编码位置置于输入数据流的开始位置。(2)在前向缓冲存储器中查找与窗口中最长的匹配串 Pointer：=匹配串指针。Length：=匹配串长度。(3)判断匹配串长度Length是否大于等于最小匹配串长度(LengthMIN_LENGTH)，如果“是”：输出指针，然后把编码位置向前移动Length个字符。如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。(4)如果前向缓冲存储器不是空的，就返回到步骤2。,4.4.3 LZSS算法,65,例4.5 编码字符串如表4-11所示，编码过程如表4-12所示。现说明如下：(1)“步骤”栏表示编码步骤。(2)“位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。(3)“匹配”栏表示窗口中找到的最长的匹配串。(4)“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。(5)“输出”栏的输出为：,4.4.3 LZSS算法,66,如果匹配串本身的长度LengthMIN_LENGTH，输出指向匹配串的指针，格式为(Back_chars,Chars_length)。该指针告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”。如果匹配串本身的长度LengthMIN_LENGTH，则输出真实的匹配串。表4-11 输入数据流,4.4.3 LZSS算法,67,表4-12 编码过程(MIN_LENGTH=2),4.4.3 LZSS算法,68,在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip,ARJ,LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。,4.4.3 LZSS算法,69,在介绍LZ78算法之前，首先说明在算法中用到的几个术语和符号：(1)字符流(Charstream)：要被编码的数据序列。(2)字符(Character)：字符流中的基本数据单元。(3)前缀(Prefix)：在一个字符之前的字符序列。(4)缀-符串(String)：前缀字符。(5)码字(Code word)：码字流中的基本数据单元，代表词典中的一串字符。,4.4.4 LZ78算法,4.4 词典编码,70,(6)码字流(Codestream)：码字和字符组成的序列，是编码器的输出。(7)词典(Dictionary)：缀-符串表。按照词典中的索引号对每条缀-符串(String)指定一个码字(Code word)。(8)当前前缀(Current prefix)：在编码算法中使用，指当前正在处理的前缀，用符号P表示。,4.4.4 LZ78算法,71,(9)当前字符(Current character)：在编码算法中使用，指当前前缀之后的字符，用符号C表示。(10)当前码字(Current code word)：在译码算法中使用，指当前处理的码字，用W表示当前码字，String.W表示当前码字的缀-符串。,4.4.4 LZ78算法,72,1.编码算法LZ78的编码思想是不断地从字符流中提取新的缀-符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流(Charstream)，生成码字流(Codestream)，从而达到压缩数据的目的。,4.4.4 LZ78算法,73,在编码开始时词典是空的，不包含任何缀-符串(string)。在这种情况下编码器就输出一个表示空字符串的特殊码字(例如“0”)和字符流中(Charstream)的第一个字符C，并把这个字符C添加到词典中作为一个由一个字符组成的缀-符串(string)。在编码过程中，如果出现类似的情况，也照此办理。,4.4.4 LZ78算法,74,在词典中已经包含某些缀-符串(String)之后，如果“当前前缀P+当前字符C”已经在词典中，就用字符C来扩展这个前缀，这样的扩展操作一直重复到获得一个在词典中没有的缀-符串(String)为止。此时就输出表示当前前缀P的码字(Code word)和字符C，并把P+C添加到词典中作为前缀(Prefix)，然后开始处理字符流(Charstream)中的下一个前缀。,4.4.4 LZ78算法,75,LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的缀-符串(String)用字符C进行扩展生成新的缀-符串(String)，然后添加到词典中。LZ78编码的具体算法如下：步骤1：在开始时，词典和当前前缀P都是空的。步骤2：当前字符C：=字符流中的下一个字符。步骤3：判断P+C是否在词典中：,4.4.4 LZ78算法,76,(1)如果“是”：用C扩展P，让P：=P+C；(2)如果“否”：输出与当前前缀P相对应的码字和当前字符C；把字符串P+C 添加到词典中。令P：=空值。(3)判断字符流中是否还有字符需要编码 如果“是”：返回到步骤2。如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。,4.4.4 LZ78算法,77,2.译码算法在译码开始时译码词典是空的，它将在译码过程中从码字流中重构。每当从码字流中读入一对码字-字符(W,C)对时，码字就参考已经在词典中的缀-符串，然后把当前码字的缀-符串string.W 和字符C输出到字符流(Charstream)，而把当前缀-符串(string.W+C)添加到词典中。在译码结束之后，重构的词典与编码时生成的词典完全相同。LZ78译码的具体算法如下：,4.4.4 LZ78算法,78,步骤1：在开始时词典是空的。步骤2：当前码字W：=码字流中的下一个码字。步骤3：当前字符C：=紧随码字之后的字符。步骤4：把当前码字的缀-符串(string.W)输出到字符流(Charstream)，然后输出字符C。步骤5：把string.W+C添加到词典中。步骤6：判断码字流中是否还有码字要译(1)如果“是”，就返回到步骤2。(2)如果“否”，则结束。,4.4.4 LZ78算法,79,例4.6 编码字符串如表4-13所示，编码过程如表4-14所示。现说明如下：(1)“步骤”栏表示编码步骤。(2)“位置”栏表示在输入数据中的当前位置。(3)“词典”栏表示添加到词典中的缀-符串，缀-符串的索引等于“步骤”序号。(4)“输出”栏以(当前码字W,当前字符C)简化为(W,C)的形式输出。,4.4.4 LZ78算法,80,与LZ77相比，LZ78的最大优点是在每个编码步骤中减少了缀-符串(String)比较的数目，而压缩率与LZ77类似。,4-13 编码字符串,4.4.4 LZ78算法,81,表4-14 编码过程,4.4.4 LZ78算法,练 习,82,在LZW算法中使用的术语与LZ78使用的相同，仅增加了一个术语前缀根(Root)，它是由单个字符串组成的缀-符串(String)。在编码原理上，LZW与LZ78相比有如下差别：LZW只输出代表词典中的缀-符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)，因此在词典中搜索的第1个缀-符串有两个字符。,4.4.5 LZW算法,4.4 词典编码,83,现将LZW编码算法和译码算法介绍如下。1.编码算法LZW编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀(Prefix)的字符序列，并且为每个表项分配一个码字(Code word)，或者叫做序号，如表4-15所示。这张转换表实际上是把8位ASCII字符集进行扩充，增加的符号用来表示在文本或图像中出现的可变长度ASCII字符串。扩充后的代码可用9位、10位、11位、12位甚至更多的位来表示。12位可以有4096个不同的12位代码，这就是说，转换表有4096个表项，其中256个表项用来存放已定义的字符，剩下3840个表项用来存放前缀(Prefix)。,4.4.5 LZW算法,84,表4-15 词典,4.4.5 LZW算法,85,LZW编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流(Charstream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流(Codestream)，码字代表单个字符或多个字符组成的字符串。,4.4.5 LZW算法,86,LZW编码器使用了一种很实用的分析(parsing)算法，称为贪婪分析算法(greedy parsing algorithm)。在贪婪分析算法中，每一次分析都要串行地检查来自字符流(Charstream)的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀(Prefix)。,4.4.5 LZW算法,87,用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Current character)作为该前缀的扩展字符，形成新的扩展字符串缀-符串(String)：Prefix.C。这个新的缀-符串(String)是否要加到词典中，还要看词典中是否存有和它相同的缀-符串String。如果有，那么这个缀-符串(String)就变成前缀(Prefix)，继续输入新的字符，否则就把这个缀-符串(String)写到词典中生成一个新的前缀(Prefix)，并给一个代码。,4.4.5 LZW算法,88,LZW编码算法的具体执行步骤如下：步骤1：开始时的词典包含所有可能的根(Root)，而当前前缀P是空的；步骤2：当前字符(C)：=字符流中的下一个字符；步骤3：判断缀-符串P+C是否在词典中(1)如果“是”：P：=P+C/(用C扩展P)；(2)如果“否”把代表当前前缀P的码字输出到码字流;把缀-符串P+C添加到词典;令P：=C/(现在的P仅包含一个字符C);,4.4.5 LZW算法,89,步骤4：判断码字流中是否还有码字要译(1)如果“是”，就返回到步骤2；(2)如果“否”把代表当前前缀P的码字输出到码字流;结束。LZW编码算法可用伪码表示。开始时假设编码词典包含若干个已经定义的单个码字。例如，256个字符的码字，用伪码可以表示成：,4.4.5 LZW算法,90,Dictionaryj all n single-character，j1,2，n j n+1 Prefix read first Character in Charstream while(C next Character)!=NULL)Begin If Prefix.C is in Dictionary Prefix Prefix.C else Codestream cW for Prefix Dictionaryj Prefix.C j n+1 Prefix C end Codestream cW for Prefix,4.4.5 LZW算法,91,2.译码算法LZW译码算法中还用到另外两个术语：当前码字(Current code word)：指当前正在处理的码字，用cW表示，用string.cW表示当前缀-符串；先前码字(Previous code word)：指先于当前码字的码字，用pW表示，用string.pW表示先前缀-符串。LZW译码算法开始时，译码词典与编码词典相同，它包含所有可能的前缀根(roots)。LZW算法在译码过程中会记住先前码字(pW)，从码字流中读当前码字(cW)之后输出当前缀-符串string.cW，然后把用string.cW的第一个字符扩展的先前缀-符串string.pW添加到词典中。,4.4.5 LZW算法,92,LZW译码算法的具体执行步骤如下：步骤1：在开始译码时词典包含所有可能的前缀根(Root)。步骤2：cW：=码字流中的第一个码字。步骤3：输出当前缀-符串string.cW到码字流。步骤4：先前码字pW：=当前码字cW。步骤5：当前码字cW：=码字流中的下一个码字。步骤6：判断先前缀-符串string.pW是否在词典中,4.4.5 LZW算法,93,(1)如果“是”，则：把先前缀-符串string.pW输出到字符流。当前前缀P：=先前缀-符串string.pW。当前字符C：=当前前缀-符串string.cW的第一个字符。把缀-符串P+C添加到词典。(2)如果“否”，则：当前前缀P：=先前缀-符串string.pW。当前字符C：=当前缀-符串string.cW的第一个字符。输出缀-符串P+C到字符流，然后把它添加到词典中。,4.4.5 LZW算法,94,步骤7：判断码字流中是否还有码字要译(1)如果“是”，就返回到步骤4。(2)如果“否”,结束。LZW译码算法可用伪码表示如下：Dictionaryj all n single-character，j1,2,n j n+1 cW first code from Codestream Charstream DictionarycW pW cW While(cW next Code word)!=NULL),4.4.5 LZW算法,95,Begin If cW is in Dictionary Charstream DictionarycW Prefix DictionarypW cW first Character of DictionarycW Dictionaryj Prefix.cW j n+1 pW cW else Prefix DictionarypW cW first Character of PrefixCharstream Prefix.cW Dictionaryj Prefix.C pW cW j n+1 end,4.4.5 LZW算法,96,例4.7 编码字符串如表4-16所示，编码过程如表4-17所示。现说明如下：(1)“步骤”栏表示编码步骤；(2)“位置”栏表示在输入数据中的当前位置；(3)“词典”栏表示添加到词典中的缀-符串，它的索引在括号中；(4)“输出”栏表示码字输出。表4-16 被编码的字符串,4.4.5 LZW算法,97,表4-17 LZW的编码过程,4.4.5 LZW算法,98,表4-18解释了译