huffman编码是一种优化的编码方法,于ASCII等固定长度的编码方法相比较,他可以使编码的长度缩短。其主要的思路是,让出现频率高的字符拥有较短的编码,让出现频率较低的字符,拥有较长的编码。但是,这样的编码方式就要求任意一个字符的编码不能是其他字符编码的前缀,通常这种编码方式叫前缀编码。
huffman编码通过构造huffmanTree来实现,贪心思想。取权值(频率)最低的2个节点为新节点的左右子节点,新节点的权值为子节点权值之和。处理之后,子节点标记为已经处理过,新节点标记为未处理。循环处理该过程。如果huffmanTree中有m个叶节点,那么huffmanTree中肯定有n=2*m-1个节点。因此,当huffmanTree中有2*m-1个节点时,huffmanTree构造就结束了。
//zoj1117.cpp #include<iostream> #include<string.h> #include<stdio.h> using namespace std; class huffmanNode { public: int value,parent,left,right,pos; bool isset; int dir; huffmanNode() { this->isset=false; this->left=-1; this->right=-1; this->parent=-1; this->pos=-1; this->dir=1; } huffmanNode(int value,int pos):value(value),pos(pos) { this->isset=false; this->left=-1; this->right=-1; this->parent=-1; this->dir=-1; } }; class huffmanTree { public: huffmanNode hflist[20000]; int n,count,flag; huffmanTree(int count,int n) { this->count=count; this->n=n; this->flag=count; } void createTree() { while(flag<n) { int a=0; int b=0; int va=99999998; int vb=99999999; for(int i=0;i<flag;i++) { if(hflist[i].isset) continue; if(hflist[i].value<vb) { b=i; vb=hflist[i].value; } if(vb<va) { int temp=vb; vb=va; va=temp; temp=b; b=a; a=temp; } } huffmanNode node(hflist[a].value+hflist[b].value,flag); node.left=a; node.right=b; hflist[flag]=node; hflist[a].parent=flag; hflist[a].dir=0; hflist[b].dir=1; hflist[b].parent=flag; hflist[a].isset=true; hflist[b].isset=true; ++flag; } } int getEncoding(int n) { if(n>=count) return 0; int flag=n; int result=0; while(hflist[flag].parent!=-1) { //cout<<hflist[flag].dir<<" "; flag=hflist[flag].parent; ++result; } return result; } }; int num[27]; int flag,m,n; int main() { char ch[20000]; memset(ch,0,sizeof(ch)); while(scanf("%s",ch)!=EOF) { //cout<<ch<<endl; if(ch[0]=='E'&&ch[1]=='N'&&ch[2]=='D'&&ch[3]=='\0') break; memset(num,0,sizeof(num)); flag=0; m=0; while(ch[flag]!=0) { if(ch[flag]=='_') { if(num[26]==0) ++m; ++num[26]; } else { if(num[ch[flag]-65]==0) ++m; ++num[ch[flag]-65]; } ++flag; } n=m*2-1; int j=0; huffmanTree tree(m,n); for(int i=0;i<27;i++) { if(i!=26&&num[i]>0) { huffmanNode node(num[i],j); tree.hflist[j]=node; j++; } if(i==26) { huffmanNode node(num[26],j); tree.hflist[j]=node; j++; } } /*for(int i=0;i<m;i++) { cout<<tree.hflist[i].value<<endl; }*/ cout<<flag*8<<" "; tree.createTree(); int result=0; if(m<=1) result=tree.hflist[0].value; else { for(int i=0;i<m;i++) { result+=tree.getEncoding(i)*tree.hflist[i].value; //cout<<endl; } } cout<<result<<" "; printf("%.1f\n",(float)8*flag/result); memset(ch,0,sizeof(ch)); } }
发表评论
-
图的割点tarjan---zoj_1119
2011-10-24 23:00 1236http://acm.zju.edu.cn/on ... -
BFS与双向BFS---zoj_1505
2011-10-09 17:14 1647http://acm.zju.edu.c ... -
静态treap+线段树---zoj_2112
2011-09-29 23:06 1712http://acm.zju.edu ... -
NIM博弈游戏,SG函数---zoj_3084,zoj_2083
2011-09-23 23:00 1322Nim游戏是两个人进行的游戏有如下规则: ... -
多重背包--zoj_2156
2011-09-14 11:10 867首先介绍经典的三种背包问题,0-1背包,完全 ... -
模式串匹配---KMP
2011-08-31 20:49 1282朴素的的模式串匹配算法通常要在向前移动文本指针 ... -
八数码问题(A*&&双向BFS)---zoj_1217
2011-08-30 22:13 1673题目地址:http://acm.zju.edu.cn/onli ... -
ac自动机以及它上面的DFA
2011-08-08 23:04 2483AC自动机(Aho-Corasick)主要用 ... -
二分图最大匹配(匈牙利算法)--zoj1516,1525,2223
2011-07-20 22:36 1189二分图G(E,V)将点集合V分成两个部分L,R ... -
网络最大流(EK)---zoj_1734
2011-07-19 16:34 2136网络最大流是图论中的一个典型问题,为了精确的定 ... -
trie和前缀检查---zoj_2876
2011-07-13 23:03 870trie树是一种多叉树,广泛用于字典检索。如 ... -
位图bitmap
2011-07-13 21:08 916bitmap是一种广泛使用的数据结构,主要用在 ... -
LAC和RMQ的转化---zoj_3195
2011-07-12 22:35 1078我擦。。纠结了好久啊,从SF到TLE,先总结2 ... -
LAC的tarjan(离线)算法---zoj_1141
2011-07-08 17:52 1662LCA就不解释了,这里主要再次复习一下LC ... -
笛卡尔树以及treap---zoj_2243
2011-07-07 15:52 2847zoj_2243笛卡 ... -
线段染色,矩形切割,离散化---zoj_2301,zoj_1128
2011-06-24 22:32 1369染色问题:在一维坐标轴上(最右端为M),有N ... -
线段树---zoj_1610
2011-06-22 21:06 755线段树是一种二叉树的拓展,在线段树每个节点中 ... -
快速排序(qsort)
2011-06-16 17:03 782快速排序是一种高效的非稳定排序,它的基本思路 ... -
斐波那契散列
2011-06-16 16:38 3083斐波那契散列法其实是一种特殊的乘法散列,先来看乘法 ... -
强连通分支(scc)---tarjan
2011-06-15 16:17 1285本文大量 ...
相关推荐
信息论与编码---Huffman编码-------------
Huffman编码与译码,实现数据结构树的功能。
良心出品Huffman编码-MATLAB程序.doc
Huffman编码在matlab下实现 Huffman编码是一种高效的基于信息上理论的编码方式
huffman编码译码,出现数字概率分析等
huffman编码程序,对研究信源编码十分有用,建议下载
功能实现(函数定义内部有对函数功能的简介) 1.编码 2.转码 3.简单菜单 4.字符集及权值可自定义
哈夫曼图像编码算法
用MATLAB编程实现Huffman编码的示例,以及对编码效率的计算
用verilog编写的huffman解码程序
PCM编码 霍夫曼huffman_psk_fsk matlab源码 个人作业 PCM编码 霍夫曼huffman_psk_fsk matlab源码 个人作业 PCM编码 霍夫曼huffman_psk_fsk matlab源码 个人作业 PCM编码 霍夫曼huffman_psk_fsk matlab源码 个人作业 ...
PCM编码_霍夫曼huffman_psk_fsk_matlab源码实现.7zPCM编码_霍夫曼huffman_psk_fsk_matlab源码实现.7zPCM编码_霍夫曼huffman_psk_fsk_matlab源码实现.7zPCM编码_霍夫曼huffman_psk_fsk_matlab源码实现.7z
Huffman编码(二叉树的应用)其中包含了源代码及实验截图
对二维图像的dct变换、huffman编码
Huffman编码,编程语言Java,面向对象思想
哈夫曼编码,运用matlab实现,原代码非常直观而且易懂。
huffman编码代码
自己实现huffman树的代码,分享出来
实现图像的huffman编码,并得到生成矩阵和字典
利用matlab实现基于哈夫曼编码的信源编码实验