23. 印刷格物致知
          23.6. 壓縮演算法
 23.6.2. LWZ 壓縮

LZW(Lempel-Ziv-Welch)是跟隨著開發此壓縮演算法的科學家 Abraham Lempel, Jakob Ziv 與 Terry Welch 命名,這是一個『基於字典』的無失真壓縮演算法。基於字典演算法掃描文件中出現一次以上的序列資料,這些序列資料儲存於壓縮文件內的字典內,每次出現重複性資料時只要替換為參照字典的索引即可。

Lempel 和 Ziv 發表了一系列論文描述說明各種不同的壓縮演算法。第一個演算法在 1977 年發表,因此它被稱為:LZ77;這種壓縮演算法將字典保持於其資料本身內。

假設你要壓縮以下字符串的文字:"the quick brown fox jumps over the lazy dog.";其中 'the' 這個詞發生兩次,所以這個資料可以壓縮成:"the quick brown fox jumps over << lazy dog.",其中 "<<" 是一個指向最前面 4 個字符的指標。

1978年 Lempel 和 Ziv 出版了第二個文件,闡述了類似的演算法,現在被稱為 LZ78。該演算法將字典獨立保持。以上述的例子來說,重複的 'the' 將被編入索引,假設該索引是*,則壓縮後的字串變成:"* quick brown fox jumps over * lazy dog.",這與實用上還很遙遠,但是它透過片語取代舉例說明壓縮方法。

實用上取代的不一定是一個單字,也可以是幾個字組成的片語,字典基礎的壓縮會以標記(token)來取代片語(phrase);片語的選取法則將影響字典的大小與取代的重複次數,各種變異型大都是在此問題上做文章;如果標記的位元數量是少於片語所需的位元數目,那麼壓縮就如此產生。

LZW 如何工作

1984 年,特里韋爾奇 (Terry Welch) 正致力於研究一種用於高性能磁盤控制器的壓縮演算法。他制定了一個基於 LZ78 演算法改良的相當簡單演算法,這就是現在所謂的 LZW 。

LZW 壓縮法是將字串替換為單一代碼,它不對輸入的字串預做任何分析,相反地,它只是對每一個新發生的字串添增加到字串表;當一串字母被替換成單一個代碼時就形成了壓縮。

LZW 演算法輸出的代碼可以是任意長度,但是必須比單一個字元 (single character) 來的長,最前面的 256 個碼(使用八位元字母)預設分配給標準字體集。舉例來說,如果壓縮程式使用到 12 位元代碼,則代碼 0-255 分配指示個別位元組,而代碼 256-4095 指示字典內的各字串。

在大部份的應用,LZW 壓縮比當時已有且廣為人之的方法提供一個比較好的壓縮率。它變成電腦上第一個被廣泛使用在一般目的資料壓縮的方法。在大的英文文本中,一般它可以壓縮到大約原來大小的一半。其他的資料種類在很多情況下也相當的有用。

優點和缺點

  • LZW 壓縮法最適合的文件內載有大量的重複數據,文字與黑白單色圖片是最佳範例;反過來例如已經壓縮過的文件的,幾乎不包含任何重複的信息,用 LZW 壓縮過後甚至會比原來更大!
  • LZW 壓縮速度快
  • 某些應用下使用 LZW 壓縮演算法需要付授權使用費(見下文)

LZW 壓縮使用於哪裡?

LZW 壓縮被用於多種檔案格式:

  • TIFF 檔案格式
  • GIF 檔案格式

備註

對於 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 檔但是不能寫入。

多年來他們的擁有者(Unisys 公司)要求任何使用他們的演算法公司付版稅,這已嚴重阻礙了 LZW 壓縮的流行。

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

Idea associations
Table of contents