◆劉海峰 劉澄澄

?

基于VC++的無損壓縮技術(shù)實(shí)現(xiàn)

◆劉海峰 劉澄澄

（陜西科技大學(xué) 陜西 710021）

數(shù)據(jù)是信息的載體，數(shù)據(jù)壓縮是信息量基本不變的情況下，降低數(shù)據(jù)量的核心技術(shù)。數(shù)據(jù)組織方式不同，數(shù)據(jù)量不同，但是信息量基本相同，為了節(jié)省數(shù)據(jù)存儲(chǔ)空間或者提升信息的傳遞效率，把數(shù)據(jù)結(jié)構(gòu)理論與算法應(yīng)用到數(shù)據(jù)壓縮中，已經(jīng)變得越來越重要。本文通過分析無損壓縮技術(shù)的原理，采用VC++編程環(huán)境實(shí)現(xiàn)無損壓縮中相對(duì)典型的哈夫曼壓縮技術(shù)，并且采用文件夾和文本比較工具Beyond Compare 4軟件將無損壓縮前與解壓還原后的數(shù)據(jù)進(jìn)行對(duì)比驗(yàn)證。通過無損壓縮實(shí)驗(yàn)測(cè)試，成功壓縮和還原了源文件，實(shí)現(xiàn)了預(yù)期目標(biāo)。

無損壓縮；VC++；哈夫曼編碼；Beyond Compare 4

0 引言

隨著信息化時(shí)代的到來，海量數(shù)據(jù)的產(chǎn)生給系統(tǒng)運(yùn)行帶來極大的壓力，單純依靠硬件設(shè)備更新提升存儲(chǔ)空間往往不能滿足系統(tǒng)運(yùn)行效率方面的需求，而專注數(shù)據(jù)壓縮技術(shù)，降低數(shù)據(jù)量，節(jié)約存儲(chǔ)空間，才能更有效緩解海量數(shù)據(jù)帶給系統(tǒng)的巨大壓力。本文論述了無損壓縮技術(shù)[1]的特征、用途和基于無損壓縮技術(shù)中哈夫曼壓縮技術(shù)的工作原理。本文研究的重點(diǎn)在于數(shù)據(jù)壓縮的兩大數(shù)學(xué)模型：數(shù)據(jù)壓縮與解壓縮。本文選用C++作為數(shù)據(jù)壓縮的編程語言，調(diào)用其中較為成熟的vector類庫、string類庫，再配合template模板來進(jìn)行哈夫曼樹的構(gòu)造和堆的建立。

1 數(shù)據(jù)壓縮簡(jiǎn)述

所謂數(shù)據(jù)壓縮，顧名思義就是壓縮數(shù)據(jù)存儲(chǔ)占據(jù)的空間，最終實(shí)現(xiàn)便于數(shù)據(jù)傳輸、處理以及節(jié)省儲(chǔ)存空間的目的，但同時(shí)該技術(shù)的使用需要做到確保數(shù)據(jù)的真實(shí)準(zhǔn)確性不受損害這一原則。該技術(shù)主要通過以下兩種方式來實(shí)現(xiàn)，一種是壓縮數(shù)據(jù)空間，另一種是依靠算法實(shí)現(xiàn)原始數(shù)據(jù)的重整，以精簡(jiǎn)空間[2]。從本質(zhì)上講，數(shù)據(jù)壓縮技術(shù)是一種編碼技術(shù)，換言之是利用不同的數(shù)據(jù)組織方式表達(dá)相同的含義、攜載基本相同的信息量。本文的目的就是通過數(shù)據(jù)編碼用最簡(jiǎn)潔的方式表達(dá)數(shù)據(jù)包含的信息，更確切地說是用更少的數(shù)據(jù)空間存儲(chǔ)更多的信息。

從源文件到編碼文件的映射過程就是數(shù)據(jù)編碼。類似于聲音、圖像、文本等等形式的源文件在計(jì)算機(jī)中都是以二進(jìn)制的形式存儲(chǔ)的，不同之處在于具體的二進(jìn)制表示方法不同。

雖然數(shù)據(jù)壓縮的方式有很多，但是一般來說可以分為有損壓縮和無損壓縮。有損壓縮是指將源文件按照某種特定的方式進(jìn)行壓縮與解壓縮，得到的數(shù)據(jù)與原始的數(shù)據(jù)有所不同或者舍去了某些內(nèi)容，這部分丟失的內(nèi)容是對(duì)信息主體意思的理解無關(guān)緊要的。因此，有損壓縮這種壓縮方式在對(duì)信息的完整性要求不是特別高的重構(gòu)信號(hào)[3]傳輸過程中使用較為廣泛。舉例來講，我們?cè)诮邮芤恍﹫D片以及音頻信息的時(shí)候，受到人體視覺以及聽覺系統(tǒng)的限制，即便是去掉一些影響較小的數(shù)據(jù)信息，對(duì)我們接受和理解圖片以及音頻信息的確定也不會(huì)有太大的影響，此時(shí)就可以使用有損壓縮。

