- 相關推薦
LHARC中的動態限長編碼壓縮算法
摘 要 該文對DOS下常用的數據壓縮軟件LHARC的算法進行了分析。該算法中采用了一種動態限長變化的不等長編碼方法,使最短碼2位,而最長碼不超過8位,達到了最佳壓縮效果。一、前言
LHARC是DOS下的數據壓縮軟件之一,與同類軟件如ARJ、PKZIP、PKARC等相比,具有如下幾個特點。
1.壓縮比高
LHARC采用先進的字符串自適應壓縮與單個字符的限長變化編碼壓縮相結合的方法,對文件進行雙重壓縮,盡可能地減少了冗余,對各類文件的壓縮效果都很好。
2.保密性好
除應具有保存文件、節約存儲空間的功能外,提高數據的保密性也是壓縮軟件的一個重要功能。LHARC由于采取了與眾不同的動態限長編碼壓縮技術,使字符與其壓縮代碼之間無固定的對應關系,壓縮后的數據更具保密性。
3.軟件短小精悍
LHARC整個軟件集壓縮、還原于一身,只有30余K,而其它同類軟件均有100余K。
LHARC的基本壓縮原理是,將待壓縮文件看作是字符流(字節流),將其中的冗余信息分成兩類:
(1) 同一字符的離散出現
如 abcda……
這里,字符a出現了兩次。
2.字符串的重復出現
如 abcdabcd……或abcd…abcd……
這里,字符串abcd出現了兩次。值得說明的是,這里串的概念是LZW方法意義下的,即將字符流中每一字符均看作是一個串的起始字符。
壓縮時,首先對字符流中的字符串進行識別,將其中的重復串用壓縮格式記載,然后再將處理后的數據用不等長編碼進行代碼變換及壓縮。下面僅就其中的動態限長變化編碼方法進行介紹。
二、動態限長編碼方法
1.基本原理
經重復串壓縮后的數據中,重復串已大大減少,而同一字符的分布式冗余問題則比較突出。由于256個字符的使用概率一般不同,往往相差懸殊,若采用不等長編碼,將高頻字符用較短代碼表示,低頻字符用較長碼表示,則提高了整體的壓縮比。
Haffman編碼是最佳不等長編碼,它根據文件中各字符的統計概率來分配代碼長度。如設文件中不同字符數為n,第i個字符的概率為Pi,代碼長度為li,則當概率滿足P1≥P2≥…≥Pn時,Haffman編碼的碼長滿足l1≤l2≤…≤ln,此時,代碼平均長度的數學期望=∑ni=1Pi·li達到最小。
在一般的數據壓縮過程中,Haffman編碼的算法實現為:先統計出待壓文件中各字符的出現概率,據此動態建立一棵Haffman樹,并以二分樹的序列形式存入壓縮數據文件首部以用于還原過程。在壓縮過程中,由Haffman樹實現字符的ASCII碼(等長碼)與其壓縮代碼(Haffman不等長碼)的轉換。這種處理方法需對待壓縮文件進行兩遍掃描,且Haffman樹須保存于壓縮數據文件中而占用額外的存儲空間。
在LHARC的算法中,對Haffman編碼的實現采用了新的方法。其基本原理是:在壓縮前動態建立一棵初始譯碼樹,在壓縮過程中不斷調整譯碼樹的結構,使各字符的壓縮代碼長度隨字符出現的次數增加而逐步縮減。最短碼的長度可達到2位,而最長碼不超過8位(二進制),從而獲得很高的壓縮比。該算法的其它優點還有:(1)無須事先統計各字符的出現概率,一次掃描即可;(2)譯碼樹須保存在壓縮數據文件中,還原時同樣生成即可;(3)字符與其壓縮代碼之間無固定對應關系,使壓縮后的數據具有一定的保密性。
2.壓縮的實現及碼樹的調整
壓縮前動態建立一棵初始譯碼樹,每個葉結點對應一個字符。由于壓縮前可以認為各字符的出現概率相等,故初始碼樹應為一有256片葉子的平衡二叉樹,如圖1所示。顯然每個字符的初始代碼長度均為8位。
@@09A04900.GIF;圖1 初始譯碼樹@@
當壓縮開始,第一個字符出現時,將其對應第一個葉結點,沿碼樹向上的通路至根,所經各邊標號(左0右1)組成的0、1序列構成該字符的初始代碼。輸出代碼后,調整碼樹,將該字符對應的葉結點之值與上一層某一結點之值互換,當該字符再次出現時,其路徑長度就會減少一結點。如字符原對應8位長代碼,則再次出現后就對應7位代碼了。如該字符繼續不斷地出現,其所對應的葉結點將逐級上升到第6層、第5層、甚至第2層,而此字符的碼長隨之減至6位、5位、直至2位。
代碼長度縮減的規律是:設n為字符當前所在層數,則當字符的重復出現次數為28-n時,代碼長度減少1位。
代碼長度的縮減會帶來一個十分關鍵的問題:當碼樹各結點值是靜態的時候,一字符對應了某一高層結點后,此結點的所有下層枝葉將不能再對應其它字符,否則一些代碼將是另一些代碼的前綴,這將使還原過程無法進行。因此代碼縮減將使編碼路徑數減少,一些后繼字符將無法由碼樹編碼。為此,該算法采取的策略是:按字符出現的次序將它們集中排列在碼樹的一側葉子上,通過移動和交換分枝點之值的方法,使各層結點之值重新組合,從而使被占用結點的下屬枝葉可“稼接”到未用的結點上。因此,當高層結點被占用后,其下屬結點仍可使用,不會減少編碼路徑數。具體來說,當一后繼字符出現并且其對應葉子的父結點已被占用,它將改變原有的編碼路徑,通過搜索找出一個未用的上層結點并由此得到其代碼。
同樣,當一字符須上升一層時,并不是升到其父結點中,而是升到上層中一個未用過的結點之中。當該字符再度出現時,它將沿新路徑得到其代碼,此代碼的長度不僅為原代碼長度減1,而且此代碼的各個位也與原代碼不同。下面以一具體例子加以說明。
設字符串為ababcabdabc……各字符的編碼路徑如圖2所示。其中的Xi表示X的第i次出現。
@@09A04901.GIF;圖2 字符編碼路徑示意圖@@
由此可看出,由該算法給出的編碼方法是逐步達到最佳碼長的。一字符的壓縮代碼不僅與字符出現的次數有關(長度不同),而且與字符在文件中的位置有關(編碼路徑不同)。
LHARC建立了兩個表專門用來記錄碼樹的占用情況及各字符出現的次數,以便確定對碼樹的各種調整。當壓縮后的數據達到32K時,將對表及碼樹進行“重組”,刪除表中部分累積的數據后再繼續進行壓縮,以后將每隔16K“重組”一次。
【LHARC中的動態限長編碼壓縮算法】相關文章：
漢字的動態編碼與顯示方案08-06
動態哈夫曼編碼的改進08-06
音頻壓縮的成功者——感知編碼08-06
噪聲圖像的分形壓縮編碼研究08-06
針對硬件實現的H.264視頻編碼算法改進08-06
GPS定位數據壓縮算法的設計與實現08-06
嵌入式零樹小波編碼及其改進算法的研究08-06