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

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

2、法。該算法利用隊列結(jié)構(gòu),從哈夫曼的根節(jié)點出發(fā),向葉子節(jié)點進行編碼,在編碼過程中僅將哈夫曼樹的每個葉子節(jié)點進行一次掃描便可以得到各個葉子節(jié)點的哈夫曼編碼。實驗表明,改進算法不僅壓縮率高于以往算法,而且保證了最終生成的壓縮文件的安全性。關(guān)鍵詞:哈夫曼編碼;哈夫曼算法;改進;數(shù)據(jù)壓縮 中圖分類號:TP312文獻標識碼: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ù)據(jù)通信傳送和下載中,媒體數(shù)據(jù)(包括視頻媒體和音頻媒體等采用數(shù)字化的格式,大量的數(shù)據(jù)資源給存儲器的存儲容量、通信信道帶寬和計算機處理速度帶來很大的負擔,但因當前科學技術(shù)發(fā)展有限,很多硬件技術(shù)還無法完全滿足計算機存儲資源的需求,與帶寬之間差距還很大,僅靠通過增加存儲容量、擴充信道容量以及提高計算機處理速度等方法來解決這個問題還有一定難度,這就需要考慮壓縮。壓縮的關(guān)鍵技術(shù)在于設計合理的編碼技術(shù),如果在計算機通信數(shù)據(jù)傳輸過程中,根據(jù)各字符在電文中出現(xiàn)的頻率的高低,采用變長的二進制位表示,出現(xiàn)頻率高的字符則編碼較短,出現(xiàn)頻率低的則編碼較短的原則對報文字符重新進行編碼,從而使原本很長

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

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

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

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

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

12、,沿線到達各頻度電文字符的葉子結(jié)點,所經(jīng)過的分支代碼序列就構(gòu)成了相應頻度電文的哈夫曼編碼。利用哈夫曼算法,可以設計出最優(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期 唐山師范學院學報 2014年9月 -42-是一種優(yōu)化靜態(tài)編碼方法。具有以下不足:(1需要事先知道輸入碼字符集的頻率分布,在不同的數(shù)據(jù)文件中,不同字符出現(xiàn)的頻率不同。(2需要對原始數(shù)據(jù)塊掃描兩次:第一次是統(tǒng)計原

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

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

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

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

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

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