無損壓縮是相對(duì)于有損壓縮來講的，該壓縮方式的特點(diǎn)在于可以最大限度地保持?jǐn)?shù)據(jù)的完整性，換言之，無損壓縮在對(duì)數(shù)據(jù)精確度要求較高，以及要求數(shù)據(jù)壓縮前后保持一致的情況下使用較為廣泛。就當(dāng)前的技術(shù)而言，使用無損壓縮最大可以將數(shù)據(jù)文件的大小減少1/2-3/4。目前使用最為廣泛的壓縮技術(shù)是LZW（Lenpel-Ziv & Welch）[4]以及哈夫曼（Huffman）這兩大類壓縮算法。

2 哈夫曼算法

哈夫曼編碼是最為傳統(tǒng)和典型的無損壓縮技術(shù)。該算法的原理為：用二進(jìn)制的方式來表示每一個(gè)符號(hào)，數(shù)據(jù)的長(zhǎng)度表示為某些特殊符號(hào)出現(xiàn)的頻率次數(shù)。對(duì)于經(jīng)常使用的符號(hào)，選擇的二進(jìn)制就短一些，而一些使用頻率較低的符號(hào)則可以適當(dāng)?shù)丶娱L(zhǎng)。哈夫曼算法[5]可以確保字符的二進(jìn)制編碼情況已經(jīng)將數(shù)據(jù)空間壓縮到極致，任何修改都難以對(duì)其空間進(jìn)行進(jìn)一步壓縮。但是該算法并沒有將符號(hào)之間的排列順序、重復(fù)出現(xiàn)等情況作為處理的重點(diǎn)。根據(jù)ASCII碼的規(guī)定，一個(gè)字符[6]由8個(gè)比特表示,但是如果提前知道了文件中各個(gè)字符出現(xiàn)的頻率，就可以對(duì)這些字符重新編碼。

哈夫曼編碼的使用過程主要如下：第一步就是對(duì)整個(gè)原始文件進(jìn)行掃描，統(tǒng)計(jì)每個(gè)字符的頻率，然后根據(jù)頻率建立哈夫曼樹，由哈夫曼樹得到每個(gè)字符的編碼。由于頻率高的字符在哈夫曼樹中離根更近，它們的哈夫曼編碼長(zhǎng)度更短；相反，頻率低的字符的編碼更長(zhǎng)。最后，用哈夫曼編碼替換原文件中的字符。

2.1 哈夫曼樹的建立與編碼

（1）統(tǒng)計(jì)數(shù)據(jù)中字符出現(xiàn)的頻率并按頻率對(duì)應(yīng)賦權(quán)，由數(shù)據(jù)中的字符集相應(yīng)得到一個(gè)權(quán)值集，由每個(gè)權(quán)值作為根節(jié)點(diǎn)的權(quán)并構(gòu)造一個(gè)只有根節(jié)點(diǎn)的二叉樹，于是得到一個(gè)二叉樹集。

（2）在二叉樹集中找到根節(jié)點(diǎn)權(quán)值最小的和次小的兩棵二叉樹，規(guī)定根節(jié)點(diǎn)權(quán)值最小的二叉樹為左子樹，根節(jié)點(diǎn)權(quán)值次小的二叉樹為右子樹，由這兩個(gè)二叉樹構(gòu)造新的二叉樹，新二叉樹根節(jié)點(diǎn)的權(quán)值為兩個(gè)子樹根節(jié)點(diǎn)權(quán)值之和。在原二叉樹集中刪去根節(jié)點(diǎn)權(quán)值最小和次小的兩棵二叉樹，把新構(gòu)造的二叉樹作為二叉樹集中的新元素。

（3）繼續(xù)進(jìn)行上述步驟（2），直到得到最后一棵樹，這就是最終得出的哈夫曼樹。

（4）規(guī)定在哈夫曼樹中所有父節(jié)點(diǎn)連接左子樹的邊上賦權(quán)0，連接右子樹的邊上賦權(quán)1。從根節(jié)點(diǎn)到每一個(gè)葉子節(jié)點(diǎn)的有向路徑把邊的權(quán)值順序排列形成0/1序列碼，稱為該葉子節(jié)點(diǎn)的哈夫曼編碼。

