0%

【Matlab编程】哈夫曼树及编译码

发表于 更新于
本文字数： 6.2k 阅读时长 ≈ 9 分钟

哈夫曼树，又称二叉树，是一类带权路径长度最短的树。所谓路径长度，就是节点到树根之间的路径长度与节点权值的乘积。

哈夫曼本人曾在MIT的信息论研究生班学习。Robert Fano教授让学生们自己决定是参加期未考试还是做一个大作业。而哈夫曼选择了后者，原因很简单，因为解决一大作业可能比期未考试更容易通过。Robert Fano教授也是信息论的先驱，学过信息论的都知道有Fano不等式，Shannon-Fano编码。当时这个大作业，Fano也解决不了，哈夫曼并不知道，于是自己尝试，最终产生了哈夫曼编码，其性能比Shannon-Fano编码更好。这个故事说明，大师级人物未能解决的问题，我们不一定解决不了，因为我们的思想比较开阔，能从不同的角度看问题。还有就是turbo码的产生也印证了这个道理。但是任何成功都离不开坚持不懈的努力。这段小故事就当你我共勉。

哈夫曼树

哈夫曼树的构造由下图可清楚明了：（总的来说就是每次将两个最小的节点合并）

图1

用上述算法来对图12.16中的叶子结点集合构造哈夫曼树的初始状态如图12.18(a)所示，第一次合并状态如图12.18(b)所示，结果状态如图12.18(c)所示。在算法中，每次合并时都是将具有较小权值的结点置为合并后结点的左孩子，而具有较大权值的结点置为合并后结点的右孩子。
具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**********************************************************\
函数功能：构造哈夫曼树
输入：    头结点、权重、元素值
输出：    无
\**********************************************************/
void HuffmanTree(huffmantree *tree,double *weight,int *data)
{
	
	int i,j;
	for(i=0;i<m;i++)//初始化
	{
		tree[i].parent=0;
		tree[i].lchild=0;
		tree[i].rchild=0;
		tree[i].weight=0.0;
		tree[i].data=0;
	}

	for(i=0;i<n;i++)
	{
		tree[i].weight=weight[i];//给每个节点赋权值和内容
		tree[i].data=data[i];
	}

	for(i=n;i<m;i++)
	{
		int p1=0;
		int p2=0;
		float small1,small2;
		small1=small2=10000;//初始化为一个很大的值
		for(j=0;j<=i-1;j++)//找出最小权重的两个节点
		{
			if(tree[j].parent==0)
			{
				if(tree[j].weight<small1)
				{
					small2=small1;
					small1=tree[j].weight;
					p2=p1;
					p1=j;
				}
				else if(tree[j].weight<small2)
				{
					small2=tree[j].weight;
					p2=j;
				}
			}
		}
		tree[p1].parent=i;
		tree[p2].parent=i;
		tree[i].lchild=p1;
		tree[i].rchild=p2;
		tree[i].weight=tree[p1].weight+tree[p2].weight;//将两个节点合并为一个节点
	}
	
}

哈夫曼编码:

通过从哈夫曼树根结点开始，对左子树分配代码“0”，右子树分配代码“1”，一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。因为形成哈夫曼树的每一次合并操作都将对应一次代码分配，因此n个叶子结点的最大编码长度不会超过n–1，所以可为每个叶子结点分配一个长度为n的编码数组。

基本思想是：从叶子tree[i]出发，利用双亲地址找到双亲结点tree[p]，再利用tree[p]的lchild和rchild指针域判断tree[i]是tree[p]的左孩子还是右孩子，然后决定分配代码是“0”还是“1”, 然后以tree[p]为出发点继续向上回溯，直到根结点为止。

具体算法实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**************************************************\
函数功能：进行哈夫曼编码
输入：    用于存储编码的数组code、哈夫曼树
输出：    无
\**************************************************/
void HuffmanCode(codetype *code,huffmantree *tree)
{
	int i,c,p;
	codetype cd;//缓冲变量
	for(i=0;i<n;i++)
	{
		cd.start=n;//从叶子节点开始回溯
		c=i;
		p=tree[c].parent;
		cd.data=tree[c].data;
		while(p!=0)
		{
			cd.start--;
			if(tree[p].lchild==c)//左节点则编为0，右节点则编为1
				cd.bits[cd.start]=0;
			else
				cd.bits[cd.start]=1;
			c=p;
			p=tree[c].parent;
		}
		code[i]=cd;
		code[i].start=cd.start;
	}
}

哈夫曼译码：

哈夫曼树译码是指由给定的代码求出代码所表示的结点值，它是哈夫曼树编码的逆过程。

译码的基本思想是：从根结点出发，逐个读入电文中的二进制代码；若代码为0则走向左孩子，否则走向右孩子；一旦到达叶子结点，便可译出代码所对应的字符。然后又重新从根结点开始继续译码，直到二进制电文结束。

