1.概述
GIF(Graphics Interchange Format，圖形交換格式)文件是由 CompuServe公司開發的圖形文件格式，版權所有，任何商業目的使用均須 CompuServe公司授權。
GIF圖象是基於顏色列表的（存儲的數據是該點的顏色對應於顏色列表的索引值），最多只支持8位（256色）。GIF文件內部分成許多存儲塊，用來存儲多幅圖象或者是決定圖象表現行為的控制塊，用以實現動畫和交互式應用。GIF文件還通過LZW壓縮算法壓縮圖象數據來減少圖象尺寸（關於LZW算法和GIF數據壓縮>>...）。
2.GIF文件存儲結構
GIF文件內部是按塊劃分的，包括控制塊（ Control Block ）和數據塊（Data Sub-blocks）兩種。控制塊是控制數據塊行為的，根據不同的控制塊包含一些不同的控制參數；數據塊只包含一些8-bit的字符流，由它前面的控制塊來決定它的功能，每個數據塊大小從0到255個字節，數據塊的第一個字節指出這個數據塊大小（字節數），計算數據塊的大小時不包括這個字節，所以一個空的數據塊有一個字節，那就是數據塊的大小0x00。下表是一個數據塊的結構：
| BYTE | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | BIT |
| 0 | 塊大小 | Block Size - 塊大小，不包括這個這個字節（不計算塊大小自身） | |||||||
| 1 | Data Values - 塊數據，8-bit的字符串 | ||||||||
| 2 | |||||||||
| ... | |||||||||
| 254 | |||||||||
| 255 | |||||||||
一個GIF文件的結構可分為文件頭(File Header)、GIF數據流(GIF Data Stream)和文件終結器(Trailer)三個部分。文件頭包含GIF文件署名(Signature)和版本號(Version)；GIF數據流由控制標識符、圖象塊(Image Block)和其他的一些擴展塊組成；文件終結器只有一個值為0x3B的字符（';'）表示文件結束。下表顯示了一個GIF文件的組成結構：
| GIF署名 | 文件頭 | |
| 版本號 | ||
| 邏輯屏幕標識符 | GIF數據流 | |
| 全局顏色列表 | ||
| ... | ||
| 圖象標識符 | 圖象塊 | |
| 圖象局部顏色列表圖 | ||
| 基於顏色列表的圖象數據 | ||
| ... | ||
| GIF結尾 | 文件結尾 | |
下面就具體介紹各個部分:
文件頭部分(Header)
~~~~~~~~~~~~~~~~~
GIF署名(Signature)和版本號(Version)
~~~~~~~~~~~~~~~~~~~~~~~~~~~
GIF署名用來確認一個文件是否是GIF格式的文件，這一部分由三個字符組成："GIF";文件版本號也是由三個字節組成,可以為"87a"或"89a".具體描述見下表:
| BYTE | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | BIT |
| 1 | 'G' | GIF文件標識 | |||||||
| 2 | 'I' | ||||||||
| 3 | 'F' | ||||||||
| 4 | '8' | GIF文件版本號：87a - 1987年5月 89a - 1989年7月 | |||||||
| 5 | '7'或'9' | ||||||||
| 6 | 'a' | ||||||||
GIF數據流部分(GIF Data Stream)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
邏輯屏幕標識符(Logical Screen Descriptor)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
這一部分由7個字節組成，定義了GIF圖象的大小(Logical Screen Width & Height)、顏色深度(Color Bits)、背景色(Blackground Color Index)以及有無全局顏色列表(Global Color Table)和顏色列表的索引數(Index Count)，具體描述見下表：
| BYTE | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | BIT | |
| 1 | 邏輯屏幕寬度 | 像素數，定義GIF圖象的寬度 | ||||||||
| 2 | ||||||||||
| 3 | 邏輯屏幕高度 | 像素數，定義GIF圖象的高度 | ||||||||
| 4 | ||||||||||
| 5 | m | cr | s | pixel | 具體描述見下... | |||||
| 6 | 背景色 | 背景顏色(在全局顏色列表中的索引，如果沒有全局顏色列表，該值沒有意義) | ||||||||
| 7 | 像素寬高比 | 像素寬高比(Pixel Aspect Radio) | ||||||||
m- 全局顏色列表標志(Global Color Table Flag)，當置位時表示有全局顏色列表，pixel值有意義.
cr - 顏色深度(Color ResoluTion)，cr+1確定圖象的顏色深度.
s - 分類標志(Sort Flag)，如果置位表示全局顏色列表分類排列.
pixel - 全局顏色列表大小，pixel+1確定顏色列表的索引數（2的pixel+1次方）.
全局顏色列表(Global Color Table)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
全局顏色列表必須緊跟在邏輯屏幕標識符後面，每個顏色列表索引條目由三個字節組成，按R、G、B的順序排列。
| BYTE | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | BIT |
| 1 | 索引1的紅色值 | ||||||||
| 2 | 索引1的綠色值 | ||||||||
| 3 | 索引1的藍色值 | ||||||||
| 4 | 索引2的紅色值 | ||||||||
| 5 | 索引2的綠色值 | ||||||||
| 6 | 索引2的藍色值 | ||||||||
| 7 | ... | ||||||||
圖象標識符(Image Descriptor)
~~~~~~~~~~~~~~~~~~~~~~~~~
一個GIF文件內可以包含多幅圖象，一幅圖象結束之後緊接著下是一幅圖象的標識符，圖象標識符以0x2C(',')字符開始，定義緊接著它的圖象的性質，包括圖象相對於邏輯屏幕邊界的偏移量、圖象大小以及有無局部顏色列表和顏色列表大小，由10個字節組成：
| BYTE | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | BIT | |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 圖象標識符開始，固定值為',' | |
| 2 | X方向偏移量 | 必須限定在邏輯屏幕尺寸範圍內 | ||||||||
| 3 | ||||||||||
| 4 | Y方向偏移量 | |||||||||
| 5 | ||||||||||
| 6 | 圖象寬度 | |||||||||
| 7 | ||||||||||
| 8 | 圖象高度 | |||||||||
| 9 | ||||||||||
| 10 | m | i | s | r | pixel | m - 局部顏色列表標志(Local Color Table Flag) | ||||
| 置位時標識緊接在圖象標識符之後有一個局部顏色列表，供緊跟在它之後的一幅圖象使用；值否時使用全局顏色列表，忽略pixel值。 i -交織標志(Interlace Flag)，置位時圖象數據使用交織方式排列（詳細描述...），否則使用順序排列。 s - 分類標志(Sort Flag)，如果置位表示緊跟著的局部顏色列表分類排列. r - 保留，必須初始化為0. pixel - 局部顏色列表大小(Size of Local Color Table)，pixel+1就為顏色列表的位數 | ||||||||||
局部顏色列表(Local Color Table)
~~~~~~~~~~~~~~~~~~~~~~~~~~
如果上面的局部顏色列表標志置位的話，則需要在這裏（緊跟在圖象標識符之後）定義一個局部顏色列表以供緊接著它的圖象使用，注意使用前應線保存原來的顏色列表，使用結束之後回複原來保存的全局顏色列表。如果一個GIF文件即沒有提供全局顏色列表，也沒有提供局部顏色列表，可以自己創建一個顏色列表，或使用系統的顏色列表。局部顏色列表的排列方式和全局顏色列表一樣：RGBRGB......
基於顏色列表的圖象數據(Table-Based Image Data)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
由兩部分組成：LZW編碼長度(LZW Minimum Code Size)和圖象數據(Image Data)。
| BYTE | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | BIT |
| 1 | LZW編碼長度 | LZW編碼初始碼表大小的位數，詳細描述見LZW編碼... | |||||||
| ... | 圖象數據，由一個或幾個數據塊(Data Sub-blocks)組成 | |||||||
數據塊 | |||||||||
... | |||||||||
GIF圖象數據使用了LZW壓縮算法（詳細介紹請看後面的『LZW算法和GIF數據壓縮』），大大減小了圖象數據的大小。圖象數據在壓縮前有兩種排列格式：連續的和交織的(由圖象標識符的交織標志控制)。連續方式按從左到右、從上到下的順序排列圖象的光柵數據；交織圖象按下面的方法處理光柵數據：
創建四個通道(pass)保存數據，每個通道提取不同行的數據：
第一通道(Pass 1)提取從第0行開始每隔8行的數據；
第二通道(Pass 2)提取從第4行開始每隔8行的數據；
第三通道(Pass 3)提取從第2行開始每隔4行的數據；
第四通道(Pass 4)提取從第1行開始每隔2行的數據；
下面的例子演示了提取交織圖象數據的順序：
| 行 | 通道1 | 通道2 | 通道3 | 通道4 | |
| 0 -------------------------------------------------------- | 1 | ||||
| 1-------------------------------------------------------- | 4 | ||||
| 2 -------------------------------------------------------- | 3 | ||||
| 3 -------------------------------------------------------- | 4 | ||||
| 4 -------------------------------------------------------- | 2 | ||||
| 5 -------------------------------------------------------- | 4 | ||||
| 6 -------------------------------------------------------- | 3 | ||||
| 7 -------------------------------------------------------- | 4 | ||||
| 8 -------------------------------------------------------- | 1 | ||||
| 9 -------------------------------------------------------- | 4 | ||||
| 10-------------------------------------------------------- | 3 | ||||
| 11 -------------------------------------------------------- | 4 | ||||
| 12 -------------------------------------------------------- | 2 | ||||
| 13 -------------------------------------------------------- | 4 | ||||
| 14 -------------------------------------------------------- | 3 | ||||
| 15 -------------------------------------------------------- | 4 | ||||
| 16 -------------------------------------------------------- | 1 | ||||
| 17 -------------------------------------------------------- | 4 | ||||
| 18 -------------------------------------------------------- | 3 | ||||
| 19 -------------------------------------------------------- | 4 | ||||
| 20 -------------------------------------------------------- | 2 |
圖形控制擴展(Graphic Control Extension)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
這一部分是可選的（需要89a版本），可以放在一個圖象塊(圖象標識符)或文本擴展塊的前面，用來控制跟在它後面的第一個圖象（或文本）的渲染(Render)形式，組成結構如下：
| BYTE | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | BIT |
| 1 | 擴展塊標識 | Extension Introducer - 標識這是一個擴展塊，固定值0x21 | |||||||
| 2 | 圖形控制擴展標簽 | Graphic Control Label - 標識這是一個圖形控制擴展塊，固定值0xF9 | |||||||
| 3 | 塊大小 | Block Size - 不包括塊終結器，固定值4 | |||||||
| 4 | 保留 | 處置方法 | i | t | i - 用戶輸入標志；t - 透明色標志。詳細描述見下... | ||||
| 5 | 延遲時間 | Delay Time - 單位1/100秒，如果值不為1，表示暫停規定的時間後再繼續往下處理數據流 | |||||||
| 6 | |||||||||
| 7 | 透明色索引 | Transparent Color Index - 透明色索引值 | |||||||
| 8 | 塊終結器 | Block Terminator - 標識塊終結，固定值0 | |||||||
處置方法(Disposal Method)：指出處置圖形的方法，當值為：
0 - 不使用處置方法
1 - 不處置圖形，把圖形從當前位置移去
2 - 回複到背景色
3 - 回複到先前狀態
4-7 - 自定義
用戶輸入標志(Use Input Flag)：指出是否期待用戶有輸入之後才繼續進行下去，置位表示期待，值否表示不期待。用戶輸入可以是按回車鍵、鼠標點擊等，可以和延遲時間一起使用，在設置的延遲時間內用戶有輸入則馬上繼續進行，或者沒有輸入直到延遲時間到達而繼續
透明顏色標志(Transparent Color Flag)：置位表示使用透明顏色
注釋擴展(Comment Extension)
~~~~~~~~~~~~~~~~~~~~~~~~~~~
這一部分是可選的（需要89a版本），可以用來記錄圖形、版權、描述等任何的非圖形和控制的純文本數據(7-bit ASCII字符)，注釋擴展並不影響對圖象數據流的處理，解碼器完全可以忽略它。存放位置可以是數據流的任何地方，最好不要妨礙控制和數據塊，推薦放在數據流的開始或結尾。具體組成：
| BYTE | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | BIT |
| 1 | 擴展塊標識 | Extension Introducer - 標識這是一個擴展塊，固定值0x21 | |||||||
| 2 | 注釋塊標簽 | Comment Label - 標識這是一個注釋塊，固定值0xFE | |||||||
... | Comment Data - 一個或多個數據塊(Data Sub-Blocks)組成 | ||||||||
注釋塊 | |||||||||
... | |||||||||
| 塊終結器 | Block Terminator - 標識注釋塊結束，固定值0 | ||||||||
圖形文本擴展(Plain Text Extension)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
這一部分是可選的（需要89a版本），用來繪制一個簡單的文本圖象，這一部分由用來繪制的純文本數據（7-bit ASCII字符）和控制繪制的參數等組成。繪制文本借助於一個文本框（Text Grid）來定義邊界，在文本框中劃分多個單元格，每個字符占用一個單元，繪制時按從左到右、從上到下的順序依次進行，直到最後一個字符或者占滿整個文本框（之後的字符將被忽略，因此定義文本框的大小時應該注意到是否可以容納整個文本），繪制文本的顏色索引使用全局顏色列表，沒有則可以使用一個已經保存的前一個顏色列表。另外，圖形文本擴展塊也屬於圖形塊(Graphic Rendering Block)，可以在它前面定義圖形控制擴展對它的表現形式進一步修改。圖形文本擴展的組成：
| BYTE | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | BIT |
| 1 | 擴展塊標識 | Extension Introducer - 標識這是一個擴展塊，固定值0x21 | |||||||
| 2 | 圖形控制擴展標簽 | Plain Text Label - 標識這是一個圖形文本擴展塊，固定值0x01 | |||||||
| 3 | 塊大小 | Block Size - 塊大小，固定值12 | |||||||
| 4 | 文本框左邊界位置 | Text Glid Left Posotion - 像素值，文本框離邏輯屏幕的左邊界距離 | |||||||
| 5 | |||||||||
| 6 | 文本框上邊界位置 | Text Glid Top Posotion - 像素值，文本框離邏輯屏幕的上邊界距離 | |||||||
| 7 | |||||||||
| 8 | 文本框高度 | Text Glid Width -像素值 | |||||||
| 9 | |||||||||
| 10 | 文本框高度 | Text Glid Height - 像素值 | |||||||
| 11 | |||||||||
| 12 | 字符單元格寬度 | Character Cell Width - 像素值，單個單元格寬度 | |||||||
| 13 | 字符單元格高度 | Character Cell Height- 像素值，單個單元格高度 | |||||||
| 14 | 文本前景色索引 | Text Foreground Color Index - 前景色在全局顏色列表中的索引 | |||||||
| 15 | 文本背景色索引 | Text Blackground Color Index - 背景色在全局顏色列表中的索引 | |||||||
| N | ... | Plain Text Data - 一個或多個數據塊(Data Sub-Blocks)組成，保存要在顯示的字符串。 | |||||||
文本數據塊 | |||||||||
... | |||||||||
| N+1 | 塊終結 | Block Terminator - 標識注釋塊結束，固定值0 | |||||||
推薦：1.由於文本的字體(Font)和尺寸(Size)沒有定義，解碼器應該根據情況選擇最合適的；
2.如果一個字符的值小於0x20或大於0xF7，則這個字符被推薦顯示為一個空格(0x20)；
3.為了兼容性，最好定義字符單元格的大小為8x8或8x16（寬度x高度）。
應用程序擴展(Application Extension)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
這是提供給應用程序自己使用的（需要89a版本），應用程序可以在這裏定義自己的標識、信息等，組成：
| BYTE | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | BIT |
| 1 | 擴展塊標識 | Extension Introducer - 標識這是一個擴展塊，固定值0x21 | |||||||
| 2 | 圖形控制擴展標簽 | Application Extension Label - 標識這是一個應用程序擴展塊，固定值0xFF | |||||||
| 3 | 塊大小 | Block Size - 塊大小，固定值11 | |||||||
| 4 | 應用程序標識符 | Application Identifier - 用來鑒別應用程序自身的標識(8個連續ASCII字符) | |||||||
| 5 | |||||||||
| 6 | |||||||||
| 7 | |||||||||
| 8 | |||||||||
| 9 | |||||||||
| 10 | |||||||||
| 11 | |||||||||
| 12 | 應用程序鑒別碼 | Application Authentication Code - 應用程序定義的特殊標識碼(3個連續ASCII字符) | |||||||
| 13 | |||||||||
| 14 | |||||||||
| N | ... | 應用程序自定義數據塊 - 一個或多個數據塊(Data Sub-Blocks)組成，保存應用程序自己定義的數據 | |||||||
應用程序數據 | |||||||||
... | |||||||||
| N+1 | 塊終結器 | lock Terminator - 標識注釋塊結束，固定值0 | |||||||
文件結尾部分
~~~~~~~~~~~
文件終結器(Trailer)
~~~~~~~~~~~~~~~~
這一部分只有一個值為0的字節，標識一個GIF文件結束.
| BYTE | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
| 1 | 文件終結 | GIF Trailer - 標識GIF文件結束，固定值0x3B | |||||||
2.LZW算法和GIF數據壓縮
~~~~~~~~~~~~~~~~~~~~~~~~~~~
GIF文件的圖象數據使用了可變長度編碼的LZW壓縮算法(Variable-Length_Code LZW Compression)，這是從LZW(Lempel Ziv Compression)壓縮算法演變過來的，通過壓縮原始數據的重複部分來達到減少文件大小的目的。
標准的LZW壓縮原理：
~~~~~~~~~~~~~~~~~~
先來解釋一下幾個基本概念：
LZW壓縮有三個重要的對象：數據流(CharStream)、編碼流(CodeStream)和編譯表(String Table)。在編碼時，數據流是輸入對象（圖象的光柵數據序列），編碼流就是輸出對象（經過壓縮運算的編碼數據）；在解碼時，編碼流則是輸入對象，數據流是輸出對象；而編譯表是在編碼和解碼時都須要用借助的對象。
字符(Character)：最基礎的數據元素，在文本文件中就是一個字節，在光柵數據中就是一個像素的顏色在指定的顏色列表中的索引值；
字符串(String)：由幾個連續的字符組成；
前綴(Prefix)：也是一個字符串，不過通常用在另一個字符的前面，而且它的長度可以為0；
根(Root)：單個長度的字符串；
編碼(Code)：一個數字，按照固定長度（編碼長度）從編碼流中取出，編譯表的映射值；
圖案：一個字符串，按不定長度從數據流中讀出,映射到編譯表條目.
LZW壓縮的原理：提取原始圖象數據中的不同圖案，基於這些圖案創建一個編譯表，然後用編譯表中的圖案索引來替代原始光柵數據中的相應圖案，減少原始數據大小。看起來和調色板圖象的實現原理差不多，但是應該注意到的是，我們這裏的編譯表不是事先創建好的，而是根據原始圖象數據動態創建的，解碼時還要從已編碼的數據中還原出原來的編譯表（GIF文件中是不攜帶編譯表信息的），為了更好理解編解碼原理，我們來看看具體的處理過程：
編碼器(Compressor)
~~~~~~~~~~~~~~~~
編碼數據，第一步，初始化一個編譯表，假設這個編譯表的大小是12位的，也就是最多有4096個單位，另外假設我們有32個不同的字符（也可以認為圖象的每個像素最多有32種顏色），表示為a，b，c，d，e...，初始化編譯表：第0項為a，第1項為b，第2項為c...一直到第31項，我們把這32項就稱為根。
開始編譯，先定義一個前綴對象Current Prefix，記為[.c.]，現在它是空的，然後定義一個當前字符串Current String，標記為[.c.]k，[.c.]就為Current Prefix，k就為當前讀取字符。現在來讀取數據流的第一個字符，假如為p，那麼Current String就等於[.c.]p（由於[.c.]為空，實際上值就等於p），現在在編譯表中查找有沒有Current String的值，由於p就是一個根字符，我們已經初始了32個根索引，當然可以找到，把p設為Current Prefix的值，不做任何事繼續讀取下一個字符，假設為q，Current String就等於[.c.]q（也就是pq），看看在編譯表中有沒有該值，當然。沒有，這時我們要做下面的事情：將Current String的值（也就是pq）添加到編譯表的第32項，把Current Prefix的值（也就是p）在編譯表中的索引輸出到編碼流，修改Current Prefix為當前讀取的字符（也就是q）。繼續往下讀，如果在編譯表中可以查找到Current String的值([.c.]k)，則把Current String的值([.c.]k)賦予Current Prefix；如果查找不到，則添加Current String的值([.c.]k)到編譯表，把Current Prefix的值([.c.])在編譯表中所對應的索引輸出到編碼流，同時修改Current Prefix為k ，這樣一直循環下去直到數據流結束。偽代碼看起來就像下面這樣：
|
來看一個具體的例子,我們有一個字母表a，b，c，d.有一個輸入的字符流abacaba。現在來初始化編譯表：#0=a,#1=b,#2=c,#3=d.現在開始讀取第一個字符a，[.c.]a=a，可以在在編譯表中找到，修改[.c.]=a;不做任何事繼續讀取第二個字符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；好了，現在沒有數據了，輸出[.c.]的值a的索引#0到編碼流，這樣最後的輸出結果就是：#0#1#0#2#4#0.
解碼器(Decompressor)
~~~~~~~~~~~~~~~~~~
好了，現在來看看解碼數據。數據的解碼，其實就是數據編碼的逆向過程，要從已經編譯的數據（編碼流）中找出編譯表，然後對照編譯表還原圖象的光柵數據。
首先，還是要初始化編譯表。GIF文件的圖象數據的第一個字節存儲的就是LZW編碼的編碼大小（一般等於圖象的位數），根據編碼大小，初始化編譯表的根條目（從0到2的編碼大小次方），然後定義一個當前編碼Current Code，記作[code]，定義一個Old Code，記作[old]。讀取第一個編碼到[code]，這是一個根編碼，在編譯表中可以找到，把該編碼所對應的字符輸出到數據流，[old]=[code]；讀取下一個編碼到[code]，這就有兩種情況：在編譯表中有或沒有該編碼，我們先來看第一種情況：先輸出當前編碼[code]所對應的字符串到數據流，然後把[old]所對應的字符（串）當成前綴prefix [...]，當前編碼[code]所對應的字符串的第一個字符當成k，組合起來當前字符串Current String就為[...]k，把[...]k添加到編譯表，修改[old]=[code]，讀下一個編碼；我們來看看在編譯表中找不到該編碼的情況，回想一下編碼情況：如果數據流中有一個p[...]p[...]pq這樣的字符串，p[...]在編譯表中而p[...]p不在，編譯器將輸出p[...]的索引而添加p[...]p到編譯表，下一個字符串p[...]p就可以在編譯表中找到了，而p[...]pq不在編譯表中，同樣將輸出p[...]p的索引值而添加p[...]pq到編譯表，這樣看來，解碼器總比編碼器『慢一步』，當我們遇到p[...]p所對應的索引時，我們不知到該索引對應的字符串（在解碼器的編譯表中還沒有該索引，事實上，這個索引將在下一步添加），這時需要用猜測法：現在假設上面的p[...]所對應的索引值是#58，那麼上面的字符串經過編譯之後是#58#59，我們在解碼器中讀到#59時，編譯表的最大索引只有#58，#59所對應的字符串就等於#58所對應的字符串(也就是p[...])加上這個字符串的第一個字符(也就是p)，也就是p[...]p。事實上，這種猜測法是很准確（有點不好理解，仔細想一想吧）。上面的解碼過程用偽代碼表示就像下面這樣：
|
GIF數據壓縮
~~~~~~~~~~~
下面是GIF文件的圖象數據結構：
| BYTE | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | BIT |
| 1 | 編碼長度 | LZW Code Size - LZW壓縮的編碼長度，也就是要壓縮的數據的位數 | |||||||
| ... | 數據塊 | ||||||||
| 塊大小 | 數據塊，如果需要可重複多次 | ||||||||
| 編碼數據 | |||||||||
| ... | 數據塊 | ||||||||
| 塊終結器 | 一個圖象的數據編碼結束，固定值0 | ||||||||
把光柵數據序列（數據流）壓縮成GIF文件的圖象數據（字符流）可以按下面的步驟進行：
1.定義編碼長度
GIF圖象數據的第一個字節就是編碼長度(Code Size)，這個值是指要表現一個像素所需要的最小位數，通常就等於圖象的色深；
2.壓縮數據
通過LZW壓縮算法將圖象的光柵數據流壓縮成GIF的編碼數據流。這裏使用的LZW壓縮算法是從標准的LZW壓縮算法演變過來的，它們之間有如下的差別：
[1]GIF文件定義了一個編碼大小(Clear Code)，這個值等於2的『編碼長度』次方，在從新開始一個編譯表（編譯表溢出）時均須輸出該值，解碼器遇到該值時意味著要從新初始化一個編譯表；
[2]在一個圖象的編碼數據結束之前（也就是在塊終結器的前面），需要輸出一個Clear Code+1的值，解碼器在遇到該值時就意味著GIF文件的一個圖象數據流的結束；
[3]第一個可用到的編譯表索引值是Clear Code+2（從0到Clear Code-1是根索引，再上去兩個不可使用，新的索引從Clare Code+2開始添加）；
[4]GIF輸出的編碼流是不定長的，每個編碼的大小從Code Size + 1位到12位，編碼的最大值就是4095（編譯表需要定義的索引數就是4096），當編碼所須的位數超過當前的位數時就把當前位數加1，這就需要在編碼或解碼時注意到編碼長度的改變。
3.編譯成字節序列
因為GIF輸出的編碼流是不定長的，這就需要把它們編譯成固定的8-bit長度的字符流，編譯順序是從右往左。下面是一個具體例子：編譯5位長度編碼到8位字符
| 0 | b | b | b | a | a | a | a | a |
| 1 | d | c | c | c | c | c | b | b |
| 2 | e | e | e | e | d | d | d | d |
| 3 | g | g | f | f | f | f | f | e |
| 4 | h | h | h | h | h | g | g | g |
| ... | ||||||||
| N | ||||||||
4.打包
前面講過，一個GIF的數據塊的大小從0到255個字節，第一個字節是這個數據塊的大小（字節數），這就需要將編譯編後的碼數據打包成一個或幾個大小不大於255個字節的數據包。然後寫入圖象數據塊中。
- This is a reposted article.
- Keywords : 數據塊, 字符, 字符串, Color, 編譯表, String, 索引, 數據, 輸出, 第一, Table, Block, 字節, Extension, 標識這, 塊大小, 圖象數據, 修改, 編碼, 組成