2.2 壓縮流程

綜上所述，完成了哈夫曼樹的建立與編碼之后，接下來便進(jìn)行數(shù)據(jù)壓縮，當(dāng)給出了所有字符對(duì)應(yīng)的權(quán)值集合時(shí)，首先把它的權(quán)值順序放在堆的Heap數(shù)組中。最初數(shù)據(jù)的排列不一定是一個(gè)最小堆，因此需要先將其調(diào)整成為一個(gè)小堆MinHeap()，然后不斷刪除最小關(guān)鍵碼記錄（葉子節(jié)點(diǎn)權(quán)值），即將其完全二叉樹的順序表示的第0號(hào)元素刪去，以此來不斷獲取權(quán)值最小和權(quán)值次小的結(jié)點(diǎn)構(gòu)成新的二叉樹，但是需要注意的是在把這個(gè)元素取走后，一般以堆的最后一個(gè)結(jié)點(diǎn)填補(bǔ)取走的堆頂元素，并將堆的實(shí)際元素個(gè)數(shù)減1，然后用最后一個(gè)元素取代堆頂元素會(huì)破壞堆，需要調(diào)用下調(diào)算法AdjustDown()從堆頂向下進(jìn)行調(diào)整，不斷維護(hù)小堆。當(dāng)小堆被Pop完時(shí)，最終得到的二叉樹就時(shí)從局部到整體的逐步構(gòu)建成的哈夫曼樹。由根節(jié)點(diǎn)沿著二叉樹路徑下行，左分支標(biāo)記為0，右分支標(biāo)記為1，則每條從根結(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑唯一表示了該葉結(jié)點(diǎn)的二進(jìn)制編碼。具體流程如圖1所示。

2.3 解壓縮流程

如圖2展示了哈夫曼解壓縮的具體流程，解壓縮需要引入配置文件（字符的種類與對(duì)應(yīng)頻率）來構(gòu)建哈夫曼樹，繼而讀入哈夫曼樹，然后由哈夫曼樹生成哈夫曼編碼。

獲取編碼本之后，從壓縮文件中讀取二進(jìn)制信息，依次與編碼本中的編碼進(jìn)行對(duì)比，“0”向左子樹走，“1”向右子樹走，走到葉子結(jié)點(diǎn)則向文件中寫入葉子結(jié)點(diǎn)下標(biāo)對(duì)應(yīng)的字符，再回到根節(jié)點(diǎn)重復(fù)上述步驟。

3 《雙城記》全英文版編碼

查爾斯?狄更斯所著的《雙城記》是以法國大革命為背景所寫成的長(zhǎng)篇?dú)v史小說，其全英版的小說內(nèi)容包含英文字母（大小寫）、標(biāo)點(diǎn)符號(hào)以及空格。

統(tǒng)計(jì)《雙城記》中所出現(xiàn)的所有字符，以及對(duì)應(yīng)字符出現(xiàn)的次數(shù)，如表1所示。

如表1所示，《雙城記》有66個(gè)不同種類的字符（!，“，(…空格），66個(gè)字符出現(xiàn)的頻率如上表所示，設(shè)其權(quán)w={13，39，2，…，6，3，1669}，葉子節(jié)點(diǎn)個(gè)數(shù)n=66。

設(shè)構(gòu)成的二叉樹集合為F={T1,T2,…T66}，從F中選取權(quán)值最小和次小的樹{T1}和{T2}分別作為左子樹和右子樹構(gòu)造一棵新的二叉樹，其新二叉樹的權(quán)值為左子樹和右子樹的根節(jié)點(diǎn)之和，將新構(gòu)建的二叉樹{T1+2}放入F集合中，并刪除F集合中上一步的兩棵二叉樹，得到新的F集合即為F={T3,T4,T5,T6,…T66,T1+2}。重復(fù)上述的步驟，直到F集合中只剩下一棵二叉樹F={T1+2+3+…+66}。構(gòu)建的哈夫曼樹如圖3所示。

由圖3可得，66個(gè)葉子節(jié)點(diǎn)的權(quán)值即代表66個(gè)不同字符。

為了得到每個(gè)葉子節(jié)點(diǎn)的哈夫曼編碼，規(guī)定每個(gè)節(jié)點(diǎn)的左分支賦權(quán)值0，右分支賦權(quán)值1，如圖1所有左右分支上的權(quán)值所示。從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)所經(jīng)過的順序路徑上的權(quán)值組合即為每個(gè)葉子節(jié)點(diǎn)的哈夫曼編碼，總結(jié)如表2所示。

