Abstract
本論文探討用在資料壓縮上的 LZW 演算法及其衍生物。資料壓縮是資料 高效率編碼的藝術表現。資料壓縮的目的在於節省資料儲存媒體的使用， 以及降低資料傳輸所需之頻寬。資料壓縮的演算法可分成破壞性(loss)和 非破壞性(lossless)壓縮，如果資料保證能夠完全在解壓縮的過程中還原 回來，則屬於非破壞性壓縮，否則為破壞性壓縮。資料壓縮演算法依其所 使用壓縮原理，主要有統計壓縮法(statistical compression)，和代換 法(susti- tutional compression)兩大類。統計壓縮法是利用資料中各 字元符號出現機率的統計資訊，將資料編碼，被廣泛使用的霍夫曼編碼 法( Huffman coding)便是屬於此類。代換法是將資料中不定長度字串以 單一碼字(codeword)代換，作為編碼。代換法中又以字典壓縮法最為重要 ，所謂字典壓縮法就是編碼時構建一編碼字典，依此作為編碼之依據。字 典壓縮法依其創始人姓名及創始年代，分成 LZ77 和 LZ78兩大類。近來 字典壓縮法因其良好的壓縮效能，已被廣泛的使用在各種資料壓縮的實際 應用上。在各種資料壓縮的演算法中，從 LZ78 衍生而來的 LZW 演算法 ，提出了一個精簡而高效率的非破壞資料壓縮設計。由於 LZW 演算法簡 單分明的架構，後來有許多改良過的資料壓縮演算法都是以 LZW演算法為 基礎發展而來。在本論文中，我們將對各個具代表性的 LZW相關資料壓縮 方法，一一探討其動機、演算法及實際應用上的考量。最後還有一些實驗 ，將 LZW 演算法及其衍生物用在一組經常被引用的測試資料檔案上，結 果可用來做為比較參考之用。