具体译码算法如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/***************************************************\
函数功能：哈夫曼译码
输入：    存储编码的数组、哈夫曼树
输出：    无
\***************************************************/
void HuffmanDecode(codetype *code,huffmantree *tree)
{
	int i=m-1;
	printf("\n译码结果为：\n");
	for(int j=0;j<n;j++)
	{
		for(int k=code[j].start;k<n;k++)//循环n次，对n个码进行译码
		{
			if(code[j].bits[k]==0)
				i=tree[i].lchild;
			else
				i=tree[i].rchild;
			if(tree[i].lchild==0)
			{
				printf("%d ",code[i].data);
				i=m-1;
			}
		}
	}
}

完整实例如下：假设有6个节点，权值分别为0.4、0.3、0.1、0.1、0.08、0.02，元素值分别为2、1、3、4、6、5.则哈夫曼树的构造过程和编码如下:

图2

图3

图4

具体的代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<stdio.h>

#define n 6 //叶子数目
#define m (2*n-1)//节点总数
#define maxsize 10

typedef int datatype;
typedef struct
{
	double weight;
	datatype data;
	int lchild,rchild,parent;
}huffmantree;

typedef struct
{
	int bits[n];
	int start;
	int data;
}codetype;

void HuffmanTree(huffmantree *tree,double *weight,int *data);
void HuffmanCode(codetype *code,huffmantree *tree);
void HuffmanDecode(codetype *code,huffmantree *tree);


void main()
{
	double weight[]={0.4,0.3,0.1,0.1,0.02,0.08};
	int data[]={2,1,3,4,5,6};
	huffmantree head[m];
	codetype code[n];

	HuffmanTree(head,weight,data);
	HuffmanCode(code,head);


	for(int i=0;i<m;i++)
		printf("%d ",head[i].parent);//对应的父节点
	printf("\n编码结果为：\n");
	for(int i=0;i<n;i++)
	{
		for(int j=code[i].start;j<n;j++)
		printf("%d ",code[i].bits[j]);
		printf("\n");
	}
		HuffmanDecode(code,head);
}
/**********************************************************\
函数功能：构造哈夫曼树
输入：    头结点、权重、元素值
输出：    无
\**********************************************************/
void HuffmanTree(huffmantree *tree,double *weight,int *data)
{
	
	int i,j;
	for(i=0;i<m;i++)//初始化
	{
		tree[i].parent=0;
		tree[i].lchild=0;
		tree[i].rchild=0;
		tree[i].weight=0.0;
		tree[i].data=0;
	}

	for(i=0;i<n;i++)
	{
		tree[i].weight=weight[i];//给每个节点赋权值和内容
		tree[i].data=data[i];
	}

	for(i=n;i<m;i++)
	{
		int p1=0;
		int p2=0;
		float small1,small2;
		small1=small2=10000;//初始化为一个很大的值
		for(j=0;j<=i-1;j++)//找出最小权重的两个节点
		{
			if(tree[j].parent==0)
			{
				if(tree[j].weight<small1)
				{
					small2=small1;
					small1=tree[j].weight;
					p2=p1;
					p1=j;
				}
				else if(tree[j].weight<small2)
				{
					small2=tree[j].weight;
					p2=j;
				}
			}
		}
		tree[p1].parent=i;
		tree[p2].parent=i;
		tree[i].lchild=p1;
		tree[i].rchild=p2;
		tree[i].weight=tree[p1].weight+tree[p2].weight;//将两个节点合并为一个节点
	}
	
}
/**************************************************\
函数功能：进行哈夫曼编码
输入：    用于存储编码的数组code、哈夫曼树
输出：    无
\**************************************************/
void HuffmanCode(codetype *code,huffmantree *tree)
{
	int i,c,p;
	codetype cd;//缓冲变量
	for(i=0;i<n;i++)
	{
		cd.start=n;//从叶子节点开始回溯
		c=i;
		p=tree[c].parent;
		cd.data=tree[c].data;
		while(p!=0)
		{
			cd.start--;
			if(tree[p].lchild==c)//左节点则编为0，右节点则编为1
				cd.bits[cd.start]=0;
			else
				cd.bits[cd.start]=1;
			c=p;
			p=tree[c].parent;
		}
		code[i]=cd;
		code[i].start=cd.start;
	}
}
/***************************************************\
函数功能：哈夫曼译码
输入：    存储编码的数组、哈夫曼树
输出：    无
\***************************************************/
void HuffmanDecode(codetype *code,huffmantree *tree)
{
	int i=m-1;
	printf("\n译码结果为：\n");
	for(int j=0;j<n;j++)
	{
		for(int k=code[j].start;k<n;k++)//循环n次，对n个码进行译码
		{
			if(code[j].bits[k]==0)
				i=tree[i].lchild;
			else
				i=tree[i].rchild;
			if(tree[i].lchild==0)
			{
				printf("%d ",code[i].data);
				i=m-1;
			}
		}
	}
}

注：如果程序出错，可能是使用的开发平台版本不同，请点击如下链接： 解释说明

坚持原创技术分享，您的支持将鼓励我继续创作！