數(shù)據(jù)壓縮及信源編碼Huffman編碼壓縮

1、數(shù)據(jù)壓縮與信源編碼大作業(yè)一-Huffman編解碼實(shí)現(xiàn)一、 實(shí)驗(yàn)?zāi)康模?）通過(guò)本次實(shí)驗(yàn)，加深對(duì)Huffman編碼算法思想的理解，掌握Huffman編碼的基本規(guī)則，熟悉并且理解Huffman編碼的基本步驟。在此基礎(chǔ)上，能夠通過(guò)編寫C語(yǔ)言代碼實(shí)現(xiàn)Huffman編碼的編寫壓縮工作。（2）通過(guò)實(shí)現(xiàn)Huffman編碼壓縮工作，進(jìn)一步進(jìn)行解碼工作，并且用C語(yǔ)言實(shí)現(xiàn)，以此進(jìn)一步加深理解。二、 實(shí)驗(yàn)內(nèi)容（1）編寫Huffman壓縮程序Huffman_Code 對(duì)abc.txt進(jìn)行壓縮，壓縮結(jié)果存儲(chǔ)在abc_code.txt中；（2）編寫Huffman解壓縮程序Huffman_Decode 對(duì)*_code.txt

2、進(jìn)行解壓，恢復(fù)結(jié)果存儲(chǔ)在*_decode.txt中；（3）默認(rèn)碼表法 / 兩遍掃描的基本方法 / 自適應(yīng)壓縮方法 任選其一。三、 算法流程（1） 兩遍掃描法進(jìn)行Huffman壓縮編碼算法流程（2） Huffman解碼算法流程四、 程序設(shè)計(jì)說(shuō)明（1） 兩遍掃描法進(jìn)行Huffman壓縮編碼算法程序說(shuō)明首先，決定程序好壞優(yōu)劣以及算法實(shí)現(xiàn)難易程度的重要因素便是程序的數(shù)據(jù)結(jié)構(gòu)。本程序使用了兩個(gè)數(shù)據(jù)結(jié)構(gòu)：typedef struct char elem; unsigned int m_weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTre

3、e; typedef struct weight char elem; unsigned int m_weight; Weight;第一個(gè)數(shù)據(jù)結(jié)構(gòu)是為了建立Huffman樹而用結(jié)構(gòu)體構(gòu)造的結(jié)構(gòu)體。其中的成員包括ASCII碼的名字elem,權(quán)重m_weight（有第一次掃描得到的頻數(shù)決定），以及用來(lái)建立二叉樹的父節(jié)點(diǎn)，左右孩子節(jié)點(diǎn)。第二個(gè)數(shù)據(jù)結(jié)構(gòu)是第一掃描統(tǒng)計(jì)各個(gè)ASCII碼得到的頻數(shù)而建立的結(jié)構(gòu)體。其次是實(shí)現(xiàn)算法的函數(shù)。第一步，我們要對(duì)文本的內(nèi)容進(jìn)行掃描，統(tǒng)計(jì)，并且記錄下來(lái)，在這里使用了方法是：對(duì)掃描得到的ASCII碼進(jìn)行從開始進(jìn)行匹配，有兩種情況：第一，改碼已經(jīng)出現(xiàn)則，直接讓對(duì)應(yīng)的權(quán)值W_w

