可變長度編碼的LZW壓縮算法(Variable-Length_Code LZW Compression)，是從LZW(Lempel Ziv Compression)壓縮算法演變過來的，通過壓縮原始數(shù)據(jù)的重復(fù)部分來達到減少文件大小的目的。

標(biāo)準的LZW壓縮原理：

先來解釋一下幾個基本概念：
LZW壓縮有三個重要的對象：數(shù)據(jù)流(CharStream)、編碼流(CodeStream)和編譯表(String Table)。在編碼時，數(shù)據(jù)流是輸入對象（圖象的光柵數(shù)據(jù)序列），編碼流就是輸出對象（經(jīng)過壓縮運算的編碼數(shù)據(jù)）；在解碼時，編碼流則是輸入對象，數(shù)據(jù)流是輸出對象；而編譯表是在編碼和解碼時都須要用借助的對象。

字符(Character)：最基礎(chǔ)的數(shù)據(jù)元素，在文本文件中就是一個字節(jié)，在光柵數(shù)據(jù)中就是一個像素的顏色在指定的顏色列表中的索引值；
字符串(String)：由幾個連續(xù)的字符組成；
前綴(Prefix)：也是一個字符串，不過通常用在另一個字符的前面，而且它的長度可以為0；
根(Root)：單個長度的字符串；
編碼(Code)：一個數(shù)字，按照固定長度（編碼長度）從編碼流中取出，編譯表的映射值；
圖案：一個字符串，按不定長度從數(shù)據(jù)流中讀出,映射到編譯表條目.

