哈夫曼编码原理
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/23 06:09:55
哈夫曼编码原理
哈夫曼编码原理
哈夫曼编码原理
霍夫曼（Huffman）编码属于码词长度可变的编码类,是霍夫曼在1952年提出的一种编码方法,即从下到上的编码方法.同其他码词长度可变的编码一样,可区别的不同码词的生成是基于不同符号出现的不同概率.生成霍夫曼编码算法基于一种称为“编码树”（coding tree）的技术.算法步骤如下：
（1）初始化,根据符号概率的大小按由大到小顺序对符号进行排序.
（2）把概率最小的两个符号组成一个新符号（节点）,即新符号的概率等于这两个符号概率之和.
（3）重复第2步,直到形成一个符号为止（树）,其概率最后等于1.
（4）从编码树的根开始回溯到原始的符号,并将每一下分枝赋值为1,上分枝赋值为0.
以下这个简单例子说明了这一过程.
1)．字母A,B,C,D,E已被编码,相应的出现概率如下：
p(A)=0.16,p(B)=0.51,p(C)=0.09,p(D)=0.13,p(E)=0.11
2)．C和E概率最小,被排在第一棵二叉树中作为树叶.它们的根节点CE的组合概率为0.20.从CE到C的一边被标记为1,从CE到E的一边被标记为0.这种标记是强制性的.所以,不同的哈夫曼编码可能由相同的数据产生.
3)．各节点相应的概率如下：
p(A)=0.16,p(B)=0.51,p(CE)=0.20,p(D)=0.13
D和A两个节点的概率最小.这两个节点作为叶子组合成一棵新的二叉树.根节点AD的组合概率为0.29.由AD到A的一边标记为1,由AD到D的一边标记为0.
如果不同的二叉树的根节点有相同的概率,那么具有从根到节点最短的最大路径的二叉树应先生成.这样能保持编码的长度基本稳定.
4)．剩下节点的概率如下：
p(AD)=0.29,p(B)=0.51,p(CE)=0.20
AD和CE两节点的概率最小.它们生成一棵二叉树.其根节点ADCE的组合概率为0.49.由ADCE到AD一边标记为0,由ADCE到CE的一边标记为1.
5)．剩下两个节点相应的概率如下：
p(ADCE)=0.49,p(B)=0.51
它们生成最后一棵根节点为ADCEB的二叉树.由ADCEB到B的一边记为1,由ADCEB到ADCE的一边记为0.
6)．图03-02-2为霍夫曼编码.编码结果被存放在一个表中：
w(A)=001,w(B)=1,w(C)=011,w(D)=000,w(E)=010
图03-02-2 霍夫曼编码例
霍夫曼编码器的编码过程可用例子演示和解释.
下面是另一个霍夫曼编码例子.假定要编码的文本是：
"EXAMPLE OF HUFFMAN CODE"
首先,计算文本中符号出现的概率（表03-02-2）.
表03-02-2 符号在文本中出现的概率
符号
概率
E
2/25
X
1/25
A
2/25
M
2/25
P
1/25
L
1/25
O
2/25
F
2/25
H
1/25
U
1/25
C
1/25
D
1/25
I
1/25
N
2/25
G
1/25
空格
3/25
最后得到图03-02-3所示的编码树.
图03-02-3 霍夫曼编码树
在霍夫曼编码理论的基础上发展了一些改进的编码算法.其中一种称为自适应霍夫曼编码（Adaptive Huffman code）.这种方案能够根据符号概率的变化动态地改变码词,产生的代码比原始霍夫曼编码更有效.另一种称为扩展的霍夫曼编码（Extended Huffman code）允许编码符号组而不是单个符号.
同香农-范诺编码一样,霍夫曼码的码长虽然是可变的,但却不需要另外附加同步代码.这是因为这两种方法都自含同步码,在编码之后的码串中都不需要另外添加标记符号,即在译码时分割符号的特殊代码.当然,霍夫曼编码方法的编码效率比香农-范诺编码效率高一些.
采用霍夫曼编码时有两个问题值得注意：①霍夫曼码没有错误保护功能,在译码时,如果码串中没有错误,那么就能一个接一个地正确译出代码.但如果码串中有错误,那怕仅仅是1位出现错误,也会引起一连串的错误,这种现象称为错误传播(error propagation).计算机对这种错误也无能为力,说不出错在哪里,更谈不上去纠正它.②霍夫曼码是可变长度码,因此很难随意查找或调用压缩文件中间的内容,然后再译码,这就需要在存储代码之前加以考虑.尽管如此,霍夫曼码还是得到广泛应用.