一、哈夫曼树
美国数学家哈夫曼在1952年发明了哈夫曼编码, 为了纪念他的成就, 于是就在他在编码中用到的二叉树称之为哈夫曼树, 用到的编码称之为哈夫曼编码.
什么叫做哈夫曼树呢? 先来看一个例子. 在学校的时候, 学校会为了避免一些人以分取人的观念, 就将分数转换为了优秀、良好、中等、及格、不及格这几个概念. 为了准备的划分这几个分类, 会根据成绩做一个划分标准.
用代码来实现就是:
if (score < 60) {
printf("不及格");
} else if (score < 70) {
printf("及格");
} else if (score < 80) {
printf("中等");
} else if (score < 90) {
printf("良好");
} else {
printf("优秀");
}
这样看上去是没什么问题, 但是好的试卷应该是让学生的成绩大部分分布在中等良好的点过范围, 优秀和不及格应该是少数的. 而这个程序中, 分布最多的位置判断至中等良好,都需要经过三四次判断处理才能得到. 这样的话效率就会变低很多.
既然分数大部分分布在中等良好的地方, 那我们就把良好中等的判断进行提前判断:
这样的话效率应该就会提高一些.
二、哈夫曼树定义与原理
先来给学生的数据定制一个百分比.
- 不及格 5%
- 及格 15%
- 中等 40%
- 良好 30%
- 优秀 10%
将上述转化为二叉树的形式:
哈夫曼树定义的路径长度: 从树中一个节点到另一个节点之间的分支构成两个节点之间的路径, 路径上的分支数目称之为路径长度.
所以上面的A路径为3 B为3 C为2 D为2 E为2
树的路径长度就是树根到每一个节点的长度只和, 所以上面的树的长度为: 3+3+2+1+2+1+2+2=16(中序算)
如果考虑到带权重的节点, 节点的带权路径长度为该节点到树根之间的路径长度与节点上权重的乘积. 树的带权路径长度为树中所有的叶子节点的带权路径长度只和. 带权重的路径长度WPL最小的二叉树称之为哈夫曼树
有了哈夫曼树的定义, 来算一下上面的树的WPL值: 3 * 5 + 3 * 15 + 2 * 40 + 2 * 30 + 2 * 10 = 220
那么现在剩下的问题就是, 上面的二叉树是如何构造出来的.
哈夫曼已经做出来解决的办法:
- 先把有权值的叶子节点按照从小到大的顺序排列, 即: A5 E10 B15 D30 C40
- 取头两个最小权值的节点作为一个新节点 N1 的两个子节点, 相对较小的为左孩子, 另外一个为右孩子.
- 将 N1 替换到有序排列中 即: N1(15) B15 D30 C40
- 重复步骤2、3, 得到N2, 即 N2(30) D30 C40
- 最终得到一个N4的节点, 如下
此时路径长度为: 40 * 1 + 30 * 2 + 15 * 3 + 4 * 10 + 4 * 5 = 205, 得到的WPL值更小了
总结一下哈夫曼算法描述:
- 根据给定的n个权值{w1, w2 ....}构成n棵二叉树的集合{T1, T2, .....}, 其中每棵二叉树T[i]中只有一个带权为w[i]根节点, 且左右子树为空
- 在所有节点F中选择两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树, 且新的二叉树的根节点的权值为其左右子树的权值之和
- 在F中删除选中的两个节点, 把新的节点放入F中
- 重复 2 3步骤, 直到F中只有一个二叉树, 这个就是哈夫曼树
三、哈夫曼编码
哈夫曼研究的这种最优数目的就为了解决当年远距离通信(主要为电报)的数据传输的最优化问题.
例如: 我们需要将 ABCDEF 这段内容用网络发送出去, 正常情况下我们就需要将它转化为二进制来表示. 设定 ABCDEF分别代表012345, 用二进制表示就是:
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 000 | 001 | 010 | 011 | 100 | 101 |
接收方可以按照3位一分来译码. 如果内容过长, 这段二进制也是非常大的数据. 不论是任何语言, 每一个语言单位出现的频率是不太相同的. 假设ABCDEF中, 它们出现的频率分别为:
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 27 | 8 | 15 | 15 | 30 | 5 |
合起来就是100%. 那么我们就可以用哈夫曼树来规划它们:
根据根节点到每一个叶子节点到路径可以分为:
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 01 | 1001 | 101 | 00 | 11 | 1000 |
根绝上面的二进制:
- 000 001 010 011 100 101 (二进制18位)
- 01 1001 101 00 11 1000 (哈夫曼编码17位)
可以很明显的看到需要使用的数据长度短了一丢丢.
我们来换一段数据, 例如: BADCADFEED
- 001 000 011 010 000 011 101 100 100 011 (二进制30位)
- 1001 01 00 101 01 00 1000 11 11 00 (哈夫曼编码25位)
节省了大概17%的存储空间. 随着文本的增多与权重不同, 这种压缩会更加的突出优势.
当我们收到了哈夫曼编码, 该如何去翻译出来呢? 其实我们仔细观察. 一位一位的去走哈夫曼树, 1001可以找到B, 10010不存在, 那么第一个数据就是B, 继续01找到A, 010不存在, 那么第二个字符就是A, 以此类推得到数据.
其实把一棵哈夫曼树的左分支设为0, 右分支设为1, 得到的从根节点到各个叶子节点的路径组成的序列就是哈夫曼编码.
三、哈夫曼编码代码实现
3.1、哈夫曼树的实现
先来定义一棵哈夫曼树:
const int MaxValue = 10000;//初始设定的权值最大值
const int MaxBit = 4;//初始设定的最大编码位数
const int MaxN = 10;//初始设定的最大结点个数
typedef struct HaffNode{
int weight;//权重
int flag;//标记(是否合并到哈夫曼树中)
int parent;//父节点
int leftChild;//左子树
int rightChild;//右子树
}HaffNode;
实现分析:
- 把所有的权重全部分配到哈夫曼树中, 最终的哈夫曼树的节点个数为 权重的个数 * 2 - 1
- 通过循环判断来获得两个最小的权重
- 生成一个新的哈夫曼树, 将这颗树的权重设为两个最小权重的和, 左右孩子分别设置为这两个最小权重的树
- 将两个最小权重的树的父节点设置为新的哈夫曼树, 并设置标记, 代表下次遍历不在遍历这两个节点
- 将新的哈夫曼树加入到初始的哈夫曼树中
void haffman(int weight[], int n, HaffNode *haffTree) {
//初始化哈夫曼树
for (int i = 0; i < 2 * n - 1; i++) {
if (i < n) {
//此时代表的是叶子节点
haffTree[i].weight = weight[i];
} else {
//此时代表的非叶子节点
haffTree[i].weight = 0;
}
haffTree[i].parent = 0;
haffTree[i].flag = 0;
haffTree[i].leftChild = -1;
haffTree[i].rightChild = -1;
}
//遍历非叶子节点
int m1;//记录最小的权重
int m2;//记录第二小的权重
int x1;//记录最小权重的节点下标
int x2;//记录第二小权重的节点下标
for (int i = 0; i < n - 1; i++) {
m1 = m2 = MaxValue;
x1 = x2 = -1;
// 2 4 5 7
for (int j = 0; j < n + i; j++) {//此处循环完就会添加新的节点到哈夫曼树中, 所以要+i
if (haffTree[j].weight < m1 && haffTree[j].flag == 0) {
m2 = m1;
x2 = x1;
m1 = haffTree[j].weight;
x1 = j;
} else if (haffTree[j].weight < m2 && haffTree[j].flag == 0) {
m2 = haffTree[j].weight;
x2 = j;
}
}
//生成新的节点放进哈夫曼树中, 此时i为新生成的第几个节点, 在哈夫曼树中向后偏移
//设置新节点的权重
haffTree[n + i].weight = haffTree[x1].weight + haffTree[x2].weight;
//左右孩子
haffTree[n + i].leftChild = x1;
haffTree[n + i].rightChild = x2;
//设置两个最小权重的父节点
haffTree[x1].parent = n + i;
haffTree[x2].parent = n + i;
//设计标记. 下次遍历将避开这两个节点
haffTree[x1].flag = 1;
haffTree[x2].flag = 1;
}
}
各个节点都已经生成完毕, 接下来就是需要将这个哈夫曼树变成哈夫曼编码
3.1、哈夫曼编码的实现
首先需要用存储哈夫编码
typedef struct Code//存放哈夫曼编码的数据元素结构
{
int bit[MaxBit];//记录节点的编码
int start; //这个节点在哈夫曼树中到根节点的距离
int weight;//这个节点的权值
}Code;
实现分析:
- 生成一个局部Code, 用来记录当前的编码
- 遍历叶子节点, 记录当前叶子节点n的父节点, 以及当前节点
- 通过父节点遍历找父节点, 每找一次就判断当前节点为这个父节点的左孩子还是右孩子, 并将0 或 1 记录到bit, 此时start++, 直到找到哈夫曼树的根节点
- 因为我们是通过叶子节点向根节点找, 所以这个编码是反的, 反转这个编码
- 将局部Code数据保存进哈夫曼编码中
void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[]) {
Code *cd =malloc(sizeof(Code));
int child;//记录当前的子节点
int parent;//记录当前的父节点
for (int i = 0; i < n; i++) {
//从0计数
cd->start = 0;
//记录权重
cd->weight = haffTree[i].weight;
//此时这个节点一定为孩子节点
child = i;
parent = haffTree[i].parent;
//从这个节点一直向根节点查找
while (parent != 0) {
//区分当前节点为父节点的左右孩子
if (child == haffTree[parent].leftChild) {
cd->bit[cd->start] = 0;
} else if (child == haffTree[parent].rightChild) {
cd->bit[cd->start] = 1;
}
cd->start++;
//将当前的父节点变为子节点, 查找它的父节点
child = parent;
parent = haffTree[child].parent;
}
//反转编码
int temp = 0;//正序对应的位置
for (int j = cd->start - 1; j >= 0; j--) {
temp = cd->start - 1 - j;//
haffCode[i].bit[temp] = cd->bit[j];
}
//将code的数据保存进去
haffCode[i].weight = cd->weight;
haffCode[i].start = cd->start;
}
}
