基于二叉樹存儲(chǔ)結(jié)構(gòu)的LZW改進(jìn)算法

崔方送

(安徽黃梅戲藝術(shù)職業(yè)學(xué)院,安徽 安慶 246052)

引言

隨著大數(shù)據(jù)時(shí)代的到來(lái),面對(duì)海量的數(shù)據(jù)信息,為了進(jìn)行傳輸和存儲(chǔ),必須對(duì)其進(jìn)行壓縮。在數(shù)據(jù)壓縮過(guò)程中,我們通常接收的是一些未知統(tǒng)計(jì)特性的信息,為了對(duì)這些數(shù)據(jù)信息進(jìn)行壓縮,自適應(yīng)的普適編碼方法就應(yīng)運(yùn)而生,其中LZ系列算法是其中一個(gè)重要分支。在1977年,以色列科學(xué)家Ziv和Lempel提出了該算法[1],并在1978年提出了一種改進(jìn)算法,這兩種算法也就是后來(lái)所稱的LZ77算法和LZ78算法[2]。在這之后,一些專家學(xué)者提出了很多改進(jìn)算法,其中最有影響的是Terry Welch在1984年提出的Lempel-Ziv-Welch算法,即LZW算法[3]。

1 LZW算法

1.1 LZW算法簡(jiǎn)介

LZW算法是一種基于字典的編碼方法,它繼承了LZ77和LZ78算法的優(yōu)點(diǎn),容易被人們所接受[4]。所謂基于字典的方法就是將字典中的詞條的編碼代替被壓縮數(shù)據(jù)中的相應(yīng)的字符串。很顯然,被壓縮信息中各詞條出現(xiàn)的頻率越高壓縮效果越好。

1.2 LZW算法基本原理

在LZW算法編碼過(guò)程中[5-6],編碼器逐個(gè)讀入字符,并累積成一個(gè)字符串C,每輸入一個(gè)字符就被串接在C后面,然后在字典中查找C,若在字典中能找到C,就重復(fù)此過(guò)程,直到在某一點(diǎn),添加下一個(gè)字符x使搜索不成功,即字符串C在字典中,而Cx不在字典中,此時(shí)就輸出字符串C在字典中的編碼,并將Cx作為新的詞條存儲(chǔ)到字典的相應(yīng)位置,同時(shí)將字符串C預(yù)置為x。

在LZW譯碼過(guò)程中,需要根據(jù)碼字,逐步重新建立字典,其過(guò)程與編碼相同,這是譯碼算法的關(guān)鍵。

1.3 LZW算法存在的問(wèn)題

LZW算法是一種自適應(yīng)算法,字典的詞條是在編碼過(guò)程中逐漸建立的,在壓縮開始時(shí),字典的詞條數(shù)目和每個(gè)詞條的長(zhǎng)度是無(wú)法量化的,而且該算法會(huì)受內(nèi)存容量、算法復(fù)雜度和計(jì)算速度等因素的限制,所以在編碼過(guò)程中,當(dāng)字典的條目很多、詞條的長(zhǎng)度較長(zhǎng)時(shí),即存儲(chǔ)字典所需的內(nèi)存空間超過(guò)了計(jì)算機(jī)的內(nèi)存,編碼效率明顯下降以及計(jì)算機(jī)運(yùn)行緩慢。因此,本文提出了改進(jìn)算法。

2 LZW算法改進(jìn)

2.1 改進(jìn)思想和原理

針對(duì)LZW算法的不足,在編碼譯碼過(guò)程中,我們應(yīng)盡量減少字典對(duì)內(nèi)存的開銷,本文采取以下方法以優(yōu)化存儲(chǔ)過(guò)程。首先編寫文件轉(zhuǎn)換算法,將待壓縮文件按每個(gè)字符8位二進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制文件，即‘0’、‘1’字符串,然后只需對(duì)該二進(jìn)制文件進(jìn)行LZW編碼,編碼過(guò)程中字典的存儲(chǔ)方式采用二叉樹結(jié)構(gòu)進(jìn)行存儲(chǔ),二進(jìn)制文件中‘0’和‘1’分別和二叉樹節(jié)點(diǎn)的左右孩子域相對(duì)應(yīng)。二叉樹節(jié)點(diǎn)結(jié)構(gòu)如圖1所示。