4、eight增加1；第二，如果掃描遍歷后發(fā)現(xiàn)沒(méi)有，則碼字總類k增加1，將該新的碼字賦給新的結(jié)構(gòu)體，權(quán)值設(shè)為1。重復(fù)值文件掃描結(jié)束。第二步，需要對(duì)其進(jìn)行Huffman樹的創(chuàng)立，并且要對(duì)其進(jìn)行編碼，生成Huffman壓縮碼。首先，根據(jù)Huffman二叉樹的算法，我們需要先得到權(quán)值最小的兩個(gè)碼字。這里程序中使用了void Select(HuffmanTree HT,int n,int *s1,int *s2)函數(shù)，用最簡(jiǎn)單的比較方法就開變了得出，并通過(guò)指針參數(shù)s1,s2傳遞。得到最小的兩個(gè)后，我們通過(guò)函數(shù)void HuffmanCoding(HuffmanTree *HT,HuffmanCode *H

5、C,Weight *w,int n)進(jìn)行Huffman編碼實(shí)現(xiàn)。算法思想即為普通的二次掃描編碼的方法，詳細(xì)見程序的該函數(shù)部分的內(nèi)容和注釋。第三步，將編好的Huffman碼寫入到壓縮文件中，再一次對(duì)文件正文進(jìn)行掃描，沒(méi)掃描到一個(gè)就用編號(hào)的Huffman碼代替相關(guān)的ASCII碼。在這之前，考慮到和解碼的相對(duì)應(yīng)，在寫入到壓縮文檔之前。需要提供一些信息給解壓縮程序，其中包括，文本的大小，用size表示，文本總的總類數(shù)目，用k表示，每種ASCII碼對(duì)應(yīng)的Huffman碼，按照Huffman樹的順序。第四部，輸出產(chǎn)生相應(yīng)的文件即可，同時(shí)打印出壓縮前后的文件的大小，為計(jì)算壓縮比提供依據(jù)。（2） Huffma

6、n解碼算法程序說(shuō)明第一步，讀出文件的前部分內(nèi)容，包括對(duì)應(yīng)的文本的大小，用size表示，文本總的總類數(shù)目，用k表示，每種ASCII碼對(duì)應(yīng)的Huffman碼。然后就可以恢復(fù)出Huffman數(shù)。這里用到unsigned int Read()函數(shù)和unsigned int Readk(unsigned int k)，這兩個(gè)函數(shù)可以配合著實(shí)現(xiàn)Huffman碼的讀取，詳細(xì)見程序及其對(duì)應(yīng)的注釋。第二部，掃描全文，將之與Huffman碼進(jìn)行匹配，每次匹配均從根節(jié)點(diǎn)開始，知道左右節(jié)點(diǎn)沒(méi)有，這樣不會(huì)出現(xiàn)重復(fù)。掃描至文檔結(jié)束即可。五、 程序壓縮性能評(píng)價(jià)經(jīng)過(guò)壓縮，abc.txt的大小S1= 20,370Byte,壓縮

7、后的abc_code的大小S2= 12,165Byte。則：壓縮率：r=S2S1=1216520370=0。597可見，其壓縮率并不是特比高。分析：因?yàn)槲募笮H為20K左右，經(jīng)過(guò)程序?qū)ξ募姆治觯募兴械腁SCII碼值得種類為77中，Huffman編碼最大碼長(zhǎng)l=8（注意，因?yàn)榇鎯?chǔ)方法按字節(jié)，所以這里8bit就可以），在存儲(chǔ)Huffman編碼時(shí)浪費(fèi)BB=（8-1）*77bit=53.9Byte。加上Huffman編碼的算法的限制，可以忍受。但是，如果文件更長(zhǎng)，會(huì)發(fā)現(xiàn)壓縮率會(huì)減小（效果會(huì)提高）。但有Huffman編碼的上限。解碼，經(jīng)過(guò)嚴(yán)格比較，發(fā)現(xiàn)完全正確。六、 程序源代碼/* 程序思路

8、：本程序采用 二次掃描的方法進(jìn)行編碼，首先先掃描一遍，得到各種ASCII字符，并存入到結(jié)構(gòu)Weight里。然后進(jìn)行Huffman編碼。本次編碼思想主要體現(xiàn)在，每一個(gè)碼子“1”“0”得出后直接當(dāng)成字節(jié)存入寫入壓縮文件中。 壓縮文件頭部信息：1.文件總字節(jié)數(shù)目，單位：byte 2.各種ASC的種類數(shù)目 3.各種ASCII的編碼輸出 4.正文寫入 */#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <fcntl.h>

