基于哈夫曼編碼的多線程無損壓縮庫的設(shè)計(jì)與實(shí)現(xiàn)

鄢 濤, 彭海峰, 李 浩, 陳 超, 劉永紅, 趙衛(wèi)東(.成都大學(xué) 信息科學(xué)與工程學(xué)院, 四川 成都 6006;2.成都大學(xué) 模式識別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室, 四川 成都 6006)

0 引 言

程序開發(fā)中，文件操作是比較常用的操作.除了創(chuàng)建、刪除及讀寫操作外，壓縮或解壓也很重要.目前，開發(fā)具有壓縮功能的程序比較常用的函數(shù)庫有7z、LZ4、QuickLZ及snappy等，但是這些庫普遍存在不開源、嵌入到自己的項(xiàng)目中不夠便捷等問題.對此，本研究介紹了一種基于哈夫曼樹的多線程壓縮C++庫.該庫以哈夫曼編碼為基礎(chǔ)，實(shí)現(xiàn)了基本的無損壓縮，同時(shí)保證了良好的壓縮率，并且使用C++的多線程實(shí)現(xiàn)了高效的壓縮速度，能夠滿足實(shí)際開發(fā)中高效敏捷的開發(fā)需求.文件壓縮通常分為無損壓縮與有損壓縮.壓縮軟件通常用的都是無損壓縮，無損壓縮又分為2種：一種是將數(shù)據(jù)替換成數(shù)據(jù)加重復(fù)次數(shù)，另一種是用較短的數(shù)來替換較長的數(shù)[1].本研究使用第2種方法，由此能有效地求出所有數(shù)據(jù)的帶權(quán)編碼最小的前綴編碼方式，同時(shí)，將采用C++的多線程來處理壓縮數(shù)據(jù)過大的情況，在保證壓縮率時(shí)提高壓縮的速度.

1 無損壓縮與哈夫曼樹

1.1 無損壓縮的原理

1.1.1 無損壓縮.

無損壓縮是指利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮，可完全恢復(fù)原始數(shù)據(jù)而不引起任何失真，但壓縮率是受到數(shù)據(jù)統(tǒng)計(jì)冗余度的理論限制，一般為2∶1到5∶1.這類方法廣泛用于文本數(shù)據(jù)、程序和特殊應(yīng)用場合的圖像數(shù)據(jù)，如指紋圖像、醫(yī)學(xué)圖像等，的壓縮[2].現(xiàn)在常用的壓縮軟件都是無損壓縮.

1.1.2 無損壓縮方式.

方式1：將數(shù)據(jù)替換成數(shù)據(jù)+重復(fù)次數(shù).例如，某個(gè)文件的內(nèi)容是AAAABBBCCCCC，就可以替換為4A3B5C，將12個(gè)字符壓縮為6個(gè)字符，大大減少了存儲(chǔ)空間，但是這種壓縮比較適用于重復(fù)性大且連續(xù)重復(fù)的情況.

方式2：用更短的數(shù)來替換較長的數(shù).在計(jì)算機(jī)中所有的數(shù)據(jù)都會(huì)以二進(jìn)制進(jìn)行存放，文件里所有的字符、數(shù)字，在計(jì)算機(jī)里都表現(xiàn)為數(shù).將每次出現(xiàn)的字符根據(jù)出現(xiàn)的權(quán)重用二進(jìn)制的1位或幾位進(jìn)行替換，這樣1個(gè)字節(jié)就能存儲(chǔ)多個(gè)字符，減少了普通編碼文件所占的空間大小.

1.2 哈夫曼樹建立

1.2.1 統(tǒng)計(jì)每個(gè)字符出現(xiàn)的頻率.

若要建立哈夫曼樹，首先要計(jì)算出該文檔中每個(gè)字符出現(xiàn)的頻率，然后根據(jù)出現(xiàn)的頻率給每個(gè)字符賦予權(quán)值.假設(shè)該文檔中有A、B、C與D 4個(gè)字符，出現(xiàn)的次數(shù)依次是10、8、5與4次，然后可以給A、B、C與D根據(jù)出現(xiàn)的次數(shù)賦予編碼.偽代碼如下:

void analyse(char * fileName)

{

while ((fread(&temp,1,1,fp))==1)//fp為該文件的指針

{

int flagExist=0;

//判斷該字符之前出現(xiàn)過沒有?

check(flagExist);

//沒有出現(xiàn)過

if (!flagExist)

save(temp);//存儲(chǔ)該字符

}

fclose(fp);

}

1.2.2 根據(jù)字符出現(xiàn)的頻率建立哈夫曼樹.

