LZ77(エルゼットななじゅうなな)とは | 意味や読み方など丁寧でわかりやすい用語解説

LZ77は、1977年にエイブラハム・レンペルとジェイコブ・ジヴによって発表された、可逆データ圧縮アルゴリズムの一つである。その名称は、考案者であるLempelとZivの頭文字と、発表年である1977年に由来する。このアルゴリズムは、辞書式圧縮と呼ばれるカテゴリに分類され、データ内に繰り返し出現するパターンを見つけ出し、それをより短い参照情報に置き換えることで圧縮を実現する。具体的には、すでに出現したデータ列（辞書）へのポインタと一致長で表現する。LZ77は、それ自体が直接使われることは少なくなったものの、その基本概念は後続の多くの圧縮アルゴリズムに引き継がれている。例えば、ZIPやGZIP、PNG画像フォーマットなどで広く利用されているDeflateアルゴリズムは、LZ77の改良版であるLZSSとハフマン符号を組み合わせたものであり、LZ77は現代のデータ圧縮技術の基礎を築いた非常に重要なアルゴリズムであると言える。

LZ77アルゴリズムの詳細な動作原理を理解するためには、「スライディングウィンドウ」という概念が中心となる。スライディングウィンドウとは、圧縮対象のデータを処理するために設けられた、固定長のバッファ領域のことである。このウィンドウは、データストリームの先頭から末尾に向かってスライドするように移動していく。スライディングウィンドウは、さらに二つの部分に分割される。一つは「検索バッファ」であり、もう一つは「前方バッファ」である。検索バッファは、ウィンドウ内で現在処理している位置よりも前にある、すでに処理済みのデータを保持する領域である。この部分が、繰り返しパターンを探すための「辞書」として機能する。一方、前方バッファは、これから圧縮処理を行う未処理のデータを保持する領域である。

圧縮プロセスは、前方バッファの先頭から始まるデータ列に注目し、そのデータ列と最も長く一致する文字列を検索バッファ内から探し出すことから始まる。もし検索バッファ内に一致する文字列が見つかった場合、その一致箇所の情報と、一致しなかった次の1文字をセットにして出力する。この出力される情報の組は、通常「オフセット、レングス、リテラル」の三つ組の符号で構成される。オフセットは、現在位置から見て検索バッファ内のどれだけ手前に一致文字列があるかを示す距離である。レングスは、一致した文字列の長さを示す。リテラルは、最長一致した文字列の次に続く1文字である。この三つの情報を出力した後、スライディングウィンドウを「レングス + 1」文字分だけデータストリーム上で進める。もし、前方バッファの先頭の文字が検索バッファ内に全く見つからなかった場合は、一致長が0であることを示す特別な符号（例えば、オフセット0、レングス0）と、その見つからなかった1文字（リテラル）を出力し、ウィンドウを1文字分進める。この処理を前方バッファが空になるまで、つまりデータの末尾に到達するまで繰り返すことで、元のデータは符号の列に変換され、圧縮が完了する。

伸長（解凍）プロセスは、この圧縮プロセスを逆に行う。伸長側も圧縮側と全く同じサイズのスライディングウィンドウを用意する。圧縮データから三つ組の符号を一つずつ読み込み、元のデータを復元していく。符号が「オフセット、レングス、リテラル」であった場合、まずオフセットで指定された距離だけウィンドウ内を遡り、その位置からレングスで指定された長さの文字列をコピーして出力する。その後、リテラルとして記録されている1文字を出力する。こうして復元されたデータは、同時にスライディングウィンドウの検索バッファにも追加されていき、次の符号を処理するための辞書として利用される。一致が見つからなかったことを示す符号を受け取った場合は、単にリテラルを出力する。この手順をすべての符号に対して繰り返すことで、元のデータが完全に復元される。

LZ77の大きな利点は、伸長処理が非常に高速であることだ。伸長側は符号を解釈して、指定された場所からデータをコピーするだけの単純な処理で済むため、計算負荷が低い。また、辞書となるデータをファイルに別途埋め込む必要がなく、データ自体を辞書として利用するため効率的である。一方で、圧縮時には検索バッファ内から最長一致文字列を探す必要があり、この探索処理に時間がかかるため、圧縮速度は比較的遅くなる傾向がある。また、データの先頭部分では検索バッファが空か、あるいは非常に短いため、繰り返しパターンを見つけることができず、圧縮率が低くなるという特性も持つ。これらの点を改良したLZSSや、さらに他の符号化方式と組み合わせたDeflateのような派生アルゴリズムが開発され、実用性を高めていった。