9、#include <io.h> typedef char * HuffmanCode; /結(jié)構(gòu)體定義區(qū) typedef struct char elem; unsigned int m_weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; /Huffman樹對(duì)應(yīng)結(jié)點(diǎn) typedef struct weight char elem; unsigned int m_weight; Weight; /符號(hào)及其出現(xiàn)次數(shù) /全局變量定義區(qū) int bits; /記錄實(shí)際比特?cái)?shù)，清空緩沖區(qū) char chl; /字節(jié) i

10、nt lbits; FILE *infp,*outfp; /輸入/出文件 /*選擇出權(quán)值最小并且父親結(jié)點(diǎn)的權(quán)值為0的2個(gè)結(jié)點(diǎn)* void Select(HuffmanTree HT,int n,int *s1,int *s2) int i; (*s1)=(*s2)=0; /初始化s1和s2 for(i=1;i<=n;i+) if(HTi.m_weight<HT(*s2).m_weight&& HTi.parent=0 &&(*s2)!=0) if(HTi.m_weight<HT(*s1).m_weight) /將權(quán)值最小的結(jié)點(diǎn)地址保存在s1中

11、(*s2)=(*s1); (*s1)=i; else (*s2)=i; if(*s1)=0|(*s2)=0)&&HTi.parent=0) /為s1和s2初始植入結(jié)點(diǎn) if(*s1)=0) (*s1)=i; else if(*s2)=0) if(HTi.m_weight<HT(*s1).m_weight) (*s2)=(*s1); (*s1)=i; else (*s2)=i; if(*s1)>(*s2) i=(*s1); (*s1)=(*s2); (*s2)=i; return; /*Huffman編碼算法* void HuffmanCoding(HuffmanTr

12、ee *HT,HuffmanCode *HC,Weight *w,int n) /Huffman編碼算法 int i,m,s1,s2,start,c,f; char *cd; if(n<=1) return; m=2*n-1; /得到數(shù)的節(jié)點(diǎn)數(shù)目 (*HT)=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /在內(nèi)存為*HT分配長(zhǎng)度為m+1個(gè)HTNode結(jié)構(gòu)體大小的連續(xù)空間 /初始化HuffmanTree前n個(gè)節(jié)點(diǎn) for(i=1;i<=n;+i) (*HT)i.elem=wi-1.elem; (*HT)i.m_weight=wi-1.m_weigh

13、t; (*HT)i.parent=(*HT)i.lchild=(*HT)i.rchild=0; /初始化HuffmanTree前n+1到m節(jié)點(diǎn) for(;i<=m;+i) (*HT)i.elem='0' (*HT)i.m_weight=(*HT)i.parent=(*HT)i.lchild=(*HT)i.rchild=0; /構(gòu)造Huffman for(i=n+1;i<=m;+i) Select(*HT,i-1,&s1,&s2); /s1,s2得到的是權(quán)值最小的兩個(gè)點(diǎn) (*HT)s1.parent=i; (*HT)s2.parent=i; (*HT)

14、i.lchild=s1; (*HT)i.rchild=s2; (*HT)i.m_weight=(*HT)s1.m_weight+(*HT)s2.m_weight; /在內(nèi)存為*HT分配長(zhǎng)度為n個(gè)char大小的連續(xù)空間 (*HC)=(HuffmanCode)malloc(n*sizeof(char*); cd=(char *)malloc(n*sizeof(char); /為cd分配n個(gè)char占的空間大小 cdn-1='0' /為每個(gè)葉子結(jié)點(diǎn)進(jìn)行編碼 for(i=1;i<=n;+i) start=n-1; /從葉子結(jié)點(diǎn)開始向上搜索，如果它是其父結(jié)點(diǎn)的左孩子，則其編碼為0，

15、否則為1，直到根結(jié)點(diǎn) for(c=i,f=(*HT)i.parent;f!=0;c=f,f=(*HT)f.parent) if(*HT)f.lchild =c) cd-start='0' else cd-start='1' (*HC)i=(char *)malloc(n-start)*sizeof(char); /為每個(gè)結(jié)點(diǎn)的編碼分配存儲(chǔ)空間 strcpy(*HC)i,&cdstart);/將結(jié)點(diǎn)的編碼首地址保存到HC中 /printf("%x ",*(*HC)i); /假設(shè)編碼時(shí)正確的 void Select(HuffmanTree

16、,int,int *,int *); /選擇結(jié)點(diǎn) /*8向outfp中寫入一個(gè)比特 *void Write(unsigned int bit) /向outfp中寫入一個(gè)比特 bits+; chl=(chl<<1)+bit; if(bits=8) /緩沖區(qū)已滿,寫入outfp fputc(chl,outfp); /printf("zhigeshi%d n",chl); bits=0; chl=0; /*向outfp中寫入k個(gè)比特 *void Writek(unsigned int num,unsigned int h) /向outfp中寫入k個(gè)比特 int *s;

17、 unsigned int i,bit; bit =0; s=(int *)malloc(h+2)*sizeof(int); for(i=1;i<=h;i+) si=0; si=num & 1; num=num>>1; for(i=h;i>0;) bit=si; Write(bit); i-; /*強(qiáng)行寫入outfp* void WriteToOutfp() int i; int l; l=bits; if(l>0) for(i=0;i<8-l;i+) Write(0); /*二進(jìn)位表示所需的位數(shù) *int NToBits(unsigned int

18、num) /0num之間的整數(shù)用二進(jìn)位表示所需的位數(shù) unsigned int l=0,power=1; while(power<=num) l+;power=power*2; return l; /*從infp中讀出一個(gè)比特 *unsigned int Read() /從infp中讀出一個(gè)比特 unsigned int bit; if(bits=0) chl=fgetc(infp); bits=8; bit=(chl & 128)>>7; chl=chl<<1; bits-; return bit; /*8從infp中讀出k個(gè)比特* unsigned i

19、nt Readk(unsigned int k) /從infp中讀出k個(gè)比特 unsigned int bit; unsigned int i; int num=0; for(i=0;i<k;) bit=Read(); num=(num<<1)+bit; i+; return num; /*void WriteToOutfp(); int NToBits(unsigned int num); /0num之間的整數(shù)用二進(jìn)位表示所需的最少位數(shù) */ int main() HuffmanTree HT; HuffmanCode HC; Weight *w; char c; /符號(hào)

