Lempel–Ziv–Welch
デコーディングアルゴリズムは以下の通り。
辞書を初期化する(エンコーディングの1と同じ)
入力からコードを1つ読み込み、入力から削除する
そのコードに対応する文字列Wを辞書から得る
出力にWを送出する
入力から次のコードを読み込む
次のコードに対応する文字列の最初の文字sをWに付け足したW + sを辞書に追加する
2に戻る
LZWは1984年に発表された。当初スペリー社が特許を保有していた。のちスペリー社はバロース社と合併し1986年にユニシス社となり、本アルゴリズムの特許権もユニシス社に引き継がれた。
前述の通りGIF画像の圧縮に用いられており、その特許料に関するユニシス社の姿勢が問題となった。詳細はGIF特許問題を参照。
日本では1984年6月20日に特許が出願され、2004年6月20日に期限切れとなった。以下、日本の特許庁産業財産権情報より:
発明の名称:圧縮装置および圧縮方法
出願日:1984年6月20日 出願番号:特許出願平7-341868
公開日:1996年9月13日 公開番号:特許公開平8-237138