前言

一、文件壓縮

1.文件壓縮的概念

文件壓縮是指在不丟失有用信息的前提下，縮減數(shù)據(jù)量以減少存儲空間，提高其傳輸、存儲和處理效率，或按照一定的算法對文件中數(shù)據(jù)進(jìn)行重新組織，減少數(shù)據(jù)的冗余和存儲的空間的一種技術(shù)方法。

2.為什么需要壓縮

①緊縮數(shù)據(jù)存儲容量，減少存儲空間。
②可以提高數(shù)據(jù)傳輸?shù)乃俣龋瑴p少帶寬占用量，提高通訊效率。
③對數(shù)據(jù)的一種加密保護(hù)，增強(qiáng)數(shù)據(jù)在傳輸過程中的安全性。

3.壓縮的分類

• 有損壓縮:有損壓縮是利用了人類對圖像或聲波中的某些頻率成分不敏感的特性，允許壓縮過程中損失一定的信息；雖然不能完全恢復(fù)原始數(shù)據(jù)，但是所損失的部分對理解原始圖像的影響縮小，卻換來了大得多的壓縮比，即指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對原始資料表達(dá)的信息造成誤解。
• 無損壓縮:對文件中數(shù)據(jù)按照特定的編碼格式進(jìn)行重新組織，壓縮后的壓縮文件可以被還原成與源文件完全相同的格式，不會(huì)影響文件內(nèi)容，對于數(shù)碼圖像而言，不會(huì)使圖像細(xì)節(jié)有任何損失。

4.壓縮的方法

壓縮的目的是讓文件變小，減少文件所占的存儲空間。

專有名詞采用的固定短語：比如：南昌大學(xué)，簡稱南大或者昌大，就可以提到壓縮的目的，但只能針對于大家所熟知的專有名詞。

縮短文件中重復(fù)的數(shù)據(jù)：比如文件中存放數(shù)據(jù)為：mnoabczxyuvwabc123456abczxydefgh
對文件中重復(fù)數(shù)據(jù)使用(距離，長度)對進(jìn)行替換，壓縮之后的結(jié)果為：mnoabczxyuvw(9,3)123456(18, 6)defgh。

給文件中每個(gè)字節(jié)找一個(gè)更短的編碼：比如文件中存放數(shù)據(jù)為：ABBBCCCCCDDDDDDD。

采用靜態(tài)等長編碼壓縮： 00010101 10101010 10000000 00000000。

采用動(dòng)態(tài)不等長編碼壓縮：10010110 11011111 11111100 00000000。

文件16個(gè)字節(jié)，壓縮完成之后占4個(gè)字節(jié)，可以起到壓縮的目的。

二、HuffmanTree文件壓縮與解壓縮

1.HuffmanTree的概念

在認(rèn)識哈夫曼樹之前，你必須知道以下幾個(gè)基本術(shù)語：

①什么是路徑？

在一棵樹中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的結(jié)點(diǎn)之間的通路，稱為路徑。

②什么是路徑長度？

某一路徑所經(jīng)過的“邊”的數(shù)量，稱為該路徑的路徑長度。

如圖，該路徑經(jīng)過了3條邊，因此該路徑的路徑長度為3。

③什么是結(jié)點(diǎn)的帶權(quán)路徑長度？

若將樹中結(jié)點(diǎn)賦給一個(gè)帶有某種含義的數(shù)值，則該數(shù)值稱為該結(jié)點(diǎn)的權(quán)。從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)的權(quán)的乘積，稱為該結(jié)點(diǎn)的帶權(quán)路徑長度。

如圖，葉子結(jié)點(diǎn)I的帶權(quán)路徑長度為 3 × 3 = 9 。

④什么是樹的帶權(quán)路徑長度？

樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記為WPL。

如圖，該二叉樹的帶權(quán)路徑長度 WPL= 2 × 2 + 2 × 6 + 3 × 1 + 3 × 3 + 2 × 2 = 32

⑤什么是哈夫曼樹？

給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達(dá)到最小，則稱該二叉樹為哈夫曼樹，也被稱為最優(yōu)二叉樹。

