LZW(エルゼットダブリュー)とは | 意味や読み方など丁寧でわかりやすい用語解説

LZW（Lempel-Ziv-Welch）は、データを完全に復元できる可逆圧縮アルゴリズムの一つである。データ内に繰り返し現れるパターンを「辞書」と呼ばれるテーブルに登録し、そのパターンの代わりに短いコード（エントリ番号）を記述することでデータ量を削減する。特にGIF（Graphics Interchange Format）画像形式の標準圧縮方式として広く知られており、他にもTIFFやPDFなど様々な場面で利用される。システムエンジニアにとって、データ効率化の基礎となる重要な概念であり、ロスレス圧縮の代表的な手法の一つとして理解しておくべきである。LZWという名称は、このアルゴリズムを開発したアブラハム・レンペル、ジェイコブ・ジフ、テリー・ウェルチの3名の名前に由来する。

LZWアルゴリズムは、1970年代後半にレンペルとジフが開発したLZ77およびLZ78アルゴリズムを基盤として、1984年にテリー・ウェルチによって改良された。LZ77やLZ78がデータストリーム中の繰り返しパターンを検出・置換する仕組みを導入したのに対し、LZWは辞書管理の仕組みをさらに洗練させ、より効率的で高速な圧縮・展開を実現した。

LZWの圧縮処理は、エンコーダ（圧縮側）とデコーダ（展開側）で動的に辞書を構築していく点が特徴である。

エンコーダの動作について説明する。圧縮を開始する際、辞書にはまず、すべての単一バイト文字（例えばASCIIコードの0から255までの各文字）が初期エントリとして登録される。エンコーダは入力データを1文字ずつ読み込みながら、現在処理中の文字列パターン（プレフィックス）に次の文字を連結し、それが辞書に存在するかどうかを確認する。もし連結された新しい文字列が辞書に存在する場合、その文字列を新たなプレフィックスとし、読み込みを続ける。もし連結された新しい文字列が辞書に存在しない場合、それまでのプレフィックス（辞書に存在する最長のパターン）に対応するコードを出力する。その後、辞書に存在しなかった新しい文字列（プレフィックスと次の文字を連結したもの）を新たなエントリとして辞書に追加する。そして、次の文字を新たなプレフィックスとして処理を再開する。このプロセスを繰り返すことで、データ内で繰り返し現れるより長い文字列パターンが動的に辞書に登録され、そのパターンが出現した際には、短いエントリコードが出力されるためデータ量が削減される。

次にデコーダの動作について説明する。展開側では、エンコーダが出力したコード列を受け取る。デコーダもエンコーダと同様に、初期辞書として単一バイト文字のエントリを持つ。デコーダは受け取ったコードを順に処理し、それが指す文字列を辞書から取り出して出力する。LZWの巧妙な点は、エンコーダが新しい文字列を辞書に追加するのと同じロジックで、デコーダも受け取ったコードから文字列を推測し、新しい文字列パターンを動的に辞書に追加していくことである。これにより、エンコーダとデコーダは明示的な辞書情報を送受信することなく、同じ内容の辞書を同期的に構築できる。デコーダがコードXとそれに続くコードYを受け取った場合、コードXが指す文字列S1と、コードYが指す文字列S2の最初の文字を組み合わせた新しい文字列を辞書に追加するというルールが一般的に適用される。この自己構築型の辞書によって、効率的なデータ展開が可能となる。

LZWアルゴリズムでは、辞書に登録されるエントリの数に応じて、出力するコードのビット長が変化する。初期状態では通常9ビットのコードが使われるが、辞書エントリが増えて表現できる数（512個）を超えると、自動的に10ビット、11ビットとコード長を拡張していく。一般的には最大で12ビットまでのコード（4096個のエントリ）が使われることが多い。これにより、より多くの繰り返しパターンを効率的に表現し、高い圧縮率を達成できる。

LZWは、データを元の状態に完全に復元できる「ロスレス圧縮」である点が大きな特徴である。これにより、画質や情報の一切の劣化が許されない画像やドキュメントデータの保存に適している。圧縮処理と展開処理が比較的シンプルで高速に実行できるため、リアルタイム性が求められる環境でも利用しやすい。しかし、その圧縮率はデータの重複パターンに大きく依存する。完全にランダムなデータに対してはほとんど圧縮効果が得られず、文字や色などの繰り返しパターンが多数存在するデータで高い圧縮率を発揮する。

過去には、LZWアルゴリズムの実装に関連する特許問題が複雑に絡み、特にGIF形式の普及に一時的な影を落とした時期があった。この特許は既に失効しているため、現在ではLZWアルゴリズムは自由に利用可能である。主な用途としては、前述のGIF画像形式が代表的である。GIFは最大256色という色数制限があるものの、Web上でアニメーションを表現できる唯一のロスレス圧縮形式として、現在でも広く利用されている。その他にも、TIFF（Tagged Image File Format）や一部のPDFファイル、PostScriptファイルなどで内部的にLZW圧縮が用いられている場合がある。