基于huffman樹的文件壓縮項目

壓縮原因
1.文件太大，節(jié)省空間
2.提高數(shù)據(jù)在網(wǎng)絡(luò)上傳輸?shù)男?br/>3.對數(shù)據(jù)起到保護作用---加密
文件壓縮類型
無損壓縮：源文件被壓縮之后，可以通過解壓縮還原成與源文件相同的格式
有損壓縮：源文件被壓縮之后，解壓縮無法還原成與源文件相同，但識別其內(nèi)容沒有影響，多用于語音，圖片，視頻壓縮
基于Huffman樹的壓縮如何實現(xiàn)
通過Huffman編碼實現(xiàn)，字符一般都是以字節(jié)存儲的，通過編碼轉(zhuǎn)換為二進制編碼（1字節(jié)=8比特位）
首先，什么是Huffman樹
給定N個權(quán)值作為N個葉子結(jié)點，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。
例如：給定權(quán)值為1（A）,3（B）,5（C）,7（D）四個節(jié)點，構(gòu)建Huffman樹

Huffman壓縮原理--基于Huffman編碼
以字符串中每個字符出現(xiàn)的次數(shù)為權(quán)值構(gòu)建Huffman樹
從根節(jié)點開始，左分支為0，右分支為1，如上圖
所有權(quán)值節(jié)點都在葉子節(jié)點位置，遍歷每條到葉子節(jié)點的路徑獲取字符的編碼

舉個栗子：ABBBCCCCCDDDDDDD
Huffman編碼：
A:100
B:101
C:11
D:0

原理就是這么簡單，一個字符占一個字節(jié)，現(xiàn)在用二進制編碼代替之后，一個字符只占三位，也就是說一個字節(jié)可以表示兩三個字符，所以說一次壓縮，就會節(jié)省很多字節(jié)，也就起到了壓縮的作用。
項目中最重要的是三點
創(chuàng)建Huffman樹

1 先用權(quán)值創(chuàng)建n棵只有根節(jié)點的二叉樹森林【意思是先創(chuàng)建n個節(jié)點】
2 選取根節(jié)點權(quán)值最小的二叉樹構(gòu)建新的二叉樹【建小堆，新二叉樹根節(jié)點權(quán)值為左右子樹的根節(jié)點權(quán)值之和】【用到了priority_queue優(yōu)先級隊列】
3 刪除使用的兩棵根節(jié)點權(quán)值較小的二叉樹
4 將新創(chuàng)建的二叉樹添加到二叉樹森林中
接下來2-4循環(huán)繼續(xù)，直到二叉樹森林中只有一棵二叉樹則Huffman樹創(chuàng)建成

文件壓縮過程：

1讀取源文件，讀取源文件中每個字符出現(xiàn)的次數(shù)
2 以每個字符出現(xiàn)的次數(shù)作為權(quán)值，創(chuàng)建huffman樹：小堆--優(yōu)先級隊列
3 通過huffman樹找每個字符對應(yīng)的編碼
4 用每個字符的新編碼重新對源文件進行改寫【翻譯的過程】

文件解壓縮的過程：

1. 從壓縮文件中獲取源文件的后綴
2. 從壓縮文件中獲取字符次數(shù)的總行數(shù)
3. 獲取每個字符出現(xiàn)的次數(shù)
4. 重建huffman樹
5. 解壓壓縮數(shù)據(jù)
   ? ? a. 從壓縮文件中讀取一個字節(jié)的獲取壓縮數(shù)據(jù)ch
   ? ? b. 從根節(jié)點開始，按照ch的8個比特位信息從高到低遍歷huffman樹：該比特位是0，取當前節(jié)點的左孩子，否則取右孩子，直到遍歷到葉子節(jié)點位置，該字符就被解析成功，將解壓出的字符寫入文件，如果在遍歷huffman過程中，8個比特位已經(jīng)比較完畢還沒有到達葉子節(jié)點，從a開始執(zhí)行
   ? ? ?c. 重復以上過程，直到所有的數(shù)據(jù)解析完畢。

寫代碼當中碰到的一些主要的問題，我將這些總結(jié)起來：

1.編譯的時候：
剛開始寫的時候測試發(fā)現(xiàn)如果壓縮文件中出現(xiàn)了中文，程序就會崩潰，最后發(fā)現(xiàn)是數(shù)組越界的錯誤，因為如果只是字符，它的范圍是-128~127，程序中使用char類型為數(shù)組下標(0~127)，所以字符沒有問題.?但是漢字的編碼是兩個字節(jié)，所以可能會出現(xiàn)越界，

解決方法：就是將char類型強轉(zhuǎn)為unsigned char，下標可表示范圍為0~255.

2.解壓縮的時候
有些特殊字符在處理需要注意一下，比如'\n'，我的程序中Getline()函數(shù)就是讀取一行字符，但是若是該字符本身就是一個'\n'呢？?這就非常的棘手了. 因為解壓縮之后出現(xiàn)了亂碼

解決方法：讀取壓縮文件時若讀到了'\n',則說明該字符就是'\n'，應(yīng)該繼續(xù)讀取它的次數(shù)

3.運行的時候：
發(fā)現(xiàn)文件篇幅很長的時候，只能壓縮和解壓縮一部分，是因為字符長度的設(shè)定太小

解決方法：_count長度設(shè)為unsigned long long類型

4.還有許多大大小小的問題等等
壓縮率

全部代碼（GitHub）：https://github.com/wake5up/My-c--code/tree/master/compress