现在的位置: 首页 > 综合 > 正文

赫夫曼编码

2018年03月16日 ⁄ 综合 ⁄ 共 3301字 ⁄ 字号 评论关闭

赫夫曼编码是一种可变字长的编码,出现概率高的字符用较短的编码、出现概率低的字符用较长的编码,这使得编码之后字符串的平均期望长度降低,从而达到无损压缩数据的目的。赫夫曼树一种带权路径长度最短的二叉树。假设5个叶子节点a(w=4),b(w=2),c(w=3),d(w=5),e(w=2),其中w表示叶子节点的权值,这5个叶子节点可以形成多个二叉树其中一个带权路径长度最短的二叉树,就是赫夫曼树。


图1,图2,图3是上面的5个叶子节点所形成的二叉树中的三种,其中图1是赫夫曼树。图1中:a的路径长度为2,b的路径长度为3,c的路径长度为2,d的路径长度为2,e的路径长度为3.该二叉树的带权路径长度为WPL=3*2+4*2+2*3+2*3+5*2=36.同理图2中二叉树的带权路径长度WPL=4*2+2*2+3*3+5*3+2*2=40.同理图3中二叉树的带权路径长度WPL=2*2+5*2+3*3+2*3+4*2=39.再任意画有上面5个节点形成的赫夫曼树其带权的路径长度都会比图1中的二叉树的带权路径长度小。

赫夫曼编码实现的基本思想是: 
1>获得赫夫曼树
2>获得赫夫曼编码表(字符编码的集合)
3 >根据赫夫曼树和赫夫曼编码表对将要编码的文件或字符串进行编码(或译码)。
本文赫夫曼编码实现的思想是参考小甲鱼的。
获得赫夫曼树需要以下步骤:
 1:获得输入的文件或字符串字符出现的次数,其中次数不为0的字符就是赫夫曼树的叶子节点、次数为其权重.

int* get_weight(char* string_to_code)
{
	int* weight = new int[256];			//将string_to_code中字符的权值存放在weight数组
	for(int i=0;i<256;i++)					//初始化新建的数组
		weight[i] = 0;
	for(int i=0;string_to_code[i]!='\0';i++)
	{
		weight[(int)string_to_code[i]]++;	//获得字符的权值	
	}
	return weight;
}

这个函数很巧妙,首先一共有256种不同的字符,其ASCII码的范围是0-255.首先动态分配一块内存用来字符出现的次数。动态分配的内存刚开始存放的是垃圾值,因此首先要对其进行初始化;(int)string_to_code[i]代表string_to_code[i]字符的ASCII码值,变量weight[(int)string_to_code[i]]能记录该字符出现的次数,将字符串遍历一遍后weight[i](0-255)就存放了文件或字符串中字符出现的次数。其对应关系是weight[i](0-255)中i代表该字符的ASCII码值,weight[i]表示该字符出现的次数即字符串或文件中字符(char)i的次数为weight[i]。

2:根据字符的权值创建一个队列,其队列节点中含有3个元素(1)指向赫夫曼树节点的指针;(2)赫夫曼树节点的权重;(3)指向下一个队列节点的指针。其结构体定义如下

#define EXVL HTNode	
typedef struct _QueueNode
{
	EXVL * ht_node;						//指向赫夫曼树节点	
	unsigned int	weight;				//权重
	struct _QueueNode*	next;			//指向下一个队列节点
}QueueNode;