圖1 二叉樹節(jié)點(diǎn)結(jié)構(gòu)

為了查找方便,本文采用二叉樹的一種主要存儲(chǔ)結(jié)構(gòu),即采用三叉鏈表節(jié)點(diǎn)結(jié)構(gòu),圖1中,Index表示該節(jié)點(diǎn)編碼,Parent指向該節(jié)點(diǎn)的父母節(jié)點(diǎn)。對(duì)該結(jié)構(gòu)進(jìn)行初始化如圖2所示。

圖2 初始化二叉樹

圖2中,T為二叉樹指針,指向二叉樹的首節(jié)點(diǎn),首節(jié)點(diǎn)中Parent域賦值為-1,表示不指向任何節(jié)點(diǎn),Index域賦值為0,表示首節(jié)點(diǎn)的編碼為0,Lchild域指向編碼為1的節(jié)點(diǎn),Rchild域指向編碼為2的節(jié)點(diǎn),同時(shí),節(jié)點(diǎn)1和節(jié)點(diǎn)2的Parent域指向首節(jié)點(diǎn),表示節(jié)點(diǎn)1和節(jié)點(diǎn)2的父母節(jié)點(diǎn)都是首節(jié)點(diǎn)。在該結(jié)構(gòu)中,‘0’和‘1’表示編碼過(guò)程中讀入的二進(jìn)制字符,當(dāng)讀入的是‘0’且需要將新詞條存儲(chǔ)到字典中時(shí),就將該詞條插入到相應(yīng)節(jié)點(diǎn)的Lchild域,當(dāng)讀入的是‘1’且需要將新詞條存儲(chǔ)到字典中時(shí),就將該詞條插入到相應(yīng)節(jié)點(diǎn)的Rchild域。

2.2 改進(jìn)算法的具體實(shí)現(xiàn)

2.2.1編碼算法[7]

步驟1:將待壓縮文件按每個(gè)字符8位二進(jìn)制的形式轉(zhuǎn)換成二進(jìn)制文件，即‘0’、‘1’字符串;

步驟2:初始化二叉樹T,樹中包含所有的根，即包含詞條‘0’和‘1’,且將當(dāng)前前綴賦值為空即C=NULL;

步驟3:從二進(jìn)制文件讀入字符x,并C=C+x;

步驟4:若所讀文件為空轉(zhuǎn)步驟6,否則讀入下一字符x;

步驟5: 查找C+x是否在二叉樹中,若在,就將字符x連接到字符串C尾部，即C=Cx,轉(zhuǎn)步驟4,若不在,輸出字符串C的編碼,并將字符x插到字符串C編碼節(jié)點(diǎn)的左孩子域或右孩子域,并置C為x,轉(zhuǎn)步驟4;

步驟6:結(jié)束。

編碼算法流程圖如圖3所示。

圖3 編碼算法流程圖

2.2.2譯碼算法

步驟1:初始化二叉樹T,樹中包含所有的根，即包含詞條‘0’和‘1’;

步驟2:讀取碼字cw,并輸出cw在T中對(duì)應(yīng)的字符串 Findstr(cw);

步驟3:前綴碼字pw=cw;

步驟4:繼續(xù)讀下一碼字cw,;

步驟5:判斷Findstr(cw)是否在樹T中

若在,輸出Findstr(cw),P=Findstr(pw),C為Findstr(cw)的首字符,Insert(P+C);

若不在,P=Findstr(pw),C為Findstr(pw)的首字符,輸出P+C,Insert(P+C);

步驟6:判斷譯碼文件是否為空,若是轉(zhuǎn)步驟3;

步驟7:將所得二進(jìn)制文件轉(zhuǎn)換成相應(yīng)的字符文件;

步驟8:結(jié)束。

2.3 算法字典存儲(chǔ)空間分析

