LZW 【Lempel-Ziv-Welch】 LZW法 / LZW圧縮 / LZWアルゴリズム

概要

LZW（Lempel-Ziv-Welch）とは、1984年に米スペリー(Sperry)社のテリー・ウェルチ(Terry A. Welch)氏が発表した汎用のデータ圧縮アルゴリズム。1978年にエイブラハム・レンペル(Abraham Lempel)氏とジェイコブ・ジブ(Jacob Ziv)氏が考案したLZ78(Lempel-Ziv 78)法を同氏が改良したもの。

LZ78は辞書圧縮と呼ばれる方式の一つで、圧縮対象のデータを端から読み込んでいき、すでに読込済みの部分の一覧（これを辞書になぞらえている）の中に一致する箇所が発見されたら、その位置と（一致する）長さで置き換えるという手順を繰り返してデータを圧縮していく。

Welch氏はLZ78の辞書の構築や管理の手法を工夫し、効率よく圧縮するよう改良した。圧縮率だけでなく、少ない計算回数で高速に圧縮できることも重視しているとされる。「LZW」という名称はLempel氏、Ziv氏および自身の名前（Welch）の頭文字を繋ぎ合わせて名付けられた。

特許問題

LZW方式は画像圧縮形式のGIFやTIFF、UNIX系OSのcompress コマンドおよびファイル形式、通信プロトコルや文書ファイル形式などで採用され、広く普及した。スペリー社はLZWの特許を世界各国で取得し、1986年に同業のバロース（Burroughs）社と合併してユニシス（Unisys）社となったが、当初はGIF形式などに対し積極的な特許権の行使は行ってこなかった。

1990年代に入りインターネット上で同形式が急速に普及すると、それまでの方針を一転して対応ソフトウェアの開発者に特許料を請求し始めた。この事件は「Unisys LZW特許問題」「GIF特許問題」などと呼ばれる。

この方針転換はインターネット利用者の大きな反発を招き、対応フォーマットからGIF形式を外すなどの動きが広がった。特許技術を用いずに画像を扱うことができる代替形式として「PNG」フォーマットの開発と普及が進んだ。その後、2004年までに各国のLZW特許は期限切れとなり、以降は再び自由にGIF形式を利用できるようになっている。

(2023.5.9更新)