檢視 LZW 的原始碼

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

伊佇一九八四年由泰瑞 ・ 衛曲改良，亞伯拉罕 ・ 藍波佮傑可布 ・ 立夫佇一九七八年發表的 LZ 七十八的版本來（主要是因為藍波、立夫的壓縮概念，設計出一套有可能歹推的邏輯程式）。

佮霍夫曼編碼相比，藍波-立夫-衛曲編碼法予人看做將無仝長度字串以固定長的碼編輯（霍夫曼編碼欲固定長度字元用無仝長度的碼編輯）。 其優點佇遮方法只需儲存一个足細的表格，雖然會當儉資料閣原底的時陣相對應，所以伊需要成本相對的地低；毋過，這種演算法的設計對重佇實現的速度，因為伊並無對資料做任何分析，所以並無一定是上好的演算法（參考 LZMA，LZ 七十七）。

==做算法概念==

===編碼===

編碼的依據是先將資料的個別單一字元先建立做一字串編碼表（CSET）， 閣分別予伊編號，比如講原始資料為 aabcaac，其字串編碼表為：

伊佇後壁編（解）碼過程，字串編碼表會綴字串鍵入來漸漸擴大，如下：

所以 aabcaac 壓縮了為十一鋪兩千三百四十三。

===解碼===

解碼依據是將壓縮資料佮原先字串編碼表對照，共對應的字囥佇咧一个暫存在列中，依序將壓縮資料讀入，若是重複資料儲存佇咧列中，若不為著重複資料，是擴充一个新的碼置佇咧字串編碼表當中。比如講壓縮資料十一鋪兩千三百四十三，其字串編碼表為：

弄青一下：讀取「一」，查字串編碼表為「a」，著：

在列 Q：

輸出：

行二：接咧，閣讀取下一筆資料「一」，查字串編碼表為「a」，著：

在列 Q：

輸出：

因為乎 aa 你佇咧字串編碼表內無，所以講擴充字串編碼表為：

弄花三：現在時會佇咧列 Q ( 一 ) 挕捒，將 Q ( 二 ) 徙到 Q ( 一 ) 位置，讀的是一个資料「二」，著：

在列 Q：

輸出：

照理講照步來做運作，最後會用得壓縮資料十一鋪二千三百四十三還原成原始資料 aabcaac。

==一種演算法說明==

方法的主要關鍵就是，伊會將欲壓縮的文字內底，自動的建立一个早前見過字串的字典。遮的字典並無需要佮遮的壓縮的文字鬥陣予傳輸，因為你若正確的伊編碼，解壓縮器嘛會當照壓縮器仝款的方法共建出來，一定會有完全佮壓縮著器字典佇咧文字的仝一點有仝款之字串。

字典會對兩百五十六條目開始，每一个是予逐種可能的字元（單一位元字串）。 每一改一字串佇字典內底並予人看過，遐爾文字中，附加佇咧單一字元了，來應該字攕的一个較長文字，就會去予儲存著字典內底。

輸出是包含字典的整數索引。遮的一開始是一个九位元，做字典成長的時陣，會當上大增加到十六位元。一个特別的符號，保留來 " 清空字典 "，會共字典回復到原先的兩百五十六條，佮九位元的索引。這對壓縮文字中有變動字元真有路用，因為佇初期的資料佇文字了後部份並袂有傷濟用處。

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

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

一般來講，字典基礎的壓縮會以標記（token）來取代片語（phrase）。 若標記得位元數量是少於片語所需要的位元數目，遐爾仔壓縮就遮爾仔產生。未壓縮的文字為：


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

壓縮過的文字：


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

這佮有效實用的閣遙遠，但是伊透過片語取代舉例說明矣壓縮方法。

==應用==

這个方法佇咧程式 " 壓縮 " 最變成廣泛地被使用，大約是一九八六年抑是濟少變做 Unix 系統內底的標準工具（自足濟法律佮技術的原因消失了後）。 數種其他受歡迎的壓縮工具嘛使用這種方法，抑是講有密實的關係的方法。

