LHARC中的動(dòng)態(tài)限長(zhǎng)編碼壓縮算法

1、LHARC中的動(dòng)態(tài)限長(zhǎng)編碼壓縮算法          摘 要 該文對(duì)DOS下常用的數(shù)據(jù)壓縮軟件LHARC的算法進(jìn)行了分析。該算法中采用了一種動(dòng)態(tài)限長(zhǎng)變化的不等長(zhǎng)編碼方法,使最短碼2位,而最長(zhǎng)碼不超過(guò)8位,達(dá)到了最佳壓縮效果。一、前言LHARC是DOS下的數(shù)據(jù)壓縮軟件之一,與同類(lèi)軟件如ARJ、PKZIP、PKARC等相比,具有如下幾個(gè)特點(diǎn)。1.壓縮比高LHARC采用先進(jìn)的字符串自適應(yīng)壓縮與單個(gè)字符的限長(zhǎng)變化編碼壓縮相結(jié)合的方法,對(duì)文件進(jìn)行雙重壓縮,盡可能地減少了冗余,對(duì)各類(lèi)文件的壓縮效果都很好。2

2、.保密性好除應(yīng)具有保存文件、節(jié)約存儲(chǔ)空間的功能外,提高數(shù)據(jù)的保密性也是壓縮軟件的一個(gè)重要功能。LHARC由于采取了與眾不同的動(dòng)態(tài)限長(zhǎng)編碼壓縮技術(shù),使字符與其壓縮代碼之間無(wú)固定的對(duì)應(yīng)關(guān)系,壓縮后的數(shù)據(jù)更具保密性。3.軟件短小精悍LHARC整個(gè)軟件集壓縮、還原于一身,只有30余K,而其它同類(lèi)軟件均有100余K。LHARC的基本壓縮原理是,將待壓縮文件看作是字符流(字節(jié)流),將其中的冗余信息分成兩類(lèi):(1) 同一字符的離散出現(xiàn)如 abcda這里,字符a出現(xiàn)了兩次。2.字符串的重復(fù)出現(xiàn)如 abcdabcd或abcdabcd這里,字符串a(chǎn)bcd出現(xiàn)了兩次。值得說(shuō)明的是,這里串的概念是LZW方法意義下的,

3、即將字符流中每一字符均看作是一個(gè)串的起始字符。壓縮時(shí),首先對(duì)字符流中的字符串進(jìn)行識(shí)別,將其中的重復(fù)串用壓縮格式記載,然后再將處理后的數(shù)據(jù)用不等長(zhǎng)編碼進(jìn)行代碼變換及壓縮。下面僅就其中的動(dòng)態(tài)限長(zhǎng)變化編碼方法進(jìn)行介紹。二、動(dòng)態(tài)限長(zhǎng)編碼方法1.基本原理經(jīng)重復(fù)串壓縮后的數(shù)據(jù)中,重復(fù)串已大大減少,而同一字符的分布式冗余問(wèn)題則比較突出。由于256個(gè)字符的使用概率一般不同,往往相差懸殊,若采用不等長(zhǎng)編碼,將高頻字符用較短代碼表示,低頻字符用較長(zhǎng)碼表示,則提高了整體的壓縮比。Haffman編碼是最佳不等長(zhǎng)編碼,它根據(jù)文件中各字符的統(tǒng)計(jì)概率來(lái)分配代碼長(zhǎng)度。如設(shè)文件中不同字符數(shù)為n,第i個(gè)字符的概率為Pi,代碼長(zhǎng)度

4、為li,則當(dāng)概率滿足P1P2Pn時(shí),Haffman編碼的碼長(zhǎng)滿足l1l2ln,此時(shí),代碼平均長(zhǎng)度的數(shù)學(xué)期望=ni=1Pi·li達(dá)到最小。在一般的數(shù)據(jù)壓縮過(guò)程中,Haffman編碼的算法實(shí)現(xiàn)為:先統(tǒng)計(jì)出待壓文件中各字符的出現(xiàn)概率,據(jù)此動(dòng)態(tài)建立一棵Haffman樹(shù),并以二分樹(shù)的序列形式存入壓縮數(shù)據(jù)文件首部以用于還原過(guò)程。在壓縮過(guò)程中,由Haffman樹(shù)實(shí)現(xiàn)字符的ASCII碼(等長(zhǎng)碼)與其壓縮代碼(Haffman不等長(zhǎng)碼)的轉(zhuǎn)換。這種處理方法需對(duì)待壓縮文件進(jìn)行兩遍掃描,且Haffman樹(shù)須保存于壓縮數(shù)據(jù)文件中而占用額外的存儲(chǔ)空間。在LHARC的算法中,對(duì)Haffman編碼的實(shí)現(xiàn)采用了新的方

