霍夫曼编码.doc

仙农-范诺编码 仙农-范诺编码算法需要用到下面两个基本概念：1. Entropy(熵)的概念(1) 熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。(2) 某个事件的信息量用Ii=-log2pi表示， 其中pi为第 个事件的概率，0pi12. 信源S的熵的定义按照仙农(Shannon)的理论，信源S的熵定义为 : 其中pi是符号si在S中出现的概率；log2(1/pi)表示包含在si中的信息量，也就是编码si所需要的位数。例如，一幅用256级灰度表示的图像，如果每一个像素点灰度的概率均为pi=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位。 符号在图像中出现的数目符 号ABCDE出现的次数157765按照仙农理论，这幅图像的熵为H(S)=(15/40)log2(40/15) + (7/40)log2(40/7) + + (5/40) log2(40/5)=2.196这就是说每个符号用2.196位表示，40个像素需用87.84位。最早阐述和实现这种编码的是Shannon(1948年)和Fano(1949年)，因此被称为仙农-范诺(Shannon- Fano)算法。这种方法采用从上到下的方法进行编码。首先按照符号出现的频度或概率排序，例如，A，B，C，D和E，如下表所示。然后使用递归方法分成两个部分，每一部分具有近似相同的次数，如图所示。按照这种方法进行编码得到的总位数为91，实际的压缩比约为1.32(120/911.32) : 1。 Shannon-Fano算法举例表符号出现的次数(pi)log2(1/pi)分配的代码需要的位数A15 (0.375)1.41500030B7 (0.175)2.51450114C7 (0.175)2.51451014D6 (0.150)2.736911018E5 (0.125)3.000011115仙农-范诺算法编码举例赫夫曼编码赫夫曼(Huffman)在1952年提出了另一种编码方法，即从下到上的编码方法。现仍以一个具体的例子说明它的编码步骤：(1) 初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如下表和下图所示。(2) 把概率最小的两个符号组成一个节点，如下图中的D和E组成节点P1。(3) 重复步骤2，得到节点P2、P3和P4，形成一棵“树”，其中的P4称为根节点。(4) 从根节点P4开始到相应于每个符号的“树叶”，从上到下标上“0”(上枝)或者“1”(下枝)，至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。(5) 从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码，如下表所示。(6) 按照仙农理论，这幅图像的熵为H(S)=(15/39)log2(39/15) + (7/39)log2(39/7) + + (5/39)log2(39/5)=2.1859 2.18593985.2501 压缩比1.34:1，(117/87=1.344828)。 赫夫曼编码举例符号出现的次数(pi)log2(1/pi)分配的代码需要的位数A15(0.3846)1.38015B7(0.1795)2.4810021C6(0.1538)2.7010118D6(0.1538)2.7011018E5(0.1282)2.9611115赫夫曼编码方法赫夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。例如，码串中的第1位为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码。赫夫曼码得到广泛应用