LZW壓縮的原理：提取原始圖象數(shù)據(jù)中的不同圖案，基于這些圖案創(chuàng)建一個編譯表，然后用編譯表中的圖案索引來替代原始光柵數(shù)據(jù)中的相應(yīng)圖案，減少原始數(shù)據(jù)大小?？雌饋砗驼{(diào)色板圖象的實現(xiàn)原理差不多，但是應(yīng)該注意到的是，我們這里的編譯表不是事先創(chuàng)建好的，而是根據(jù)原始圖象數(shù)據(jù)動態(tài)創(chuàng)建的，解碼時還要從已編碼的數(shù)據(jù)中還原出原來的編譯表（GIF文件中是不攜帶編譯表信息的），為了更好理解編解碼原理，我們來看看具體的處理過程：

編碼器(Compressor)

編碼數(shù)據(jù)，第一步，初始化一個編譯表，假設(shè)這個編譯表的大小是12位的，也就是最多有4096個單位，另外假設(shè)我們有32個不同的字符（也可以認為圖象的每個像素最多有32種顏色），表示為a，b，c，d，e...，初始化編譯表：第0項為a，第1項為b，第2項為c...一直到第31項，我們把這32項就稱為根。

開始編譯，先定義一個前綴對象Current Prefix，記為[.c.]，現(xiàn)在它是空的，然后定義一個當(dāng)前字符串Current String，標(biāo)記為[.c.]k，[.c.]就為Current Prefix，k就為當(dāng)前讀取字符?，F(xiàn)在來讀取數(shù)據(jù)流的第一個字符，假如為p，那么Current String就等于[.c.]p（由于[.c.]為空，實際上值就等于p），現(xiàn)在在編譯表中查找有沒有Current String的值，由于p就是一個根字符，我們已經(jīng)初始了32個根索引，當(dāng)然可以找到，把p設(shè)為Current Prefix的值，不做任何事繼續(xù)讀取下一個字符，假設(shè)為q，Current String就等于[.c.]q（也就是pq），看看在編譯表中有沒有該值，當(dāng)然。沒有，這時我們要做下面的事情：將Current String的值（也就是pq）添加到編譯表的第32項，把Current Prefix的值（也就是p）在編譯表中的索引輸出到編碼流，修改Current Prefix為當(dāng)前讀取的字符（也就是q）。繼續(xù)往下讀，如果在編譯表中可以查找到Current String的值([.c.]k)，則把Current String的值([.c.]k)賦予Current Prefix；如果查找不到，則添加Current String的值([.c.]k)到編譯表，把Current Prefix的值([.c.])在編譯表中所對應(yīng)的索引輸出到編碼流，同時修改Current Prefix為k ，這樣一直循環(huán)下去直到數(shù)據(jù)流結(jié)束。偽代碼看起來就像下面這樣：

來看一個具體的例子,我們有一個字母表a，b，c，d.有一個輸入的字符流abacaba?，F(xiàn)在來初始化編譯表：#0=a,#1=b,#2=c,#3=d.現(xiàn)在開始讀取第一個字符a，[.c.]a=a，可以在在編譯表中找到，修改[.c.]=a;不做任何事繼續(xù)讀取第二個字符b，[.c.]b=ab，在編譯表中不能找，那么添加[.c.]b到編譯表：#4=ab，同時輸出[.c.]（也就是a）的索引#0到編碼流，修改[.c.]=b；讀下一個字符a，[.c.]a=ba，在編譯表中不能找到：添加編譯表#5=ba，輸出[.c.]的索引#1到編碼流，修改[.c.]=a；讀下一個字符c，[.c.]c=ac，在編譯表中不能找到：添加編譯表#6=ac，輸出[.c.]的索引#0到編碼流，修改[.c.]=c；讀下一個字符a，[.c.]c=ca，在編譯表中不能找到：添加編譯表#7=ca，輸出[.c.]的索引#2到編碼流，修改[.c.]=a；讀下一個字符b，[.c.]b=ab，編譯表的#4=ab，修改[.c.]=ab；讀取最后一個字符a，[.c.]a=aba，在編譯表中不能找到：添加編譯表#8=aba，輸出[.c.]的索引#4到編碼流，修改[.c.]=a；好了，現(xiàn)在沒有數(shù)據(jù)了，輸出[.c.]的值a的索引#0到編碼流，這樣最后的輸出結(jié)果就是：#0#1#0#2#4#0.

解碼器(Decompressor)

好了，現(xiàn)在來看看解碼數(shù)據(jù)。數(shù)據(jù)的解碼，其實就是數(shù)據(jù)編碼的逆向過程，要從已經(jīng)編譯的數(shù)據(jù)（編碼流）中找出編譯表，然后對照編譯表還原圖象的光柵數(shù)據(jù)。

首先，還是要初始化編譯表。GIF文件的圖象數(shù)據(jù)的第一個字節(jié)存儲的就是LZW編碼的編碼大?。ㄒ话愕扔趫D象的位數(shù)），根據(jù)編碼大小，初始化編譯表的根條目（從0到2的編碼大小次方），然后定義一個當(dāng)前編碼Current Code，記作[code]，定義一個Old Code，記作[old]。讀取第一個編碼到[code]，這是一個根編碼，在編譯表中可以找到，把該編碼所對應(yīng)的字符輸出到數(shù)據(jù)流，[old]=[code]；讀取下一個編碼到[code]，這就有兩種情況：在編譯表中有或沒有該編碼，我們先來看第一種情況：先輸出當(dāng)前編碼[code]所對應(yīng)的字符串到數(shù)據(jù)流，然后把[old]所對應(yīng)的字符（串）當(dāng)成前綴prefix [...]，當(dāng)前編碼[code]所對應(yīng)的字符串的第一個字符當(dāng)成k，組合起來當(dāng)前字符串Current String就為[...]k，把[...]k添加到編譯表，修改[old]=[code]，讀下一個編碼；我們來看看在編譯表中找不到該編碼的情況，回想一下編碼情況：如果數(shù)據(jù)流中有一個p[...]p[...]pq這樣的字符串，p[...]在編譯表中而p[...]p不在，編譯器將輸出p[...]的索引而添加p[...]p到編譯表，下一個字符串p[...]p就可以在編譯表中找到了，而p[...]pq不在編譯表中，同樣將輸出p[...]p的索引值而添加p[...]pq到編譯表，這樣看來，解碼器總比編碼器『慢一步』，當(dāng)我們遇到p[...]p所對應(yīng)的索引時，我們不知到該索引對應(yīng)的字符串（在解碼器的編譯表中還沒有該索引，事實上，這個索引將在下一步添加），這時需要用猜測法：現(xiàn)在假設(shè)上面的p[...]所對應(yīng)的索引值是#58，那么上面的字符串經(jīng)過編譯之后是#58#59，我們在解碼器中讀到#59時，編譯表的最大索引只有#58，#59所對應(yīng)的字符串就等于#58所對應(yīng)的字符串(也就是p[...])加上這個字符串的第一個字符(也就是p)，也就是p[...]p。事實上，這種猜測法是很準確（有點不好理解，仔細想一想吧）。上面的解碼過程用偽代碼表示就像下面這樣：

GIF數(shù)據(jù)壓縮

下面是GIF文件的圖象數(shù)據(jù)結(jié)構(gòu)：

把光柵數(shù)據(jù)序列（數(shù)據(jù)流）壓縮成GIF文件的圖象數(shù)據(jù)（字符流）可以按下面的步驟進行：
1.定義編碼長度
GIF圖象數(shù)據(jù)的第一個字節(jié)就是編碼長度(Code Size)，這個值是指要表現(xiàn)一個像素所需要的最小位數(shù)，通常就等于圖象的色深；
2.壓縮數(shù)據(jù)
通過LZW壓縮算法將圖象的光柵數(shù)據(jù)流壓縮成GIF的編碼數(shù)據(jù)流。這里使用的LZW壓縮算法是從標(biāo)準的LZW壓縮算法演變過來的，它們之間有如下的差別：
[1]GIF文件定義了一個編碼大小(Clear Code)，這個值等于2的『編碼長度』次方，在從新開始一個編譯表（編譯表溢出）時均須輸出該值，解碼器遇到該值時意味著要從新初始化一個編譯表；
[2]在一個圖象的編碼數(shù)據(jù)結(jié)束之前（也就是在塊終結(jié)器的前面），需要輸出一個Clear Code+1的值，解碼器在遇到該值時就意味著GIF文件的一個圖象數(shù)據(jù)流的結(jié)束；
[3]第一個可用到的編譯表索引值是Clear Code+2（從0到Clear Code-1是根索引，再上去兩個不可使用，新的索引從Clare Code+2開始添加）；
[4]GIF輸出的編碼流是不定長的，每個編碼的大小從Code Size + 1位到12位，編碼的最大值就是4095（編譯表需要定義的索引數(shù)就是4096），當(dāng)編碼所須的位數(shù)超過當(dāng)前的位數(shù)時就把當(dāng)前位數(shù)加1，這就需要在編碼或解碼時注意到編碼長度的改變。
3.編譯成字節(jié)序列
因為GIF輸出的編碼流是不定長的，這就需要把它們編譯成固定的8-bit長度的字符流，編譯順序是從右往左。下面是一個具體例子：編譯5位長度編碼到8位字符

打包

前面講過，一個GIF的數(shù)據(jù)塊的大小從0到255個字節(jié)，第一個字節(jié)是這個數(shù)據(jù)塊的大?。ㄗ止?jié)數(shù)），這就需要將編譯編后的碼數(shù)據(jù)打包成一個或幾個大小不大于255個字節(jié)的數(shù)據(jù)包。然后寫入圖象數(shù)據(jù)塊中。