5、法。其基本原理是:在壓縮前動(dòng)態(tài)建立一棵初始譯碼樹(shù),在壓縮過(guò)程中不斷調(diào)整譯碼樹(shù)的結(jié)構(gòu),使各字符的壓縮代碼長(zhǎng)度隨字符出現(xiàn)的次數(shù)增加而逐步縮減。最短碼的長(zhǎng)度可達(dá)到2位,而最長(zhǎng)碼不超過(guò)8位(二進(jìn)制),從而獲得很高的壓縮比。該算法的其它優(yōu)點(diǎn)還有:(1)無(wú)須事先統(tǒng)計(jì)各字符的出現(xiàn)概率,一次掃描即可;(2)譯碼樹(shù)須保存在壓縮數(shù)據(jù)文件中,還原時(shí)同樣生成即可;(3)字符與其壓縮代碼之間無(wú)固定對(duì)應(yīng)關(guān)系,使壓縮后的數(shù)據(jù)具有一定的保密性。2.壓縮的實(shí)現(xiàn)及碼樹(shù)的調(diào)整壓縮前動(dòng)態(tài)建立一棵初始譯碼樹(shù),每個(gè)葉結(jié)點(diǎn)對(duì)應(yīng)一個(gè)字符。由于壓縮前可以認(rèn)為各字符的出現(xiàn)概率相等,故初始碼樹(shù)應(yīng)為一有256片葉子的平衡二叉樹(shù),如圖1所示。顯然每個(gè)

6、字符的初始代碼長(zhǎng)度均為8位。09A04900.GIF;圖1 初始譯碼樹(shù)當(dāng)壓縮開(kāi)始,第一個(gè)字符出現(xiàn)時(shí),將其對(duì)應(yīng)第一個(gè)葉結(jié)點(diǎn),沿碼樹(shù)向上的通路至根,所經(jīng)各邊標(biāo)號(hào)(左0右1)組成的0、1序列構(gòu)成該字符的初始代碼。輸出代碼后,調(diào)整碼樹(shù),將該字符對(duì)應(yīng)的葉結(jié)點(diǎn)之值與上一層某一結(jié)點(diǎn)之值互換,當(dāng)該字符再次出現(xiàn)時(shí),其路徑長(zhǎng)度就會(huì)減少一結(jié)點(diǎn)。如字符原對(duì)應(yīng)8位長(zhǎng)代碼,則再次出現(xiàn)后就對(duì)應(yīng)7位代碼了。如該字符繼續(xù)不斷地出現(xiàn),其所對(duì)應(yīng)的葉結(jié)點(diǎn)將逐級(jí)上升到第6層、第5層、甚至第2層,而此字符的碼長(zhǎng)隨之減至6位、5位、直至2位。代碼長(zhǎng)度縮減的規(guī)律是:設(shè)n為字符當(dāng)前所在層數(shù),則當(dāng)字符的重復(fù)出現(xiàn)次數(shù)為28-n時(shí),代碼長(zhǎng)度減少1位

7、。代碼長(zhǎng)度的縮減會(huì)帶來(lái)一個(gè)十分關(guān)鍵的問(wèn)題:當(dāng)碼樹(shù)各結(jié)點(diǎn)值是靜態(tài)的時(shí)候,一字符對(duì)應(yīng)了某一高層結(jié)點(diǎn)后,此結(jié)點(diǎn)的所有下層枝葉將不能再對(duì)應(yīng)其它字符,否則一些代碼將是另一些代碼的前綴,這將使還原過(guò)程無(wú)法進(jìn)行。因此代碼縮減將使編碼路徑數(shù)減少,一些后繼字符將無(wú)法由碼樹(shù)編碼。為此,該算法采取的策略是:按字符出現(xiàn)的次序?qū)⑺鼈兗信帕性诖a樹(shù)的一側(cè)葉子上,通過(guò)移動(dòng)和交換分枝點(diǎn)之值的方法,使各層結(jié)點(diǎn)之值重新組合,從而使被占用結(jié)點(diǎn)的下屬枝葉可“稼接”到未用的結(jié)點(diǎn)上。因此,當(dāng)高層結(jié)點(diǎn)被占用后,其下屬結(jié)點(diǎn)仍可使用,不會(huì)減少編碼路徑數(shù)。具體來(lái)說(shuō),當(dāng)一后繼字符出現(xiàn)并且其對(duì)應(yīng)葉子的父結(jié)點(diǎn)已被占用,它將改變?cè)械木幋a路徑,通過(guò)搜索找出一個(gè)未用的上層結(jié)點(diǎn)并由此得到其代碼。同樣,當(dāng)一字符須上升一層時(shí),并不是升到其父結(jié)點(diǎn)中,而是升到上層中一個(gè)未用過(guò)的結(jié)點(diǎn)之中。當(dāng)該字符再度出現(xiàn)時(shí),它將沿新路徑得到其代碼,此代碼的長(zhǎng)度不僅為原代碼長(zhǎng)度減1,而且此代碼的各個(gè)位也與原代碼不同。下面以一具體例子加以說(shuō)明。設(shè)字符串為ababcabdabc各字符的編碼路徑如圖2所示。其中的Xi表示X的第i次出現(xiàn)。09A04901.GIF;圖2 字符編碼路徑示意圖由此可看出,由該算法給出的編碼方法是逐步達(dá)到最佳碼長(zhǎng)的。一字符的壓縮代碼不僅與字符出現(xiàn)的次數(shù)有關(guān)(長(zhǎng)度不同),而且與字符在文件中的位置有關(guān)(編碼路徑不同)。LHARC建立了