|
香农-范诺编码算法需要用到下面两个基本概念：
1. Entropy(熵)的概念
熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，
数学上就是概率越小。
某个事件的信息量用表示 ， 其中为第个事件的概率，
2. 信源S的熵的定义
按照仙农(Shannon)的理论，信源S的熵定义为
其中是符号在S中出现的概率；表示包含在中的信息量，也就是编码所需要的位数。例如
，一幅用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 符号在图像中出现的数目
符 号
出现的次数
15
7
7
6
6
5
按照仙农理论，这幅图像的熵为
H(S) = (15/40) ′ (40/15) + (7/40) ′ (40/7) + ? ? ? + (5/40) ′ (40/5)
=2.1
96
这就是说每个符号用2.196位表示，40个象素需用87.84位。
最早阐述和实现这种编码的是Shannon(1948年)和Fano(1949年)，因此被称为仙农-范诺
(Shannon- Fano)算法。这种方法采用从上到下的方法进行编码。首先按照符号出现的频
度或概率排序，例如，，，，和，如表4-02所示。然后使用递归方法分成两个部分，每
一部分具有近似相同的次数，如图4-01所示。按照这种方法进行编码得到的总位数为91
。压缩比约为1.3 : 1。
表4-02 Shannon-Fano算法举例表
符号
出现的次数()
分配的代码
需要的位数
A
15 (0.375)
1.4150
00
30
B
7 (0.175)
7 (0.175)
2.5145
01
14
C
7 (0.175)
2.5145
10
14
D
6 (0.150)
2.7369
110
18
E
5 (0.125)
3.0000
111
15
图4-01 香农-范诺算法编码举例
4.1.2 霍夫曼编码
霍夫曼(Huffman)在1952年提出了另一种编码方法，即从下到上的编码方法。现仍以一个
具体的例子说明它的编码步骤：
初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如表4-03和图4-02所示
。
把概率最小的两个符号组成一个节点，如图4-02中的D和E组成节点P1。
重复步骤2，得到节点P2、P3和P4，形成一棵“树”，其中的P4称为根节点。
从根节点P4开始到相应于每个符号的“树叶”，从上到下标上“0”(上枝)或者“1”(下
枝)，至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而
代码的平均长度是相同的。
从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码，如表4-03所示。
按照仙农理论，这幅图像的熵为
H(S) = (15/39) ′ (39/15) + (7/39) ′ (39/7) + ? ? ? + (5/39) ′ (39/5)
= 2.
1859
压缩比1.37:1。
表4-03 霍夫曼编码举例
符号
出现的次数
log2(1/pi)
分配的代码
需要的位数
A
15(0.3846)
1.38
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)。计算机对这种错误也无能为力，说不出错在哪里，更
谈不上去纠正它。②霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的
内容，然后再译码，这就需要在存储代码之前加以考虑。尽管如此，霍夫曼码还是得到
广泛应用。
与仙农-范诺编码相比，这两种方法都自含同步码，在编码之后的码串中都不须要另外添
加标记符号，即在译码时分割符号的特殊代码。此外，霍夫曼编码方法的编码效率比仙
农-范诺编码效率高一些。请读者自行验证。
|
