軟件壓縮/解壓縮軟件Szip（Huffman算法及應(yīng)用）

完整代碼下載地址

1．需求規(guī)格說明

【問題描述】

利用哈夫曼樹編碼進(jìn)行對已有文件進(jìn)行重新編碼可以大大提高減小文件大小，減少存儲空間，但是，這要求在首先對一個(gè)現(xiàn)有文件進(jìn)行編碼形成新的文件，也就是壓縮。在文件使用時(shí)，再對壓縮文件進(jìn)行解壓縮，也就是譯碼，復(fù)原原有文件。試為完成此功能，寫一個(gè)壓縮/解壓縮軟件（控制臺程序，不要求界面）

【基本要求】（60%）

一個(gè)完整得系統(tǒng)應(yīng)具有以下功能：
（1）壓縮準(zhǔn)備。讀取指定被壓縮文件，對文件進(jìn)行分析，建立哈夫曼樹，并給出分析結(jié)果（包括數(shù)據(jù)集大小，每個(gè)數(shù)據(jù)得權(quán)值，壓縮前后文件得大小），在屏幕上輸出。
（2）壓縮。利用已建好的哈夫曼樹，對文件進(jìn)行編碼，并將哈夫曼編碼及文件編碼后的數(shù) 據(jù)一起寫入文件中，形成壓縮文件(**.Haf)。
（3）解壓縮。打開已有壓縮文件(*.Haf)，讀取其中的哈夫曼編碼，構(gòu)建哈夫曼樹，讀取其 中的數(shù)據(jù)，進(jìn)行譯碼后，寫入文件，完成解壓縮。
（4）程序使用命令行方式運(yùn)行
壓縮命令 ：SZip A Test.Haf 1.doc
解壓縮命令：SZip X Test.Haf 2.doc 或 SZip X Test.Haf
用戶輸入的命令不正確時(shí)，給出提示。
（5）使用面向?qū)ο蟮乃枷刖幊?#xff0c;壓縮/解壓縮、哈夫曼構(gòu)建功能分別構(gòu)建類實(shí)現(xiàn)。

【提高要求】（40%）

（1）采用不同的數(shù)據(jù)集，比較其壓縮比，采用最有效的壓縮方式。
（2）多個(gè)文件的壓縮。
（3）試構(gòu)建程序框架，使其能添加新的壓縮/解壓縮算法（例如書上 LZW 壓縮算法）。

2．總體分析與設(shè)計(jì)

（1）設(shè)計(jì)思想：

【存儲結(jié)構(gòu)】

1、構(gòu)建一個(gè)哈夫曼樹結(jié)點(diǎn)的結(jié)構(gòu)體，其中包括記錄結(jié)點(diǎn)權(quán)值的數(shù)據(jù)元素、記錄結(jié)點(diǎn)雙親位置及左右孩子位置的數(shù)據(jù)元素、記錄結(jié)點(diǎn)哈夫曼編碼的int型指針、記錄結(jié)點(diǎn)哈夫曼樹編碼長度的數(shù)據(jù)元素。
2、利用動態(tài)數(shù)組來保存哈夫曼編碼。
3、本題通過構(gòu)建哈夫曼樹來進(jìn)行壓縮和解壓縮，當(dāng)壓縮式即從下至上建樹，解壓縮時(shí)即從上至下讀樹。

【主要的算法思想】

