GIF 與 LZW 專利：壓縮原理、PNG 誕生及專利屆滿的歷史

Jacob Ziv 與 Abraham Lempel 於 1977 年發表的論文，與參照先前出現過的數據序列的 LZ77 方法有關。兩人 1978 年論文所介紹的 LZ78，則會把讀取過的序列加入字典。後來 PNG 採用的 DEFLATE 結合 LZ77 與 Huffman 編碼，並非 GIF 所用的 LZW。

Terry A. Welch 在 1984 年 6 月的論文中，說明了以 LZ78 為基礎的高速字典壓縮方法。LZW 是 Lempel–Ziv–Welch 的縮寫。演算法已公開發表，不等於其實作不涉及專利；若把「已公開」直接理解為「可不受限制地實作」，便會錯過這段歷史的核心爭議。

LZW 利用字典中的代碼，表示重複出現的符號序列。編碼器與解碼器只要採用相同的初始字典及更新規則，就能還原數據，而毋須傳送整份完成後的字典。以下教學例子的初始字典只有 A=0、B=1，並不是 GIF 檔案的位元組（byte）串流。

輸出是 0, 1, 2, 4。解碼器一面輸出 A、B、AB，一面建立字典。當收到最後的代碼 4，而字典尚未有該項目時，會取上一個序列 AB 的首個符號 A，接在 AB 後面，還原成 ABA。這個特殊處理適用於收到的代碼正好等於下一個待分配代碼的情況。

7 個字元變成 4 個代碼，不代表檔案大小必定縮至原來的 4/7。代碼位元寬度、初始化與結束代碼、圖片標頭等也佔空間。輸入太短或重複性不足時，壓縮後甚至可能更大。

CompuServe 的 GIF87a 規格日期是 1987 年 6 月 15 日。GIF 使用 LZW 壓縮指向色彩表的索引序列，而非直接壓縮色彩值。一個色彩表最多有 256 個項目。LZW 雖然是無損壓縮，但把照片轉換成有限色彩的調色盤時，仍可能先失去部分色彩資訊。

按 GIF89a 的規則，最小代碼大小為 m 時，起始代碼寬度是 m+1 位元（bit），最多增至 12 位元。m=8 時由 9 位元開始，但不是所有 GIF 都如此。即使是雙色圖片，m 也須設為 2。Clear 代碼會重設字典，End of Information 代碼則表示數據結束。字典容量用盡時，並非必須立即送出 Clear 代碼。

GIF87a 已有在同一數據串流中儲存多張圖片的結構。GIF89a 的 Graphic Control Extension 可指定延遲時間、透明色及圖片顯示後的處理方式。因此，不能說儲存多張圖片的能力是 89a 才首次加入。

美國專利 US 4,558,302 列出的發明人是 Welch，原受讓人是 Sperry。該專利於 1983 年 6 月 20 日申請，獲批專利的公告於 1985 年 12 月 10 日發出。1984 年是論文發表年份，不是專利申請年份。Sperry 與 Burroughs 在 1986 年合併後，相關權利由 Unisys 承接。

較早期美國專利的有效期涉及制度過渡規則，不能單憑現今常見的「自申請日起 20 年」說法，一律推算屆滿日期。下文採用當時授權文件明列的日期，也不把 Google Patents 自動顯示的法律狀態當作個別案件的法律判斷。

參與 PNG 開發的 Greg Roelofs 記錄，CompuServe 在 1994 年 12 月 28 日的公告是一個重要轉折。Unisys 與 CompuServe 的磋商早於公告展開；磋商開始、公佈日期及合約的實際條款，應分開理解。

問題的核心，是實作壓縮技術的軟件所涉及的專利授權，而不是對 GIF 副檔名徵稅。「GIF tax」只是俗稱，並非稅制。包括後來涉及網站的授權要求，具體條件也因時期、合約及所用實作而異，不能簡化為「所有展示 GIF 的網站都要繳付劃一費用」。

1995 年初，Thomas Boutell 等人開始討論 GIF 的替代格式。避開專利問題是其中一個動機；更多色彩、更靈活的透明度等技術改進，同樣影響了 PNG 的設計。

• 1996 年 10 月 1 日：PNG 1.0 成為 W3C 推薦標準（Recommendation）。
• 1997 年 3 月：RFC 2083 發表，並非與 1996 年的 W3C 推薦標準同日發佈。
• 2004 年 3 月：ISO/IEC 15948:2004 出版，其版本名稱不是 2003 年版。

PNG 採用 DEFLATE，是選擇另一種壓縮方式，並非等待 LZW 專利屆滿後才使用 LZW。RFC 1951 將 DEFLATE 描述為 LZ77 與 Huffman 編碼的組合。

PNG 1.0 並不包括動畫，所以最初主要替代 GIF 的靜態圖片用途。這個限制並非一直不變：2025 年 6 月 24 日的 PNG 第三版 W3C 推薦標準已包括 APNG 動畫。PNG 的透明度亦不是一律限於 8 位元，而是要按色彩類型及位元深度的規則處理。

下表列出 Stellent 與 Guidance Software 在 2005 年訂立、由 SEC 公開的 License Agreement 中，LZW 通知所述的日期。這是有關指定 Unisys 專利的當時記錄，不代表本文已逐一重新查核各國專利登記冊。

來源：Stellent Chicago Sales, Inc. / SEC: License Agreement（LZW 通知）。

美國的屆滿日期不是全球屆滿日期。這張表亦不能證明其他公司持有的專利，或涵蓋改良技術的權利，都在 2004 年消失。同一通知也提到改良技術涉及另外的專利及專利申請。

選擇圖片格式時，毋須只由 GIF 的歷史作決定。應比較色彩數目、透明度、靜態或動畫用途、顯示環境的支援、編碼時間及檔案大小。WebP 或 AVIF 有時能產生較小檔案，但不保證每次都只有 GIF 的五分之一或十分之一。比較時應使用相同素材、畫質、解像度及影格數；亦可參閱我們的 WebP、AVIF 與 JPEG 比較文章。

NanToo 日文版的 GIF 動畫製作工具使用 gif.js，這個程式庫以 MIT 授權條款發佈。專利有效期結束，與實作軟件的版權及授權條款是兩回事。分發程式庫時仍可能須保留相關聲明，輸入圖片的使用權利也要另外確認。

LZW 把重複序列表示為字典代碼；GIF 是採用這項技術的圖片格式。1983 年專利申請、1984 年論文、1985 年專利批出，以及 1994 年底的授權公告，是不同事件。其後 PNG 的開發，以及 1996、1997、2004 年的標準化里程碑，也應分開看待。

相關 Unisys 專利在 2003–2004 年屆滿是重要里程碑，但軟件授權條款和圖片版權並不因此消失。本文是技術與專利史的一般介紹；如需評估某份合約或某項產品的法律問題，應先確定實作方式及司法管轄區，再向合適的專業人士查詢。