- 相關(guān)推薦
LHARC中的動態(tài)限長編碼壓縮算法
摘 要 該文對DOS下常用的數(shù)據(jù)壓縮軟件LHARC的算法進行了分析。該算法中采用了一種動態(tài)限長變化的不等長編碼方法,使最短碼2位,而最長碼不超過8位,達到了最佳壓縮效果。
一、前言
LHARC是DOS下的數(shù)據(jù)壓縮軟件之一,與同類軟件如ARJ、PKZIP、PKARC等相比,具有如下幾個特點。
1.壓縮比高
LHARC采用先進的字符串自適應(yīng)壓縮與單個字符的限長變化編碼壓縮相結(jié)合的方法,對文件進行雙重壓縮,盡可能地減少了冗余,對各類文件的壓縮效果都很好。
2.保密性好
除應(yīng)具有保存文件、節(jié)約存儲空間的功能外,提高數(shù)據(jù)的保密性也是壓縮軟件的一個重要功能。LHARC由于采取了與眾不同的動態(tài)限長編碼壓縮技術(shù),使字符與其壓縮代碼之間無固定的對應(yīng)關(guān)系,壓縮后的數(shù)據(jù)更具保密性。
3.軟件短小精悍
LHARC整個軟件集壓縮、還原于一身,只有30余K,而其它同類軟件均有100余K。
LHARC的基本壓縮原理是,將待壓縮文件看作是字符流(字節(jié)流),將其中的冗余信息分成兩類:
(1) 同一字符的離散出現(xiàn)
如 abcda……
這里,字符a出現(xiàn)了兩次。
2.字符串的重復(fù)出現(xiàn)
如 abcdabcd……或abcd…abcd……
這里,字符串a(chǎn)bcd出現(xiàn)了兩次。值得說明的是,這里串的概念是LZW方法意義下的,即將字符流中每一字符均看作是一個串的起始字符。
壓縮時,首先對字符流中的字符串進行識別,將其中的重復(fù)串用壓縮格式記載,然后再將處理后的數(shù)據(jù)用不等長編碼進行代碼變換及壓縮。下面僅就其中的動態(tài)限長變化編碼方法進行介紹。
二、動態(tài)限長編碼方法
1.基本原理
經(jīng)重復(fù)串壓縮后的數(shù)據(jù)中,重復(fù)串已大大減少,而同一字符的分布式冗余問題則比較突出。由于256個字符的使用概率一般不同,往往相差懸殊,若采用不等長編碼,將高頻字符用較短代碼表示,低頻字符用較長碼表示,則提高了整體的壓縮比。
Haffman編碼是最佳不等長編碼,它根據(jù)文件中各字符的統(tǒng)計概率來分配代碼長度。如設(shè)文件中不同字符數(shù)為n,第i個字符的概率為Pi,代碼長度為li,則當概率滿足P1≥P2≥…≥Pn時,Haffman編碼的碼長滿足l1≤l2≤…≤ln,此時,代碼平均長度的數(shù)學期望=∑ni=1Pi·li達到最小。
在一般的數(shù)據(jù)壓縮過程中,Haffman編碼的算法實現(xiàn)為:先統(tǒng)計出待壓文件中各字符的出現(xiàn)概率,據(jù)此動態(tài)建立一棵Haffman樹,并以二分樹的序列形式存入壓縮數(shù)據(jù)文件首部以用于還原過程。在壓縮過程中,由Haffman樹實現(xiàn)字符的ASCII碼(等長碼)與其壓縮代碼(Haffman不等長碼)的轉(zhuǎn)換。這種處理方法需對待壓縮文件進行兩遍掃描,且Haffman樹須保存于壓縮數(shù)據(jù)文件中而占用額外的存儲空間。
在LHARC的算法中,對Haffman編碼的實現(xiàn)采用了新的方法。其基本原理是:在壓縮前動態(tài)建立一棵初始譯碼樹,在壓縮過程中不斷調(diào)整譯碼樹的結(jié)構(gòu),使各字符的壓縮代碼長度隨字符出現(xiàn)的次數(shù)增加而逐步縮減。最短碼的長度可達到2位,而最長碼不超過8位(二進制),從而獲得很高的壓縮比。該算法的其它優(yōu)點還有:(1)無須事先統(tǒng)計各字符的出現(xiàn)概率,一次掃描即可;(2)譯碼樹須保存在壓縮數(shù)據(jù)文件中,還原時同樣生成即可;(3)字符與其壓縮代碼之間無固定對應(yīng)關(guān)系,使壓縮后的數(shù)據(jù)具有一定的保密性。
2.壓縮的實現(xiàn)及碼樹的調(diào)整
壓縮前動態(tài)建立一棵初始譯碼樹,每個葉結(jié)點對應(yīng)一個字符。由于壓縮前可以認為各字符的出現(xiàn)概率相等,故初始碼樹應(yīng)為一有256片葉子的平衡二叉樹,如圖1所示。顯然每個字符的初始代碼長度均為8位。
@@09A04900.GIF;圖1 初始譯碼樹@@
當壓縮開始,第一個字符出現(xiàn)時,將其對應(yīng)第一個葉結(jié)點,沿碼樹向上的通路至根,所經(jīng)各邊標號(左0右1)組成的0、1序列構(gòu)成該字符的初始代碼。輸出代碼后,調(diào)整碼樹,將該字符對應(yīng)的葉結(jié)點之值與上一層某一結(jié)點之值互換,當該字符再次出現(xiàn)時,其路徑長度就會減少一結(jié)點。如字符原對應(yīng)8位長代碼,則再次出現(xiàn)后就對應(yīng)7位代碼了。如該字符繼續(xù)不斷地出現(xiàn),其所對應(yīng)的葉結(jié)點將逐級上升
[1] [2]
【LHARC中的動態(tài)限長編碼壓縮算法】相關(guān)文章：
動態(tài)車間調(diào)度算法04-27
均值漂移算法在LAMOST動態(tài)選星中的應(yīng)用04-29
基于模式特征的圖像壓縮算法05-01
Euler方程無網(wǎng)格算法在可壓縮流場中的應(yīng)用05-01
SAR原始數(shù)據(jù)壓縮算法04-27
動態(tài)規(guī)劃算法在最優(yōu)航路規(guī)劃中的應(yīng)用04-27
非線性動態(tài)濾波的迭代算法04-29