哈夫曼树Huffman tree 又称最优完全二叉树,切入正题之前,先看几个定义
1、路径 Path
简单点讲,路径就是从一个指定节点走到另一个指定节点所经过的分支,比如下图中的红色分支(A->C->B与C->D->E->F)
图1
2、路径长度(Path Length)
即路径中的分支个数,比如上图(a)中的路径长度为2,上图(b)中的路径长度为3
3、结点的权重(Weight of Node)
在一些特定应用中,有时候要刻意区分节点之间的重要程度(或优先程度),比如认为A节点比B节点要重要(更优先),可以给这些节点增加一个int型的属性值weight,用该值来标明这种重要性,这就是结点的权重.
图2
4、结点的带权(重)路径长度(Weight Path Length of Node):
从该节点到树的根节点的路径长度*该结点的权重,得到的结果就是这个东东
上图中
节点1的带权路径长度为 1 * 2 = 2;
节点2的带权路径长度为 2 * 2 = 4;
节点3的带权路径长度为 3 * 2 = 6;
节点4的带权路径长度为 4 * 2 = 8;
5、树的带权(重)路径长度
树中的每个节点均按4中的定义计算自身的带权路径长度,然后把得到的结果加在一起,就是整颗树的带权路径长度。
上图(即图2)中,树的带权路径长度为 2 + 4 + 6 + 8 = 20
如果给定4个节点,其权重值分别是1,2,3,4,那么构造一颗完全二叉树的方法有很多种,如下图:
上图显示,(c)树的带权路径总长最小(为19),而其它树的带权路径均为20,ok,它就是传说中的哈夫曼树,可通俗的理解为:
给定一组带权重的叶节点,用它们来构造完全二叉树,最终整颗树的带权路径(总)长度最小的即为啥夫曼树。(当然,这是根据我的理解给出的民间山寨定义,官方定义大家自己去看“数据结构与算法”这本书吧,上面有一堆数学符号,对于不喜欢数字的同学们,估计看起来很晕)
啥夫曼树的构造算法:
1、在给定的带权叶节点中,找出权重最小的二个(通常为了方便,可以先将叶节点按权重从小到大先排好,这样只需要取前面二项即可),然后添加一个临时节点作为这二个节点的父节点(其权重为这二个叶节点的权重之合)
2、将刚才处理过的二个节叶点去掉,然后把新增加的临时节点与剩下的叶节点放在一起做同样的处理,即:从新节点和叶节点的集合中,继续找到权重最小的二个,再继续增加新节点,做第1中的处理
3、重复以上过程,直到每个叶节点都处理完。
假如我们现在有权重为1,2,3,4的一组叶节点,上述过程图解为:
c#的算法实现:
先回顾上一篇提到的二个重要知识点:
1、由二叉树的数学特性4知:
对于一棵非空二叉树,如果度为0的结点数目为x,度为2的结点数目为y,则有 x = y +1(即y = x-1)
也就是说全部节点总数为 x+y = x + (x-1) = 2*x-1
2、完全二叉树,可以方便的使用顺序存储(即用线性结构的数组或List<T>来存储)
Huffman树的节点类Node.cs:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace 哈夫曼树
{
public class Node
{
private int weight;//权重值
private int lChild;//左子节点的序号
private int rChild;//右子节点的序号
private int index;//本节点的序号
public int Weight
{
get { return weight; }
set { weight = value; }
}
public int LChild
{
get { return this.lChild; }
set { lChild = value; }
}
public int RChild
{
get { return this.rChild; }
set { rChild = value; }
}
public int Index
{
get { return this.index; }
set { index = value; }
}
public Node()
{
weight = 0;
lChild = -1;
rChild = -1;
index = -1;
}
public Node(int w, int lc, int rc, int p)
{
weight = w;
lChild = lc;
rChild = rc;
index = p;
}
}
}
HuffmanTree.cs(注:下面这段代码的Create算法在运行效率上也许并非最高的,但很容易理解)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace 哈夫曼树
{
public class HuffmanTree
{
private List<Node> _tmp;
private List<Node> _nodes;
public HuffmanTree(params int[] weights)
{
if (weights.Length < 2)
{
throw new Exception("叶节点不能少于2个!");
}
int n = weights.Length;
Array.Sort(weights);
//先生成叶子节点,并按weight从小到大排序
List<Node> lstLeafs = new List<Node>(n);
for (int i = 0; i < n; i++)
{
var node = new Node();
node.Weight = weights[i];
node.Index = i;
lstLeafs.Add(node);
}
//创建临时节点容器
_tmp = new List<Node>(2 * n - 1);
//真正存放所有节点的容器
_nodes = new List<Node>(_tmp.Capacity);
_tmp.AddRange(lstLeafs);
_nodes.AddRange(_tmp);
}
/// <summary>
/// 构造Huffman树
/// </summary>
public void Create()
{
while (this._tmp.Count > 1)
{
var tmp = new Node(this._tmp[0].Weight + this._tmp[1].Weight, _tmp[0].Index, _tmp[1].Index, this._tmp.Max(c => c.Index) + 1);
this._tmp.Add(tmp);
this._nodes.Add(tmp);
//删除已经处理过的二个节点
this._tmp.RemoveAt(0);
this._tmp.RemoveAt(0);
//重新按权重值从小到大排序
this._tmp = this._tmp.OrderBy(c => c.Weight).ToList();
}
}
/// <summary>
/// 测试输出各节点的关键值(调试用)
/// </summary>
/// <returns></returns>
public override string ToString()
{
StringBuilder sb = new StringBuilder();
for (int i = 0; i < _nodes.Count; i++)
{
var n = _nodes[i];
sb.AppendLine("index:" + i + ",weight:" + n.Weight.ToString().PadLeft(2, ' ') + ",lChild_index:" + n.LChild.ToString().PadLeft(2, ' ') + ",rChild_index:" + n.RChild.ToString().PadLeft(2, ' '));
}
return sb.ToString();
}
}
}
测试一下:
using System;
namespace 哈夫曼树
{
class Program
{
static void Main(string[] args)
{
HuffmanTree tree = new HuffmanTree(2,1,4,3);
tree.Create();
Console.WriteLine("最终树的节点值如下:");
Console.WriteLine(tree.ToString());
Console.ReadLine();
}
}
}
输出结果如下:
最终树的节点值如下: index:0,weight: 1,lChild_index:-1,rChild_index:-1 index:1,weight: 2,lChild_index:-1,rChild_index:-1 index:2,weight: 3,lChild_index:-1,rChild_index:-1 index:3,weight: 4,lChild_index:-1,rChild_index:-1 index:4,weight: 3,lChild_index: 0,rChild_index: 1 index:5,weight: 6,lChild_index: 2,rChild_index: 4 index:6,weight:10,lChild_index: 3,rChild_index: 5
输出结果也许并不直观,对照下面这张图就明白了
哈夫曼编码(Huffman Encoding)
先扯貌似不相干的话题,在电报传输中,通常要对传输的内容进行编码(因为电报发送时只用0,1表示,所以需要将ABCDE这类字符最终变成0与1的组合,这就涉及到如何将字符集[A-Z]与[0,1]组合一一对应的问题)
假设现在有电文内容:AAAABBBCCD 需要编码后转送,现在要一套编码方案
首先很容易想到下面的这种定长编码方案,每个字符用2位数字表示,比如:
A->00 B->01 C->10 D->11 那么AAAABBBCCD最终的编码为00,00,00,00,01,01,01,10,10,11(注:这里加逗号是为了看得更直观,实际编码中并不需要)
但电报砖家们,提出了另一种更短的不定长编码方案:
A->0 B->10 C->111 D->110
按这种编码方案,AAAABBBCCD最终的编码为:0,0,0,0,10,10,10,111,111,110
把这二种方案的编码列在一起对比一下:
00,00,00,00,01,01,01,10,10,11 (不算逗号共20位)
0,0,0,0,10,10,10,111,111,110 (不算逗号共19位)
砖家果然是砖家! 仔细分析一下,会发现这种“不定长”的编码方案要想解码成功,要有一个重要的前提:任何一个编码,都不能是其它编码的前缀!否则解码时就会出现歧义。
比如:如果C编码为10,D编码为101,A编码为1,B编码为01
现在接收到了一个 10101,那么到底是解码为 CCA,还是DB呢?
现在揭晓哈夫曼编码的秘密:
就刚才举例的AAAABBBCCD而言,电文中仅包含A,B,C,D这个字符,如果把它们看作叶节点,并且考虑到权重(D出现次数最小,权重认为最低;C出现次数比D高,因此权重高于D,其它类推),这样我们就有了一组带权重的叶节点(A-权重4,B-权重3,C-权重2,D-权重1),用它们来构造一颗哈夫曼树:
同时,我们把有分支做一个约定:向左的分支对应为数字0,向右的分支对应为数字1,这样从根节点到每个叶子节点的路径就能得到一串数字。
即: A->0,B->10,C->110,D->111 ,这就是一种编码!
另外应该注意到,对于二叉树,某一个确定的叶节点只可能在一个唯一的分支上(即不可能一个叶节点即在这个分支上,又在其它分支上),这就保证了每个叶节点得到的编码都不可能是其它编码的前缀。
OK,寻找哈夫曼编码的问题最终就转化成了哈夫曼树的构造问题,问题得到解决了。(学会了哈夫曼编码,也许我们能跟某些冰雪聪明的MM们玩点另类告白的小游戏,发一串数字过去,然后配一张图,看她懂不懂你的心意,如果她能成功解出背后的含义是ILOVEYOU,然后回发一串吉祥数字给你,那么...恭喜你!)