LZW压缩技术

**藍波 - 立夫 - 衛曲編碼法**（Lempel-Ziv-Welch，縮寫 LZW），是以色列科學家亞伯拉罕・藍波、傑可布・立夫與美國學者泰瑞・衛曲共同提出的一種無損資料壓縮演算法。

它在 1984 年由泰瑞・衛曲改良，亞伯拉罕・藍波與傑可布・立夫在 1978 年發表的 LZ78 的版本而來（主要是基於藍波、立夫的壓縮概念，設計出一套具有可逆推的邏輯程式）。

與霍夫曼編碼相比，藍波 - 立夫 - 衛曲編碼法被視作將不同長度字串以固定長的碼編輯（霍夫曼編碼將固定長度字元用不同長度的碼編輯）。其優點在於此方法只需儲存一個相當小的表格，即可儲存資料還原時相對應的值，所以所需成本相對地低；然而，這種演算法的設計著重在實現的速度，由於它並沒有對資料做任何分析，所以並不一定是最好的演算法（參考 LZMA，LZ77）。

## 演算法概念

### 編碼

編碼依據是先將資料的個別單一字元先建立成一個字串編碼表（CSET），再分別給予編號，例如原始資料為 aabcaac，其字串編碼表為：

在隨後的編（解）碼過程，字串編碼表會隨著字串鍵入而逐漸擴大，如下：

因此 aabcaac 壓縮後為 112343。

### 解碼

解碼依據是將壓縮資料與原先字串編碼表對照，並將對應的字元放於一個暫存佇列中，依序將壓縮資料讀入，若為重複資料儲存於佇列中，若不為重複資料，則擴充一個新的碼置於字串編碼表中。例如壓縮資料 112343，其字串編碼表為：

步驟 1：讀取「1」，查字串編碼表為「a」，則：

佇列 Q：

輸出：

步驟 2：接著，再讀取下一筆資料「1」，查字串編碼表為「a」，則：

佇列 Q：

輸出：

因為 aa 在字串編碼表內沒有，因此擴充字串編碼表為：

步驟 3：此時將佇列 Q (1) 丟棄，將 Q (2) 移至 Q (1) 位置，讀取下一個資料「2」，則：

佇列 Q：

輸出：

依上述步驟重複運作，最後可將壓縮資料 112343 還原成原始資料 aabcaac。

## 另一種演算法說明

方法的主要關鍵是，它會在將要壓縮的文字中，自動地建立一個先前見過字串的字典。這些字典並不需要與這些壓縮的文字一起被傳輸，因為如果正確地編碼，解壓縮器也能夠依照壓縮器一樣的方法把它建出來，將會有完全與壓縮器字典在文字的同一點有同樣之字串。

字典會從 256 個條目開始，每一個是給每種可能的字元（單一位元字串）。每一次一個字串在字典中並被見過，那麼文字中，附加在單一字元後，接著該字串的一個較長文字，就會被儲存到字典中。

輸出是包含字典的整數索引。這些一開始每個是 9 位元，當字典成長時候，可以最大增加到 16 位元。一個特別的符號，保留來 "清空字典"，會把字典回復到原先的 256 個條目，和 9 位元的索引。這對於壓縮文字中含有變動字元很有用處，因為在初期的資料在文字後部份並不會有太多用處。

可變動地增加索引大小的使用是 Welch 貢獻之一。其他是用來詳細說明儲存字典的一種有效率資料結構。

### 字典基礎壓縮演算法的簡單範例

一般而言，字典基礎的壓縮會以標記（token）來取代片語（phrase）。如果標記得位元數量是少於片語所需的位元數目，那麼壓縮就如此產生。未壓縮的文字為：

　
: I am dumb and because I am dumb, I can't even tell you that I am dumb.

壓縮過的文字：

　
: $1 and because $1, I can't even tell you that $1. $1=[I am dumb]

這與有效實用上還很遙遠，但是它透過片語取代舉例說明了壓縮方法。

## 應用

