這份資料的格式很不錯(cuò)，收了！謝謝整理者。

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

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

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

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

編碼器(Compressor)

　　編碼數(shù)據(jù)，第一步，初始化一個(gè)編譯表，假設(shè)這個(gè)編譯表的大小是12位的，也就是最多有4096個(gè)單位，另外假設(shè)我們有32個(gè)不同的字符（也可以認(rèn)為圖象的每個(gè)像素最多有32種顏色），表示為a，b，c，d，e...，初始化編譯表：第0項(xiàng)為a，第1項(xiàng)為b，第2項(xiàng)為c...一直到第31項(xiàng)，我們把這32項(xiàng)就稱為根。
　　開始編譯，先定義一個(gè)前綴對(duì)象Current Prefix，記為[.c.]，現(xiàn)在它是空的，然后定義一個(gè)當(dāng)前字符串Current String，標(biāo)記為[.c.]k，[.c.]就為Current Prefix，k就為當(dāng)前讀取字符?，F(xiàn)在來讀取數(shù)據(jù)流的第一個(gè)字符，假如為p，那么Current String就等于[.c.]p（由于[.c.]為空，實(shí)際上值就等于p），現(xiàn)在在編譯表中查找有沒有Current String的值，由于p就是一個(gè)根字符，我們已經(jīng)初始了32個(gè)根索引，當(dāng)然可以找到，把p設(shè)為Current Prefix的值，不做任何事繼續(xù)讀取下一個(gè)字符，假設(shè)為q，Current String就等于[.c.]q（也就是pq），看看在編譯表中有沒有該值，當(dāng)然。沒有，這時(shí)我們要做下面的事情：將Current String的值（也就是pq）添加到編譯表的第32項(xiàng)，把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.])在編譯表中所對(duì)應(yīng)的索引輸出到編碼流，同時(shí)修改Current Prefix為k ，這樣一直循環(huán)下去直到數(shù)據(jù)流結(jié)束。偽代碼看起來就像下面這樣：

Initialize String Table;
[.c.] = Empty;
[.c.]k = First Character in CharStream;
while ([.c.]k != EOF )
{
　　if ( [.c.]k is in the StringTable)
　　{
　　　　[.c.] = [.c.]k;
　　}
　　else
　　{
　　　　add [.c.]k to the StringTable;
　　　　Output the Index of [.c.] in the StringTable to the CodeStream;
　　　　[.c.] = k;
　　}
　　[.c.]k = Next Character in CharStream;
}
Output the Index of [.c.] in the StringTable to the CodeStream;

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

