关于huffman树的理解

---

Huffman数

路径和路径长度

在一棵树中，从一个节点往下可以达到的孩子或孙子节点之间的通路，称为 路径 。通路中分支的数目称为 路径长度。若规定根节点的层号为1， 则从根节点到第L层节点的路径长度为 L-1 。

节点的权和带权路径长度

若为树中节点赋予一个具有某种含义的(非负)数值，则这个数值称为该节点的 权。节点的 带权路径长度 是指，从根节点到该节点之间的路径长度与该节点的权的乘积。

树的带权路径长度

树的带权路径长度 规定为所有叶子节点的带权路径长度之和。

二叉树 是每个节点最多有两个子树的有序树。两个子树通常被称为“左子树”和“右子树”, 定义中的“有序”是指两个子树有左右之分，顺序不能颠倒。

给定 n 个权值作为n个叶子节点，构造一棵二叉树，若它的带权路径长度达到做小，则称这样的二叉树为 最优二叉树， 也成为 Huffman树。

例1: 给定4个叶子节点a, b, c 和 d, 分别带权 7, 5, 2 和 4，如下图所示

根据树的带权路径长度的定义，从左到右，三棵树的带权路径长度分别为:

• 7∗2+5∗2+2∗2+4∗2=36$$7\ast 2+5\ast 2+2\ast 2+4\ast 2=36$$
• 7∗3+5∗3+4∗2+2∗1=46$$7\ast 3+5\ast 3+4\ast 2+2\ast 1=46$$
• 7∗1+5∗2+4∗3+2∗3=35$$7\ast 1+5\ast 2+4\ast 3+2\ast 3=35$$

从上面的例子中，我们可以看到当权重越小的节点离根节点越远，而权重越大的节点离根节点越近时，得到树的带权路径长度会越小。从这个想法出发，则构造Huffman树的方法就很容易想出来了。

Huffman树构造

给定 n 个权值{ω1,ω2,…,ωn}$\{{\omega }_1,{\omega }_2,\dots ,{\omega }_n\}$作为二叉树的 n$n$个叶子节点，可以通过以下的算法构造一棵Huffman树。

Huffman树构造算法:

1. 将 {ω1,ω2,…,ωn}$\{{\omega }_1,{\omega }_2,\dots ,{\omega }_n\}$看成是有 n 棵树的森林(每棵树仅有一个节点)
2. 在森林中选出两个根节点的权值最小的树合并，作为一个新树的左右子树，且新树的根节点权值为其左右子树根节点的权值之和
3. 从森林中删除选取的两棵树，并将新树加入森林
4. 重复步骤2、3，直到森林中只剩一棵树为止，该树即为所求的Huffman树。

备注: 这个Huffman树的构造算法，是每次都选择权值最小的树合并，然后一步步的达到根节点，其实，也是将权值越小的节点离根节点越远，权值越大的节点离根节点越近。

Huffman树示例

例2: 假设在2014年世界杯期间，从新浪微博中抓取了若干条与足球相关的微博，经统计，“我”、“喜欢”、“观看”、“巴西”、“足球”、“世界杯”这六个词出现的次数分别为15, 8, 6, 5, 3, 1. 请以这6个词为叶子节点，以相应词频当权值，构造一棵Huffman树。

图1. Huffman树的构造实例

Huffman编码

在例2以及图1中，我们介绍了构造Huffman树的方法，这里，我们介绍一下Huffman编码。我们仍然以例2的数据为例。

在图1的例子中，我们约定（词频较大的）左孩子节点编码为1，（词频较小的）右孩子编码为0，这样一来，“我”，“喜欢”，“观看”，“巴西”，“足球”，“世界杯”这六个子的Huffman编码分别为 0, 111, 110, 101, 1001, 1000.

图2. Huffman编码

Huffman编码的用处

我们上面讲了Huffman树和Huffman编码，但是Huffman树和Huffman编码到底有什么用户呢？

这里，我们引用下面的例子进行理解。

在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符.例如,需传送的报文为“AFTER DATA EAR ARE ART AREA”,这里用到的字符集为“A,E,R,T,F,D”,各字母出现的次数为{8,4,5,3,1,1}.现要求为这些字母设计编码.要区别6个字母,最简单的二进制编码方式是等长编码,固定采用3位二进制,可分别用000、001、010、011、100、101对“A,E,R,T,F,D”进行编码发送,当对方接收报文时再按照三位一分进行译码.显然编码的长度取决报文中不同字符的个数.若报文中可能出现26个不同字符,则固定编码长度为5.然而,传送报文时总是希望总长度尽可能短.在实际应用中,各个字符的出现频度或使用次数是不相同的,如A、B、C的使用频率远远高于X、Y、Z,自然会想到设计编码时,让使用频率高的用短码,使用频率低的用长码,以优化整个报文编码.

上面的这个例子说明了一个问题，就是说Huffman编码具有压缩的功能。这里怎么理解“压缩”呢？也就是说，当我们使用编码的形式表示字母时，有些字母的出现频率非常大，而另外一些字母的出现频率却偏小，如果出现频率高的字符的编码比频率低的字符的编码短，那么对于一段相同的字符串，我们就可以使用更短的编码表示这个字符串。而要完成这个目的，就需要首先构建Huffman树，然后通过Huffman树得到每个字符的Huffman编码。