|
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ /*huffman压缩与解压程序（解压部分复杂度挺高，可由读者换种算法实现）*/ /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ /****************************************************************/ /*头文件的包含*/ #include<iostream> #include<fstream> #include<iomanip> #include<string> #include<stack> #include<cmath> #include<ctime> #include<windows.h> using namespace std; #define SIZE 514 //树节点的上限，最多256个内节点，257个叶节点，最后一个结束； #define CODE 32 //编码数组长度； /*****************************************************************/ /*****************************************************************/ struct Huffman_node{ //Huffman树节点的结构； char ch_; //字符； long freq_; //字符出现频率； int lc_; //左子； int rc_; //右子； int parent_; //父节点； char code_[CODE]; //哈弗曼编码； }; typedef struct Huffman_node Hfmn; /*****************************************************************/ /*****************************************************************/ /*全局变量*/ Hfmn root; //根节点； Hfmn Node[SIZE]; //定义Huffman树节点数组； int min; //频率最小节点下标； int total; //内点数； string file; //要压缩的文件； int zero; //补‘ double first=0,last=0; //压缩前与压缩后文件长度； clock_t start1,finish1; //计算压缩时间； clock_t start2,finish2; //计算解压时间； //string filey; /*****************************************************************/ /*****************************************************************/ /*函数声明*/ void Node_initialize(void); //初始化数组Node； void Freq_count(void); //打开指定文件统计字符出现频率； void Node_selectmin(long a[],int b);//从数组中找出概率最小的； void Huffman_tree_create(void); //构造Huffman树； void Huffman_code(void); //构建Huffman编码； void Huffman_save(void); //存储Huffman树到文件； void Huffman_compress(void); //实现Huffman压缩； void Huffman_decompress(void); //实现Huffman解压； /*****************************************************************/ /*****************************************************************/ /*函数实现*/ /*初始化数组Node函数*/ void Node_initialize(void) { for(int i=0;i<SIZE;i++){ Node[i].ch_='#'; Node[i].freq_=0; Node[i].lc_=-1; Node[i].rc_=-1; Node[i].parent_=-1; for(int k=0;k<CODE;k++){ (Node[i].code_)[k]='\0'; } } } /*统计频率函数*/ void Freq_count(void) { char ch; //暂存从文件读出的字符； int i=0,j=0; //用于循环控制； bool same; //判断是否是新的字符； cout<<"请输入要压缩的文件："<<endl; getline(cin,file); //获取要压缩的文件； start1=clock(); //压缩开始时间； fstream tfile(file.c_str(),ios_base::binary|ios_base::in); ch=tfile.get(); //读取文件中第一个字符； if(!tfile.eof()){ Node[i].ch_=ch; //添加新字符到数组； Node[i].freq_++; //频率加1； i++; //推进数组； ch=tfile.get(); //读下一个字符； while(!tfile.eof()){ for(j=0;j<i;j++){ //将字符与现有字符比较； ch==Node[j].ch_?same=true:same=false; if(same==true){ //如果相同，频率加1； Node[j].freq_++; break; } } if(same==false){ //如果不同，添加进数组； Node[i].ch_=ch; Node[i].freq_++; i++; //推进数组； } ch=tfile.get(); //往下读； } total=i-1; //获取字符总数； } tfile.close(); } /*找频率最小节点函数*/ void Node_selectmin(long a[],int size) { min=0; for(int i=0;i<size;i++){ if(a[i]<a[min]){ min=i; //获取频率最小节点的下标； } } } /*构造Huffman树函数*/ void Huffman_tree_create(void) { long F[SIZE]; //用于操作的节点数组频率拷贝； int ini=total; //内节点开始的数组下表； int size=total; //拷贝数组的元素个数； int a,b; //辅助变量； for(int i=0;i<total;i++){ //拷贝频率； F[i]=Node[i].freq_; } for(int j=0;j<total-1;j++){ //构造Huffman树； Node_selectmin(F,size); //构建左子； Node[ini].lc_=min; Node[min].parent_=ini; a=min; F[min]=9999999; Node_selectmin(F,size); //构建右子； Node[ini].rc_=min; Node[min].parent_=ini; b=min; F[min]=9999999; Node[ini].freq_=Node[a].freq_+Node[b].freq_; //父节点权值； F[ini]=Node[ini].freq_; //将新节点加入拷贝数组； ini++; //推进树节点数组； size++; //增加拷贝数组长度； } root.freq_=Node[ini-1].freq_; //根节点赋值； root.lc_=Node[ini-1].lc_; root.rc_=Node[ini-1].rc_; root.ch_=Node[ini-1].ch_; Node[ini-1].parent_=-1; } /*构建Huffman编码函数，由下往上编码*/ void Huffman_code(void) { int x,y; //辅助变量； std::stack<char> hold; //用栈； for(int i=0;i<total;i++){ //构建Huffman编码； x=Node[i].parent_; //父节点下标； y=i; //现结点下标； while(x!=-1){ //不到根节点时继续循环； if(Node[x].lc_==y){ //为左子时，'1'入栈； hold.push('1'); } else if(Node[x].rc_==y){ //为右子时，'0'入栈； hold.push('0'); } else cout<<"error"<<endl; y=Node[y].parent_; //现节点推进； x=Node[x].parent_; //父节点推进； } int j=0; while(!hold.empty()){ //将字符出栈，得到Huffman编码； Node[i].code_[j]=hold.top(); hold.pop(); j++; } Node[i].code_[j]='\0'; } } /*存储Huffman树信息函数*/ void Huffman_save() { ofstream tfile("Huffmancode.txt",ios_base::out); for(int i=0;i<total;i++){ tfile<<Node[i].ch_<<endl<<"霍夫曼编码是："<<Node[i].code_<<endl; tfile<<"出现次数为："<<Node[i].freq_<<endl; tfile<<"父节点为："<<Node[i].parent_<<endl<<endl; int j=Node[i].parent_; tfile<<"左子为："<<Node[j].lc_<<endl<<"右子为："<<Node[j].rc_<<endl<<endl; } tfile.close(); } /*Huffman压缩函数*/ void Huffman_compress(void) { char ch0,ch; //ch0从要压缩文件，读取字符；ch暂存压缩字符的ASCII码； int a=0,c=0; //辅助变量； char str[9]; //暂存8位要操作0,1编码 str[8]='\0'; ifstream tfilein(file.c_str(),ios_base::binary|ios_base::in); fstream tfile("file1.txt",ios_base::binary|ios_base::out); ch0=tfilein.get(); while(!tfilein.eof()){ //将字符转换为Huffman编码输出到中介文件； while(Node[a].ch_!='#'){ if(ch0==Node[a].ch_){ tfile<<Node[a].code_; break; } a++; } a=0; ch0=tfilein.get(); first++; //统计要压缩文件的大小； } tfilein.close(); tfile.close(); tfile.open("file1.txt",ios_base::binary|ios_base::in); ofstream tfileout("yasuo.txt",ios_base::binary|ios_base::out); for(int k=0;k<8;k++){ //读取中介文件中的8位字符； str[k]=tfile.get(); } while(!tfile.eof()){ //将每8位编码字符转换成一位压缩字符，输出到文件； c=0; for(int i=0;i<8;i++){ //将8位字符转换为一位ASCII码； if(str[i]!='0') c=c+(int)(str[i]-'0')*pow(2,8-1-i); } ch=(char)c; //强制转换为压缩字符； tfileout.write(&ch,1); //写入压缩文件； if(str[8]=='0') break; //如果文件结束，跳出循环； for(int k=0;k<8;k++){ //读取字符； str[k]=tfile.get(); if(str[k]==EOF){ //文件结束，未满8位则补'0'； for(int j=k;j<9;j++) { str[j]='0'; } zero=8-k; //记录补'0'数； break; } } } tfile.close(); tfileout.close(); finish1=clock(); //压缩结束时间； } /*Huffman解压函数*/ void Huffman_decompress(void) { char ch[9]; //暂存ASCII码转换成的8位1,0字符； int c; //暂存压缩文件里的压缩字符； int j=0,k=0; //辅助变量； char str[CODE]; //用于与Huffman编码对比的数组； ch[8]='\0'; start2=clock(); //解压开始时间； ifstream tfilein("yasuo.txt",ios_base::binary|ios_base::in); fstream tfile("jieya2.txt",ios_base::binary|ios_base::out); while(!tfilein.eof()){ //将压缩字符转换为1,0字符； c=(int)(tfilein.get()); //取得压缩字符的ASCII码； last++; //统计压缩文件大小； for(int i=7;i>=0;i--){ //将一位ASCII码还原为8位1,0字符； ch[i]=(char)(c%2+'0'); c=c/2; } tfile<<ch; } tfilein.close(); tfile.close(); tfile.open("jieya2.txt",ios_base::binary|ios_base::in); ofstream tfileout("jieya.txt",ios_base::binary|ios_base::out); while(!tfile.eof()){ //利用Huffman码将0,1字符串还原为原文字符； for(j=0;j<CODE;j++){ //从一位开始比较； str[j]=tfile.get(); str[j+1]='\0'; for(k=0;k<total;k++){ //与每个字符的编码比较； if(!strcmp(str,Node[k].code_)){ tfileout<<Node[k].ch_; goto L1; //找到，跳出循环； } } } L1:; } tfile.close(); tfileout.close(); finish2=clock(); //解压结束时间； } /**************************************************************************/ /**************************************************************************/ /*main函数*/ main() { double d; //存放压缩率； double time1,time2; //存放压缩和解压时间； Node_initialize(); //初始化数组Node； Freq_count(); //打开指定文件统计字符出现次数； Huffman_tree_create(); //构造Huffman树； Huffman_code(); //构建Huffman编码； Huffman_save(); //存储Huffman树到文件； Huffman_compress(); //根据Huffman编码压缩文件； Huffman_decompress(); //根据编码解压缩文件； DeleteFileA("file1.txt"); //删除无用文件； DeleteFileA("jieya2.txt"); //删除无用文件； DeleteFileA("Huffmancode.txt"); //删除无用文件； d=(double)(last/first)*100; //计算压缩率； time1=(double)(finish1-start1)/CLOCKS_PER_SEC; //计算压缩时间； time2=(double)(finish2-start2)/CLOCKS_PER_SEC; //计算解压时间； cout<<"压缩时间为："<<time1<<"s"<<endl; cout<<"解压时间为："<<time2<<"s"<<endl; cout<<"压缩率为："<<setprecision(4)<<d<<"%"<<endl; return 0; } /**************************************************************************/ /*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ |
|
|