本題需要我們運(yùn)用哈夫曼樹的算法來實(shí)現(xiàn)軟件的壓縮和解壓，而壓縮即可以理解為從下至上建樹，解壓縮時(shí)即可以理解為從上至下讀樹。
在壓縮時(shí)，我們首先要把需要壓縮的文件用二進(jìn)制的形式打開，然和把其中的字符轉(zhuǎn)換成ascll碼，然后進(jìn)行對比，把具有相同ascll碼的字符統(tǒng)計(jì)出來進(jìn)行歸類，并計(jì)算同類字符的權(quán)重，根據(jù)權(quán)重從下至上建立哈夫曼樹，再生成哈夫曼編碼（其中，權(quán)重大的結(jié)點(diǎn)哈夫曼編碼短，權(quán)重小的結(jié)點(diǎn)哈夫曼編長，），然后把哈夫曼編碼列出來后，8位進(jìn)1（1Byte=8 Bit），當(dāng)后面的哈夫曼編碼不足八位時(shí) 則要在其后邊進(jìn)行補(bǔ)0后向進(jìn)1，然后再將所有的字節(jié)輸出到文件中，形成壓縮文件。
在解壓縮時(shí)，我們同樣是要把需要解壓縮的文件用二進(jìn)制的方式進(jìn)行打開，然后從上至下的讀取哈夫曼樹，讀取哈夫曼編碼，將哈夫曼編碼裝換成編碼前對應(yīng)的內(nèi)容，即分別對應(yīng)哈夫曼樹中結(jié)點(diǎn)的內(nèi)容，這里要注意的是我們讀取的最后一個(gè)字節(jié)可能是不足8位的，所以我們要注意記錄不足八位時(shí)的缺省個(gè)數(shù)，然后再分別對應(yīng)哈夫曼樹中的數(shù)據(jù)，從而實(shí)現(xiàn)解壓操作，最后把解壓后的內(nèi)容輸出即可。
最后編寫計(jì)算文件內(nèi)占用字節(jié)大小的函數(shù)，再根據(jù)占用內(nèi)存大小計(jì)算壓縮率；然后通過對比壓縮前和解壓后文件內(nèi)每個(gè)字符是否一致來判斷解壓前和解壓后的文件內(nèi)容是否完全一致。

（2）設(shè)計(jì)表示：

（3）詳細(xì)設(shè)計(jì)表示：