根據(jù)樹的帶權(quán)路徑長度的計(jì)算規(guī)則，我們不難理解：樹的帶權(quán)路徑長度與其葉子結(jié)點(diǎn)的分布有關(guān)。
即便是兩棵結(jié)構(gòu)相同的二叉樹，也會(huì)因?yàn)槠淙~子結(jié)點(diǎn)的分布不同，而導(dǎo)致兩棵二叉樹的帶權(quán)路徑長度不同。

那如何才能使一棵二叉樹的帶權(quán)路徑長度達(dá)到最小呢？
根據(jù)樹的帶權(quán)路徑長度的計(jì)算規(guī)則，我們應(yīng)該盡可能地讓權(quán)值大的葉子結(jié)點(diǎn)靠近根結(jié)點(diǎn)，讓權(quán)值小的葉子結(jié)點(diǎn)遠(yuǎn)離根結(jié)點(diǎn)，這樣便能使得這棵二叉樹的帶權(quán)路徑長度達(dá)到最小。

2.HuffmanTree的構(gòu)建

下面給出一個(gè)非常簡潔易操作的算法，來構(gòu)造一棵哈夫曼樹：
1、初始狀態(tài)下共有n個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)的權(quán)值分別是給定的n個(gè)數(shù)，將他們視作n棵只有根結(jié)點(diǎn)的樹。
2、合并其中根結(jié)點(diǎn)權(quán)值最小的兩棵樹，生成這兩棵樹的父結(jié)點(diǎn)，權(quán)值為這兩個(gè)根結(jié)點(diǎn)的權(quán)值之和，這樣樹的數(shù)量就減少了一個(gè)。
3、重復(fù)操作2，直到只剩下一棵樹為止，這棵樹就是哈夫曼樹。

例如，現(xiàn)給定5個(gè)數(shù)，分別為1、2、2、3、6，要求構(gòu)建一棵哈夫曼樹。
動(dòng)圖演示：

1、初始狀態(tài)：有5棵只有根結(jié)點(diǎn)的樹。

2、合并權(quán)值為1和2的兩棵樹，生成這兩棵樹的父結(jié)點(diǎn)，父結(jié)點(diǎn)權(quán)值為3。

3、合并權(quán)值為2和3的兩棵樹，生成這兩棵樹的父結(jié)點(diǎn)，父結(jié)點(diǎn)權(quán)值為5。

4、合并權(quán)值為3和5的兩棵樹，生成這兩棵樹的父結(jié)點(diǎn)，父結(jié)點(diǎn)權(quán)值為8。

5、合并權(quán)值為6和8的兩棵樹，生成這兩棵樹的父結(jié)點(diǎn)，父結(jié)點(diǎn)權(quán)值為14。

6、此時(shí)只剩下一棵樹了，這棵樹就是哈夫曼樹。

3.文件壓縮

1.統(tǒng)計(jì)源文件中每個(gè)字符出現(xiàn)的頻數(shù)

2.根據(jù)統(tǒng)計(jì)的結(jié)果創(chuàng)建HuffmanTree

3.借助Huffman樹獲取每個(gè)字節(jié)的編碼

4.使用獲取到的字節(jié)編碼對源文件進(jìn)行改寫，對源文件每個(gè)字節(jié)替換成huffman編碼

4.文件解壓縮

1.解壓縮需要獲取的信息

1.獲取源文件后綴
2.構(gòu)建字節(jié)頻次信息，統(tǒng)計(jì)有效字符總行數(shù)
3.寫入信息

2.從壓縮文件讀取解壓縮需要用到的信息

3.恢復(fù)huffmanTree

4.讀取壓縮信息,結(jié)合huffmanTree進(jìn)行解壓縮

三、HuffmanTree壓縮解壓縮碰到的問題

1.創(chuàng)建優(yōu)先級隊(duì)列要使用自己寫的仿函數(shù)

