基于改進(jìn)哈夫曼編碼的數(shù)據(jù)壓縮方法研究-

1、第36卷第5期 唐山師范學(xué)院學(xué)報(bào) 2014年9月 Vol.36 No.5 Journal of Tangshan Teachers College Sep. 2014 收稿日期:2014-04-10作者簡介:張紅軍(1979-,男,河南平輿縣人,碩士,講師,研究方向?yàn)榫W(wǎng)絡(luò)與多媒體技術(shù)。 -40-計(jì)算機(jī)科學(xué)與技術(shù)基于改進(jìn)哈夫曼編碼的數(shù)據(jù)壓縮方法研究張紅軍,徐 超(安陽師范學(xué)院 人文管理學(xué)院,河南 安陽 455000摘 要:作為一種無損壓縮編碼方法,哈夫曼編碼在數(shù)據(jù)壓縮中具有重要的應(yīng)用。經(jīng)典的哈夫曼編碼是在構(gòu)造哈夫曼的基礎(chǔ)上自下而上進(jìn)行的,通過分析哈夫曼算法的思想,給出了一種改進(jìn)的哈夫曼數(shù)據(jù)壓縮算

2、法。該算法利用隊(duì)列結(jié)構(gòu),從哈夫曼的根節(jié)點(diǎn)出發(fā),向葉子節(jié)點(diǎn)進(jìn)行編碼,在編碼過程中僅將哈夫曼樹的每個(gè)葉子節(jié)點(diǎn)進(jìn)行一次掃描便可以得到各個(gè)葉子節(jié)點(diǎn)的哈夫曼編碼。實(shí)驗(yàn)表明,改進(jìn)算法不僅壓縮率高于以往算法,而且保證了最終生成的壓縮文件的安全性。關(guān)鍵詞:哈夫曼編碼;哈夫曼算法;改進(jìn);數(shù)據(jù)壓縮 中圖分類號:TP312文獻(xiàn)標(biāo)識碼:A 文章編號:1009-9115(201405-0040-04Research of Data Compression Method Based on the ImprovedHuffman Code AlgorithmZHANG Hong-jun, XU Chao(College o

3、f Humanistic and Management, Anyang Normal University, Anyang 455000, ChinaAbstract: As a non-losing compressing coding algorithm, Huffman coding has many important application to the current data compression field.The classic algorithm to get Huffman coding is from bottom to top on the basis of the

4、 Huffman tree. This paper gives an improved Huffman algorithm of data compression by the analysis of the Huffman algorithm, in which algorithm go from the root node to leaf nodes of the Huffman tree by using the queue structure.In the coding process, every leaf node is only scanned once before getti

5、ng the Huffman coding.The experimental result shows the fact that the improved algorithm not only the compression ratio is higher than classic algorithm, but also ensure the security and confidentiality of the resulting compressed.Key Words: Huffman coding; Huffman algorithm; improve; data compressi

6、on在互聯(lián)網(wǎng)時(shí)代,在數(shù)據(jù)通信傳送和下載中,媒體數(shù)據(jù)(包括視頻媒體和音頻媒體等采用數(shù)字化的格式,大量的數(shù)據(jù)資源給存儲器的存儲容量、通信信道帶寬和計(jì)算機(jī)處理速度帶來很大的負(fù)擔(dān),但因當(dāng)前科學(xué)技術(shù)發(fā)展有限,很多硬件技術(shù)還無法完全滿足計(jì)算機(jī)存儲資源的需求,與帶寬之間差距還很大,僅靠通過增加存儲容量、擴(kuò)充信道容量以及提高計(jì)算機(jī)處理速度等方法來解決這個(gè)問題還有一定難度,這就需要考慮壓縮。壓縮的關(guān)鍵技術(shù)在于設(shè)計(jì)合理的編碼技術(shù),如果在計(jì)算機(jī)通信數(shù)據(jù)傳輸過程中,根據(jù)各字符在電文中出現(xiàn)的頻率的高低,采用變長的二進(jìn)制位表示,出現(xiàn)頻率高的字符則編碼較短,出現(xiàn)頻率低的則編碼較短的原則對報(bào)文字符重新進(jìn)行編碼,從而使原本很長

7、的電文代碼大大縮短,得到平均長度最短的電文編碼,使報(bào)文在存儲和傳輸中,存儲空間降低,信息傳輸效率提高,實(shí)現(xiàn)壓縮目的1。計(jì)算機(jī)數(shù)據(jù)編碼方式有哈夫曼編碼、限定長度變化編碼、算法編碼等。作為一種無損數(shù)據(jù)壓縮編碼,哈夫曼編碼廣泛應(yīng)用于文本、圖像、視頻壓縮、通信數(shù)據(jù)傳輸、密碼等信息壓縮編碼標(biāo)準(zhǔn)中。但目前的哈夫曼編碼方式是通過對構(gòu)造好的哈夫曼樹進(jìn)行自下向上的方式實(shí)現(xiàn)數(shù)據(jù)編張紅軍,等:基于改進(jìn)哈夫曼編碼的數(shù)據(jù)壓縮方法研究 -41-碼,該方式有一些可以待改進(jìn)之處2,3:在算法的時(shí)間復(fù)雜度上,如果定義葉子節(jié)點(diǎn)所在的層次為第1層,其父節(jié)點(diǎn)為第2層,依次類推,處在第n 層上的節(jié)點(diǎn)要被掃描n-1次,在程序運(yùn)行過程中存

8、在著許多指針移動,其時(shí)間復(fù)雜度為O(n 2。針對以上問題,本文設(shè)計(jì)出一種改進(jìn)的哈夫曼編碼方式,它不僅可實(shí)現(xiàn)從樹的根節(jié)點(diǎn)向葉子節(jié)點(diǎn)的編碼,而且可以使編碼的時(shí)間復(fù)雜度降低為O(n,從而節(jié)省了程序的執(zhí)行時(shí)間,達(dá)到了高效壓縮的目的。1 哈夫曼編碼與數(shù)據(jù)壓縮理論哈夫曼編碼是David Huffman 于1952年提出的一種編碼方法,其理論基礎(chǔ)是根據(jù)字符出現(xiàn)的頻率值來構(gòu)造出一棵哈夫曼樹,利用該哈夫曼樹來設(shè)計(jì)平均長度最短的前綴編碼,從而實(shí)現(xiàn)用最短的編碼表示最常用的數(shù)據(jù)塊或出現(xiàn)頻率最高的數(shù)據(jù)。因其編碼效率最接近或達(dá)到100%,有時(shí)又稱為最佳編碼,通常應(yīng)用在數(shù)據(jù)通信、數(shù)據(jù)傳送以及對數(shù)據(jù)的壓縮處理等方面。1.1

9、數(shù)據(jù)壓縮數(shù)據(jù)壓縮是一種對原始的數(shù)據(jù)進(jìn)行一系列的再次編碼,這樣可以消除掉原始數(shù)據(jù)中多余的數(shù)據(jù),可以把數(shù)據(jù)量減低到最小,從而達(dá)到壓縮處理計(jì)算機(jī)上圖像、音頻以及視頻等各種媒體數(shù)據(jù)的目的。一般來說這種技術(shù)的產(chǎn)生是因?yàn)槎嗝襟w數(shù)據(jù)的量太大,很容易對計(jì)算機(jī)的存儲造成負(fù)擔(dān),對網(wǎng)絡(luò)的傳輸帶來不便,如果按照幀的速率為25幀/秒,那么1 s 傳輸?shù)臄?shù)據(jù)量也只有25 MB 左右,用640 MB 的光盤進(jìn)行存貯也只能存放僅僅25 s 的動態(tài)畫面,因此需要對其進(jìn)行數(shù)據(jù)壓縮,壓縮后的文件和數(shù)據(jù)到需要時(shí)通過解壓或者還原,通過對數(shù)據(jù)的冗余進(jìn)行很大程度的壓縮,才更有可能方便計(jì)算機(jī)的存貯和傳輸4。常見的壓縮方法有無損壓縮方法和有損

10、壓縮方法。無損壓縮方法是壓縮后的數(shù)據(jù)經(jīng)解壓縮還原后,得到數(shù)據(jù)與原始數(shù)據(jù)是完全一樣的,是一種基于信息原理的可逆編碼方法。無損壓縮方法常用的有游程編碼、基于字典編碼技術(shù)的LZW 算法和基于哈夫曼編碼原理的壓縮算法5。1.2 哈夫曼樹哈夫曼樹(Huffman 的音譯,又叫赫夫曼、霍夫曼,是由n 個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中帶權(quán)路徑長度WPL 最小的二叉樹,是一種帶權(quán)路徑長度最短的樹,又叫最優(yōu)二叉樹。1.3 哈夫曼樹算法的構(gòu)造過程(1根據(jù)給定的n 個(gè)權(quán)值w 1,w 2,w n 對應(yīng)的n 個(gè)結(jié)點(diǎn),構(gòu)造n 棵只有根結(jié)點(diǎn)的二叉樹,n 棵二叉樹構(gòu)成了二叉樹的森林F=F 1,F2,F n 。(2在森林F 中

11、選取兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹作為左、右子樹,構(gòu)造一棵新的二叉樹,置新二叉樹根結(jié)點(diǎn)權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和。(3從森林F 中刪除被選中的兩棵樹,同時(shí)將新得到的二叉樹加入森林F 中。(4重復(fù)(2、(3兩步,直到森林中只含有一棵二叉樹為止,此時(shí)得到的這棵二叉樹即為哈夫曼樹。例如,給定權(quán)值集合為w=5,2,7,10,4,18,32,22,可以構(gòu)造如下圖1所示的哈夫曼樹。圖1 哈夫曼樹的構(gòu)造1.4 哈夫曼編碼算法哈夫曼編碼算法基本思想:以每個(gè)電文的使用頻率為權(quán)值構(gòu)造哈夫曼樹,然后在構(gòu)造好的哈夫曼樹約定:葉結(jié)點(diǎn)表示電文字符,向左的分支(即左子樹用0表示,向右的分支(即右子樹用1表示,從根結(jié)點(diǎn)開始

12、,沿線到達(dá)各頻度電文字符的葉子結(jié)點(diǎn),所經(jīng)過的分支代碼序列就構(gòu)成了相應(yīng)頻度電文的哈夫曼編碼。利用哈夫曼算法,可以設(shè)計(jì)出最優(yōu)的前綴編碼6。1.5 哈夫曼編碼的構(gòu)造例,電文字符集a,b,c,d,e,f,g,h出現(xiàn)的頻度分別為10,4,2,5,7,18,32,22,其哈夫曼編碼構(gòu)造如圖2所示。圖2 哈夫曼編碼的構(gòu)造1.6 現(xiàn)有編碼的弊端在數(shù)據(jù)壓縮中,哈夫曼編碼是一種變長編碼,采用的第36卷第5期 唐山師范學(xué)院學(xué)報(bào) 2014年9月 -42-是一種優(yōu)化靜態(tài)編碼方法。具有以下不足:(1需要事先知道輸入碼字符集的頻率分布,在不同的數(shù)據(jù)文件中,不同字符出現(xiàn)的頻率不同。(2需要對原始數(shù)據(jù)塊掃描兩次:第一次是統(tǒng)計(jì)原

13、始數(shù)據(jù)中各符號出現(xiàn)的頻率并排序,利用得到的頻率值創(chuàng)建哈夫曼樹并將樹的有關(guān)信息保存起來,便于解壓時(shí)使用;第二次是進(jìn)行編碼,根據(jù)前面得到的哈夫曼樹對原始數(shù)據(jù)進(jìn)行編碼,并將編碼信息存儲起來,便于存儲和傳輸。如果將這種方法用于數(shù)據(jù)的網(wǎng)絡(luò)通信中.兩遍掃描勢必會引起較大的延時(shí),兩次掃描所引發(fā)的低效率不容忽視;同時(shí),如果用于文件數(shù)據(jù)的壓縮中,重復(fù)掃描增加了磁盤訪問,額外的磁盤訪問將會降低該算法的數(shù)據(jù)壓縮速度,從而降低壓縮效率7。2 改進(jìn)的哈夫曼編碼算法本算法用二叉樹層次遍歷方式,利用隊(duì)列(Queue 對整棵哈夫曼樹進(jìn)行一次掃描,即可得到各節(jié)點(diǎn)的哈夫曼編碼。2.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)在本結(jié)構(gòu)體中,除了包含節(jié)點(diǎn)的編碼

14、信息域及權(quán)值之外,還應(yīng)包含該節(jié)點(diǎn)所對應(yīng)的排序碼key ,指向其右右孩子的指針left 和right ,指針其雙親結(jié)點(diǎn)的指針parent ,具體設(shè)計(jì)如下:Typedef struct node *BT; Struct node char date,key10; Int weight;Struct node *left,*right,*parent;本算法采用循環(huán)隊(duì)列,head 指向隊(duì)頭節(jié)點(diǎn),tail 指向隊(duì)尾節(jié)點(diǎn),numbers 表示當(dāng)前隊(duì)列中節(jié)點(diǎn)的個(gè)數(shù),queuelist是表示隊(duì)列的數(shù)組。Typedef struct circle int head,tail; int numbers; BT

15、queuelistsize; 2.2 算法描述改進(jìn)算法從哈夫曼的根節(jié)點(diǎn)出發(fā),通過利用隊(duì)列,按照層次遍歷的方法依次對樹中每個(gè)葉子節(jié)點(diǎn)進(jìn)行編碼。算法執(zhí)行過程如下:(1根據(jù)字符集c1,c2,cn 和相應(yīng)的權(quán)值集w1,w2,wn建立相應(yīng)的哈夫曼樹,并將哈夫曼樹的根節(jié)點(diǎn)入隊(duì);(2當(dāng)隊(duì)列為非空時(shí),遞歸執(zhí)行以下操作: a .指針p 指向當(dāng)前隊(duì)頭節(jié)點(diǎn);b .若當(dāng)前隊(duì)頭節(jié)點(diǎn)無雙親節(jié)點(diǎn),表示該節(jié)點(diǎn)為根節(jié)點(diǎn),將該根節(jié)點(diǎn)出隊(duì)(Dequeue ,并讓其左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)先后入隊(duì)(Enqueue ;c .若當(dāng)前節(jié)點(diǎn)有雙親節(jié)點(diǎn),則給其左、右孩子節(jié)點(diǎn)分別賦值為父節(jié)點(diǎn)的哈夫曼編碼,然后,若此節(jié)點(diǎn)為其父節(jié)點(diǎn)的左孩子,則在其父

16、節(jié)點(diǎn)所賦給的編碼后面加一個(gè)“0”,若此節(jié)點(diǎn)為其父節(jié)點(diǎn)的右孩子,則在其父節(jié)點(diǎn)所賦給的編碼后面加一個(gè)“1”;由于根節(jié)點(diǎn)無編碼,可以直接分別得到“O ”,“1”作為自己的編碼;d .隊(duì)頭節(jié)點(diǎn)出隊(duì);若出隊(duì)節(jié)點(diǎn)有左右孩子節(jié)點(diǎn),則讓其左右孩子分別入隊(duì),若出隊(duì)節(jié)點(diǎn)沒有左右孩子節(jié)點(diǎn),轉(zhuǎn)向e ;e .判斷當(dāng)前隊(duì)列是否為空,若為空則編碼工作完成。 編碼過程如圖3所示。圖3(a表示一棵已經(jīng)建好但還未進(jìn)行編碼的二叉樹。圖3(b表示對根節(jié)點(diǎn)的孩子進(jìn)行編碼。圖3(c表示先將B 節(jié)點(diǎn)的編碼“0”賦給其孩子節(jié)點(diǎn)D 和E ,而D 是B 的左孩子,故在編碼“0”的后面加“0”,E 是B 的右孩子節(jié)點(diǎn),故在編碼“0”的后面加“1”

17、;同理,將C 節(jié)點(diǎn)的編碼“1”賦給其孩子節(jié)點(diǎn)F 和G ,而F 是C 的左孩子,故在編碼“1”的后面加“0”,G 是C 的右孩子節(jié)點(diǎn),故在編碼“1”的后面加“1”;圖3(d表示先將D 的編碼“00”賦給其孩子節(jié)點(diǎn)H 和I ,H 是D 的左孩子,故在編碼“00”后面加“000”,I 是D 的右孩子,故在編碼“00”后面加“001”。(a編碼前的哈夫曼樹(b給第3層節(jié)點(diǎn)編碼(c給第2層節(jié)點(diǎn)編碼 (d給第1層節(jié)點(diǎn)編碼圖3 編程過程示意圖2.3 算法具體實(shí)現(xiàn)流程開始;將根節(jié)點(diǎn)入隊(duì)列;判斷隊(duì)列是否為空;如果為空,則轉(zhuǎn)向j ; 指針q 指向隊(duì)頭節(jié)點(diǎn);張紅軍,等:基于改進(jìn)哈夫曼編碼的數(shù)據(jù)壓縮方法研究-43-判

18、斷q 是否為根節(jié)節(jié);如果是根節(jié)點(diǎn),則轉(zhuǎn)向h ;否則復(fù)制其父節(jié)點(diǎn)的編碼信息;判斷該節(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子還是右孩子;如果是左孩子,則在復(fù)制的父節(jié)點(diǎn)的編碼后面添加一個(gè)“0”,否則在復(fù)制的父節(jié)點(diǎn)的編碼后面添加一個(gè)“1”;隊(duì)頭節(jié)點(diǎn)出隊(duì);判斷出隊(duì)節(jié)點(diǎn)是否有左右孩子,如果有,則將出隊(duì)節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)入隊(duì),否則轉(zhuǎn)向c ;結(jié)束。利用C 、C+或VC+等編程語言,可以方便地將該算法進(jìn)行具體實(shí)現(xiàn)。2.4 算法測試假定某個(gè)壓縮信息所含的五種字符a,b,c,d,e 出現(xiàn)頻率分別為10,16,5,6,9。如果采用ASCII 碼表示該信息需要8*(10+16+5+6+9=368位。如果通過調(diào)用本文描述的算法,對這五種字符進(jìn)行哈夫曼編碼,得到這五種字符的編碼表為a:00, b:11, c:100, d:101, e:01。 該信息編碼后的碼長為2*16+2*(9+10+3*(5+6=103位。從測試結(jié)果看,壓縮后的字符傳送編碼要比原來的小,因此在報(bào)文存儲和傳輸中,用改進(jìn)的哈夫曼算法可以達(dá)到壓縮的目的,減少了存儲空間,提高了信息傳輸效率。2.5 算法效率分析用改進(jìn)的編碼算法對m 個(gè)節(jié)點(diǎn)進(jìn)行改進(jìn)編碼,生成的哈夫曼樹共有2m-1個(gè)節(jié)點(diǎn)。本改算法通過隊(duì)列對節(jié)點(diǎn)進(jìn)行編碼,所以每個(gè)節(jié)點(diǎn)只掃描了一次。因此該改進(jìn)算法在有2m-1個(gè)節(jié)點(diǎn)的哈夫曼樹上的執(zhí)行頻度為2m-1,其時(shí)間復(fù)雜度為O(n。 3 結(jié)束語哈