來看一個(gè)具體的例子,我們有一個(gè)字母表a，b，c，d.有一個(gè)輸入的字符流abacaba?，F(xiàn)在來初始化編譯表：#0=a,#1=b,#2=c,#3=d.現(xiàn)在開始讀取第一個(gè)字符a，[.c.]a=a，可以在在編譯表中找到，修改[.c.]=a;不做任何事繼續(xù)讀取第二個(gè)字符b，[.c.]b=ab，在編譯表中不能找，那么添加[.c.]b到編譯表：#4=ab，同時(shí)輸出[.c.]（也就是a）的索引#0到編碼流，修改[.c.]=b；讀下一個(gè)字符a，[.c.]a=ba，在編譯表中不能找到：添加編譯表#5=ba，輸出[.c.]的索引#1到編碼流，修改[.c.]=a；讀下一個(gè)字符c，[.c.]c=ac，在編譯表中不能找到：添加編譯表#6=ac，輸出[.c.]的索引#0到編碼流，修改[.c.]=c；讀下一個(gè)字符a，[.c.]c=ca，在編譯表中不能找到：添加編譯表#7=ca，輸出[.c.]的索引#2到編碼流，修改[.c.]=a；讀下一個(gè)字符b，[.c.]b=ab，編譯表的#4=ab，修改[.c.]=ab；讀取最后一個(gè)字符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í)就是數(shù)據(jù)編碼的逆向過程，要從已經(jīng)編譯的數(shù)據(jù)（編碼流）中找出編譯表，然后對(duì)照編譯表還原圖象的光柵數(shù)據(jù)。
　　首先，還是要初始化編譯表。GIF文件的圖象數(shù)據(jù)的第一個(gè)字節(jié)存儲(chǔ)的就是LZW編碼的編碼大?。ㄒ话愕扔趫D象的位數(shù)），根據(jù)編碼大小，初始化編譯表的根條目（從0到2的編碼大小次方），然后定義一個(gè)當(dāng)前編碼Current Code，記作[code]，定義一個(gè)Old Code，記作[old]。讀取第一個(gè)編碼到[code]，這是一個(gè)根編碼，在編譯表中可以找到，把該編碼所對(duì)應(yīng)的字符輸出到數(shù)據(jù)流，[old]=[code]；讀取下一個(gè)編碼到[code]，這就有兩種情況：在編譯表中有或沒有該編碼，我們先來看第一種情況：先輸出當(dāng)前編碼[code]所對(duì)應(yīng)的字符串到數(shù)據(jù)流，然后把[old]所對(duì)應(yīng)的字符（串）當(dāng)成前綴prefix [...]，當(dāng)前編碼[code]所對(duì)應(yīng)的字符串的第一個(gè)字符當(dāng)成k，組合起來當(dāng)前字符串Current String就為[...]k，把[...]k添加到編譯表，修改[old]=[code]，讀下一個(gè)編碼；我們來看看在編譯表中找不到該編碼的情況，回想一下編碼情況：如果數(shù)據(jù)流中有一個(gè)p[...]p[...]pq這樣的字符串，p[...]在編譯表中而p[...]p不在，編譯器將輸出p[...]的索引而添加p[...]p到編譯表，下一個(gè)字符串p[...]p就可以在編譯表中找到了，而p[...]pq不在編譯表中，同樣將輸出p[...]p的索引值而添加p[...]pq到編譯表，這樣看來，解碼器總比編碼器『慢一步』，當(dāng)我們遇到p[...]p所對(duì)應(yīng)的索引時(shí)，我們不知到該索引對(duì)應(yīng)的字符串（在解碼器的編譯表中還沒有該索引，事實(shí)上，這個(gè)索引將在下一步添加），這時(shí)需要用猜測(cè)法：現(xiàn)在假設(shè)上面的p[...]所對(duì)應(yīng)的索引值是#58，那么上面的字符串經(jīng)過編譯之后是#58#59，我們?cè)诮獯a器中讀到#59時(shí)，編譯表的最大索引只有#58，#59所對(duì)應(yīng)的字符串就等于#58所對(duì)應(yīng)的字符串(也就是p[...])加上這個(gè)字符串的第一個(gè)字符(也就是p)，也就是p[...]p。事實(shí)上，這種猜測(cè)法是很準(zhǔn)確（有點(diǎn)不好理解，仔細(xì)想一想吧）。上面的解碼過程用偽代碼表示就像下面這樣：

Initialize String Table;
[code] = First Code in the CodeStream;
Output the String for [code] to the CharStream;
[old] = [code];
[code] = Next Code in the CodeStream;
while ([code] != EOF )
{
　　if ( [code] is in the StringTable)
　　{
　　　　Output the String for [code] to the CharStream; // 輸出[code]所對(duì)應(yīng)的字符串
　　　　[...] = translation for [old]; // [old]所對(duì)應(yīng)的字符串
　　　　k = first character of translation for [code]; // [code]所對(duì)應(yīng)的字符串的第一個(gè)字符
　　　　add [...]k to the StringTable;
　　　　[old] = [code];
　　}
　　else
　　{
　　　　[...] = translation for [old];
　　　　k = first character of [...];
　　　　Output [...]k to CharStream;
　　　　add [...]k to the StringTable;
　　　　[old] = [code];
　　}
　　[code] = Next Code in the CodeStream;
}