基于Huffman算法和LZ77算法的文件壓縮（三）

基于Huffman算法和LZ77算法的文件壓縮（一）和
基于Huffman算法和LZ77算法的文件壓縮（二）講解Huffman壓縮的基本原理和文件壓縮的整個過程，接下來講解文件解壓縮的過程

一、 利用hu?man編碼對源文件進行解壓縮

解壓縮的整個流程：

從壓縮文件中獲取源文件的后綴

從壓縮文件中獲取字符次數的總行數

獲取每個字符出現的次數

重建hu?man樹

解壓縮

二. 從壓縮文件中獲取源文件的后綴

如果想要解壓縮文件，那么就需要Huffman樹，如果需要Huffman樹，就需要字符頻度信息，最后還要把解壓縮出來的數據保存在文件中，就需要獲取文件后綴信息。那么這些標記信息已經在壓縮文件的時候寫入到壓縮文件當中，接下來直接讀取即可。

為了方便讀取一行，先封裝一個函數：

//讀一行函數 void FileCompressHuffman::ReadLine(FILE* fIn, std::string& strInfo) {assert(fIn);//注意這里的feof是針對二進制文件的，因為我們為了解決可以壓縮漢字的相關問題，//選擇以二進制的方式打開，并不是以文本文件的方式打開，文本文件的結束標識是EOF，//而二進制文件的結束標識是FEOFwhile (!feof(fIn)){char ch = fgetc(fIn);if (ch == '\n')break;strInfo += ch;} }

注意：

• 注意這里的feof是針對二進制文件的，因為我們為了解決可以壓縮漢字的相關問題，選擇以二進制的方式打開，并不是以文本文件的方式打開，文本文件的結束標識是EOF，而二進制文件的結束標識是FEOF

讀取文件后綴

//文件后綴std::string strFilePostFix;ReadLine(fIn, strFilePostFix);

三. 從壓縮文件中獲取字符次數的總行數

//讀取文件數據的行數std::string strCount;ReadLine(fIn, strCount);int lineCount = atoi(strCount.c_str());

四. 獲取每個字符出現的次數信息

