当前位置:首页 > IT教程

哈夫曼编码原理及实现代码

时间:2020-05-20 11:31:59来源:金橙教程网 作者:admin8 阅读:69次 [手机版]
 

哈夫曼编码

霍夫曼编码是一种“从下到上”的熵编码方法,采用霍夫曼编码方法给每个符号分配的代码长度不是固定的,但在编码时却不需要再生成的码流中附加同步代码,原因是在解码时可按霍夫曼码本身的特性加以区分,这也使得很难随意查找或者调用压缩文件的内容,然后再译码,这需要在编码时加以考虑。

霍夫曼码没有错误保护功能,在存储或传输过程中,如果码流中没有出现错误,解码时就能一个接一个地正确译出代码。如果码流中出现错误,会出现错误传播现象。

其算法步骤如下:

(1)初始化,根据符号概率的大小,按由大到小顺序对符号进行排序。

(2)把概率最小的两个符号组成一个节点,新节点的概率等于这两个符号概率之和。

(3)重复步骤2,直到形成一棵“树”为止,根节点概率等于1。

(4)从树的根节点开始到对应于每个符号的叶节点,按照从上到下的顺序选择

下述两种方法之一进行标注:

①在上分枝标“0”(对应概率大的节点),在下分枝标“1”(对应概率小的节点)。

②在上分枝标“1”(对应概率大的节点),在下分枝标“0”(对应概率小的节点)。这两种标法的最后结果仅仅是分配的代码不同,代码的平均长度是相同的。

构造哈夫曼树的步骤如下:

(1)初始化:根据给定的n个权值 ,构造n棵只有一个根结点的二叉树, n个权值分别是这些二叉树根结点的权。

(2)找最小树:在F中选取两棵根结点树值最小的树作为左、右子树,构造一颗新的二叉树,置新二叉树根的权值为左、右子树根结点权值之和;

(3)删除与加入:从F中删除这两颗树,并将新树加入F;

判断:重复 (2)和(3),直到F中只含一颗树为止,此时得到的这颗二叉树就是哈夫曼树。

而香农-范诺编码是一种“从上到下”的熵编码方法。其基本思想是产生编码长度可变的码词。估计码词长度的准则是符号出现的概率。出现次数越多的符号,给它分配的代码位数就越少。其算法步骤如下:

(1)根据符号出现的概率有大到小的顺序对待编码的符号进行排序。

(2)将符号分成两组,使这两组符号概率和相等或几乎相等。

(3)将第一组赋值为0,第二组赋值为1。

(4)对每一组,重复步骤2的操作,直到分配完所有待编码的符号。

与霍夫曼编码相比,这两种方法产生的代码都是自含同步的代码,在编码之后的码流中都不需要另外添加标记符号,即在译码时分割符号的特殊代码。此外,霍夫曼编码的编码效率比香农-范诺编码效率高一些。

代码实现如下:

#include "stdio.h"
#include "String"
#include "iOStream"
#define MAX_LEN 200
#define MAX_NUM 1000
using namespace std;

double sum = 0;
typedef struct //定义Huffman树的结点结构体类型
{
	int weight;//weight变量用于保存该结点的权值,即出现的次数
	char value;
	char lchild,rchild,parent;//lchild、rchild和parent分别保存该结点的左子树、右子树、双亲结点在字符数组中的下标
}huffTree_element;

typedef struct{
	int start;	//存放编码起始位置
	char bits[20];	//存放编码位串
}codetype_element;

typedef struct{
	char symbol;	//存储字符	
	codetype_element code;
}huffCode_element;

void SELECT_min(huffTree_element huffTree[], int *i1, int *i2, int n){
	int temp1 = MAX_NUM, temp2 = MAX_NUM;
	*i1 = *i2 = 0;
	for(int i = 0; i < n; i++){
		if(huffTree[i].parent  ==  -1 && temp1 >= huffTree[i].weight){
			temp1 = huffTree[i].weight;
			*i1 = i;
		} 
	}
	for(int i = 0; i < n; i++){
		if( temp2 >= huffTree[i].weight && i != *i1 && huffTree[i].parent == -1){
			temp2 = huffTree[i].weight;
			*i2 = i;
		}
	}
}

