哈夫曼树
2021-03-14 本文已影响0人
奉灬孝
戴维·哈夫曼.png
戴维·哈夫曼【David Huffman】
著名的“霍夫曼编码”的发明人戴维.霍夫曼 （David Albert Huffman）已于1999年10月17日因癌症去世，享年74岁。他发明了著名的霍夫曼编码。
除了霍夫曼编码外，霍夫曼在其他方面也还有不少创造，比如他设计的二叉最优搜索树算法就被认为是同类算法中效率最高的，，因而被命名为霍夫曼算法，是动态规划（dynamic programming）的一个范例。霍夫曼在MIT一直工作到1967年。之后他转入加州大学的 Santa Cruz 分校，是该校计算机科学系的创始人，1970一1973年任系主任。1994年霍夫曼退休。
霍夫曼除了获得计算机先驱奖以外，还在1973年获得IEEE的 McDowell 奖。1998年 IEEE 下属的信息论分会为纪念信息论创立50周年，授予他 Golden Jubilee 奖。霍夫曼去世前不久的1999年6月，他还荣获以哈明码发明人命名的哈明奖章（Hamming Medal）。
哈夫曼树
哈夫曼树（霍夫曼树）又称为最优树.
路径和路径长度
- 路径：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为
路径。 - 路径长度：通路中分支的数目称为路径长度，也就是等于路径上的结点数减
1。
结点的权及带权路径长度
- 结点的权：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。
- 带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为 WPL。
哈夫曼树的实现
哈夫曼树的实现思路:
- 初始化哈夫曼二叉树
- 循环不断找到结点中，最小的
2个结点值.加入到哈夫曼树中
哈夫曼编码
哈夫曼编码的结点
哈夫曼编码的结点.png
哈夫曼编码的存储表示:
typedef struct Code //存放哈夫曼编码的数据元素结构
{
int bit [MaxBitl；//数组
int start；//编码的起始下标
int weight；//字符的权值
}Code；
哈夫曼树构建
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
假设给定的权值如下：
A：5
E：10
B：15
D：30
C：40
- 首先取集合中最小的两个数：5+10=15，再删除集合中
5和10的值，把15放入原集合,
原集合变成:15,15,30,40；
图1
- 再从
15,15,30,40中再取2个最小的数构成一个树。再删除集合中15和15的值，把30放入原集合,
原集合变成:30,30,40；
图2
- 再从
30,30,40中再取2个最小的数构成一个树。再删除集合中30和30的值，把60放入原集合,
原集合变成:40,60；
图3.png
- 由于
40比60小，所以40应该放在60的左边。
图4.png
思考: 计算这棵树的WPL?
WPL= 40 * 1 + 30 * 2 + 15 * 3 + 10 * 4 + 5 * 4 = 205
哈夫曼思考
一堆字符串其中ABCDEF出现的次数如下所示：
A 000 27
B 001 8
C 010 15
D 011 15
E 100 30
F 101 5
排序之后
F 101 5
B 001 8
C010 15
D011 15
A 000 27
E 100 30
然后构建哈夫曼树
哈弗曼树.png
然后哈夫曼树根据字符出现的权重进行编码
A 01
B 1001
C 101
D 00
E 11
F 1001
BADCADFEED 编码
原编码二进制: 001 000 011 010 000 011 101 100 100 011（共30个字符）
新编码二进制:1001 01 00 101 01 00 1001 11 11 00（共25个字符）
可见哈夫曼编码的确能够实现文本的压缩
哈夫曼编码的代码实现
哈夫曼树的实现思路:
- 获取根据权值构建的哈夫曼树
- 循环遍历
[0,n]个结点； - 创建临时结点
cd，从根结点开始对齐进行编码，左孩子为0，右孩子为1； - 将编码后的结点存储
haffCode[i] - 设置
haffCode[i]的开始位置以及权值；
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
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;
typedef struct Code//存放哈夫曼编码的数据元素结构
{
int bit[MaxBit];//数组
int start; //编码的起始下标
int weight;//字符的权值
}Code;
//1.
//根据权重值,构建哈夫曼树;
//{2,4,5,7}
//n = 4;
void Haffman(int weight[],int n,HaffNode *haffTree){
int j,m1,m2,x1,x2;
//1.哈夫曼树初始化
//n个叶子结点. 2n-1
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;
}
//2.构造哈夫曼树haffTree的n-1个非叶结点
for (int i = 0; i< n - 1; i++){
m1 = m2 = MaxValue;
x1 = x2 = 0;
//2,4,5,7
for (j = 0; j< n + i; j++)//循环找出所有权重中，最小的二个值--morgan
{
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;
}
}
//3.将找出的两棵权值最小的子树合并为一棵子树
haffTree[x1].parent = n + i;
haffTree[x2].parent = n + i;
//将2个结点的flag 标记为1,表示已经加入到哈夫曼树中
haffTree[x1].flag = 1;
haffTree[x2].flag = 1;
//修改n+i结点的权值
haffTree[n + i].weight = haffTree[x1].weight + haffTree[x2].weight;
//修改n+i的左右孩子的值
haffTree[n + i].leftChild = x1;
haffTree[n + i].rightChild = x2;
}
}
/*
9.2 哈夫曼编码
由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode
//{2,4,5,7}
*/
void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[])
{
//1.创建一个结点cd
Code *cd = (Code * )malloc(sizeof(Code));
int child, parent;
//2.求n个叶结点的哈夫曼编码
for (int i = 0; i<n; i++)
{
//从0开始计数
cd->start = 0;
//取得编码对应权值的字符
cd->weight = haffTree[i].weight;
//当叶子结点i 为孩子结点.
child = i;
//找到child 的双亲结点;
parent = haffTree[child].parent;
//由叶结点向上直到根结点
while (parent != 0)
{
if (haffTree[parent].leftChild == child)
cd->bit[cd->start] = 0;//左孩子结点编码0
else
cd->bit[cd->start] = 1;//右孩子结点编码1
//编码自增
cd->start++;
//当前双亲结点成为孩子结点
child = parent;
//找到双亲结点
parent = haffTree[child].parent;
}
int temp = 0;
for (int j = cd->start - 1; j >= 0; j--){
temp = cd->start-j-1;
haffCode[i].bit[temp] = cd->bit[j];
}
//把cd中的数据赋值到haffCode[i]中.
//保存好haffCode 的起始位以及权值;
haffCode[i].start = cd->start;
//保存编码对应的权值
haffCode[i].weight = cd->weight;
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, 哈夫曼编码!\n");
int i, j, n = 4, m = 0;
//权值
int weight[] = {2,4,5,7};
//初始化哈夫曼树, 哈夫曼编码
HaffNode *myHaffTree = malloc(sizeof(HaffNode)*2*n-1);
Code *myHaffCode = malloc(sizeof(Code)*n);
//当前n > MaxN,表示超界. 无法处理.
if (n>MaxN)
{
printf("定义的n越界，修改MaxN!");
exit(0);
}
//1. 构建哈夫曼树
Haffman(weight, n, myHaffTree);
//2.根据哈夫曼树得到哈夫曼编码
HaffmanCode(myHaffTree, n, myHaffCode);
//3.
for (i = 0; i<n; i++)
{
printf("Weight = %d\n",myHaffCode[i].weight);
for (j = 0; j<myHaffCode[i].start; j++)
printf("%d",myHaffCode[i].bit[j]);
m = m + myHaffCode[i].weight*myHaffCode[i].start;
printf("\n");
}
printf("Huffman's WPS is:%d\n",m);
return 0;
}
```