默認(rèn)創(chuàng)建的是根據(jù)節(jié)點(diǎn)的地址來比較，這里寫最后是按地址的大小比較,因?yàn)閭鬟^去的是節(jié)點(diǎn)的指針，而我們要根據(jù)根據(jù)節(jié)點(diǎn)里面的權(quán)值來創(chuàng)建小堆，所以自己寫仿函數(shù)。

2.自定義類型結(jié)構(gòu)體類型相加和仿函數(shù)要重載operator+和operator>

3.剔除在HuffmanTree出現(xiàn)0次的字符，不用統(tǒng)計(jì)出現(xiàn)0次的字符

4.如果在解壓縮時(shí)，最后一個(gè)字節(jié)的壓縮數(shù)據(jù)不滿8個(gè)比特位，則在解壓縮過程中如何處理？

5.在解壓縮源文件中有漢字，解壓縮過時(shí)出現(xiàn)亂碼，怎么處理？

首先應(yīng)該注意到是的亂碼出現(xiàn)的原因：
1.文件中存在漢字，而漢字的編碼對應(yīng)ASCII表可能是使用多個(gè)字節(jié)來編碼一個(gè)漢字，但是在解碼過程中是逐字節(jié)獲取，這就導(dǎo)致了該字節(jié)在表中對應(yīng)一個(gè)負(fù)數(shù)。

壓縮帶中文的文件，程序就會(huì)崩潰。

最后發(fā)現(xiàn)數(shù)組越界的問題.
因?yàn)閏har它的范圍是-128127，程序中使用char類型為數(shù)組下標(biāo)（0127），所以字符沒有問題，但是漢字是占兩個(gè)字節(jié)的，所以會(huì)出現(xiàn)越界的問題，解決的方法就是char類型強(qiáng)轉(zhuǎn)為unsigned char，它的范圍為0~255。

6.文件中包含多行文本時(shí)解壓縮出現(xiàn)亂碼

最直接的排錯(cuò)方式：查看壓縮與解壓縮時(shí)使用的Huffman樹是否相同，相當(dāng)于比較壓縮與解壓縮時(shí)所使用的字節(jié)頻次信息是否相同，遇到換行時(shí)，直接開始下一次循環(huán)，以至于最后的循環(huán)少一次。

7.解壓縮文件大小小于源文件大小，沒有解壓縮全部如何解決

①如何判斷解壓縮文件是否正確，使用的是Ultar Edit

②文件讀取時(shí)，”r"文本方式讀入，讀取時(shí)遇到-1就會(huì)結(jié)束，所以在此處要采用二進(jìn)制方式進(jìn)行讀寫“rb”

四、測試結(jié)果

1.字符文件

自帶的壓縮軟件為1KB,這個(gè)為6KB。

2.文本文件

3.圖片文件

4.如果對壓縮結(jié)果二次或者多次壓縮，會(huì)不會(huì)每次都變小

不會(huì)，對壓縮文件再次壓縮就相當(dāng)于在進(jìn)行一次Huffman編碼的基礎(chǔ)上再進(jìn)行編碼，結(jié)果不一定。

5.Huffman壓縮有無出現(xiàn)壓縮結(jié)果變大的可能

有，在文件中如果字節(jié)的種類非常多，而且出現(xiàn)次數(shù)比較均衡的情況下，變大的可能性就越大，Huffman樹在越接近平衡二叉樹的情況下，壓縮結(jié)果越不理想，字節(jié)的編碼長度都差不多，比如壓縮音頻以及視頻文件，壓縮率都超過了100%！

6.結(jié)論

文本文件的壓縮率比二進(jìn)制文件的壓縮率更好，因?yàn)槲谋疚募木幋a相比于二進(jìn)制文件的編碼相對更簡單，導(dǎo)致了文件壓縮率的差距較大。相比傳統(tǒng)的壓縮工具，這個(gè)工具壓縮效率基本為傳統(tǒng)壓縮效率的3分之一。

到此這篇關(guān)于C++項(xiàng)目基于HuffmanTree實(shí)現(xiàn)文件的壓縮與解壓縮功能的文章就介紹到這了,更多相關(guān)C++文件的壓縮與解壓縮內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論