1、countFrequency()統(tǒng)計(jì)字符出現(xiàn)次數(shù)
首先以二進(jìn)制方式打開文件，然后讀取其中的字符，判斷這個(gè)字符是否是第一次出現(xiàn)，如果是就把它初始化，然后葉子結(jié)點(diǎn)總數(shù)加一要是不是第一次出現(xiàn)，就把權(quán)值加1。
2、createHuffmanTree()建哈夫曼樹
先找出兩個(gè)權(quán)值最小的結(jié)點(diǎn)然后建樹，一直到最后只有一棵樹，為了減少壓縮文件中需要寫入的huffman樹的信息，約定小標(biāo)小的結(jié)點(diǎn)做為雙親結(jié)點(diǎn)的左孩子。
3、calculateCode() 計(jì)算哈夫曼編碼
從下往上一直找到根節(jié)點(diǎn)，然后一層一層加，計(jì)算哈夫曼的長度然后再從上往下找，左孩子編碼0，右孩子編碼1。
4、addBit(int bit)對一個(gè)未滿8bit的byte中加入一個(gè)bit
如果新增的為0，直接就左移；如果新增為1，就先左移然后與1按位或。
5、resetByte()將byte清空
將byte與byte中bit的個(gè)數(shù)都賦值0，即清空。
6、doCompress(…）壓縮函數(shù)
調(diào)用前面編寫的函數(shù)，首先計(jì)算每個(gè)字符的權(quán)值，再根據(jù)權(quán)值大小建立哈夫曼樹，再給樹上的結(jié)點(diǎn)進(jìn)行哈夫曼編碼，然后把哈夫曼樹從上之下將結(jié)點(diǎn)位置寫入輸出文件；將字符的哈夫曼編碼寫入byte中，即八位算一字節(jié)，如果滿了就輸出字節(jié)，并將原字節(jié)清空，然后把不足8位的后面補(bǔ)0，然后輸出，再清空。
7、doDecompress(…)解壓函數(shù)
首先讀出根節(jié)點(diǎn)的位置，然后確立各個(gè)幾點(diǎn)之間的雙親關(guān)系（先左后右），然后方便讀取 將數(shù)據(jù)放入隊(duì)列，由于在壓縮的時(shí)候是從上之下存入到文件當(dāng)中的 所以這個(gè)時(shí)候直接依此彈出隊(duì)頂元素即可實(shí)現(xiàn)從上至下讀樹，然后八位一循環(huán)，分別與哈夫曼樹的左右孩子進(jìn)行比較，找出哈夫曼編碼最后一個(gè)字原本對應(yīng)的內(nèi)容，注意最后不足8位的字節(jié)要單獨(dú)處理。

3．編碼

1、編碼過程中遇到一些問題，在建立huffman樹時(shí)不知如何在壓縮過程中同時(shí)進(jìn)行編碼和建樹，不知如何存放編碼，編碼必須要存儲才能建立有效的huffman樹。后來想到可以用動態(tài)數(shù)組保存huffman編碼，由于編碼長度不定，用動態(tài)數(shù)組可以彌補(bǔ)這個(gè)空缺。
2、對于不滿足八位的字符，最開始沒預(yù)想到這種情況，壓縮過程中出現(xiàn)錯(cuò)誤，后來通過同學(xué)的提醒，才意識要進(jìn)行補(bǔ)位的操作。若新增的bit為0，則直接將byte按位左移；新增的bit為1，先將byte按位左移，再與1按位或運(yùn)算的規(guī)律進(jìn)行補(bǔ)位操作。補(bǔ)位時(shí)，還需要預(yù)留一個(gè)字符，等壓縮完后在該位置寫入不足一個(gè)byte的bit個(gè)數(shù)。
3、在測試過程中，解壓縮后的文件總是會比原文件大一點(diǎn)，而文件內(nèi)容的最后總會出現(xiàn)一些亂碼，后來通過調(diào)試和查找相關(guān)資料，我明白了，在ofstream中自帶一種文件流指針，便于我們讀取文件中的字符，在我壓縮的過程當(dāng)中，壓縮到最后，這個(gè)文件流指針就走到了文件的最后，而該指針占用一i定的內(nèi)存，所以在壓縮過程中把該指針也進(jìn)行了壓縮，解壓縮時(shí)自然也輸出了該指針，所以會出現(xiàn)解壓縮后的文件要比原文件大，所以我在壓縮函數(shù)中增加了ofsFile.seekp(0, ios::beg);函數(shù)，將寫指針移動到文件開頭，從而解決了該問題。

4．程序及算法分析

【使用說明】

輸入文件存儲的位置，壓縮/解壓縮文件
（寫博客的時(shí)候才發(fā)現(xiàn)，我這里給的執(zhí)行命令好像和老師要求的執(zhí)行命令不一樣，不過是小問題哈哈，讀者私下自己改一下好了😁）

【測試數(shù)據(jù)】

1、壓縮文件

2、解壓縮文件

3、對比原文件與解壓縮后的文件

【討論與分析】

Huffman壓縮以字節(jié)為單位進(jìn)行壓縮，將8個(gè)bit作為一個(gè)byte，通過對bit進(jìn)行操作，以達(dá)到壓縮與解壓的目的

【改進(jìn)設(shè)想】

1、我現(xiàn)在只實(shí)現(xiàn)了基本要求，沒能實(shí)現(xiàn)多個(gè)文件的同時(shí)壓縮
2、我的壓縮算法不是很好，以至于我的壓縮率比較大，日后還需要多多學(xué)習(xí)才能逐步提高自己的能力

5．附錄

【壓縮函數(shù)核心代碼】

//壓縮函數(shù) 成功執(zhí)行返回 true 失敗 false bool HuffmanTree::doCompress(char *pcInput, char *pcOutput) {if (!countFrequency(pcInput)) //如果不能計(jì)算字符出現(xiàn)的次數(shù)就返回false 可以計(jì)算就繼續(xù)執(zhí)行程序return false;createHuffmanTree();calculateCode();ifstream ifsFile;ofstream ofsFile;ifsFile.open(pcInput, ios::binary);ofsFile.open(pcOutput, ios::binary);char c;if (!ifsFile){cout << "Unable to open the file" << pcInput << '!' << endl;return false;}if (!ofsFile){cout << "Unable to open the file" << pcOutput << '!' << endl;return false;}//輸出huffman編碼/*while (ifsFile.get(c)){ int _nTem = c + 128;for (int i = 0; i < HT[_nTem].nCodeLenght; i++){ofsFile << HT[_nTem].pnCode[i] << endl;}}*/ofsFile.put(0); //預(yù)留一個(gè)字符，等壓縮完后在該位置寫入不足一個(gè)byte的bit個(gè)數(shù)ofsFile.put(mnRoot - 384); //將根節(jié)點(diǎn)的位置-384寫入（為使該值不超過char的最大表示范圍）//384=256+128for (int i = 0; i<nLeaf * 2 - 1; i++) //從上往下{ //寫入每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)位置if (HT[i].nParent == -1) //若該節(jié)點(diǎn)沒有雙親結(jié)點(diǎn)，則寫入127(一個(gè)字節(jié)所能表示的最大值2?-1=128-1=127)ofsFile.put(127);else //否則將雙親結(jié)點(diǎn)的位置-384再寫入（為使該值不超過char的最大表示范圍）ofsFile.put(HT[i].nParent - 384);}while (ifsFile.get(c)){ //將字符的huffman編碼并加入byte中int _nTem = c + 128;for (int i = 0; i < HT[_nTem].nCodeLenght; i++){//ofsFile.put(HT[_nTem].pnCode[i]);addBit(HT[_nTem].pnCode[i]); //將字符的huffman編碼并加入byte中if (mnBitsNum == 8){ //若byte已滿8位，則輸出該byte并將byte清空ofsFile.put(mcByte);resetByte();}}}if (mnBitsNum != 0){//滿足8位的前面已經(jīng)通過resetByte()函數(shù)清空了 mbitsNum置為0 而不滿足8位的執(zhí)行下面語句//處理最后未滿8個(gè)字符的byte，用0填充并記錄填充的個(gè)數(shù)for (int i = mnBitsNum; i<8; i++){addBit(0);mnLackNum++;}ofsFile.put(mcByte); //再輸出and清空resetByte();}ofsFile.seekp(0, ios::beg); //將寫指針移動到文件開頭（文件流指針）ofsFile.put(mnLackNum); //寫入最后一個(gè)字節(jié)缺失的bit個(gè)數(shù)ifsFile.close();ofsFile.close();return true; }

【解壓縮函數(shù)核心代碼】

//解壓縮函數(shù) 成功執(zhí)行返回 true 失敗 false bool HuffmanTree::doDecompress(char *pcInput, char *pcOutput) {queue<char> q;char c;ifstream ifsFile;ofstream ofsFile;ifsFile.open(pcInput, ios::binary);ofsFile.open(pcOutput, ios::binary);if (!ifsFile){cout << "Unable to open the file" << pcInput << '!' << endl;return true;}if (!ofsFile){cout << "Unable to open the file" << pcOutput << '!' << endl;return false;}ifsFile.get(c);mnLackNum = c; //讀出最后一個(gè)字節(jié)缺失的bit個(gè)數(shù)ifsFile.get(c);mnRoot = c + 384; //讀出根結(jié)點(diǎn)的位置for (int i = 0; i < nLeaf * 2 - 1; i++){ //建立各結(jié)點(diǎn)之間的雙親孩子關(guān)系ifsFile.get(c);if (c == 127) //等于127->根節(jié)點(diǎn)continue;else{HT[i].nParent = c + 384;if (HT[c + 384].nLeftChild == -1)//雙親孩子關(guān)系——先左后右HT[c + 384].nLeftChild = i;elseHT[c + 384].nRightChild = i;}}int _nPoint = mnRoot;//為了方便處理最后一個(gè)可能有缺失bit的字節(jié)，先將讀出的數(shù)據(jù)放入隊(duì)列while (ifsFile.get(c))q.push(c);//還原文件過程while (q.size()>1){ //還未到最后一個(gè)字節(jié)c = q.front(); //返回隊(duì)頂元素for (int i = 0; i < 8; i++){ //先左后右if (int(c & 128) == 0){_nPoint = HT[_nPoint].nLeftChild;//這個(gè)左孩子沒有左孩子也沒有右孩子就把這個(gè)輸出if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1){ofsFile.put(char(_nPoint - 128));_nPoint = mnRoot; //更新}c = c << 1;}else{_nPoint = HT[_nPoint].nRightChild;if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1){ofsFile.put(char(_nPoint - 128));_nPoint = mnRoot;}c = c << 1;}}q.pop(); //彈出隊(duì)頂元素}c = q.front(); //最后一個(gè)字節(jié)for (int i = 0; i < 8 - mnLackNum; i++) //原理同上{if (int(c & 128) == 0){_nPoint = HT[_nPoint].nLeftChild;if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1){ofsFile.put(char(_nPoint - 128));_nPoint = mnRoot;}c = c << 1;}else{_nPoint = HT[_nPoint].nRightChild;if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1){ofsFile.put(char(_nPoint - 128));_nPoint = mnRoot;}c = c << 1;}}q.pop();ifsFile.close();ofsFile.close();return true; }

注：點(diǎn)擊此處下載源代碼程序包，感謝閱讀~

總結(jié)

以上是生活随笔為你收集整理的c++ 数据结构 软件压缩/解压缩软件Szip（Huffman算法及应用）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。