英文文件的壓縮和解壓縮程序

合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系一、問(wèn)題分析和任務(wù)定義1、題目采用哈夫曼編碼思想實(shí)現(xiàn)英文文本的壓縮與解壓縮，并提供壓縮前后的占用空間比。要求1）壓縮原文件規(guī)模不小于5K2）提供解壓縮文件后文件與原文件的相同性比較功能2、問(wèn)題分析壓縮過(guò)程 news.txt->news1.txt1、以讀的形式打開(kāi)需要壓縮的一個(gè)英文本文件，把其中出現(xiàn)的所有字符按其在文本中出現(xiàn)的頻率利用哈夫曼樹(shù)進(jìn)行編碼。2、以寫的形式打開(kāi)一個(gè)新的文本文件，把它作為英文文本壓縮后的文本文件，掃描需要壓縮的英英文本文件（new.txt）中所有字符，把其對(duì)應(yīng)的編碼通過(guò)轉(zhuǎn)換后存入新的文本文件（new1.txt）中。3、把需要壓縮的英文文本（new.txt）中所出現(xiàn)的字符及其編碼等原始文件的信息保存在新的文本文件中。解壓縮過(guò)程news1.txt-^news2.txt1、以讀的形式打開(kāi)一個(gè)壓縮文件news1.txt，按其中保存的原始文件的信息還原哈夫曼樹(shù)及字符編碼。2、以寫的形式打開(kāi)一個(gè)新的文本文件，作為解壓后的英文文本news2.txt，逐個(gè)掃描壓縮文件news1.txt中的所有字符，把其中所有轉(zhuǎn)換后的編碼再轉(zhuǎn)換回來(lái)并與哈夫曼樹(shù)中存儲(chǔ)的字符編碼比較，把其對(duì)應(yīng)的字符寫入聯(lián)亞$2"乂=中。一個(gè)字符在文本文件中存儲(chǔ)時(shí)占一個(gè)字節(jié)，而其二進(jìn)制編碼若直接存入文本文件其所占的空間不會(huì)少于一個(gè)字節(jié)。例如：假設(shè)字符E的編碼為001，若把001直接存入文件只能用字符串的形式，其所占用的空間為三個(gè)字節(jié)。達(dá)不到文件壓縮的目的，所以必須對(duì)編碼的存儲(chǔ)空間進(jìn)行轉(zhuǎn)換。3編碼轉(zhuǎn)換在文本文件中字符之間是連續(xù)的，所以在文本文件中存儲(chǔ)編碼也是連續(xù)的?？梢园堰B續(xù)的不同字符的編碼存入同一個(gè)字節(jié)，再把這一個(gè)字節(jié)的二進(jìn)制碼轉(zhuǎn)換成一個(gè)字符，把轉(zhuǎn)換后的字符存儲(chǔ)在文本文件中。二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)：1此程序采用的數(shù)據(jù)結(jié)構(gòu)為順序表。哈夫曼樹(shù)是二叉樹(shù)的一種，二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中可以把結(jié)點(diǎn)間的關(guān)系放在其存儲(chǔ)位置中，無(wú)需附加任何信息就能在這種結(jié)構(gòu)中找到每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)，這正是哈夫曼編碼所需要的。哈夫曼樹(shù)順序表：結(jié)構(gòu)體header[512],表中每個(gè)結(jié)點(diǎn)包括以下信息unsignedcharb字符名