HTNode表示赫夫曼树节点的类型,将赫夫曼树节点定义成一个结构体其包含三个元素(1)一个char类型的元素;(2)指向左子树的一个指针;(3指向右子树的一个指针。其结构体定义如下:

typedef struct _HTNode
{
	char ch;
	struct _HTNode* left;
 	struct _HTNode* right;
}HTNode;

然后就是赫夫曼树叶子节点的度将其插入队列中,如果度相同的话,ASCII码值小的在前面。通过这样便可以获得一个有赫夫曼树叶子节点和度构成的链队列。队列的生成过程见下图:

从图1-1到图1-5是队列生成的过程。在图1-1中刚开始创建一个指向队列的指针Queue,队列结构体有两个元素,size表示队列中元素的个数,first指针指向队列的第一个元素。在生成对列的过程中注意每增加一个队列节点就要进行两次动态内存的分配,一次是为赫夫曼树叶子节点分配内存区,HNode指向这块内存区;另一次是为队列节点分配内存区,first或next指向这块内存区。

3:创建赫夫曼树。其创建过程见下图:

我们知道n个字符充当叶子节点,则队列需要合并n-1次,每合并一次就要将队列中权值最小的两个元素(即队列的前两个元素)出队列生成一个新队列节点。新的队列节点(A)和原始队列中权值最小的两个元素B、C(B的权值小于C的权值)的关系是:A->weight = B->weight+C->weight;    A->HNode->left = B->HNode;   A->HNode->right = C->HNode;因此每合并一次队列中的元素个数就少1,当队列中还剩下一个元素时,就形成了赫夫曼树见图2-5。此时队列中的第一个元素HNode就指向赫夫曼树的根节点了,将HNode赋给指向赫夫曼树根节点的指针root此时就得到最终的赫夫曼树了,见图2-6.实现的具体步骤见图2-1到2-6(其中图2-1是队列的初始状态,图2-6就是赫夫曼树)。这就是得到赫夫曼树的步骤。

4:获得赫夫曼编码表:

获得了赫夫曼树后再得到赫夫曼编码就相对简单了,由于现在我只是知道一颗赫夫曼树(图2-6),只要得到叶子节点的编码就可以了。实现方式:

//字符的哈弗曼编码
typedef struct _HCode
{
	char ch;
	char *code;
	struct _HCode* next; 
}HCode;
//哈弗曼编码
typedef struct _Table
{
	HCode*  first;
	HCode*  last;
}Table;

有上面的结构体可知,Table是一个队列,first指向第一个元素,last指向最后一个元素。其中Hcde的ch元素存放字符,code指向ch编码的字符串,next指向下一个队列元素。

实现流程图:

一个赫夫曼树最多有256个叶子节点(因为最多有256个互异的字符),那我就定义一个缓冲数组code[256];遍历赫夫曼树,如果左子树不为空,就将code[k]='0',如果右子树不为空,就将code[k]='1',如果其左子树不为空并且右子树不为空,code[k]='\0'此时code[0]-code[k]的构成的字符串即为当前叶子节点的赫夫曼编码,接下来的工作就是将该赫夫曼编码保存到赫夫曼表中。函数的返回值就是赫夫曼表的首地址,这样就得到一个赫夫曼表。

5:字符串赫夫曼编码与与译码的实现:

其程序实现的流程图为:

图3-1为字符串编码流程图:1>S指向待编码字符串的首地址,aux指向赫夫曼编码队列,当前字符*S不等于’\0’,如果等于当前队列元素(*aux)中的字符元素就输出aux中code元素所指向的内容即当前字符(*S)的编码,否则aux指向队列的下一个元素。2>指向当前字符的指针S自加1指向下一个字符,重复步骤1,直至*S =’\0’.

图3-2为字符串译码流程图:1>获得待译码字符串的指针S,获得当前字符*S,然后开始循环遍历赫夫曼树如果*S等于字符0,就遍历左子树,如果其等于1就遍历右子树,如果等于其他,待编译字符串有误结束函数,直至遍历到当前节点为叶子节点。2>此时输出叶子节点的字符元素,指向当前字符的指针S++,重复步骤1>,直至*S=’\0’.

example:

字符串“abcdaabccddddee”有13个字符其中有5个不同的字符,按照一般的编码方式每个字符至少需要三位,也就是说需要65位的空间。按照赫夫曼树编码字符串其赫夫曼树就是上图1所示,其赫夫曼编码见下图,其共需要36位所以赫夫曼编码能够很大程度的减少编码所占据的存储空间。

源代码见:http://download.csdn.net/detail/zhuangyongkang/8351117

抱歉!评论已关闭.