這個方法在程式 "壓縮" 上變為廣泛地被使用，大約在 1986 年或多或少變成 Unix 系統中的標準工具（自很多法律和技術的原因消失之後）。數種其他受歡迎的壓縮工具也使用這種方法，或者是有緊密關係的方法。

於 1987 年，在它變為 GIF 影像格式的一部份後，它變成非常廣泛地被使用。它也可以（可選擇）被使用於 TIFF 檔案。

在大部份的應用中，LZW 壓縮演算法和當時已有且廣為人知的方法相比，能夠提供一個比較好的壓縮率。lzw 壓縮演算法是使用在電腦上的，第一個被廣泛用於一般資料的壓縮，對於大的英文文字，一般可以使用 lzw 將其壓縮到大約原來大小的一半。另外，對於其他的種類資料的壓縮，它在很多情況下也相當有用。

## 專利議題

對於 LZW 和類似的演算法，在美國和其他國家已經發行數個專利。LZ78 是包含在美國專利第 4,464,650 號，由蘭波、立夫、柯亨（Cohn）和伊士曼（Eastman）指派給史佩瑞（Sperry）公司，後來是優利系統公司，申請於 1981 年 8 月 10 日，而且現在已經到期。

針對 LZW 演算法有兩個美國專利：由維克特・S・米勒（Victor S. Miller）和馬克・N・維格曼（Mark N. Wegman）的美國專利第 4,814,746 號，指派給 IBM，原本於 1983 年 6 月 1 日申請和衛曲的美國專利第 4,558,302 號，讓受給史佩瑞公司，後來為優利系統公司，於 1983 年 6 月 20 日申請。

美國專利 4,558,302 是最常導致爭論的一個。優利系統在當時授權免除使用費的專利執照給自由軟體和免費獲得的私有軟體之開發者；該公司於 1999 年八月終止該執照。很多法律的專家已斷定該專利並不包含只能解壓縮 LZW 資料而無法壓縮它的各種裝置；因為這個原因，普遍使用的 Gzip 程式只能讀取.Z 檔但是不能寫入。

Debian 每週新聞以 comp.compression 討論串為基礎所作的報導，稱在美國的優利系統專利於它被授權後的 17 年又 10 天之後的 2002 年 12 月 20 日到期。大部份其他來源宣稱該專利於它提出申請的 20 年後的 2003 年 6 月到期。

根據優利系統網站上的一個陳述，在英國、法國、德國、義大利、和日本之 LZW 相對應的專利，已經在 2004 年 6 月過期，而加拿大的專利於 2004 年 7 月 7 日到期。

IBM 的美國專利已於 2006 年 8 月 11 日到期。

## 名稱問題

雖然 LZW 縮寫明顯地是意指 Lempel、Ziv、和 Welch 這些發明者，某些人聲稱智慧財產權是給 Ziv 為第一位，因此這個方法必須稱為 _Ziv-Lempel-Welch 演算法_，而不是 _Lempel-Ziv-Welch 演算法_。

## 參考資料

* 資料壓縮原理與實務。張真誠，蔡文輝著。松崗電腦圖書資料股份有限公司。1994/4/12。
* Welch, T.A., "A Technique for High-Performance Data Compression" ,Computers, Vol. C-17, No.6; 1984, pp.8-19.
* 美國專利 4,558,302 （頁面存檔備份，存於網際網路檔案館）
* "LZW Data Compression", by Mark Nelson （頁面存檔備份，存於網際網路檔案館）（DDJ Article with source code）
* Sad day... GIF patent dead at 20 （頁面存檔備份，存於網際網路檔案館）（簡短且可能過於簡化的簡單故事內容，更多歷史細節可以在 GIF 條目找到）
* _Bringing back LZW compression_ by Nathan Willis
* LZW 函式庫，論文，以及其他資源的列表 （頁面存檔備份，存於網際網路檔案館）
* 應用於 LZW 壓縮序列之高效能字串比對機制 Efficient Pattern Matching Scheme in LZW Compressed Sequences （頁面存檔備份，存於網際網路檔案館）