for (int i = 0; i < lineCount; ++i) {//記錄讀取每一行的數據std::string strchCount;ReadLine(fIn, strchCount);//如果讀到的數據為空，說明可能讀到了換行符if (strchCount.empty()) {strchCount += '\n';ReadLine(fIn, strchCount);}//因為數據的格式是 A:3，記錄讀取到的相關字符信息方便構建哈夫曼樹,_fileInfo[(unsigned char)strchCount[0]]._count = atoi(strchCount.c_str() + 2);}

注意：

• 如果文件當中含有多行（即有人為換行），需要再向后讀取一行，因為我們封裝的ReadLine函數是遇到換行就break掉，沒有成功把換行讀到緩沖區當中，所以需要if (strchCount.empty())判斷，如果沒有讀取到任何字符，就代表讀取到了換行符，就把換行符追加到strchCount，再向下讀取一行獲取換行符的出現次數

五. 重建hu?man樹

HuffmanTree<CharInfo> t;t.CreateHuffmanTree(_fileInfo, CharInfo(0));//構建哈夫曼樹

六. 解壓縮

//解壓縮后的文件名std::string newFileName = "3" + strFilePostFix;FILE* fOut = fopen(newFileName.c_str(), "wb");if(fOut == nullptr){perror("open file is error\n");return ;}char *pReadBuff = new char[1024];char ch = 0;HuffmanTreeNode<CharInfo>* pCur = t.GetRoot();//拿到根節點，也就拿到了整個哈夫曼樹的權值之和size_t fileSize = pCur->_Weight._count;//記錄待解壓的總字節數size_t unCount = 0;//記錄已經解壓字符的個數while (1) {size_t rdsize = fread(pReadBuff, 1, 1024, fIn);if (rdsize == 0) {break;}for (size_t i = 0; i < rdsize; ++i) {ch = pReadBuff[i];for (int pos = 0; pos < 8; ++pos) {//0x80--->1000 0000 所以是用來判斷一個字節的高位是1還是0的//規定 1--->往哈夫曼樹的右子樹走 0--->往哈夫曼樹的左子樹走if (ch & 0x80) {pCur = pCur->_pRight;}else {pCur = pCur->_pLeft;}ch <<= 1;//如果pCur左右孩子都為空，說明走到葉子節點了，就可以獲取到具體的字符了if (nullptr == pCur->_pLeft && nullptr == pCur->_pRight) {++unCount;fputc(pCur->_Weight._ch, fOut);pCur = t.GetRoot();//因為每次不一定剛好是整字節數，所以防止多讀，需要進行判斷if (unCount == fileSize)break;}}}

注意：

• 規定1往右走，0往左走，當走到葉子節點的時候，就把解壓出來的字符寫入到解壓縮文件當中
• 因為存儲字符信息的時候是一個字節一個字節存儲的，即8bite，如果我們知道每個bite位為0還是為1，就可以控制其在Huffman中是朝左走，還是朝有走，最后走到葉子節點拿到字符信息，所以我們 &0x80（1000 0000） ，如果結果為真代表該bite位為1，反之為0，這樣就可以控制走 向了
• 最后還要 根據Huffman樹根節點的權值信息來獲取到整個文件的大小，防止最后一個bit位解壓過頭， 在每成功解壓出一個數據后，就對++unCount，最后判斷unCount和fileSize的大小，如果相等就代表已經全部解壓出來，后序bit位不是壓縮數據
• 最最最最后再說一次，保存字符信息的相關變量要用unisigned char類型，不能用char類型，否則在壓縮或解壓縮漢字時會報錯
• 文本文件的末尾標志是EOF（-1），而壓縮文件的結果是有可能FF的情況（即1111 1111 …，32個1），那么在文本文件當中在$if（！EOF（））$判斷的時候就會意外終止，所以需要以二進制的方式讀寫文件

解壓縮完整代碼：

//解壓縮 void FileCompressHuffman::UnCompressFile(const std::string& path) {FILE* fIn = fopen(path.c_str(), "rb");if (nullptr == fIn) {//assert(false);perror("open file is error");return;}//文件后綴std::string strFilePostFix;ReadLine(fIn, strFilePostFix);//讀取文件數據的行數std::string strCount;ReadLine(fIn, strCount);int lineCount = atoi(strCount.c_str());for (int i = 0; i < lineCount; ++i) {//記錄讀取每一行的數據std::string strchCount;ReadLine(fIn, strchCount);//如果讀到的數據為空，說明可能讀到了換行符if (strchCount.empty()) {strchCount += '\n';ReadLine(fIn, strchCount);}//因為數據的格式是 A:3，記錄讀取到的相關字符信息方便構建哈夫曼樹,_fileInfo[(unsigned char)strchCount[0]]._count = atoi(strchCount.c_str() + 2);}HuffmanTree<CharInfo> t;t.CreateHuffmanTree(_fileInfo, CharInfo(0));//構建哈夫曼樹//解壓縮后的文件名std::string newFileName = "3" + strFilePostFix;FILE* fOut = fopen(newFileName.c_str(), "wb");if(fOut == nullptr){perror("open file is error\n");return ;}char *pReadBuff = new char[1024];char ch = 0;HuffmanTreeNode<CharInfo>* pCur = t.GetRoot();//拿到根節點，也就拿到了整個哈夫曼樹的權值之和size_t fileSize = pCur->_Weight._count;//記錄待解壓的總字節數size_t unCount = 0;//記錄已經解壓字符的個數while (1) {size_t rdsize = fread(pReadBuff, 1, 1024, fIn);if (rdsize == 0) {break;}for (size_t i = 0; i < rdsize; ++i) {ch = pReadBuff[i];for (int pos = 0; pos < 8; ++pos) {//0x80--->1000 0000 所以是用來判斷一個字節的高位是1還是0的//規定 1--->往哈夫曼樹的右子樹走 0--->往哈夫曼樹的左子樹走if (ch & 0x80) {pCur = pCur->_pRight;}else {pCur = pCur->_pLeft;}ch <<= 1;//如果pCur左右孩子都為空，說明走到葉子節點了，就可以獲取到具體的字符了if (nullptr == pCur->_pLeft&&nullptr == pCur->_pRight) {++unCount;fputc(pCur->_Weight._ch, fOut);pCur = t.GetRoot();//因為每次不一定剛好是整字節數，所以防止多讀，需要進行判斷if (unCount == fileSize)break;}}}}fclose(fIn);fclose(fOut);delete[] pReadBuff; }

基于Huffman壓縮還存在的問題：

• 無法壓縮視屏、圖片、音頻文件，只能壓縮文本文件，壓縮視頻、圖片等文件會發現壓縮后等文件變大

總結

以上是生活随笔為你收集整理的基于Huffman算法的文件解压缩的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。