注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C++霍夫曼编码(Huffman Coding)

OC/C/C++ 水墨上仙 1444次浏览 已收录 手机上查看

霍夫曼编码(Huffman Coding)是一种编码方式,是一种用于无损数据压缩的熵编码(权编码)算法。1952年,David A. Huffman在麻省理工攻读博士时所发明的,并发表于《一种构建极小多余编码的方法》(A Method for the Construction of Minimum-Redundancy Codes)一文。
在计算机数据处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。(http://zh.wikipedia.org/wiki/Huffman%E7%B7%A8%E7%A2%BC)
转自:
http://blog.csdn.net/here1009/article/details/8071251

 #include<iostream>
 #include<string>
 #include<queue>
 using namespace std;
 
 class node{
	 public:
		node(string con, float wht, node* left, node* right, string co ){
			content=con;
			weight=wht;
			leftchild=left;
			rightchild=right;
			code=co;
			}
		string content;
		float weight;
		node* leftchild;
		node* rightchild;
		string code;
	 };
void insertion_sort(node** array, int low, int high){
	for(int i=low+1;i<high;i++){
		node* tem=array[i];
		int j=i-1;
		while(array[j]->weight>tem->weight&&j>=low){
			array[j+1]=array[j];
			j--;
			}
		array[j+1]=tem;
		}
	}
void create_huffman_tree(string* s, float* w,int n,node** array){
	for(int i=0;i<n;i++){
		array[i]=new node(s[i],w[i],NULL,NULL,"");
		}
	insertion_sort(array,0,n);
	//~ for(int i=0;i<n;i++){
		//~ cout<<array[i]->content<<"*";
		//~ }
	int p=0;
	while(p!=n-1){
		node* min_1=array[p];
		node* min_2=array[p+1];
		node* new_node=new node("",min_1->weight+min_2->weight,min_1,min_2,"");
		//cout<<new_node->weight<<endl;
		array[p+1]=new_node;
		p=p+1;
		insertion_sort(array,p,n);
		}
	
	}
	
void create_huffman_code(node* p){
	queue<node*> nq;
	nq.push(p);
	while(nq.size()!=0){
		node* cur=nq.front();
		nq.pop();
		node* l=cur->leftchild;
		if(l!=NULL){l->code=cur->code+"0"; nq.push(l);}
		node* r=cur->rightchild;
		if(r!=NULL){r->code=cur->code+"1"; nq.push(r);}
		if(l==NULL&&r==NULL){
			cout<<cur->content<<": "<<cur->code<<endl;
			}
		}
	}
 int main(int argc, char** argv){
	 node* array[8];
	 string s[8]={"a","b","c","d","e","f","g","h"};
	 float w[8]={1,1,2,3,5,8,13,21};
	 create_huffman_tree(s,w,8,array);
	 create_huffman_code(array[7]);
	 }


喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……