LZW(Lempel Ziv Welch)壓縮編碼是壹種先進的數據壓縮技術,屬於無損壓縮編碼,該編碼主要用於圖像數據的壓縮。對於簡單圖像和平滑且噪聲小的信號源具有較高的壓縮比,並且有較高的壓縮和解壓縮速度。
1977年,兩位以色列教授Lempel和Ziv提出了查找冗余字符和用較短的符號標記替代冗余字符的概念。1985年,由Welch加以充實而形成LZW,簡稱“LZW”技術。
1.LZW壓縮基本原理
LZW壓縮技術把數據流中復雜的數據用簡單的代碼來表示,並把代碼和數據的對應關系建立壹個轉換表,又叫“字符串表”。
轉換表是在壓縮或解壓縮過程中動態生成的表,該表只在進行壓縮或解壓縮過程中需要,壹旦壓縮和解壓縮結束,該表將不再起任何作用。
2.LZW算法
LZW算法基於轉換串表(字典)T,將輸入字符串映射成定長(通常為12位)的碼字。在12位4096種可能的代碼中,256個代表單字符,剩下3840給出現的字符串。
LZW字典中的字符串具有前綴性,即 。
LZW算法流程:
1)初始化:將所有的單字符串放入串表
2)讀第壹個輸入字符給前綴串ω
3)Step: 讀下壹個輸入字符K;
if 沒有這樣的K(輸入已窮盡):
碼字(ω) 輸出;結束。
If ωK 已存在於串表中:
ωK:=ω;repeat Step;
else ωK不在於串表中:
碼字(ω) 輸出;
ωK加進串表;
K:=ω;repeat Step.
例子:ababcbababaaaaaaa
LZW編碼:a,b,c,ab,ba,abc,cb,bab,baba,aa,aaa,aaaa
3.LZW壓縮的特點
LZW碼能有效利用字符出現頻率冗余度進行壓縮,且字典是自適應生成的,但通常不能有效地利用位置冗余度。
具體特點如下:
l)LZW壓縮技術對於可預測性不大的數據具有較好的處理效果,常用於GIF格式的圖像壓縮,其平均壓縮比在2)1以上,最高壓縮比可達到3:1。
2)對於數據流中連續重復出現的字節和字串,LZW壓縮技術具有很高的壓縮比。
3)除了用於圖像數據處理以外,LZW壓縮技術還被用於文本程序等數據壓縮領域。
4)LZW壓縮技術有很多變體,例如常見的ARC、RKARC、PKZIP高效壓縮程序。
5)對於任意寬度和像素位長度的圖像,都具有穩定的壓縮過程。壓縮和解壓縮速度較快。
6)對機器硬件條件要求不高,在 Intel 80386的計算機上即可進行壓縮和解壓縮。