◆劉海峰 劉澄澄

?

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

◆劉海峰 劉澄澄

（陜西科技大學 陜西 710021）

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

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

0 引言

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

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

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

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

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

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

2 哈夫曼算法

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

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

2.1 哈夫曼樹的建立與編碼

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

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

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

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

2.2 壓縮流程

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

2.3 解壓縮流程

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

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

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

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

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

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

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

由圖3可得，66個葉子節(jié)點的權值即代表66個不同字符。

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

圖1 壓縮流程圖

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

4 《雙城記》壓縮驗證

為了驗證哈夫曼壓縮效果，隨機抽取《雙城記》中的三段如下，段落1到段落3的長度逐漸遞增。

段落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)計每一段的字符種類并對應哈夫曼編碼表1和表2分別找出對應字符的哈夫曼編碼，計算其壓縮前所占的字節(jié)與壓縮后所占的字節(jié)，計算壓縮比，對比驗證壓縮率。如表3所示。

圖2 解壓縮流程圖

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

圖3 哈夫曼樹的構造

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

表3 壓縮對比表

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

5 結束語

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

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

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

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

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

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

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

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

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