【算法导论】哈夫曼树及编译码-阿里云开发者社区

开发者社区> 人工智能> 正文

【算法导论】哈夫曼树及编译码

简介: 哈夫曼树及编译码 哈夫曼树,又称二叉树,是一类带权路径长度最短的树。所谓路径长度,就是节点到树根之间的路径长度与节点权值的乘积。哈夫曼本人曾在MIT的信息论研究生班学习。

哈夫曼树及编译码

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

哈夫曼树

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

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

/**********************************************************\
函数功能:构造哈夫曼树
输入:    头结点、权重、元素值
输出:    无
\**********************************************************/
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]为出发点继续向上回溯,直到根结点为止。
具体算法实现如下
/**************************************************\
函数功能:进行哈夫曼编码
输入:    用于存储编码的数组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则走向左孩子,否则走向右孩子;一旦到达叶子结点,便可译出代码所对应的字符。然后又重新从根结点开始继续译码,直到二进制电文结束。
具体译码算法如下: 
/***************************************************\
函数功能:哈夫曼译码
输入:    存储编码的数组、哈夫曼树
输出:    无
\***************************************************/
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.则哈夫曼树的构造过程和编码如下:


具体的代码实现如下:
#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;
			}
		}
	}
}


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


原文:http://blog.csdn.net/tengweitw/article/details/9838343

作者:nineheadedbird





版权声明:本文首发在云栖社区,遵循云栖社区版权声明:本文内容由互联网用户自发贡献,版权归用户作者所有,云栖社区不为本文内容承担相关法律责任。云栖社区已升级为阿里云开发者社区。如果您发现本文中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,阿里云开发者社区将协助删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章