圖1 壓縮流程圖

由表1和表2對(duì)比可知，一個(gè)字符在數(shù)據(jù)中出現(xiàn)的頻率越高，其最終構(gòu)建出來的哈夫曼編碼的長(zhǎng)度越短，反之字符出現(xiàn)的頻率越低，構(gòu)建的編碼長(zhǎng)度越長(zhǎng)。例如《雙城記》中的“空格”頻率為0.1669，該英文格式的空格為半角空格，每個(gè)半角空格占用0.5個(gè)字節(jié)，1669乘以0.5即為834.5個(gè)字節(jié)；而根據(jù)哈夫曼編碼表2所示，一個(gè)“空格”所對(duì)應(yīng)的哈夫曼編碼為111，1669個(gè)空格則為5007個(gè)1，哈夫曼編碼是八位二進(jìn)制，5007除以8即為625.875個(gè)字節(jié)；綜上所述，未壓縮前的空格所占字節(jié)數(shù)為834.5壓縮后的空格所占字節(jié)數(shù)為625.875?！峨p城記》中的“空格”壓縮率即為3/4。

4 《雙城記》壓縮驗(yàn)證

為了驗(yàn)證哈夫曼壓縮效果，隨機(jī)抽取《雙城記》中的三段如下，段落1到段落3的長(zhǎng)度逐漸遞增。

段落1：“France, less favoured on…to be atheistical and traitorous.”

段落2：“Mr. Attorney-General had to inform the jury…h(huán)oped there were many like him.”

段落3：“The Knitting Done…far better rest that I go to than I have ever known.”

統(tǒng)計(jì)每一段的字符種類并對(duì)應(yīng)哈夫曼編碼表1和表2分別找出對(duì)應(yīng)字符的哈夫曼編碼，計(jì)算其壓縮前所占的字節(jié)與壓縮后所占的字節(jié)，計(jì)算壓縮比，對(duì)比驗(yàn)證壓縮率。如表3所示。

圖2 解壓縮流程圖

表1 《雙城記》出現(xiàn)的所有字符以及對(duì)應(yīng)頻率

圖3 哈夫曼樹的構(gòu)造

表2 《雙城記》出現(xiàn)的所有字符以及對(duì)應(yīng)的哈夫曼編碼

表3 壓縮對(duì)比表

根據(jù)表3所示，可以驗(yàn)證哈夫曼壓縮效果明顯，并且隨著壓縮前的源文件所占字節(jié)數(shù)的增加，壓縮效果越來越明顯。

5 結(jié)束語

本系統(tǒng)還可以壓縮多種格式的單個(gè)文件，如：.txt、.doc、.jpg、.mp3等等，計(jì)算量小，處理速度快，壓縮算法簡(jiǎn)潔，不會(huì)占用系統(tǒng)太多空間。但仍存在壓縮率漏洞。下一步將進(jìn)一步改進(jìn)完善，爭(zhēng)取實(shí)現(xiàn)一個(gè)壓縮率更高的無損壓縮。

[1]宋秉璽.高效無損壓縮算法的研究與實(shí)現(xiàn)[D].西安電子科技大學(xué),2014.

[2]汪帥,呂江花,汪溁鶴,等.一種支持?jǐn)?shù)據(jù)去冗和擴(kuò)容的多媒體文件云存儲(chǔ)系統(tǒng)實(shí)現(xiàn)[J].計(jì)算機(jī)研究與發(fā)展,2018,55(5):1034-1048.

[3] 李暢.無損圖像壓縮算法與有損圖像壓縮算法分析[J].現(xiàn)代計(jì)算機(jī)(專業(yè)版),2014(35):61-64.

[4] 鄢海舟,胥布工,石東江,等.無損壓縮算法LZW前綴編碼優(yōu)化及應(yīng)用[J].計(jì)算機(jī)工程,2017,43(3):299-303.

[5]王防修,劉春紅.一種哈夫曼編碼的改進(jìn)算法[J].武漢輕工大學(xué)學(xué)報(bào),2016,35(1):88-91.

[6]劉娜.淺談?dòng)?jì)算機(jī)中的字符編碼[J].科技創(chuàng)新與應(yīng)用,2017(1):107-107.

[7]王防修劉春紅.基于哈夫曼編碼的選擇算法[J].武漢輕工大學(xué)學(xué)報(bào),2016,35(2):79-82.

[8]苑思明,鄭晗,李俊杰.基于哈夫曼樹壓縮的加密技術(shù)[J].信息記錄材料,2018(6).