第4章无损数据压缩 (5)从根节点P开始顺着树枝到每个叶子分别写出每个符号的代码,如表4-03所示。 (6)按照仙农理论,这幅图像的熵为 BS)=(15/39)×bg2(39/15)+(7/39)xkog2(39/7)+…+(5/39)x bog2(39/5)=2.1859 压缩比1.37:1 表4-03赫夫曼编码举例 符号出现的次数|1og2(1/p)分配的代码需要的位数 A15(0.3846 15 B7(0.1795)2.48 C6(0.1538) 2.70 101 D6(0.1538270 110 E5(0.1282) 2.96 111 A(0.3846) 0 B(0.1795) c015381P2 D(01538)-0 E(0.1282) PI 图4-02赫夫曼编码方法 赫夫曼码的码长虽然是可变的,但却不需要另外附加同步代码。例如,码串中的第1位 为0,那末肯定是符号A,因为表示其他符号的代码没有一个是以0开始的,因此下一位就表 示下一个符号代码的第1位。同样,如果出现“110”,那么它就代表符号D。如果事先编写 出一本解释各种代码意义的“词典”,即码簿,那么就可以根据码簿一个码一个码地依次进 行译码 采用赫夫曼编码时有两个问题值得注意:①赫夫曼码没有错误保护功能,在译码时,如 果码串中没有错误,那么就能一个接一个地正确译出代码。但如果码串中有错误,哪怕仅仅 是1位出现错误,不但这个码本身译错,更糟糕的是一错一大串,全乱了套,这种现象称为 错误传播( error propagation)。计算机对这种错误也无能为力,说不出错在哪里,更谈不 上去纠正它。②赫夫曼码是可变长度码,因此很难随意查找或调用压缩文件中间的内容,然 后再译码,这就需要在存储代码之前加以考虑。尽管如此,赫夫曼码还是得到广泛应用。 与仙农一范诺编码相比,这两种方法都自含同步码,在编码之后的码串中都不须要另外 加标记符号,即在译码时分割符号的特殊代码。此外,赫夫曼编码方法的编码效率比仙农 范诺编码效率高一些。请读者自行验证。 4.2算术编码 算术编码在图像数据压缩标准(如JPEG,JBIG)中扮演了重要的角色。在算术编码中,消 息用0到1之间的实数进行编码,算术编码用到两个基本的参数:符号的概率和它的编码间隔 信源符号的概率决定压缩编码的效率,也决定编码过程中信源符号的间隔,而这些间隔包含第4章 无损数据压缩 3 (5) 从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码，如表4-03所示。 (6) 按照仙农理论，这幅图像的熵为 H(S) = (15/39)  2 log (39/15) + (7/39)  2 log (39/7) +  + (5/39)  2 log (39/5) = 2.1859 压缩比1.37:1。 表4-03 赫夫曼编码举例 符号 出现的次数 log2(1/pi) 分配的代码 需要的位数 A 15(0.3846) 1.38 0 15 B 7(0.1795) 2.48 100 21 C 6(0.1538) 2.70 101 18 D 6(0.1538) 2.70 110 18 E 5(0.1282) 2.96 111 15 图4-02 赫夫曼编码方法 赫夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。例如，码串中的第1位 为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表 示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写 出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进 行译码。 采用赫夫曼编码时有两个问题值得注意：①赫夫曼码没有错误保护功能，在译码时，如 果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅仅 是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为 错误传播(error propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不 上去纠正它。②赫夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然 后再译码，这就需要在存储代码之前加以考虑。尽管如此，赫夫曼码还是得到广泛应用。 与仙农-范诺编码相比，这两种方法都自含同步码，在编码之后的码串中都不须要另外 添加标记符号，即在译码时分割符号的特殊代码。此外，赫夫曼编码方法的编码效率比仙农 -范诺编码效率高一些。请读者自行验证。 4.2 算术编码 算术编码在图像数据压缩标准(如JPEG，JBIG)中扮演了重要的角色。在算术编码中，消 息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。 信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含