此處以二進(jìn)制字符串“1110010110010101”為例進(jìn)行編碼、譯碼分析[8]。圖4是編碼過(guò)程中二叉樹字典結(jié)構(gòu)。

圖4 編碼過(guò)程中字典結(jié)構(gòu)

對(duì)字符串“1110010110010101”編碼后輸出的碼子為2,3,1,1,2,6,7,6,10,2。圖3中,節(jié)點(diǎn)中的數(shù)字代表相應(yīng)字符串的編碼,節(jié)點(diǎn)間的二進(jìn)制代表從二進(jìn)制文件中讀入的二進(jìn)制字符串。如果讀入的是‘0’且需要插入詞條,就插在相應(yīng)節(jié)點(diǎn)的左孩子域；若讀入的是字符‘1’且需要插入詞條,就插在相應(yīng)節(jié)點(diǎn)的右孩子域。

該二叉樹字典中存儲(chǔ)空間分析:節(jié)點(diǎn)1代表的是字符串“0”,節(jié)點(diǎn)6代表的是字符串“01”,節(jié)點(diǎn)10代表的是字符串“010”,節(jié)點(diǎn)11代表的是字符串“0101”,顯然,在插入節(jié)點(diǎn)6時(shí),只需在節(jié)點(diǎn)1的右孩子域插入即可;在插入節(jié)點(diǎn)10時(shí),只需在節(jié)點(diǎn)6的左孩子域插入即可;在插入節(jié)點(diǎn)11時(shí),只需在節(jié)點(diǎn)10的右孩子域插入即可?？梢钥闯?詞條“0”“01”“010”“0101”只用了4個(gè)節(jié)點(diǎn)就可以存儲(chǔ),這里的“0”“01”“010”都沒(méi)有重復(fù)存儲(chǔ),當(dāng)二叉樹的深度越深時(shí),節(jié)點(diǎn)代表的字符串越長(zhǎng),此時(shí)可節(jié)省大量的存儲(chǔ)空間,從而有效克服原LZW算法字典存儲(chǔ)的不足。

3 算法測(cè)試

根據(jù)改進(jìn)算法,對(duì)不同大小的文本文件做了仿真測(cè)試,結(jié)果如表1所示。

表1 改進(jìn)算法和原算法壓縮效果比較(單位:KB)

從表1中可以看出,隨著文件大小的增大,壓縮效果越來(lái)越明顯。當(dāng)文件比較小時(shí),該壓縮算法起不到壓縮效果,如文件1、文件2和文件3,這是因?yàn)楫?dāng)文件比較小時(shí),文件中重復(fù)的詞條較少,字典中的詞條相對(duì)較多且詞條不長(zhǎng),同時(shí)轉(zhuǎn)換成二進(jìn)制字符串文件后,文件增大,壓縮率大于1。隨著文件的增大,文件中重復(fù)的詞條較多,字典中詞條比較長(zhǎng),盡管一個(gè)字符被轉(zhuǎn)換成8位二進(jìn)制字符串后,壓縮率仍然小于1。

4 總結(jié)

LZW算法是一種有效的自適應(yīng)數(shù)據(jù)壓縮算法,本文在此基礎(chǔ)上,主要從如下兩方面做了一些改進(jìn):一方面,將待壓縮文件轉(zhuǎn)換成二進(jìn)制文件再進(jìn)行LZW壓縮,這樣實(shí)現(xiàn)該算法簡(jiǎn)單方便;另一方面,采取二叉樹結(jié)構(gòu)來(lái)存儲(chǔ)編碼過(guò)程中字典的詞條,以便減少字典中詞條內(nèi)容的重復(fù)存儲(chǔ),從而減輕算法運(yùn)行中內(nèi)存的壓力。本文改進(jìn)算法對(duì)LZW算法的字典存儲(chǔ)提供了新的研究思路,對(duì)數(shù)據(jù)壓縮算法的研究有一定參考價(jià)值和現(xiàn)實(shí)意義,但還存在一些有待解決的問(wèn)題。