20、unsigned int i; /用于循環(huán) int x; int ch; char y; bits=0; /清空緩沖區(qū) chl=0; unsigned int n; /符號(hào)數(shù) int wei; /符號(hào)對(duì)應(yīng)的個(gè)數(shù) int total=0; int num; unsigned int size,l; unsigned int k=0; /頻度大于零的字符數(shù) unsigned int char_index256; /字符對(duì)應(yīng)在樹結(jié)點(diǎn)表的下標(biāo)(char_index0到char_indexn-1) char infName256,outfName256; if(infp=fopen("abc.

21、txt","rb")=NULL) printf("不能打開文件:%sn",infName); exit(1); if(outfp=fopen("abc_code.txt","wb")=NULL) printf("不能打開文件:%sn",outfName); exit(1); fseek(infp,0,SEEK_END); size=ftell(infp); /計(jì)算打開的文件的大小 printf("壓縮前文件的總字節(jié)數(shù)為:%dn",size); rewind(infp

22、); /將文件指針重新指向開頭 w=(Weight *)malloc(256*sizeof(Weight); /為w分配空間 ch=fgetc(infp); /從文件中獲取一個(gè)字符 w0.elem=ch; w0.m_weight=0; char_indexch=1; /char_index 字符對(duì)應(yīng)在樹結(jié)點(diǎn)表的下標(biāo)(char_index0到char_indexn-1) while(ch!=EOF) /保存符合和出現(xiàn)次數(shù) unsigned int i; for(i=0;i<=k;i+) /掃描已經(jīng)出現(xiàn)過(guò)的字符，并且權(quán)值加1 if(ch = wi.elem) wi.m_weight=wi.m

23、_weight+1; break; if(i>k) /之前沒(méi)有出現(xiàn)過(guò)字符進(jìn)行記錄，操作 k=k+1; wk.elem=ch; wk.m_weight=1; char_indexch=k+1; ch=fgetc(infp); k=k+1; HuffmanCoding(&HT,&HC,w,k);/進(jìn)行Huffman編碼 num=0; rewind(outfp); /將文件指針重新指向輸出文件的開頭 fwrite(&size,sizeof(unsigned int),1,outfp); /寫入文件的長(zhǎng)度 Writek(k-1,8); /寫入字符種類數(shù)目 for(i=0;

24、i<k;i+) fwrite(&(wi.elem),sizeof(char),1,outfp); /寫入各個(gè)符合 l=NToBits(2*k-1); /k用二進(jìn)位表示所需的最少位數(shù) for(i=k+1;i<=2*k-1;i+) Writek(HTi.lchild,l); Writek(HTi.rchild,l); rewind(infp); /將文件指針重新指向輸入文件的開頭 ch=fgetc(infp); /讀取一個(gè)字符 while(feof(infp)=0) /將編碼寫入文件 unsigned int c; c=char_indexch; for(i=0;i<st

25、rlen(HCc);i+) if(HCci='0')Write(0); else Write(1); ch=fgetc(infp); WriteToOutfp(); fseek(outfp,0,SEEK_END); num=ftell(outfp); /計(jì)算壓縮后文件的大小 printf("壓縮后文件的總字節(jié)數(shù)為:%dn",num); fclose(infp);fclose(outfp); system("pause"); return 0; /* 本程序?yàn)榻獯a程序，與編碼程序是相對(duì)應(yīng)的。 l->是最長(zhǎng)的編碼所需要的比特?cái)?shù) bit=

26、read（）->對(duì)應(yīng)的1B表示的一個(gè)編碼數(shù)（0、1） 首先：1.讀出文件開始的文件的總長(zhǎng)度->size 單位：B 2.讀出字符總類數(shù)目 3.回復(fù)huffman樹，進(jìn)行編碼匹配 4.掃描恢復(fù)全文。*/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <fcntl.h> #include <io.h> /結(jié)構(gòu)體 struct HTNode1 /壓縮用Huffman樹結(jié)點(diǎn) unsigned lo

27、ng weight; /字符頻度（權(quán)值） unsigned int parent,lchild,rchild; ; typedef char ElemType; typedef struct ElemType elem; unsigned int m_weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; /Huffman樹對(duì)應(yīng)結(jié)點(diǎn) typedef char * HuffmanCode; typedef int Status; typedef struct weight char elem; unsigned int m_

28、weight; Weight; /符號(hào)及其出現(xiàn)次數(shù) int bits; /記錄實(shí)際比特?cái)?shù)，清空緩沖區(qū) char chl; /字節(jié) int lbits; void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int); /Huffman編碼算法 void Select(HuffmanTree,int,int *,int *); /選擇結(jié)點(diǎn) unsigned int Readk(unsigned int k);/從infp中讀出k個(gè)比特 FILE *infp,*outfp; /輸入/出文件 /*函數(shù)程序部分* void Write(unsi

29、gned int bit) /向outfp中寫入一個(gè)比特 bits+; chl=(chl<<1)+bit; if(bits=8) /緩沖區(qū)已滿,寫入outfp ，存起來(lái) fputc(chl,outfp); bits=0; chl=0; /*8向outfp中寫入k個(gè)比特*void Writek(unsigned int num,unsigned int h) /向outfp中寫入k個(gè)比特 int *s; unsigned int i,bit; bit =0; s=(int *)malloc(h+2)*sizeof(int); for(i=1;i<=h;i+) si=0; si=

30、num & 1; num=num>>1; for(i=h;i>0;) bit=si; Write(bit); i-; /*強(qiáng)行寫入outfp* void WriteToOutfp() int i; int l; l=bits; if(l>0) for(i=0;i<8-l;i+) Write(0); /*0num之間的整數(shù)用二進(jìn)位表示所需的最少位數(shù)int NToBits(unsigned int num) /0num之間的整數(shù)用二進(jìn)位表示所需的位數(shù) unsigned int l=0,power=1; while(power<=num) l+;power

31、=power*2; return l; /*從infp中讀出一個(gè)比特*unsigned int Read() /從infp中讀出一個(gè)比特 unsigned int bit; if(bits=0) chl=fgetc(infp); bits=8; bit=(chl & 128)>>7; chl=chl<<1; bits-; return bit; /*從infp中讀出k個(gè)比特 *unsigned int Readk(unsigned int k) / unsigned int bit; unsigned int i; int num=0; for(i=0;i<

32、;k;) bit=Read(); num=(num<<1)+bit; i+; return num; int main(void) HuffmanTree HT; HuffmanCode HC; Weight *w; unsigned int i; unsigned int n; int wei; int total=0; int num; unsigned int size; unsigned int l; unsigned int bit,c; char infName256,outfName256; char Leaf256; /葉結(jié)點(diǎn)對(duì)應(yīng)字符(leaf1到leafn) un

33、signed int k; bits=0; /清空緩沖區(qū) chl=0; if(infp=fopen("abc_code.txt","rb")=NULL) printf("不能打開文件:%sn",infName); exit(1); if(outfp=fopen("abc_decode.txt","wb")=NULL) printf("不能打開文件:%sn",outfName); exit(1); fseek(infp,0,SEEK_END); size=ftell(infp)

34、; /計(jì)算文件大小 printf("解壓縮前文件的總字節(jié)數(shù)為:%dn",size); bits=0; /清空緩沖區(qū) chl=0; rewind(infp); /將文件指針重新指向輸入文件的開頭 fread(&size,sizeof(unsigned int),1,infp); k=Readk(8); /讀取字符數(shù)目 k=k+1; /ASCII碼的種類數(shù)目 w=(Weight *)malloc(256*sizeof(Weight); /分配空間 for(i=1;i<=k;i+) fread(&Leafi,sizeof(char),1,infp); l=N

35、ToBits(2*k-1); HT=(HuffmanTree)malloc(l+1)*sizeof(HTNode); /分配空間 for(i=1;i<=k;i+) /讀出葉結(jié)點(diǎn) HTi.lchild=HTi.rchild=0; for(i=k+1;i<=2*k-1;i+) HTi.lchild=Readk(l); HTi.rchild=Readk(l); bit=Read(); /讀一個(gè)bit for(i=0;i<size;i+) c=2*k-1; /2*k-1為根結(jié)點(diǎn)的下標(biāo) while(HTc.lchild!=0|HTc.rchild!=0)&&(feof(

36、infp)=0) if(bit=0) c=HTc.lchild; else c=HTc.rchild; bit=Read(); fputc(Leafc,outfp); /將字符寫入outfp中 fseek(outfp,0,SEEK_END); size=ftell(outfp); printf("解壓縮后文件的總字節(jié)數(shù)為:%dn",size); fclose(infp); fclose(outfp); return 0; 七、 測(cè)試數(shù)據(jù)文件-/-/-/ Copyright 251 Mentor Graphics Corporation, 1996-2004, All Rig

37、hts Reserved.-/ UNPUBLISHED, LICENSED SOFTWARE.-/ CONFIDENTIAL AND PROPRIETARY INFORMATION WHICH IS THE-/ PROPERTY OF MENTOR GRAPHICS CORPORATION OR ITS LICENSORS.-/-/LIBRARY ieee ;use IEEE.std_logic_1164.all ;use IEEE.std_logic_arith.all ;package dualport_ram_be_pkg is component dualport_ram_be gen

38、eric (ram_id : integer; words : integer; width : integer; addr_width : integer; a_reset_active : integer; s_reset_active : integer; enable_active : integer; re_active : integer; we_active : integer; num_byte_enables : integer; clock_edge : integer; num_input_registers : integer; num_output_registers : integer; no_of_dualport_readwrite_port : integer ); port ( data_in : in STD_LOGIC_VECTOR(no_of_dualport_readwrite_port * width) - 1 downto 0) ; addr : in STD_LOGIC_VECTOR(no_of_dualport_readwrite_port * addr_width) - 1 downt