佇一九八七年，佇伊變做講 GIF 影像格式的一部份了，伊變做非常廣泛地予人用。伊嘛是會當（會當選擇）予人使用佇 TIFF 檔案。

大部份的應用中，LZW 壓縮演算法佮彼當陣已經有廣為人知的方法相比，會當提供一个較好的壓縮率。lzw 壓縮演算法是使用佇電腦的，第一个被廣泛用於一般資料的壓縮，對大漢的英文字，一般會當使用 lzw 共壓縮大約原來大細的一半。另外咧，對其他的種類資料的壓縮，伊嘛佇足濟情形下嘛足有路用的。

==專利議題==

對於 LZW 佮類似的演算法，佇美國佮其他國家已經發行數個專利。LZ 七十八是包含佇美國專利第四 , 四仔六十四 , 六百五十號，由蘭波、立夫、柯亨（Cohn）佮伊士曼（Eastman）指派予史佩瑞（Sperry）公司，尾仔是優利系統公司，申請於一九八一年八月十號，而且這馬已經到期矣。

針對 LZW 演算法有兩个美國專利：是由維克特 ・ S ・ 米勒（Victor S . Miller）佮馬克 ・ N ・ 維格曼（Mark N . Wegman）的美國專利第四 , 八百十四 , 七百四十六號，指派予 IBM，自本佇一九八三年六月一號申請佮衛曲的美國專利第四 , 五仔五十八 , 三百空二號，予受予史佩瑞公司，尾仔為著優利系統公司，佇一九八三年六月二十號申請。

美國專利四 , 五仔五十八 , 三百空二是上捷致使爭論的一个。優利系統佇彼當時授權免除使用費的專利執照予自由軟體佮免費得著的私有軟體之開發者；該公司於一九九九年八月終止該執照。真濟法律的專家已經斷定這个專利並無包含干焦會使解壓縮 LZW 資料無法度共伊壓縮的各種裝置；因為這个原因，普遍使用 Gzip 程式干焦會當讀 . Z 檔但是袂使寫入去。

Debian 每一禮拜新聞以 comp . compression 討論串為基礎所做的報導，講佇美國的優利系統專利佇伊予授權了後的一七年閣十日了後的二空空二年十二月二十日到期。大部份其他的來源就是宣稱這个專利伊提出申請的二空年以後的二空空三年六月到期。

根據優利系統網站頂的一个對陳述，佇咧英國、法國、德國、義大利、佮日本之 LZW 相對應的專利，已經佇二空空四年六月，加拿大的專利佇咧二空空四年七月初七到期。

IBM 的美國專利已經二空空六年八月十一到期。

==名稱問題==

雖然 LZW 縮寫明顯地是意指 Lempel、Ziv、和 Welch 遮的發明者，某一寡人的聲稱智慧財產權是予 Ziv 為第一位，因此這个方法著愛稱為 _ Ziv-Lempel-Welch 演算法 _，毋是 _ Lempel-Ziv-Welch 演算法 _。

==參考資料==

* 資料壓縮原理佮實務。張真誠，蔡文輝著。松崗電腦圖書資料股份有限公司。四分之一千九百九十四 / 十二。
* Welch , T . A . , " A Technique for High-Performance Data Compression " , Computers , Vol . C 鋪十七 , No . 六 ; 一千九百八十四 , pp . 八堵十九 .
* 美國專利四 , 五仔五十八 , 三百空二
* " LZW Data Compression " , by Mark Nelson（DDJ Article with source code）
* Sad day . . . GIF patent dead at 二十（簡短而且可能較過簡單的簡單故事內容，閣較濟歷史細節會當佇咧 GIF 條目揣著）
* _ Bringing back LZW compression _ by Nathan Willis
* LZW 函式庫，論文，以及其他資源的列表
* 應用佇咧 LZW 壓縮序列之高效能字串比對機制 Efficient Pattern Matching Scheme in LZW Compressed Sequences

[[分類: 待校正]]