赫夫曼

浅浅的花香味﹌ 2022-08-07 13:50 150阅读 0赞

在数据膨胀.信息爆炸的今天,数据压缩的意义不言而喻!

谈到数据压缩,就不能提赫夫曼(Huffman)编码,赫夫曼编码是首个实用的压缩编码方案,即使在今天的许多知名压缩算法里,依然可以见到赫夫曼编码的影子!

另外,在数据通信中,用二进制给每个字符进行编码时不得不面对的一个问题是如何使用电文总长度最短且不产生二义性。根据字符出现频率，利用赫夫曼编码可以构造一种不等长的二进制，使编码后的电文长度最短，且保证不产生二义性。

介绍赫夫曼编码前，我们必须得介绍赫夫曼树。

什么叫赫夫曼树呢？我们先来看一个例子。

以下程序在效率上有什么问题呢？

if(a<60)
    	printf("不及格");
    else if(a<70)
    	printf("及格");
    else if(a<90)
    	printf("良好");
    else
    	printf("优秀");

![20150413223754112][]

从上图可以分析得到，基本上70-89的情况占有70%，所以上面的算法并不是最有效的，下图进行了优化:

![20150413223844937][]

赫夫曼树定义与原理:

结点的路径长度:

从根结点到该结点的路径上的连接数.

![20150413224353849][]从根结点走到C结点的连接数是:3

树的路径长度:

树种每个叶子节点的路径长度之和。

如下图：

A=1，B=2，C=3，D=3，所以共=9

![20150413224742124][]

结点带权路径长度：

结点的路径长度与结点的权值的乘积。

C：3\*70=210

![20150413224353849][]

树的带权路径长度：

WPL（Weighted Path Length）是树中所有叶子节点的带权路径长度之和！

如下图：

A：1\*5=5，B：2\*15=30，C：3\*70=210，D：3\*10=30，共：275

![20150413224742124][]

生成赫夫曼树过程：

![20150413235548102][]

![20150413235700237][]

![20150413235749751][]

最后如果需要阅读赫夫曼代码和结合编码和解码的实现，推荐看小甲鱼数据结构：

53赫夫曼编码C语言实现.zip

[20150413223754112]: /images/20220805/8f2ae08af49249149f8733d0b56d0be3.png
[20150413223844937]: /images/20220805/f3e7e9f9d78243f6bd1c830417c37ee8.png
[20150413224353849]: /images/20220805/05de218c80e84481877e2cbb920ea085.png
[20150413224742124]: /images/20220805/844cb69790a249d69479084cd85a4c5e.png
[20150413235548102]: /images/20220805/9c3d12717d1643a8a1b455bae692e6d6.png
[20150413235700237]: /images/20220805/8a5913acb7eb4efb81e2f6d2d3f9ae4d.png
[20150413235749751]: /images/20220805/ced0b86311c641e0946070e8f5a70404.png