Huffman编码原理

新客网 XKER.COM 2003-07-12 来源：收藏本文

Huffman
我们这里指的Huffman不是一个人，而是一编码方法，我们不要被一个个的名词给吓坏了，这就是把一些字母或什么东西表示成二进制的方法。Huffman于1952年提出了这种方法，开始主要用于电报报文的编码，常用的英文字母E，T应该如何编码，不常用的应该如何编码，这样编下来使报文最短。我们下面举一个例子：有了例子，我们就可以看清楚了。
如果几个字母的使用率如下表所示：那么得出的编码应该如表后面所附的值。

a	7	0
b	5	10
c	2	110
d	4	111

Huffman编码构造过程

下面几个图可以看到Huffman编码的构造过程是一个反复比较的过程，它总是选择两个使用频率较小的结点进行合并，生成出一个树，这个树经过编码后就会得到Huffman编码。

在上图中各点中的数字代表各点的使用次数，您可以把这几个方块想成A，B，C，D，它们在某一文章中的使用频率为7次，5次，1次等等。

选择使用率小的两个点1，3构成新点4。

在状态1图中选择5，4（也是两个最小的，注意不是1，3，因为1，3现在已经归在4里面了）进行合并。

在状态2表中的最小两个点已经变为7，6了，这时合并它们两个生成新点13。

只剩两个点了，不管多少它们也是最小的了，合并了算了。

请注意这个编码，每个点下面有两个分枝，分别编码为0，1，当然这是为了方便计算机及其它数字设备使用，您也可以编码为“张三”和“李四”。至此编码结束，所得到编码即从最上面的点延线下行，至所要编码的点，将沿路经过的0和1记录下来就是了。现在您应该明白为什么总是先把小的合并了吧，因为先合并的会在最下面，编码长度最长，而先合并的也是最不常使用的，因此编码长度最长也是应该的。

7	11
6	10
5	00
3	011
1	010

上一篇：浅谈图像压缩算法（好文章。看看吧。再别说不了解JPG的原理了）下一篇：Huffman 编码简介（讲解的更好一些，有C的分析）

【收藏】【评论】【推荐】【投稿】【打印】【关闭】