如何写压缩软件,运用哈夫曼算法实现
到文件压缩大家很容易想到的就是rar,zip等我们常见的压缩格式。
然而,还有一种就是大家在学习数据结构最常见到的哈夫曼树的数据结构,以前还不知道他又什么用,其实他最大的用途就是用来做压缩,也是一些rar,zip压缩的祖先,称为哈弗曼压缩(什么你不知道谁是哈弗曼,也不知道哈弗曼压缩,不急等下介绍)。
随着网络与多媒体技术的兴起,人们需要存储和传输的数据越来越多,数据量越来越大,以前带宽有限的传输网络和容量有限的存储介质难以满足用户的需求。
特别是声音、图像和视频等媒体在人们的日常生活和工作中的地位日益突出,这个问题越发显得严重和迫切。
如今,数据压缩技术早已是多媒体领域中的关键技术之一。
一、什么是哈弗曼压缩Huffman(哈夫曼)算法在上世纪五十年代初提出来了,它是一种无损压缩方法,在压缩过程中不会丢失信息熵,而且可以证明Huffman算法在无损压缩算法中是最优的。
Huffman原理简单,实现起来也不困难,在现在的主流压缩软件得到了广泛的应用。
对应用程序、重要资料等绝对不允许信息丢失的压缩场合,Huffman算法是非常好的选择。
二、怎么实现哈弗曼压缩哈夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件。
哈夫曼压缩属于可变代码长度算法一族。
意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代。
因此,在文件中出现频率高的符号,使用短的位序列,而那些很少出现的符号,则用较长的位序列。
故我们得了解几个概念:1、二叉树:在计算机科学中,二叉树是每个结点最多有两个子树的有序树。
通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree)。
2、哈夫曼编码(Huffman Coding):是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。
uffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字,有时称之为最佳编码,一般就叫作Huffman编码。
三、哈夫曼编码生成步骤:①扫描要压缩的文件,对字符出现的频率进行计算。
②把字符按出现的频率进行排序,组成一个队列。
③把出现频率最低(权值)的两个字符作为叶子节点,它们的权值之和为根节点组成一棵树。
④把上面叶子节点的两个字符从队列中移除,并把它们组成的根节点加入到队列。
⑤把队列重新进行排序。
重复步骤③④⑤直到队列中只有一个节点为止。
⑥把这棵树上的根节点定义为0(可自行定义0或1)左边为0,右边为1。
这样就可以得到每个叶子节点的哈夫曼编码了。
既如 (a)、(b)、(c)、(d)几个图,就可以将离散型的数据转化为树型的了。
如果假设树的左边用0表示右边用1表示,则每一个数可以用一个01串表示出来。
则可以得到对应的编码如下:1-->1102-->1113-->104-->0每一个01串,既为每一个数字的哈弗曼编码。
为什么能压缩:压缩的时候当我们遇到了文本中的1、2、3、4几个字符的时候,我们不用原来的存储,而是转化为用它们的01串来存储不久是能减小了空间占用了吗。
(什么01串不是比原来的字符还多了吗?怎么减少?)大家应该知道的,计算机中我们存储一个int型数据的时候一般式占用了2^32-1个01位,因为计算机中所有的数据都是最后转化为二进制位去存储的。
所以,想想我们的编码不就是只含有0和1嘛,因此我们就直接将编码按照计算机的存储规则用位的方法写入进去就能实现压缩了。
比如:1这个数字,用整数写进计算机硬盘去存储,占用了2^32-1个二进制位而如果用它的哈弗曼编码去存储,只有110三个二进制位。
效果显而易见。
霍夫曼编码的应用,找一篇英文文章或书籍进行处理压缩存储利用霍夫...
一.模型表示: 计算机使用数字代码来存储字符,ASC II码是最常用的编码。
一个ASC II码值占一个字节(8个二进制位),其最高位(b7)用作奇偶校验位,共128个。
要对一个文本文件进行压缩,就是要对文件内的字符重新编码,使出现次数较多的字符用较短的编码存储,而出现次数少的字符则采用相对较长的编码存储,最终使压缩后整个文件的大小小于原文件。
这里采用哈夫曼编码方式来对每个字符重新编码,因为哈夫曼树具有最小带权路径长度的性质,能够生成用于压缩的二进制前缀码。
程序使用的 “静态统计模型”,也就是说在编码前统计要编码的信息中所有字符的出现频率,字符的出现频率即为字符的权,然后根据统计出的信息建立编码树,进行编码。
利用所得的编码生成压缩文件。
由于采用的是“静态统计模型”,在压缩文件里必须保存统计出的结果以便解码时构造相同的编码树,或者直接保存编码树本身。
在解压缩时,首先从文件头读入保存的编码信息,从而对后续的编码解码,还原成ASCII的形式,生成与原文相同的文件。
二.概要设计: 由于一棵有n个叶子结点的哈夫曼树共有2n-1个结点,考虑到程序的执行效率,可以将二叉树存放在连续空间里(静态链表),空间的每个结点内仍有左子树、右子树、双亲等指针,以便译码和解码。
即存储在一个大小为2n-1的一维数组中,每个结点的结构为: struct HNode { char elem; //保存结点所表示的字符(主要用于译码时) unsigned long weight; //保存结点的权值,对于叶子,即为字符的出现次数 int parent, lchild, rchild; //保存结点的双亲,左右孩子的位置
利用huffman树实现文件的压缩与解压
这是本人写的动态哈夫曼压缩算法实现,压缩与解压缩时, 根据文件内容自动生成哈夫曼树,并动态调整节点的权重 和树的形状。
900MHZ的PIII赛扬每秒钟可以压缩的好几MB 的数据,只是压缩率不高,文本文件的压缩后容量一般可 以减少25%,比RAR差远了。
源文件共三个,你在VC6.0中新建一个空的命令行项目, 将它们加进去,编译完就可以用了。
===========hfm.cpp=================== #include #include #include #include #include #include "Huffman.h" int wh; int rh; bool Write(unsigned char *s,int len){ _write(wh,s,len); return true; } bool OpenFile(char* source,char* target){ int w_flag=_O_WRONLY | _O_CREAT | _O_EXCL | _O_BINARY; int r_flag=_O_RDONLY | _O_BINARY; rh=_open(source,r_flag,_S_IREAD | _S_IWRITE); wh=_open(target,w_flag,_S_IREAD | _S_IWRITE); if(rh==-1 || wh==-1){ if(rh!=-1){ _close(rh); printf("\n打开文件:'%s'失败!",target); } if(wh!=-1){ _close(wh); printf("\n打开文件:'%s'失败!",source); } return false; }else{ return true; } } void PrintUsage(){ printf("\n以动态哈夫曼算法压缩或解压缩文件。
\n\n"); printf("\thfm -?\t\t\t\t显示帮助信息\n"); printf("\thfm -e -i source -o target\t压缩文件\n"); printf("\thfm -d -i source -o target\t解压缩文件\n\n"); } void main(int argc,char *args[]){ int mode,i,j,K=0; char src[4096]; char target[4096]; unsigned char buffer[BUFFER_SIZE]; Huffman *h; mode=0; for(i=1;i if(args[i][0]=='-' || args[i][0]=='/'){ switch(args[i][1]){ case '?': mode=0;//帮助 break; case 'e': case 'E': mode=1;//压缩 break; case 'd': case 'D': mode=2;//解压缩 break; case 'o': case 'O': if(i+1>=argc){ mode=0; }else{//输出文件 j=0; while(args[i+1][j]!='\0' && j target[j++]=args[i+1][j]; } if(j==4096){ mode=0; }else{ target[j]='\0'; K |= 1; } } break; case 'i': case 'I': if(i+1>=argc){ mode=0; }else{//输入文件 j=0; while(args[i+1][j]!='\0' && j src[j++]=args[i+1][j]; } if(j==4096){ mode=0; }else{ src[j]='\0'; K |=2; } } break; } } } if(K!=3)mode=0; switch(mode){ case 0: PrintUsage(); return; case 1://压缩 if(!OpenFile(src,target))return; h=new Huffman(&Write,true); i=BUFFER_SIZE; while(i==BUFFER_SIZE){ i=_read(rh,buffer,BUFFER_SIZE); h->Encode(buffer,i); } delete h; _close(rh); _close(wh); printf("压缩完毕!"); break; case 2://解压缩 if(!OpenFile(src,target))return; h=new Huffman(&Write,false); i=BUFFER_SIZE; while(i==BUFFER_SIZE){ i=_read(rh,buffer,BUFFER_SIZE); h->Decode(buffer,i); } delete h; _close(rh); _close(wh); printf("解压缩完毕!"); break; } } =======end of hfm.cpp======================= =======Huffman.cpp============================= // Huffman.cpp: implementation of the Huffman class. // ////////////////////////////////////////////////////////////////////// #include "Huffman.h" ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// Huffman::Huffman(Output *output,bool mode) { Hbtree *tmp; int i; this->mode=mode; //设置输出函数,当缓冲区满时,将调用该函数输出 this->output=output; //初始化列表 for(i=0;i list[i]=NULL; //初始化哈夫曼树 this->root=this->NewNode(NOT_CHAR,LEFT,NULL); this->current=this->root; tmp=this->NewNode(CODE_ESCAPE,RIGHT,root); tmp->count=1; tmp=this->NewNode(CODE_FINISH,LEFT,root); tmp->count=0; root->count=root->child[LEFT]->count+root->child[RIGHT]->count; //设置缓冲区指针 this->char_top=BOTTOM_BIT; this->bit_top=TOP_BIT; this->buffer[0]=0; //重构哈夫曼树的最大计数值 this->max_count=MAX_COUNT; this->shrink_factor=SHRINK_FACTOR; this->finished=false; } Huffman::~Huffman() { if(this->mode==true){//如果是编码 //输出结束码 this->OutputEncode(CODE_FINISH); this->char_top++; } //强制清空缓冲区 this->Flush(); //释放空间 this->ReleaseNode(this->root); } Hbtree * Huffman::NewNode(int value, int index, Hbtree *parent) { Hbtree *tmp=new Hbtree; tmp->parent=parent; tmp->child[0]=NULL; tmp->child[1]=NULL; tmp->count=(1 tmp->index=(index==0) ? 0 : 1; tmp->value=value; if(value!=NOT_CHAR)this->list[tmp->value]=tmp; if(parent!=NULL)parent->child[tmp->index]=tmp; return tmp; } void Huffman::ReleaseNode(Hbtree *node) { if(node!=NULL){ this->ReleaseNode(node->child[LEFT]); this->ReleaseNode(node->child[RIGHT]); delete node; } } //输出一位编码 int Huffman::OutputBit(int bit) { unsigned char candidates[]={1,2,4,8,16,32,64,128}; if(bit!=0) this->buffer[this->char_top] |= candidates[this->bit_top]; this->bit_top--; if(this->bit_top this->bit_top=TOP_BIT; this->char_top++; if(this->char_top >= BUFFER_SIZE){//输出缓冲区 this->output(this->buffer,BUFFER_SIZE); this->char_top=0; } this->buffer[this->char_top]=0; } return 0; } //输出缓冲区 int Huffman::Flush() { this->...
哈夫曼编码与压缩 输入一段文本,统计其中字符出现频率,设计相应的...
#include#include#include#includestruct HuffmanTree{ int weight; int parent,lchild,rchild; char ch;};typedef char** HuffmanCode;struct return_value_sel{ int re_s1; int re_s2;};struct return_value_def{ char re_p[100]; int *re_in; int re_count;};struct return_value_HTHC{ HuffmanTree *re_HT; HuffmanCode re_HC;};return_value_def def_wei(char in_ch[]){ char ch[100]; int ch_wei[100]; int i,j,n = 0,tab = 1; return_value_def re; for(i = 0;in_ch[i] != '\0';i++) { for(j = 0;j =1;i--) if(HT[i].parent==0 && HT_wei>=HT[i].weight) {HT_wei = HT[i].weight; s1 = i;} if(s1==t) { HT_wei = HT[t-1].weight; } else { HT_wei = HT[t].weight; } for(i=t;i>=1;i--) if(HT[i].parent==0 && HT_wei>=HT[i].weight && i!=s1) {HT_wei = HT[i].weight; s2 = i;} re.re_s1 = s1; re.re_s2 = s2; return re;}return_value_HTHC HuffmanCoding(HuffmanTree *HT,int *w,int n,char ch_in[]){ int m,i; HuffmanTree *p; char *cd; HuffmanCode HC; return_value_HTHC re_value_HTHC; return_value_sel get_re; if(nweight = *w; p->lchild = 0; p->rchild = 0; p->parent = 0; p->ch = ch_in[i-1]; } for(;iweight = 0; p->lchild = 0; p->rchild = 0; p->parent = 0; p->ch = NULL; } for(i=n+1;i>ch; choose = ch[0]; for(;;) { if(choose != '1'&&choose!='2'&&choose!= '3'&&choose!='0') { cout>ch; choose = ch[0]; } else break; } switch(choose) { case '1': cout>edit_str; cout>trans_str; for(i=0;trans_str[i]!='\0';i++) if(trans_str[i]!='0'&&trans_str[i]!='1') { cout<<"输入中有非法字符,请重新输入!!"<<endl; cout<...
哈夫曼编码原理
霍夫曼(Huffman)编码属于码词长度可变的编码类,是霍夫曼在1952年提出的一种编码方法,即从下到上的编码方法。
同其他码词长度可变的编码一样,可区别的不同码词的生成是基于不同符号出现的不同概率。
生成霍夫曼编码算法基于一种称为“编码树”(coding tree)的技术。
算法步骤如下:(1)初始化,根据符号概率的大小按由大到小顺序对符号进行排序。
(2)把概率最小的两个符号组成一个新符号(节点),即新符号的概率等于这两个符号概率之和。
(3)重复第2步,直到形成一个符号为止(树),其概率最后等于1。
(4)从编码树的根开始回溯到原始的符号,并将每一下分枝赋值为1,上分枝赋值为0。
以下这个简单例子说明了这一过程。
1).字母A,B,C,D,E已被编码,相应的出现概率如下: p(A)=0.16, p(B)=0.51, p(C)=0.09, p(D)=0.13, p(E)=0.112).C和E概率最小,被排在第一棵二叉树中作为树叶。
它们的根节点CE的组合概率为0.20。
从CE到C的一边被标记为1,从CE到E的一边被标记为0。
这种标记是强制性的。
所以,不同的哈夫曼编码可能由相同的数据产生。
3).各节点相应的概率如下: p(A)=0.16, p(B)=0.51, p(CE)=0.20, p(D)=0.13 D和A两个节点的概率最小。
这两个节点作为叶子组合成一棵新的二叉树。
根节点AD的组合概率为0.29。
由AD到A的一边标记为1,由AD到D的一边标记为0。
如果不同的二叉树的根节点有相同的概率,那么具有从根到节点最短的最大路径的二叉树应先生成。
这样能保持编码的长度基本稳定。
4).剩下节点的概率如下:p(AD)=0.29, p(B)=0.51, p(CE)=0.20AD和CE两节点的概率最小。
它们生成一棵二叉树。
其根节点ADCE的组合概率为0.49。
由ADCE到AD一边标记为0,由ADCE到CE的一边标记为1。
5).剩下两个节点相应的概率如下:p(ADCE)=0.49, p(B)=0.51它们生成最后一棵根节点为ADCEB的二叉树。
由ADCEB到B的一边记为1,由ADCEB到ADCE的一边记为0。
6).图03-02-2为霍夫曼编码。
编码结果被存放在一个表中: w(A)=001, w(B)=1, w(C)=011, w(D)=000, w(E)=010图03-02-2 霍夫曼编码例霍夫曼编码器的编码过程可用例子演示和解释。
下面是另一个霍夫曼编码例子。
假定要编码的文本是: "EXAMPLE OF HUFFMAN CODE"首先,计算文本中符号出现的概率(表03-02-2)。
表03-02-2 符号在文本中出现的概率符号 概率E 2/25X 1/25A 2/25M 2/25P 1/25L 1/25O 2/25F 2/25H 1/25U 1/25C 1/25D 1/25I 1/25N 2/25G 1/25空格 3/25最后得到图03-02-3所示的编码树。
图03-02-3 霍夫曼编码树在霍夫曼编码理论的基础上发展了一些改进的编码算法。
其中一种称为自适应霍夫曼编码(Adaptive Huffman code)。
这种方案能够根据符号概率的变化动态地改变码词,产生的代码比原始霍夫曼编码更有效。
另一种称为扩展的霍夫曼编码(Extended Huffman code)允许编码符号组而不是单个符号。
同香农-范诺编码一样,霍夫曼码的码长虽然是可变的,但却不需要另外附加同步代码。
这是因为这两种方法都自含同步码,在编码之后的码串中都不需要另外添加标记符号,即在译码时分割符号的特殊代码。
当然,霍夫曼编码方法的编码效率比香农-范诺编码效率高一些。
采用霍夫曼编码时有两个问题值得注意:①霍夫曼码没有错误保护功能,在译码时,如果码串中没有错误,那么就能一个接一个地正确译出代码。
但如果码串中有错误,那怕仅仅是1位出现错误,也会引起一连串的错误,这种现象称为错误传播(error propagation)。
计算机对这种错误也无能为力,说不出错在哪里,更谈不上去纠正它。
②霍夫曼码是可变长度码,因此很难随意查找或调用压缩文件中间的内容,然后再译码,这就需要在存储代码之前加以考虑。
尽管如此,霍夫曼码还是得到广泛应用。
数据结构实验,求大神提供完整代码(c或c++),不胜感激啊…… 利...
#include #include #include #include #include #include #define INF 10000using namespace std;//------哈夫曼树的存储表示------typedef struct{char data; //结点的字符int weight; //结点的权值int parent,lchild,rchild; //结点的双亲,左孩子,右孩子下标}HTNode,*HFMTree;HFMTree HT;//------哈夫曼编码表的存储表示------typedef char** HFMcode; //动态分配数组存储哈夫曼编码表HFMcode HC;int N; //字符集个数//函数声明void hello(); //欢迎界面void func(); //具体功能函数void initHFM(HFMTree &,int); //构造哈夫曼树void select(HFMTree,int,int&); //构造哈弗曼树的子函数--选择结点void creatHFMcode(HFMTree,HFMcode &,int); //求哈夫曼编码void add_code_to_file(HFMTree,HFMcode,int); //将初始哈夫曼编码存入文件hfmTree中void Encoding(); //编码void Decoding(); //译码void Print(); //显示编码//函数定义void hello(){cout>c;switch(c){case'I':case'i':cout>N;initHFM(HT,N);break;case'E':case'e':Encoding();break;case'D':case'd':Decoding();break;case'P':case'p':Print();break;case'T':case't':;case'O':case'o':case'0':exit(0);default:cout>HT[i].weight; //输入前n个单元叶子结点的权值for(int i=n+1;iHT[j].weight){minn=HT[j].weight;s=j;}}}HT[s].parent=x+1;}void creatHFMcode(HFMTree HT,HFMcode &HC,int n){//从叶子到根逆向求每个字符的哈夫曼编码,存储在编码表HC中HC=new char*[n+1]; //分配存储n个字符编码的动态数组空间char *cd=new char[n]; //分配临时存放每个字符编码的动态数组空间cd[n-1]='\0'; //编码结束符for(int i=1;i<=n;i++) //逐个字符求哈夫曼编码{int start=n-1; //start开始时指向最后,及编码结束符位置int c=i,f=HT[i].parent; //f指向c的双亲结点while(f!=0){--start;if(HT[f].lchild==c)cd[start]='0';else cd[start]='1';c=f;f=HT[f].parent;}HC[i]=new char[n-start];strcpy(HC[i],&cd[start]);}delete cd;}void add_code_to_file(HFMTree HT,HFMcode HC,int n){//将初始哈夫曼编码存入文件hfmTree中ofstream out;out.open("hfmTree.txt",ios::out);out<<left;out<<setw(4)<<"字符"<<':'<<"编码"<<endl;for(int i=1;i<=n;i++)out<<' '<<HT[i].data<<" :"<<HC[i]<<'\n';out.close();}void Encoding(){ofstream out1;out1.open("ToBeTran.txt",ios::out);out1<<"THIS PROGRAM IS MY FAVORITE";out1.close();ifstream in;in.open("ToBeTran.txt",ios::in);char str[1000];in.getline(str,999);ofstream out2;out2.open("CodeFile.txt",ios::out);for(int i=0;str[i]!='\0';i++){for(int j=1;j<=N;j++){if(str[i]==HT[j].data){out2<<HC[j];out2<<' ';}}}out2.close();in.close();cout<<"编码成功,请继续操作\n";hello();}void Decoding(){ifstream in;in.open("CodeFile.txt",ios::in);char str[1000];in.getline(str,999);for(int i=0;str[i]!='\0';){char s[N];int j=i;int t=0;while(str[j]!=' '){s[t]=str[j];t++;j++;i++;}s[t]='\0';//cout<<s<<' ';for(int x=1;x<=N;x++)if(strcmp(s,HC[x])==0)cout<<HT[x].data;i++;}in.close();cout<<"\n译码成功,请继续操作\n";hello();}void Print(){ifstream in;in.open("CodeFile.txt",ios::in);char str[1000];in.getline(str,999...
转载请注明出处51数据库 » 利用哈夫曼编码的文本压缩软件