LHARC中的動態(tài)限長編碼壓縮算法

一些代碼將是另一些代碼的前綴,這將使還原過程無法進行。因此代碼縮減將使編碼路徑數(shù)減少,一些后繼字符將無法由碼樹編碼。為此,該算法采取的策略是:按字符出現(xiàn)的次序將它們集中排列在碼樹的一側葉子上,通過移動和交換分枝點之值的方法,使各層結點之值重新組合,從而使被占用結點的下屬枝葉可“稼接”到未用的結點上。因此,當高層結點被占用后,其下屬結點仍可使用,不會減少編碼路徑數(shù)。具體來說,當一后繼字符出現(xiàn)并且其對應葉子的父結點已被占用,它將改變原有的編碼路徑,通過搜索找出一個未用的上層結點并由此得到其代碼。
同樣,當一字符須上升一層時,并不是升到其父結點中,而是升到上層中一個未用過的結點之中。當該字符再度出現(xiàn)時,它將沿新路徑得到其代碼,此代碼的長度不僅為原代碼長度減1,而且此代碼的各個位也與原代碼不同。下面以一具體例子加以說明。
設字符串為ababcabdabc……各字符的編碼路徑如圖2所示。其中的Xi表示X的第i次出現(xiàn)。
@@09A04901.GIF;圖2 字符編碼路徑示意圖@@
由此可看出,由該算法給出的編碼方法是逐步達到最佳碼長的。一字符的壓縮代碼不僅與字符出現(xiàn)的次數(shù)有關(長度不同),而且與字符在文件中的位置有關(編碼路徑不同)。
LHARC建立了兩個表專門用來記錄碼樹的占用情況及各字符出現(xiàn)的次數(shù),以便確定對碼樹的各種調整。當壓縮后的數(shù)據(jù)達到32K時,將對表及碼樹進行“重組”,刪除表中部分累積的數(shù)據(jù)后再繼續(xù)進行壓縮,以后將每隔16K“重組”一次。