LZW

概念

LZW（Lempel‑Ziv‑Welch）是一種無失真壓縮算法，屬於資料壓縮領域的經典技術。它的核心思想是在壓縮過程中動態建立字典，將重複出現的字串序列以較短的代碼取代，從而實現資料體積的減少。

歷史

1977年，Abraham Lempel與Jacob Ziv首先提出基於字典的LZ77與LZ78方法。此後在1984年，Terry Welch對其進行改進，簡化字典管理並提升效率，形成了今日廣泛使用的LZW算法。

應用

LZW最早被運用於GIF圖像格式的壓縮，後來也被容納於TIFF標記影像以及ZIP壓縮檔案中。由於其實現簡單、壓縮速度快，常在硬碟空間有限的早期桌上出版與網路傳輸中被採用。

運作原理

1. 初始化：建立一個包含所有單一字元的初始字典。
2. 掃描：讀取輸入資料，當遇到字典中已存在的字串時，擴展該字串並繼續匹配；當遇到新字串時，輸出當前匹配的最長字典代碼，並將新字串加入字典。
3. 輸出：以代碼序列替代原始字元，實現壓縮。 解壓時則依據同樣的字典還原原始資料，保證無失真的特性。

影響

LZW的即時字典機制為後續的許多壓縮技術奠定基礎，例如LZMA。它的簡單實現亦成為教學中說明壓縮概念的良好範例。