一種前綴映射編碼的改進壓縮算法

　　隨著信息時代的到來，各領(lǐng)域需要分析、傳送和儲存的數(shù)據(jù)也與日俱增。對數(shù)據(jù)進行壓縮后再傳送與儲存，既可以保證傳送的速度，也可以有效節(jié)省儲存空間，這使得無損壓縮算法十分有用。早期的無損壓縮算法主要是基于統(tǒng)計方法心，直到1977年，以色列學(xué)者Ziv J和Lempel A利用數(shù)據(jù)流中重復(fù)數(shù)據(jù)可用短碼編碼的思想，提出了基于字典的壓縮算法，稱為L277壓縮算法。次年，兩人對算法進行改進，用“前綴，字符”在字典中匹配代替了原來在窗口中查找相同字符，新算法減少了“前綴，字符”的比較數(shù)目，稱之為L278算法。之后，對L278算法的改進越來越多，LZW算法就是其中一個變種。當(dāng)數(shù)據(jù)重復(fù)度大時，LZW算法壓縮比優(yōu)于基于統(tǒng)計的壓縮算法。相對基于統(tǒng)計的壓縮算法，基于字典的壓縮算法在運算速度上更具優(yōu)勢，因為前者需要掃描2遍原數(shù)據(jù)。LZW壓縮算法在壓縮及解壓數(shù)據(jù)時，動態(tài)生成一個字典，用于保存已壓縮的歷史數(shù)據(jù)，當(dāng)“前綴，字符”可在字典中查找到時，則繼續(xù)讀人待編碼數(shù)據(jù)，直到“前綴，字符”無法在字典中匹配時，對前綴進行編碼輸出以達到壓縮的目的。LZW壓縮算法在壓縮時間及壓縮性能上的優(yōu)勢使其應(yīng)用范圍十分廣泛。

　　本文分析LZW壓縮算法基本原理，在其基礎(chǔ)上提出改進算法，并通過英文文本數(shù)據(jù)的仿真及殘差數(shù)據(jù)的壓縮應(yīng)用驗證該算法的有效性。
?