先簡單介紹一下前綴編碼，前綴編碼是指任一字符的編碼都不是另一個(gè)字符編碼的前綴，這種編碼翻譯時(shí)不會(huì)出現(xiàn)歧義.哈夫曼編碼是一種帶權(quán)路徑最小的前綴編碼[3]，非常適用于文件壓縮.獲取哈夫曼編碼的偽代碼如下：

void createCoding(FileState * pfileState)

{

//建立根節(jié)點(diǎn)

node * root=createHuffman(pfileState);

//創(chuàng)建哈夫曼樹

fillHuffmanCode(root,pfileState);

//獲取哈夫曼編碼

int i,j;

for(i=0;isymbolCount;i++)

{

printf(″%c″,pfileState->symbolArray[i].character);

for(j=0;j<20;j++)

printf(″%d ″,pfileState->symbolArray[i].huffCode[j]);

}

}

其中，F(xiàn)ileState為文件字符總結(jié)構(gòu)體，有文件中總字符數(shù)及每個(gè)出現(xiàn)的字符數(shù)字2個(gè)屬性.

本研究需要先建立哈夫曼樹，每次依次尋找節(jié)點(diǎn)數(shù)組中最小的2個(gè)數(shù)，然后將其組建成一個(gè)二叉樹，直到讓所有的節(jié)點(diǎn)都組建到這棵二叉樹上為止，然后根據(jù)哈夫曼樹對左右兩邊的節(jié)點(diǎn)賦予編碼，即得到哈夫曼編碼.注意，用1、2進(jìn)行編碼而不是0、1，因?yàn)?可能會(huì)與一個(gè)字節(jié)初始的0產(chǎn)生混淆，所以用2來代替，在壓縮和解壓時(shí)需要把2替換成0，以便進(jìn)行位的操作[4].

2 文件的壓縮與解壓

2.1 文件的壓縮

根據(jù)獲取的哈夫曼編碼來讀文件，將讀到的數(shù)據(jù)按編碼進(jìn)行替換，再用C++的位操作將每個(gè)字符的0、1編碼合成1個(gè)字節(jié)，再存到文件中，這樣1個(gè)字節(jié)就可以存儲(chǔ)多個(gè)字符，從而達(dá)到壓縮效果.偽代碼如下：

void compressor(char * fileName,char * newFileName)

{

//打開文件

ostream outFile;

if (outFile.open(fileName,ios::out)==0)

{

cout<<″打開失敗″<

return;

}

ostream inFile;

if (inFile.open(newFileName,ios::in)==0)

{

cout<<″打開失敗″<

return;

}

//將字典結(jié)構(gòu)體先寫到文件里面，方便解壓時(shí)讀取

writeHeader(fp2,pfileState);

//根據(jù)字典對文件重新編碼實(shí)現(xiàn)壓縮效果

writeCode(fp1,fp2,pfileState);

outFile.close();

inFile.close();

}

本研究修改文件的后綴為ycf，即Linux下的壓縮文件格式，然后對照著編碼表，將每個(gè)字符翻譯成二進(jìn)制中的位，再用C++中的位操作將這些位合成字節(jié)實(shí)現(xiàn)壓縮.

2.2 文件的解壓

解壓過程正好與壓縮過程相反.解壓過程是，依次讀取文件中每個(gè)字符，然后根據(jù)字符的二進(jìn)制對照哈夫曼編碼進(jìn)行翻譯，將翻譯的結(jié)果存儲(chǔ)到指定的文件中，這樣就完成了解壓[4].解壓偽代碼[5-6]如下：

void deCompress(char * fileName，char * newFileName)

{

memset(&fileState,0,sizeof(fileState));

//讀取文件獲得相關(guān)信息存儲(chǔ)到fileState中

readHeader(fileNmae, & fileState);

//創(chuàng)建哈夫曼樹

node * root=NULL;

root=createHuffman(&fileState);

//翻譯哈夫曼編碼得到新的解壓文件

writeDeCompressfile(fp,fileName,root,newFileName);

}

解壓時(shí)，先讀取文件，然后依次翻譯當(dāng)中的每個(gè)字節(jié)，將字節(jié)中的位翻譯成字符，因?yàn)楣蚵幋a是一種前置編碼，在翻譯過程中不會(huì)產(chǎn)生歧義，這樣讀完整個(gè)文件即可完成解壓過程.

3 優(yōu)化、封裝與性能測試

3.1 多線程優(yōu)化

