第4章 无损数据压缩.docx

第 4 章 无损数据压缩数据压缩可分成两种类型，一种叫做无损压缩，另一种叫做有损压缩无损压缩是指使用压缩后的数据进行重构（或者叫做还原，解压缩），重构后的数据与原来的 数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合一个很常见的例 子是磁盘文件的压缩根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩 到原来的1/2〜1/4一些常用的无损压缩算法有霍夫曼（Huffman）算法和LZW（Lenpel-Ziv & Welch）压缩算法有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响 人对原始资料表达的信息造成误解有损压缩适用于重构信号不一定非要和原始信号完全相 同的场合例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我 们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的 意思产生误解，但可大大提高压缩比本章主要介绍目前用得最多和技术最成熟的无损压缩编码技术，包括包含霍夫曼编码、算术 编码、RLE编码和词典编码对于不打算开发压缩技术和编写压缩程序的读者可不必深究 编译码的详细过程4.1 香农-范诺与霍夫曼编码香农-范诺编码算法需要用到下面两个基本概念：1. Entropy （熵）的概念1. 熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越 小，数学上就是概率越小。

2. 某个事件的信息量用表示，其中凤为第i个事件的概率，0 Y戸S2. 信源S的熵的定义按照仙农（Shannon）的理论，信源S的熵定义为丹⑸="为申1昭2（打円） 其中円是符号闫在S中出现的概率；log 2 （1/耳）表示包含在闫中的信息量，也就是编码闫所需要的位数例如，一幅用 256 级灰度表示的图像，如果每一个象素点灰度的概率均为编码每一个象素点就需要8位［例4.1］有一幅40个象素组成的灰度图像，灰度共有5级，分别用符号A、B、C、D和E 表示，40个象素中出现灰度A的象素数有15个，出现灰度B的象素数有7个，出现灰度C 的象素数有7个等等，如表4-01所示如果用3个位表示5个等级的灰度值，也就是每个 象素用 3位表示，编码这幅图像总共需要120位表 4-01 符号在图像中出现的数目符号BCDE出现的次数157765按照仙农理论，这幅图像的熵为H(S) = (15/40) X 託言2 (40/15) + (7/40) x 聪2 (40/7) + ••- + (5/40) x 强2(40/5)=2.196 这就是说每个符号用2.196位表示， 40个象素需用87.84位最早阐述和实现这种编码的是Shannon（1948年）和Fano（1949年），因此被称为仙农-范诺 （Shannon- Fano）算法。

这种方法采用从上到下的方法进行编码首先按照符号出现的频度 或概率排序，例如，山，月，°和運，如表4-02所示然后使用递归方法分成两个 部分，每一部分具有近似相同的次数，如图4-01所示按照这种方法进行编码得到的总位 数为91压缩比约为1.3 : 1表 4-02 Shannon-Fano 算法举例表符号出现的次数（刃）分配的代码需要的位数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年提出了另一种编码方法，即从下到上的编码方法现仍以一个具 体的例子说明它的编码步骤：1. 初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如表 4-03 和图 4-02 所示2. 把概率最小的两个符号组成一个节点，如图4-02中的D和E组成节点P13. 重复步骤2,得到节点P2、P3和P4,形成一棵“树”，其中的P4称为根节点4. 从根节点 P4 开始到相应于每个符号的“树叶”，从上到下标上“0”(上枝)或者“1”(下 枝)，至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而 代码的平均长度是相同的。

5. 从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码，如表4-03所示6. 按照仙农理论，这幅图像的熵为H(S) = (15/39) X bg2 (39/15) + (7/39) x 砲2 (39/7) + ••- + (5/39) x 砲2 (39/5)= 2.1859 压缩比 1.37:1表 4-03 霍夫曼编码举例符号出现的次数log2(1/pi)分配的代码需要的位数A15(0.3846)1.38015B7(0.1795)2.4810021C6(0.1538)2.7010118D6(0.1538)2.7011018E5(0.1282)2.9611115A(0.3846)B(0.1795)C(0.1538)PlD(0.1538)E(0.1282)图 4-02 霍夫曼编码方法 霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码例如，码串中的第1位为0， 那末肯定是符号A,因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下 一个符号代码的第1位同样，如果出现“110”，那么它就代表符号D如果事先编写出 一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行 译码。

