C++項目基於HuffmanTree實現文件的壓縮與解壓縮功能
前言
一、文件壓縮
1.文件壓縮的概念
文件壓縮是指在不丟失有用信息的前提下，縮減數據量以減少存儲空間，提高其傳輸、存儲和處理效率，或按照一定的算法對文件中數據進行重新組織，減少數據的冗餘和存儲的空間的一種技術方法。
2.為什麼需要壓縮
①緊縮數據存儲容量，減少存儲空間。
②可以提高數據傳輸的速度，減少帶寬占用量，提高通訊效率。
③對數據的一種加密保護，增強數據在傳輸過程中的安全性。
3.壓縮的分類
- 有損壓縮:有損壓縮是利用瞭人類對圖像或聲波中的某些頻率成分不敏感的特性，允許壓縮過程中損失一定的信息；雖然不能完全恢復原始數據，但是所損失的部分對理解原始圖像的影響縮小，卻換來瞭大得多的壓縮比，即指使用壓縮後的數據進行重構，重構後的數據與原來的數據有所不同，但不影響人對原始資料表達的信息造成誤解。
- 無損壓縮:對文件中數據按照特定的編碼格式進行重新組織，壓縮後的壓縮文件可以被還原成與源文件完全相同的格式，不會影響文件內容，對於數碼圖像而言，不會使圖像細節有任何損失。
4.壓縮的方法
壓縮的目的是讓文件變小，減少文件所占的存儲空間。
專有名詞采用的固定短語：比如：南昌大學，簡稱南大或者昌大，就可以提到壓縮的目的，但隻能針對於大傢所熟知的專有名詞。
縮短文件中重復的數據：比如文件中存放數據為：mnoabczxyuvwabc123456abczxydefgh
對文件中重復數據使用(距離，長度)對進行替換，壓縮之後的結果為：mnoabczxyuvw(9,3)123456(18, 6)defgh。
給文件中每個字節找一個更短的編碼：比如文件中存放數據為：ABBBCCCCCDDDDDDD。
采用靜態等長編碼壓縮： 00010101 10101010 10000000 00000000。
采用動態不等長編碼壓縮：10010110 11011111 11111100 00000000。
文件16個字節，壓縮完成之後占4個字節，可以起到壓縮的目的。
二、HuffmanTree文件壓縮與解壓縮
1.HuffmanTree的概念
在認識哈夫曼樹之前，你必須知道以下幾個基本術語：
①什麼是路徑？
在一棵樹中，從一個結點往下可以達到的結點之間的通路，稱為路徑。
②什麼是路徑長度？
某一路徑所經過的“邊”的數量，稱為該路徑的路徑長度。
如圖，該路徑經過瞭3條邊，因此該路徑的路徑長度為3。
③什麼是結點的帶權路徑長度？
若將樹中結點賦給一個帶有某種含義的數值，則該數值稱為該結點的權。從根結點到該結點之間的路徑長度與該結點的權的乘積，稱為該結點的帶權路徑長度。
如圖，葉子結點I的帶權路徑長度為 3 × 3 = 9 。
④什麼是樹的帶權路徑長度？
樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL。
如圖，該二叉樹的帶權路徑長度 WPL= 2 × 2 + 2 × 6 + 3 × 1 + 3 × 3 + 2 × 2 = 32
⑤什麼是哈夫曼樹？
給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，則稱該二叉樹為哈夫曼樹，也被稱為最優二叉樹。
根據樹的帶權路徑長度的計算規則，我們不難理解：樹的帶權路徑長度與其葉子結點的分佈有關。
即便是兩棵結構相同的二叉樹，也會因為其葉子結點的分佈不同，而導致兩棵二叉樹的帶權路徑長度不同。
那如何才能使一棵二叉樹的帶權路徑長度達到最小呢？
根據樹的帶權路徑長度的計算規則，我們應該盡可能地讓權值大的葉子結點靠近根結點，讓權值小的葉子結點遠離根結點，這樣便能使得這棵二叉樹的帶權路徑長度達到最小。
2.HuffmanTree的構建
下面給出一個非常簡潔易操作的算法，來構造一棵哈夫曼樹：
1、初始狀態下共有n個結點，結點的權值分別是給定的n個數，將他們視作n棵隻有根結點的樹。
2、合並其中根結點權值最小的兩棵樹，生成這兩棵樹的父結點，權值為這兩個根結點的權值之和，這樣樹的數量就減少瞭一個。
3、重復操作2，直到隻剩下一棵樹為止，這棵樹就是哈夫曼樹。
例如，現給定5個數，分別為1、2、2、3、6，要求構建一棵哈夫曼樹。
動圖演示：
1、初始狀態：有5棵隻有根結點的樹。
2、合並權值為1和2的兩棵樹，生成這兩棵樹的父結點，父結點權值為3。
3、合並權值為2和3的兩棵樹，生成這兩棵樹的父結點，父結點權值為5。
4、合並權值為3和5的兩棵樹，生成這兩棵樹的父結點，父結點權值為8。
5、合並權值為6和8的兩棵樹，生成這兩棵樹的父結點，父結點權值為14。
6、此時隻剩下一棵樹瞭，這棵樹就是哈夫曼樹。
3.文件壓縮
1.統計源文件中每個字符出現的頻數
2.根據統計的結果創建HuffmanTree
3.借助Huffman樹獲取每個字節的編碼
4.使用獲取到的字節編碼對源文件進行改寫，對源文件每個字節替換成huffman編碼
4.文件解壓縮
1.解壓縮需要獲取的信息
1.獲取源文件後綴
2.構建字節頻次信息，統計有效字符總行數
3.寫入信息
2.從壓縮文件讀取解壓縮需要用到的信息
3.恢復huffmanTree
4.讀取壓縮信息,結合huffmanTree進行解壓縮
三、HuffmanTree壓縮解壓縮碰到的問題
1.創建優先級隊列要使用自己寫的仿函數
默認創建的是根據節點的地址來比較，這裡寫最後是按地址的大小比較,因為傳過去的是節點的指針，而我們要根據根據節點裡面的權值來創建小堆，所以自己寫仿函數。
2.自定義類型結構體類型相加和仿函數要重載operator+和operator>
3.剔除在HuffmanTree出現0次的字符，不用統計出現0次的字符
4.如果在解壓縮時，最後一個字節的壓縮數據不滿8個比特位，則在解壓縮過程中如何處理？
5.在解壓縮源文件中有漢字，解壓縮過時出現亂碼，怎麼處理？
首先應該註意到是的亂碼出現的原因：
1.文件中存在漢字，而漢字的編碼對應ASCII表可能是使用多個字節來編碼一個漢字，但是在解碼過程中是逐字節獲取，這就導致瞭該字節在表中對應一個負數。
壓縮帶中文的文件，程序就會崩潰。
最後發現數組越界的問題.
因為char它的范圍是-128127，程序中使用char類型為數組下標（0127），所以字符沒有問題，但是漢字是占兩個字節的，所以會出現越界的問題，解決的方法就是char類型強轉為unsigned char，它的范圍為0~255。
6.文件中包含多行文本時解壓縮出現亂碼
最直接的排錯方式：查看壓縮與解壓縮時使用的Huffman樹是否相同，相當於比較壓縮與解壓縮時所使用的字節頻次信息是否相同，遇到換行時，直接開始下一次循環，以至於最後的循環少一次。
7.解壓縮文件大小小於源文件大小，沒有解壓縮全部如何解決
①如何判斷解壓縮文件是否正確，使用的是Ultar Edit
②文件讀取時，”r”文本方式讀入，讀取時遇到-1就會結束，所以在此處要采用二進制方式進行讀寫“rb”
四、測試結果
1.字符文件
自帶的壓縮軟件為1KB,這個為6KB。
2.文本文件
3.圖片文件
4.如果對壓縮結果二次或者多次壓縮，會不會每次都變小
不會，對壓縮文件再次壓縮就相當於在進行一次Huffman編碼的基礎上再進行編碼，結果不一定。
5.Huffman壓縮有無出現壓縮結果變大的可能
有，在文件中如果字節的種類非常多，而且出現次數比較均衡的情況下，變大的可能性就越大，Huffman樹在越接近平衡二叉樹的情況下，壓縮結果越不理想，字節的編碼長度都差不多，比如壓縮音頻以及視頻文件，壓縮率都超過瞭100%！
6.結論
文本文件的壓縮率比二進制文件的壓縮率更好，因為文本文件的編碼相比於二進制文件的編碼相對更簡單，導致瞭文件壓縮率的差距較大。相比傳統的壓縮工具，這個工具壓縮效率基本為傳統壓縮效率的3分之一。
到此這篇關於C++項目基於HuffmanTree實現文件的壓縮與解壓縮功能的文章就介紹到這瞭,更多相關C++文件的壓縮與解壓縮內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！