LZW

维基百科,自由的百科全书
跳转至: 导航搜索

LZWLempel-Ziv-Welch)是Abraham LempelJacob ZivTerry Welch提出的一種無損数据压缩演算法。它在1984年由Terry Welch改良Abraham LempelJacob Ziv在1978年发表的LZ78的版本而來。这种算法的設計著重在实现的速度,由于它并没有对数据做任何分析,所以并不一定是最好的演算法(參考LZMALZ77)。

演算法[编辑]

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

字典會從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,由Lempel, Ziv, Cohn,和Eastman,指派給Sperry公司,後來是Unisys公司,申請於1981年8月10日,而且大概現在已經到期。針對LZW算法有兩個美國專利:由Victor S. Miller和Mark N. Wegman的美國專利 4,814,746,指派給IBM,原本於1983年6月1日申請,和Welch的美國專利 4,558,302,讓受給Sperry公司,後來為Unisys公司,於1983年6月20日申請。

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

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

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

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

Lempel-Ziv-Welch vs. Ziv-Lempel-Welch[编辑]

雖然LZW縮寫明顯地是意指Lempel、Ziv、和Welch這些發明者,某些人聲稱知识产权是給Ziv為第一位,因此這個方法必須稱為Ziv-Lempel-Welch算法,而不是Lempel-Ziv-Welch算法

外部連結[编辑]