圖1 程序的實(shí)現(xiàn)過(guò)程表1 程序中所包括的函數(shù)及其功能函數(shù)名所實(shí)現(xiàn)的功能compress()實(shí)現(xiàn)文件壓縮 （被主函數(shù)調(diào)用）uncompress()實(shí)現(xiàn)文件解壓縮（被主函數(shù)調(diào)用）huffman()對(duì)文件中出現(xiàn)的字符進(jìn)行編碼（被以上兩函數(shù)調(diào)用）Main()pressuncohuffamMain()pressuncohuffam圖2 程序模塊間的調(diào)用關(guān)系2、算法流程（假如原文件中只有一句話Iamhere）1）壓縮過(guò)程（主函數(shù)調(diào)用compress（）函數(shù)）掃描文檔知alcount=9n=6eIamhrcount2211111parent1077889bits101100000001010011001權(quán)值：count表2 利用權(quán)值進(jìn)行編碼圖3 進(jìn)行哈夫曼樹(shù)的構(gòu)造000011000101011011100011012862270因?yàn)榘宋坏亩M(jìn)制碼轉(zhuǎn)化為的整數(shù)完全可以用ASCLL碼值對(duì)應(yīng)的字符來(lái)代替在原文件（new.txt）中一共占用了9個(gè)字節(jié)，而如果按上圖的存儲(chǔ)方式存入文件則只要4個(gè)字節(jié)2）解壓縮過(guò)程12862271286227把以字符的形式存儲(chǔ)在文件（new1.txt）中的編碼還原0000110001010110111000110依次把還原后的存儲(chǔ)編碼與字符的編碼比較，若相同則把字符寫入文件(new2.txt)11000101011011100011000010101101110001100101101110001101101110001100111000110100011000110圖4 哈夫曼編碼的還原過(guò)程二、 詳細(xì)設(shè)計(jì)和編碼.要完成對(duì)文件的壓縮和解壓縮，首先要建立哈夫曼編碼的算法，而要建立哈夫曼編碼的算法，就要定義哈夫曼樹(shù)采用的順序表結(jié)構(gòu)以下是基本的數(shù)據(jù)結(jié)構(gòu)的定義哈夫曼樹(shù)采用順序表的結(jié)構(gòu)structhead{ 〃結(jié)構(gòu)體unsignedcharb; 〃存儲(chǔ)字符intcount; 〃權(quán)值longparent,lch,rch;charbits[256]; 〃編碼}header[512],tmp;.〃文件壓縮過(guò)程a.要實(shí)現(xiàn)文件的壓縮過(guò)程，首先要從文本中讀入一個(gè)字符，若讀入的是哈夫曼樹(shù)中的第i個(gè)字符，則把第i個(gè)字符的編碼接在之前定義過(guò)的字符串buf的未尾Buf[0]=0；while(q!=alcount){fread(&c,1,1,ifp);//從文本中讀入一個(gè)字符

fread(&c,1,1,ifp);//從文本中讀入一個(gè)字符q++；for(i=0;i<n;i++) //n為不重復(fù)計(jì)數(shù)的所有字符數(shù)if(c==header[i].b)break; 〃如果讀入的是哈夫曼樹(shù)中的第i個(gè)字符strcat(buf,header[i].bits); //把第i個(gè)字符的編碼接在字符串buf的末尾j=strlen(buf);b.當(dāng)字符串buf的長(zhǎng)度大于或等于8時(shí)，把前8位的編碼轉(zhuǎn)化為整數(shù),之后再把這個(gè)整數(shù)強(qiáng)制轉(zhuǎn)化為字符串并寫入壓縮文件，最后把已經(jīng)寫入文件的編碼從buf中去掉while(j>=8)時(shí){f=0;for(p=7;p>=0;p--)用了if(buf[p]==,1')f=shuxue(7-p)+f;c=(unsignedchar)f;fwrite(&c,1,1,ofp);pt1++;strcpy(buf,buf+8);中去掉j=strlen(buf);〃當(dāng)字符串buf的長(zhǎng)度大于或等于8//把前8位的編碼轉(zhuǎn)化為整數(shù)(調(diào)shuxue函數(shù)求2的次方)//把這個(gè)整數(shù)變?yōu)樽址?/寫入壓縮文件〃當(dāng)字符串buf的長(zhǎng)度大于或等于8//把前8位的編碼轉(zhuǎn)化為整數(shù)(調(diào)shuxue函數(shù)求2的次方)//把這個(gè)整數(shù)變?yōu)樽址?/寫入壓縮文件〃把已經(jīng)寫入文件的編碼從buf//j用來(lái)統(tǒng)計(jì)字符串的if(j>0){f=0;for(p=j-1;p>=0;p--)文件if(buf[p]==,1')f=shuxue(j-p-1)+f;c=(unsignedchar)f;fwrite(&c,1,1,ofp);pt1++;//當(dāng)buf中最后的字符串小于8位時(shí)〃把它變成整數(shù)，轉(zhuǎn)化為字符寫入壓縮在解壓縮前必順依靠字符的權(quán)值班重新對(duì)字符進(jìn)行哈夫曼編碼(調(diào)用huffman函數(shù)).文件的解壓縮過(guò)程a.若要實(shí)現(xiàn)文件的解壓縮，在解壓縮前必順依靠字符的權(quán)值班重新對(duì)字符進(jìn)行哈夫曼編碼(調(diào)用huffman函數(shù))，首先定義一個(gè)字符串，當(dāng)字符串bx的長(zhǎng)度小于p時(shí)，從壓縮文件讀入一字符(8位)，并把字符轉(zhuǎn)化為整數(shù)，之后再把整數(shù)轉(zhuǎn)化為二進(jìn)制碼的字符串存入字符串buf，統(tǒng)計(jì)字符串buf的長(zhǎng)度，如果小于8位，則給編碼補(bǔ)零，并把字符串buf接在字符串bx末abx[0]=0;while(1){時(shí)fread(&c,1,1,ifp)(8位)f=c;itoa(f,buf,2);串buf〃p為編碼最長(zhǎng)的字符的編碼長(zhǎng)度〃p為編碼最長(zhǎng)的字符的編碼長(zhǎng)度〃當(dāng)字符串bx的長(zhǎng)度小于p//從壓縮文件讀入一字符把字符轉(zhuǎn)化為整數(shù)//把整數(shù)轉(zhuǎn)化為二進(jìn)制碼的字符串存入字符f=strlen(buf);if(f<8){for(i=0;i<8-f;i++){memmove(buf+1,buf,f+1)buf[0]='0';))strcat(bx,buf);bx末}//統(tǒng)計(jì)字符串buf的長(zhǎng)度}//如果小于8位//給編碼補(bǔ)零//把字符串buf接在字符串b.當(dāng)完成上面步驟時(shí)，把bx的部分編碼與字符的編碼進(jìn)行比較，若相同，則去掉bx中這部分相同的編碼，并把找到的字符寫入解壓文件。for(i=0;i<n;i++) 〃把bx的部分編碼與字符的編碼進(jìn)行比較{f=strlen(header[i].bits); //若相同if(memcmp(header[i].bits,bx,f)==0)break;strcpy(bx,bx+f);//則去掉strcpy(bx,bx+f);//則去掉bx中這部分相同的c=header[i].b;c=header[i].b;編碼//并把找到的字符寫入解壓文件fwrite(&c,1,1,ofp);m++;if(m==alcount)break;）四、上機(jī)調(diào)試問(wèn)題1：在文件中一個(gè)字符占一個(gè)字節(jié)，給字符編碼后，其編碼要如何存入壓縮文件才能起到壓縮的作用。解決：若直接存儲(chǔ)，編碼只能用字符串，這樣存儲(chǔ)空間不僅沒(méi)有減少反而增大了。所以必順把多個(gè)編碼存在一個(gè)字節(jié)中，以字符的形式寫入文件。即：多個(gè)編碼一一＞一個(gè)八位二進(jìn)制碼一一＞ASCLL碼（整數(shù)）一一＞字符（寫入）問(wèn)題2：生成了壓縮文件，可以實(shí)現(xiàn)文件的壓縮，但不能解壓縮。原因：在解壓過(guò)程中，把從壓縮文件中讀出的字符轉(zhuǎn)化為整數(shù)進(jìn)而再轉(zhuǎn)化為二進(jìn)制編碼時(shí)沒(méi)有給編碼補(bǔ)零。解釋：對(duì)于前面的例子 IamhereeIamhrcount2211111parent1077889bits101100000001010011001解壓縮時(shí)從壓縮文件中讀出的字符轉(zhuǎn)化為整數(shù)時(shí)為12862270若不補(bǔ)零，轉(zhuǎn)化成的編碼為11001010110111000110而正確的編碼為0000110001010110111000110不把流失掉的零補(bǔ)齊的話，解壓后的文件輕則出現(xiàn)亂碼，重則根本讀不出來(lái)。在開(kāi)始編寫這個(gè)程序的時(shí)候，以為自己把各種可能的情況以及細(xì)節(jié)的問(wèn)題考慮得很全面了，也做了充分的準(zhǔn)備。真正做起來(lái)才發(fā)現(xiàn)原來(lái)不是這么回事，出現(xiàn)的問(wèn)題是一個(gè)接著一個(gè)。原因還是自己在做之前，沒(méi)有充分的考慮細(xì)節(jié)問(wèn)題。五、測(cè)試結(jié)果及其用例IFffiIFffi3*C:kl'ocuMentsandEettinigCAdiinistratniA臬面\英又支件的壓縮和解壓縮TDeb.■?R解后縮文件ConfidcnceineuhatyoiipConfidenceIspawei*—ConfidcnceineuhatyoiipConfidencelifewouldbelikeifyouhadanabundanceofselfconfIdencetisnftaninherited七『日:Lt.it，氏alearnedone.ThismeansthatyouckhcLvccindbuinidcince口FseIf-confIdcncc.Stoi'there^rigrhtnuvj.府出字符及其編碼<.IXe.BBllXn.BllllXa,01100X1.00101>Ct.00011>(0,00010X(1,Bill01>Cc,00030Xp,0±1010><￡,011011)<S,010000Xh,01G001>(U,010010X1,600011)<,.0100±ll>Cv,0111600)<.,UUlMOLIWXp.0111001O><bRaillMBll>C-,OtlO01was<J,ai31BQlB0)CL00100101)(G,00100110><S,001B0L110><T,001601111)<?J0100I1000X^,010011001><k,010011010X1,010011011Jcomppesssuccessfully*anykeytocortlnus(16縮文件R解壓縮文件名；neL71.txt后的文件命名：neu2.txt,CsVDocusLcntiSandSettin程w\jLd>.:Lni,；s(16縮文件R解壓縮文件名；neL71.txt后的文件命名：neu2.txt"二：klli?conent3and.Se,tiingsAdmixiis七工MdiA桌H1英文文件的壓^和解壓縮鞫出字符及其編弱：<.IXe.BBllXn.01111><a.01100>(<00101><t.00011X0,00010><d.011101>Cn,00000><r.0il010iC￡,01101LXe>010600>CK01O001><u,01G010)<1,000911><^0106111><?,0111600>€L0010B00Xp,011±0010><h,01110011>—60801S0><3P,0000101Xn.00100010><cf,00106011><B,06100100)<011010XI,010011011>Unccmpi'esssuccessfullii?Pressanykeytocentinue.Ld程序調(diào)試后，分別對(duì)壓縮功能和解壓縮功能實(shí)現(xiàn)后的截屏□BE□BErTlBTUtEt—記事本丁中匚軍用。括HL白擊？幫以如M 期陛桂■”皿？''1r■南泡博度俳帚翁：隼圭唯學(xué)"?*-r|iMib師邪師匕niiuc?富士I.勤■”r一■起異色花■TBH■*?；FF焊"■”■"NY苣”?南施■■■10苛山市即-?lltld。逮eF?ND?■?q「日3￡3山n2G!22i"116g5d13cm1fin與卬h9u91九5心.岬加3-網(wǎng)爾氏g"少妹1WT力1U111S1圖6 壓縮過(guò)后的文本文件的截屏Bnn2rtst_記事本 L|fnj''X文伴舊翩匡）格式審查看5幫助她CoriFidlericeispower--thepouertuattract?pprsuade^iofluemiice^aridsu^iceed.ImagioF黑hatyourlifewuldbelifceifyouhadanabundanceofselfconFidence!Confidiencpisn"taninheritedtraitslt'5aJlearneslone.Thisncansthatjjmucanhaueanabundanceofself-confidenceaStdrthere9rightrm%圖7 解壓縮過(guò)后的文本文件的截屏六、用戶使用說(shuō)明運(yùn)行程序，按提示輸入文件名（必須為Txt格式），程序運(yùn)行結(jié)束后可在相應(yīng)的根目錄下查看壓縮文件和解壓縮文件。七、參考文獻(xiàn)1）王昆侖李紅色 《數(shù)據(jù)結(jié)構(gòu)與算法》 中國(guó)鐵道出版社20072）譚浩強(qiáng) 《C程序設(shè)計(jì)》（第三版） 清華大學(xué)出版社2005八、附錄#include<stdio.h>#include<string.h>#include<stdlib.h>#include<conio.h>structhead{ 〃結(jié)構(gòu)體unsignedcharb; //存儲(chǔ)字符intcount; 〃權(quán)值longparent91ch,rch;charbits[256]; 〃編碼}header[512],tmp;voidhuffman(intn,intm)〃用哈夫曼樹(shù)進(jìn)行編碼{intij,p1,p2,f;intsmali1,small2;i=n;whiie(i<512){p2=p1=0;small2=smali1=1000;for(j=0;j<=i-1;j++)if(header[j].parent==-1){ if(header[j].count<smaU1){small2=small1;small1=header[j].count;p2=p1;p1=j;}elseif(header[j].count<small2){small2=header[j].count;p2=j;}}header[p1].parent=header[p2].parent=i;header[i].count=smaU1+small2;header[i].lch=p1;header[i].rch=p2;i++;for(i=0;i<n;i++){f=i;while(header[f].parent!=-1){j=f;f=header[f].parent;if(header[f].rch==j)j=strlen(header[i].bits);memmove(header[i].bits+19header[i]?bitsj+1);header[i].bits[0]=T;elseif(header[f].lch==j)j=strlen(header[i].bits);memmove(header[i]?bits+1,header[i]?bitsj+1);header[i].bits[0]='0';printf("\n輸出字符及其編碼：\n");fOr(i=0;i<n;i++)printf("(%c,%s)”,header[i].b,header[i].bits);}intshuxue(inti) 〃用于計(jì)算2的i次方的函數(shù){intj,k=1;for(j=1j<=i;j++)k=2*k;returnk;voidcompress() 〃壓縮文件{charfilename[30],outputfile[30],buf[512];unsignedcharc;longijf,p,q,n,m,alcount=0,pt1;FILE*ifp,*ofp;printf(“請(qǐng)輸入文件名:")；scanf("%s”,&filename);printf("請(qǐng)為壓縮后的文件命名:")；scanf("%s”,&outputfile);if((ifp=fopen(filename,"r"))==NULL)/^開(kāi)英文本文件{printf("不能打開(kāi)文件!”)；return;}if((ofp=fopen(outputfileJw"))==NULL)/^建壓縮文件{printf("不能打開(kāi)文件!”)；return; }printf("文件打開(kāi)\n");while(!feof(ifp))〃統(tǒng)計(jì)英文文本文件字?jǐn)?shù)及每個(gè)字符出現(xiàn)的次數(shù)fread(&c,1,1,ifp);printf("%c",c);header[c].count++;alcount++;}alcount--;header[c].count--;for(i=0;i<512;i++){if(header[i].count>0)header[i].b=(unsignedchar)i;elseheader[i].b=0;}for(i=0;i<256;i++){for(j=i+1;j<256;j++)if(header[i].count<header[j].count){tmp=header[i];header[i]=header[j];header[j]=tmp;}}for(i=0;i<256;i++)if(header[i].count==0)break;n=i;m=2*n-1;huffman(n,m); 〃調(diào)用哈夫曼編碼函數(shù)fseek(ifp,0,SEEK_SET);fwrite(&alcountjsizeof(long),1,ofp);//把字符總數(shù)寫入文件fseek(ofp,8,SEEK_SET);pt1=8;buf[0]=0;q=0;while(q!=alcount) 〃文件壓縮過(guò)程{fread(&c,1,1,ifp);q++;for(i=0;i<n;i++)if(c==header[i].b)break;strcat(buf,header[i].bits);j=strlen(buf);while(j>=8)f=0;for(p=7;p>=0;p--)if(buf[p]=='1')f=shuxue(7-p)+f;c=(unsignedchar)f;fwrite(&c,1,1,ofp);pt1++;strcpy(buf,buf+8);j=strlen(buf);if(j>0){f=0;for(p=j-1;p>=0;p--)if(buf[p]==T)f=shuxue(j-p-1)+f;c=(unsignedchar)f;fwrite(&c,1,1,ofp);pt1++;}fseek(ofp,4,SEEK_SET);fwrite(&pt1,sizeof(long),1,ofp);fseek(ofp,pt1,SEEK_SET);fWrite(&n,sizeof(long),1,ofp);for(i=0;i<n;i++) 〃把結(jié)點(diǎn)信息存入文件{fprintf(ofp9"%c"9header[i].b);fprintf(ofpj%d”,header[i].count);}fclose(ifp);fclose(ofp);printf("compresssuccessfully!\nn);return;}voiduncompress() 〃解壓縮函數(shù){charfilename[255],outputfile[255],buf[255],bx[255];unsignedcharc;longij^mwfp,pt1;longalcount;FILE*ifp,*ofp;printf(“請(qǐng)輸入文件名:")；scanf("%s”,&filename);printf("請(qǐng)為壓縮后的文件命名:")；scanf("%s"9&outputflle);if((ifp=fopen(filename,"r"))==NULL)/^開(kāi)壓縮文件{printf("不能打開(kāi)文件即)；return;}if((ofp=fopen(outputfleJwb"))==NULL)〃新建解壓縮文件{printf("不能打開(kāi)文件!”)；return;}fread(&alcount,sizeof(long)91,ifp);fread(&pt1,sizeof(long),1,ifp);fseek(