void HuffmanTree(huffTree_element huffTree[], int weights[], int n, int max_char){
	for(int i = 0; i < 2*n - 1; i++){ //初始化二叉树的所有结点
		huffTree[i].parent = -1;
		huffTree[i].lchild = -1;
		huffTree[i].rchild = -1;
		huffTree[i].value = -1;
	}
	int m = 0;
	for(int j = 0 ; j <= max_char && m < n; j++){//构造n棵只含有根节点的二叉树
	 	if(weights[j] != 0) {
	 		huffTree[m].weight = weights[j];
	 		huffTree[m].value = j; 
	 		m++;
		 }
	}
	for(int k = n; k < 2*n - 1; k++){
		int i_min_1 = -1, i_min_2 = -1;
		select_min(huffTree, &i_min_1, &i_min_2, k); //查找权值最小的两个根结点,下标为i_min_1,i_min_2
		huffTree[i_min_1].parent = k;
		huffTree[i_min_2].parent = k;
		huffTree[k].weight = huffTree[i_min_1].weight + huffTree[i_min_2].weight;
		huffTree[k].lchild = i_min_1;
		huffTree[k].rchild = i_min_2;
		huffTree[k].value  = 0;
	}
}

//生成Huffman编码表 
void GenerateHuffCode(huffTree_element tree[], huffCode_element table[], int n)

{ 

	int i,j,s,f; //s和f分别指示tree中孩子和双亲的位置
	codetype_element c; //临时存放编码 
	sum = sum - 1; //在VS中会键入一个空行符,故总字符数应该减1,在Dev++中不需减1
	for(i = 0; i < n; i++) //求叶子tree[i]的编码 
	{
		printf("%c -- ", tree[i].value);
		c.start = n + 1;
		s = i; //叶子tree[i]开始上溯 
		while(tree[s].parent != -1) //至上溯到树根为止 
		{ 
			f = tree[s].parent ;
			c.bits[--c.start] = (s == tree[f].lchild) ? '0':'1';
			s = f;
		}
		for(j = c.start; j < n + 1; j++)
		printf("%c", c.bits[j]);
		
		printf(" -- %.4f", tree[i].weight/sum);
		printf("\n");
		// 
 		table[i].code = c;
 		table[i].symbol = tree[i].value;
 	}
}

int main(){
	char s[MAX_LEN];
	int len = 0;
	int i = 0;
	int w[MAX_NUM] = {0};
	int index_max_char = 0;
	string str;
	cout << "Please input a string :";
	cin >> str;
	const char *p = str.c_str();
	strncpy(s, p, strlen(p));
	*(s + strlen(p) + 1) = '\0';
	for( ; s[i] != '\0'; i++){
		if(w[s[i]] == 0){
			len ++;
			index_max_char = s[i];
		}
		w[s[i]] ++;
		sum++;
	}
	//huffTree_element huff_s[len*2-1];
	huffTree_element *huff_s;
	huff_s = (huffTree_element *)malloc((len*2-1)*sizeof(huffTree_element));
	huffCode_element code_t[1000];
	HuffmanTree(huff_s, w, len, index_max_char);
	GenerateHuffCode(huff_s, code_t, len);
	printf("The Huffman Code of the string is : "); 
	for(i = 0; s[i] != '\0'; i++){
		for(int j = 0; j < len; j++){
			if(s[i] == code_t[j].symbol){
				for(int k = code_t[j].code.start; k < len + 1; k++)
					printf("%c", code_t[j].code.bits[k]);
			}
		}
	} 
	printf("\n");
    getchar();
	return 0;
}

运行结果如下:

Huffman Code 运行结果截图

相关阅读

WPF随笔(十)--使用AvalonDock实现可停靠式布局

我们每天使用的许多软件都使用了可停靠式布局,可以方便的打开、关闭、收起、展开、移动选项卡。今天就来说明如何使用AvalonDock实

PHP+Mysql 实现用户登录,注册界面

目标: 实现用户的登录 、注册 、修改密码、重置密码、添加书签,显示书签,删除书签 等功能 进一步目标: 实现对 用户输入信息的控制,具

如何选择代码签名

什么是代码签名证书(Code Signing Certificate )代码签名证书是对在线数据 文档和其他文件的实用工具进行数字加密,保护原始发布者发

频谱仪原理与重要指标的作用

1.频率范围 这个就不详说了。一般来讲频率测量范围是由本振决定的,一般我们说低频频谱分析仪基本上是3G左右,高频频谱分析仪能到67G

小编教你电脑蓝屏代码0x000000ed怎么处理

今天是周末,苦逼的小编还要上班,打开qq看到一个用户留言询问电脑蓝屏代码0x000000ed怎么处理,电脑蓝屏代码0x000000ed这个问题还

分享到:

IT相关

程序相关

推荐文章

热门文章