基于赫夫曼編碼的文本壓縮程序-文庫吧
2025-04-17 21:14 本頁面
【正文】 樹如圖 2所示。赫夫曼樹存儲(chǔ)結(jié)構(gòu)的初始狀態(tài)如圖3(a)，終結(jié)狀態(tài)如圖 3(b)。 圖 2根據(jù)表 1 構(gòu)造的赫夫曼樹 圖 3(a)HT 初始狀態(tài)圖 3(b)HT 終止?fàn)顟B(tài) 根據(jù)生成的赫夫曼樹對(duì) HC 表中的字符進(jìn)行編碼，編碼的方法：從 該葉子到根逆向求該字符的編碼。例如圖 2 中 把 的權(quán)值為 14，對(duì)應(yīng)的編碼為： 000。將得到的赫夫曼編碼寫入 HC[i].internal_code_address[j].code 指向的區(qū)域。當(dāng)字符編碼完成之后，打開壓縮文件，將赫夫曼樹 HT中除權(quán)重以外的數(shù)據(jù) (解碼無需權(quán)重信息 )寫入壓縮文件中，作為下一次解壓縮的解碼表。再次打開要壓縮的文本文件，讀取文件中的字符，根據(jù)編碼的范圍確定該字符是 ASCII 還是GB2312，如果 ASCII 則調(diào)用折半查找函數(shù)，在編碼表 HC 中進(jìn)行縱向查找，查找此 ASCII 出現(xiàn)的位置 p1，該 字符的編碼為HC[p1].internal_code_address[1].code；如果字符是漢字，則調(diào)用折半查找先縱向查找該漢字的第一字節(jié)機(jī)內(nèi)碼在 HC中的位置 p1，然后從HC[p1].internal_code_address 開始橫向查找該漢字的第二字節(jié)機(jī)內(nèi)碼的位置p2，這樣就得到了該漢字的赫夫曼編碼為HC[p1].internal_code_address[p2].code 因?yàn)楹辗蚵幋a在 HC 表中是以字符串形式存放 (因?yàn)橛?jì)算機(jī)的基本儲(chǔ)單位是字節(jié)，如果以位存放，需要另設(shè)一個(gè)空間來表示未編碼的位空間大小 )。所以需要將字符串 0101轉(zhuǎn)換為二進(jìn)制 0101寫入文件。因?yàn)槊總€(gè)赫夫曼編碼的長度是不一樣的，假設(shè)某字符的赫夫曼長度為 4，則將該編碼寫入一個(gè)字節(jié)后，還剩余 4個(gè)位，則下一次可以繼續(xù)從第 5個(gè)位開始寫入，當(dāng)所有字符的編碼都寫入完畢后，最后一個(gè)字節(jié)并不一定會(huì)用完，所以需要附設(shè)一個(gè)字節(jié)來記錄最后一個(gè)字符編碼實(shí)際寫入的編碼位數(shù)。編碼文件的結(jié)構(gòu)如下圖所示： 圖 4壓縮文件存儲(chǔ)結(jié)構(gòu) 程序解壓文件：打開壓縮文件，取出壓縮文件的解碼表長度 N，根據(jù) N 讀取 N條解碼表記錄，重建解碼表 HT，然后讀取壓縮數(shù)據(jù) DATA，解碼的過程是從根出 發(fā)，按 DATA數(shù)據(jù)的 0或 1 確定找左子樹還是右子樹，直至葉子結(jié)點(diǎn)，便求得了 DATA相應(yīng)的字符。將字符寫入文件，直至所有 DATA 數(shù)據(jù)處理完畢，整個(gè)解壓過程結(jié)束。 三、程序源代碼 ifndef _COURSEDESIGN_H_ define _COURSEDESIGN_H_ //Huffman 樹存儲(chǔ)結(jié)構(gòu) typedef struct { char ch[3]； unsigned int weight； unsigned int parent,lchild,rchild； }HTNode,*HuffmanTree； //Huffman 編碼表存儲(chǔ)結(jié)構(gòu) typedef struct { char internal_code； char*code； }InternalCode； typedef struct { int count； char internal_code； InternalCode*internal_code_address； }HuffmanCode,*HuffmanPCode； //解碼表存儲(chǔ)結(jié)構(gòu) typedef struct { char ch[3]； unsigned int lchild,rchild； }DecodeList,*DecodePList； //輔助數(shù)組，置 /取一個(gè)字節(jié)的指定位 const static unsigned char mask[8]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01}； template class Tstatic int xj_Search_Bin(int key,T L,int low,int high)； template class Tstatic void xj_InsertSort(T L,int start,int end)； void xj_Select(const HuffmanTree HT,int n,intamp。s1,intamp。s2)； void xj_Statistics(HuffmanPCodeamp。HC,int internal_code1,int internal_code2,int(*FrequencyMeter)[255],intamp。n)； bool xj_Init(char*filename,HuffmanPCodeamp。HC,int*amp。w,intamp。n)； void xj_CreateHuffmanTree(HuffmanTreeamp。HT,const HuffmanPCode HC,const int*w,int n)； void xj_HuffmanCoding(const HuffmanTree HT,HuffmanPCode HC,int n)； bool xj_Compress(char*ifilename,char*ofilename,const HuffmanPCode HC,const HuffmanTree HT,int n)； bool xj_DeCompress(char*ifilename,char*ofilename)； void xj_Interface()； endif include include iostream include fstream include iomanip include include using namespace std； //折半查找 template class T int xj_Search_Bin(int key,T L,int low,int high) { int mid=0； int internal_code； while(low=high) { mid=(low+high)/2； internal_code=int(L[mid].internal_codeamp。0xFF)； if(key==internal_code) { return mid； } else if(internal_code key) { high=mid1； } else { low=mid+1； } } return 0； } //對(duì) HC表的字符域做插入非遞減排序 template class T void xj_InsertSort(T L,int start,int en
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1