LZW

具体的には、入力情報のあるデータ列に対して附番した「辞書」を作成しておき、再度同じデータ列が出現した場合は、その番号を符号として用いる。

データ列の照合は、最も長いものを優先させる最長一致法と呼ばれる方法を用いている。

LZ78との大きな違いは、LZ78は符号化されたものの中に必ず元の入力データ列そのものが含まれるが、LZWはこれに目をつけ、一文字で構成されるデータ列を前もって辞書に登録することで符号語中に入力データ列が含まれないよう工夫し、常に辞書の番号のみで符号化できるようにして効率を上げた。

LZWは特許のトラブルが多いことでも有名で、米国では2003(平成15)年6月20日に特許が切れるまで、数多くの問題を起こした。

古くはPKWAREがARC(PKPAK)で提訴された事件、最近ではGIFの圧縮のアルゴリズムに関する事件などがある。

特許は日本でも取得されており、1984(昭和59)年6月20日に「デイジタル信号ストリーム圧縮方法及び圧縮装置」(公告番号 平5-68893)として出願され特許が成立、2004(平成16)年6月20日まで特許が有効だった。

GIFで使われるLZWの特許問題である。

いわゆるサブマリン特許と呼ばれるもので、GIF画像については1999(平成11)年後半から、個人でもUnisysに対しライセンス契約を強要するようになり、世界中で大問題となった。

特許の利用契約をした企業製品から作られたGIFならライセンス契約無しでも使用可能だとされたが、「念のためライセンス契約を結ぶ事を推奨」していた。とはいえ、最も安価な契約である「LZW Webライセンス」ですら5000 US$(約50万円)以上した。しかもこの契約は「個人運営、非商用、広告非掲載、アクセス制限なし」の場合に制限され、それ以外の条件ではパテント(特許)契約で、収入に応じたパーセンテージの契約が必要となった。

当然の事ながら、このようなボッタクリに付き合う人は少なく、個人ページではGIF(LZW)が忌避されるようになり、それ以外の圧縮アルゴリズムを使用した形式(PNGやJPEG)へのシフトが進んだ。