如果處理的文件較大，則單線程的設(shè)計(jì)模式效率就會(huì)很低.壓縮一個(gè)文件可能需要幾分鐘甚至更久，由于這么長的壓縮時(shí)間不能滿足實(shí)際開發(fā)需要，所以必須要引入多線程的設(shè)計(jì)模式[7-8].本研究使用C++11的多線程開發(fā)加快壓縮速率.壓縮過程的偽代碼如下：

void compress(char * fileName,char * newFileName)

{

//用2個(gè)線程讓分析文件與創(chuàng)建哈夫曼編碼同時(shí)進(jìn)行

std::thread th1(analyse,fileName);

std::thread th2(createCoding, & fileState);

//阻塞主線程

th1.join();

th2.join();

writeFile(fileName, & fileState,newFileName);

}

本研究使用C++11庫中的thread類來進(jìn)行并發(fā)操作，同時(shí)使用2個(gè)線程讓分析文件與創(chuàng)建哈夫曼樹同時(shí)進(jìn)行，這樣能大大加快壓縮速度.

3.2 封裝成庫

封裝成靜態(tài)庫的過程很簡單，只需要調(diào)節(jié)項(xiàng)目的相關(guān)屬性，再生成項(xiàng)目即可.庫封裝好之后，調(diào)用庫中函數(shù)的步驟如下：

1)更改項(xiàng)目的相關(guān)屬性，導(dǎo)入庫；

2)引入頭文件，應(yīng)用相關(guān)函數(shù)進(jìn)行壓縮或者解壓，代碼如下：

//引入頭文件

#include

#include

#include

int main(int argc, char ** argv)

{

ycl::compressor t;//定義庫中的壓縮類

std::string op,tar;

//被壓縮的文件絕對路徑名及壓縮后的文件名

std::cin >> op >> tar;

t.compress(op,tar);//壓縮

t.deCompress(op,tar);//解壓縮

return 0;

}

本研究以7z的庫為例介紹如何用7z庫函數(shù)進(jìn)行壓縮與解壓縮.由于7z的庫中沒有現(xiàn)成的壓縮函數(shù)，而且開源社區(qū)也只有7z的源代碼，程序員需要自己編譯成靜態(tài)庫，然后導(dǎo)入到自己的項(xiàng)目中，具體步驟如下：

1)從網(wǎng)絡(luò)下載源代碼，用VS對其編譯成靜態(tài)庫；

2)新建自己的項(xiàng)目導(dǎo)入編譯好的靜態(tài)庫；

3)編寫壓縮與解壓函數(shù).這個(gè)過程非常麻煩，因?yàn)樾枰畮熘兴泻瘮?shù)，才能將其應(yīng)用到自己的函數(shù)中，這將大大降低開發(fā)的效率，增加不必要的開發(fā)難度與時(shí)間消耗[9].

3.3 性能測試分析

封裝好庫后，在Windows平臺下分別對圖片、文本文檔及視頻等常用文件進(jìn)行大量的數(shù)據(jù)測試，因?yàn)閷?shí)際開發(fā)中所要壓縮的文件大小都是以MiB為單位，所以本研究的測試文件都為1 MiB到1 GiB之間的文件.為了保證數(shù)據(jù)的可靠性，每種文件的樣本數(shù)量為100，由于手動(dòng)壓縮文件較麻煩，本研究先把文件存在文件夾中，然后用C語言循環(huán)遍歷此文件夾進(jìn)行壓縮.

測試壓縮率如表1所示.

表1 測試壓縮率

表1中的文件大小都為樣本容量中的平均文件大小.從表1可知，本研究設(shè)計(jì)的庫的壓縮率與現(xiàn)有的庫還有一定的差距.但是，在CSDN、掘金、博客園等論壇上尋找的近100份問答中，一般情況下，本研究所探討的壓縮率已經(jīng)能完全符合實(shí)際開發(fā)的需求，同時(shí)使用起來簡單便捷，然而使用7z的平均學(xué)習(xí)時(shí)間是8 h左右，但使用本研究的庫最多需要2 h的學(xué)習(xí)時(shí)間，且不需要繁瑣的導(dǎo)入過程，開發(fā)效率高.

4 結(jié) 語

本研究討論了利用哈夫曼編碼的多線程壓縮程序.實(shí)驗(yàn)表明，哈夫曼編碼的壓縮方法具有良好的壓縮率，缺點(diǎn)在于需要耗費(fèi)大量時(shí)間，所以在庫中加入了C++11中的多線程，這樣大大縮短了壓縮時(shí)間.簡潔的庫也保證了程序員使用過程中的便捷，相對于目前常用的庫較大地提高了開發(fā)效率，同時(shí)對研究文件壓縮過程和壓縮算法的改進(jìn)具有一定的參考意義.