采用霍夫曼编码时有两个问题值得注意：①霍夫曼码没有错误保护功能，在译码时，如果码 串中没有错误，那么就能一个接一个地正确译出代码但如果码串中有错误，哪仅是1位出 现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误传播 (error propagation)计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正 它②霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容,然后再译码， 这就需要在存储代码之前加以考虑尽管如此，霍夫曼码还是得到广泛应用与仙农-范诺编码相比，这两种方法都自含同步码，在编码之后的码串中都不须要另外添加 标记符号，即在译码时分割符号的特殊代码此外，霍夫曼编码方法的编码效率比仙农-范 诺编码效率高一些请读者自行验证4.2 算术编码算术编码在图像数据压缩标准(如JPEG, JBIG)中扮演了重要的角色在算术编码中，消息 用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔 信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含 在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, 0.7)[0.7, 1)如果二进制消息序列的输入为：10 00 11 00 10 11 0 1 编码时首先输入的符号是1 0 ，找 到它的编码范围是［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-05和表 4-06中根据上面所举的例子，可 把计算过程总结如下考虑一个有M个符号务=（12…血[的字符表集，假设概率左他）=处输入符号用©表示，第用个子间隔的范围用表示其中血T和肌=0表示间隔左边界的值，G表示间隔右边界的值,仁=匚一*表示间隔长度编码步骤如下: 步骤1：首先在1和0之间给每个符号分配一个初始子间隔，子间隔的长度等于它的概率初始子间隔的范围用厶=乩片）=[£风」，）表示令&\=F\7\,，=h和应=1步骤2： L和R的二进制表达式分别表示为:9Ji 和其中叫和叫等于“1”或者“0”比较的和呛：①如果叭f，不发送任何数据，转到步骤3；②如果叭〜，就发送二进 制符号的比较旳和巾：①如果迅工匕，不发送任何数据，转到步骤3；②如果叫=巾，就发送二 进制符号盹这种比较一直进行到两个符号不相同为止，然后进入步骤3，步骤3：加1,读下一个符号假设第起个输入符号为心=円，按照以前的步骤把这个间 隔分成如下所示的子间隔：4 =[4-i +^-i^a-i?4-i + 乳一 i 工刃）i-1 2-1令£=打，应=心和％ =q _打，然后转到步骤2。

表 4-05 编码过程步骤输入 符号编码间隔编码判决110[0.5, 0.7)符号的间隔范围[0.5, 0.7）200[0.5, 0.52)[0.5, 0.7）间隔的第一个1/10311[0.514, 0.52)[0.5, 0.52 ）间隔的最后一个1/10400[0.514, 0.5146)[0.514, 0.52)间隔的第一个 1/10510[0.5143, 0.51442)[0.514, 0.5146）间隔的第五个1/10开始，二个1/10611[0.514384,0.51442)[0.5143, 0.51442)间隔的最后 3 个 1/10701[0.5143836,0.514402)[0.514384, 0.51442)间隔的 4 个 1/10，从第 1 个1/10开始8从[0.5143876, 0.514402中选择一个数作为输出：0.5143876表 4-06 译码过程步 骤间隔译码符号译码判决1[0.5, 0.7)100.51439 在间隔[0.5, 0.7)2[0.5, 0.52)000.51439 在间隔[0.5, 0.7)的第 1 个 1/103[0.514, 0.52)110.51439 在间隔[0.5, 0.52)的第 7 个 1/104[0.514, 0.5146)000.51439 在间隔[0.514, 0.52)的第 1 个 1/105[0.5143, 0.51442)100.51439 在间隔[0.514, 0.5146)的第 5 个 1/106[0.514384,0.51442)110.514。