LZW
 |
藍波-立夫-衛曲編碼法（Lempel-Ziv-Welch，縮寫LZW），是以色列科學家亞伯拉罕·藍波、傑可布·立夫與美國學者泰瑞·衛曲共同提出的一種無損數據壓縮演算法。
它在1984年由泰瑞·衛曲改良，亞伯拉罕·藍波與傑可布·立夫在1978年發表的LZ78的版本而來（主要是基於藍波、立夫的壓縮概念，設計出一套具有可逆推的邏輯程序）。
與霍夫曼編碼相比，藍波-立夫-衛曲編碼法受視作將不同長度字串以固定長的碼編輯（霍夫曼編碼將固定長度字元用不同長度的碼編輯）。其優點在於此方法只需儲存一個相當小的表格，即可儲存資料還原時相對應的值，所以所需成本相對地低；然而，這種算法的設計著重在實現的速度，由於它並沒有對數據做任何分析，所以並不一定是最好的演算法（參考LZMA，LZ77）。
概念
[編輯]演算法
[編輯]編碼和解碼的演算法分別如下：
編碼
[編輯]- 先將資料的個別單一字元建立成一個字串編碼表（CSET），再分別給予編號。與此同時設 S 為輸入字串的第一個字元。
- 設 C 為在字串的下一個字元，並且將字串 C 連接到 S 的後面。設 W 為這個新的字串。
- 確認 W 有沒有在字串編碼表內，針對存在與否可以有以下兩種反應：
- 假如字串編碼表內存在字串 W ，則將 S 設成 W 。
- 假如字串編碼表內不存在字串 W ，則我們將 S 所對應到的編碼加到輸出編碼序列的最末端，接著將 W 新增到字串編碼表裡，最後再將 S 設成 C 。
- 重複步驟 2~3 直到輸入字串裡所有的字元都已經編碼完成。
- 最後將字串 S 所對應到的編碼加到輸出編碼序列的最末端，即完成整個編碼程序。
解碼
[編輯]- 先將資料的個別單一字元建立成一個字串編碼表（CSET），再分別給予編號。與此同時設 S 為一空字串。
- 從編碼序列的第一個編碼開始，設定當前的編碼所對應字元(串)為 W ，並且將該字元(串)加到輸出字串的最末端。
- 假如目前字串 S 並非空字串，則我們將字串 W 的第一個字元連接到字串 S 的後面，並且將這個新字串新增到字串編碼表裡。
- 將 S 設成 W ，然後複步驟 2~3 直到輸入編碼序列裡所有的編碼都已經復原完成。
範例
[編輯]編碼
[編輯]設原始資料為aabcaac，我們先將資料的個別單一字元先建立成一個字串編碼表（CSET），再分別給予編號如下：
| 字串 | 編碼 |
|---|---|
| a | 1 |
| b | 2 |
| c | 3 |
依照上面所示的編碼過程，字串編碼表會隨著字串鍵入而逐漸擴大而擴展成如下列表：
| 字串 | 編碼 |
|---|---|
| a | 1 |
| b | 2 |
| c | 3 |
| aa | 4 |
| ab | 5 |
| bc | 6 |
| ca | 7 |
| aac | 8 |
則原始字串 aabcaac 經過編碼壓縮後就是編碼序列112343。
解碼
[編輯]解碼的首要步驟亦為將資料的個別單一字元先建立成一個字串編碼表（CSET），並將對應的字元放於一個暫存佇列中。依序將編碼壓縮資料讀入，若為該編碼存在於字串編碼表中就將對應字元(串)保存於輸出佇列中，若不存在則擴充一個新的碼置於字串編碼表中。例如壓縮資料112343，其字串編碼表為：
| 字串 | 編碼 |
|---|---|
| a | 1 |
| b | 2 |
| c | 3 |
步驟1：讀取「1」，查字串編碼表為「a」，則：
佇列Q：
| a | — | — |
輸出：
| a |
步驟2：接著，再讀取下一筆資料「1」，查字串編碼表為「a」，則：
佇列Q：
| a | a | — |
輸出：
| aa |
因為aa在字串編碼表內沒有，因此擴充字串編碼表為：
| 字串 | 編碼 |
|---|---|
| a | 1 |
| b | 2 |
| c | 3 |
| aa | 4 |
步驟3：此時將佇列Q(1)丟棄，將Q(2)移至Q(1)位置，讀取下一個資料「2」，則：
佇列Q：
| a | b | — |
輸出：
| aab |
依上述步驟重複運作，最後可將壓縮資料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 （頁面存檔備份，存於網際網路檔案館）