前言

一、文件壓縮

1.文件壓縮的概念

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

2.為什么需要壓縮

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

3.壓縮的分類

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

4.壓縮的方法

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

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

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

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

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

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

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

二、HuffmanTree文件壓縮與解壓縮

1.HuffmanTree的概念

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

①什么是路徑？

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

②什么是路徑長(zhǎng)度？

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

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

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

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

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

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

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

如圖，該二叉樹的帶權(quán)路徑長(zhǎng)度 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)路徑長(zhǎng)度達(dá)到最小，則稱該二叉樹為哈夫曼樹，也被稱為最優(yōu)二叉樹。

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

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

2.HuffmanTree的構(gòu)建

下面給出一個(gè)非常簡(jiǎn)潔易操作的算法，來構(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é)編碼對(duì)源文件進(jìn)行改寫，對(duì)源文件每個(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)先級(jí)隊(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.文件中存在漢字，而漢字的編碼對(duì)應(yīng)ASCII表可能是使用多個(gè)字節(jié)來編碼一個(gè)漢字，但是在解碼過程中是逐字節(jié)獲取，這就導(dǎo)致了該字節(jié)在表中對(duì)應(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”

四、測(cè)試結(jié)果

1.字符文件

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

2.文本文件

3.圖片文件

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

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

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

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

6.結(jié)論

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

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

最新評(píng)論