LZ77アルゴリズム詳解：辞書圧縮の仕組み

結論から言うと：LZ77 はスライディングウィンドウベースの辞書圧縮アルゴリズムです。コア思想は「過去のデータを辞書として使い、重複コンテンツに遭遇したら参照に置き換える」こと。エンコード時には三元グループ (distance, length, next_char) を出力します：distance 文字戻ってマッチを探し、マッチ長が length、その直後の未マッチ文字が next_char です。例えば "abracadabra" の 11 文字は、LZ77 でエンコードするとわずか 5 つの三元グループで表せます（下表参照）。LZ77 は DEFLATE（ZIP/GZIP/PNG）のコア構成要素であり、LZSS/LZMA/LZ4 などの現代圧縮アルゴリズムの共通の祖先です。以下ではスライディングウィンドウの原理から説明し、エンコードプロセスを順に見ていきます。

Huffman エンコードの原理にまだ馴染みがない場合は、先にHuffman エンコード原理：圧縮アルゴリズムの基石詳解をご覧ください。

一、辞書圧縮とは

圧縮アルゴリズムは大きく 2 つの流儀に分かれます：統計エンコード（例えば Huffman エンコード）は文字の出現頻度に応じて可変長のコードを割り当てます；辞書圧縮は「参照」で重複コンテンツを置き換えます。LZ77 は辞書圧縮の流儀に属し、事前に辞書テーブルを構築せず、すでに処理した履歴データを暗黙の辞書として使います——重複コンテンツに遭遇したら、「後方参照ポインタ」で以前に現れた位置を指します。

圧縮流儀	コア原理	代表アルゴリズム	メリット	デメリット
統計エンコード	頻度に応じて可変長コードを割り当て	Huffman, 算術エンコード	エントロピー下限に迫る	長距離の反復が苦手
辞書圧縮	参照で重複コンテンツを置き換え	LZ77, LZW, LZMA	反復パターンに強い	ランダムデータには効果が薄い
混合エンコード	辞書＋統計の 2 段階	DEFLATE, ZSTD	総合力が最も高い	実装がやや複雑
変換エンコード	周波数領域へ変換し量子化	DCT(JPEG), DWT	非可逆圧縮の効率が高い	情報の損失がある

実務で最も普及している圧縮アルゴリズムはほぼすべて「混合エンコード」——まず LZ77 で反復パターンを除去し、その後 Huffman で残差を頻度圧縮します。DEFLATE は LZ77 + Huffman の古典的な組み合わせで、ZIP、GZIP、PNG に広く使われています。

二、LZ77 アルゴリズム原理詳解

LZ77 のコアはスライディングウィンドウ機構です。ウィンドウは 2 つの部分に分かれます：検索バッファ（すでに処理済みの履歴データ）と先読みバッファ（処理待ちのデータ）。エンコード時には先読みバッファから一節を取り、検索バッファ内で最長マッチを探します。見つかれば三元グループを出力し、見つからなければ元文字を出力します。

1. 滑動ウィンドウ構造

スライディングウィンドウのサイズは圧縮効果を直接左右します——ウィンドウが大きいほど、遡って検索できる履歴データが増え、マッチ確率が高まります。アルゴリズムによるウィンドウサイズの差は非常に大きいのです。

アルゴリズム	検索バッファ	先読みバッファ	最大マッチ長	典型シナリオ
LZ77元	数KB	十数バイト	16バイト	教学例
DEFLATE	32KB	258バイト	258バイト	ZIP/GZIP/PNG
LZMA	8MB（設定可）	273バイト	273バイト	7z/xzアーカイブ
LZ4	64KB	制限なし	制限なし	リアルタイム圧縮
ZSTD	8MB（最大1GB）	制限なし	制限なし	現代の汎用用途

2. 三元グループエンコード形式

LZ77 の出力単位は三元グループ (distance, length, next_char) で、3 つのフィールドの意味は下表の通りです。

フィールド	意味	取値範囲(DEFLATE)	エンコードビット数	例
distance	後方参照距離（何文字戻ってマッチを探すか）	1–32768	15 bit	distance=10 → 10 文字前に戻る
length	マッチ長（連続してマッチする文字数）	3–258	8 bit	length=5 → 5 文字マッチ
next_char	マッチ後の次の 1 文字	0–255	8 bit	next_char='d' → ASCII 100

三元グループの巧妙な点は、マッチ終了後に必ず 1 文字の next_char を出力することで、エンコーダーが常に少なくとも 1 文字前進することが保証され、停止しない点です。マッチが見つからない場合（length=0）は、distance と length がともに 0 となり next_char のみを出力——実質的に元文字のそのまま保存に退化します。

3. マッチ検索戦略

マッチ検索は LZ77 の性能のボトルネックです——先読みバッファから一節を取り、検索バッファ内で最長マッチを探します。素朴な検索は O(n×m) の計算量になるため、実際の実装ではハッシュテーブルや接尾辞木で高速化します。

検索戦略	データ構造	計算量	メモリ消費	典型適用
素朴な検索	なし	O(n×m)	低い	教学例
ハッシュチェーン	ハッシュテーブル＋リンクリスト	O(n)平均	低い	zlib(DEFLATE)
ハッシュバケット	ハッシュテーブル＋配列	O(1)平均	中	LZ4
接尾辞木	接尾辞木／接尾辞配列	O(n)最悪	高い	LZMA

三、実戦事例："abracadabra"エンコード演示

LZ77 で "abracadabra"（11 文字）を完全にエンコードしてみます。初期状態では検索バッファは空で、先読みバッファには文字列全体が入っています。位置ごとに走査し、履歴データから最長マッチを探します。

原文： a b r a c a d a b r a

エンコードプロセス：

ステップ	現在位置	先読みコンテンツ	検索バッファ内の検索	出力三元グループ	説明
1	位置1	abracadabra	空、マッチなし	(0, 0, 'a')	最初の文字、そのまま出力
2	位置2	bracadabra	"a"はあるが"b"にマッチなし	(0, 0, 'b')	初出、そのまま出力
3	位置3	racadabra	"ab"はあるが"r"にマッチなし	(0, 0, 'r')	初出、そのまま出力
4	位置4	acadabra	"abr"の中に"a"あり	(0, 0, 'a')	"a"は出現するが後続のマッチなし
5	位置5	cadabra	"abra"の中に"c"なし	(0, 0, 'c')	初出、そのまま出力
6	位置6	adabra	"abrac"の中に"a"あり	(0, 0, 'a')	"a"はマッチするが後続なし
7	位置7	dabra	"abraca"の中に"d"なし	(0, 0, 'd')	初出、そのまま出力
8	位置8	abra	7 文字戻って "abra" にマッチ	(7, 4, end)	"abra" の 4 文字にマッチ

エンコード効率の比較：

エンコード方法	出力単位数	1単元あたりbit	合計bit	vs元の節約率
ASCII原文	11文字	8	88	—（基準）
LZ77(マッチ最適化なし)	8三元グループ	31（平均）	248	-182%（膨張）
LZ77(フラグビット最適化)	8単元	12（平均）	96	-9%（わずかに膨張）
LZ77+Huffman	8単元	4.5（平均）	36	59%

結果分析： 素の LZ77 では短い文字列はかえって膨張することがあります（三元グループが元文字より多くの領域を占めるため）。これが LZ77 が通常 Huffman エンコードと組み合わせて使われる理由であり、DEFLATE はまさに LZ77 + Huffman です。"abracadabra" の例では、位置 8 の "abra" マッチ（distance=7, length=4）が重要な圧縮ポイントで、4 文字を 1 つの三元グループで表しています。より長く、反復パターンの多いテキスト（コードファイルやログなど）では、LZ77 の圧縮効果はより顕著になります。

四、LZ77 の変種と現代的な進化

LZ77 は 1977 年の提案後、大量の変種を派生させました。各変種は特定のシナリオに向けて最適化されています。以下の表で主流の LZ77 ファミリーを比較します。

アルゴリズム	主な改良	圧縮率	圧縮速度	解凍速度	典型的な用途
LZ77(元)	三元グループエンコード	低い	遅い	中	教育用
LZSS	フラグビットでマッチ/リテラルを区別	中	中	速い	初期のシステム
DEFLATE	LZSS+Huffmanの2段階	中高い	中	速い	ZIP/GZIP/PNG
LZMA	大きなウィンドウ+レンジエンコード+最適パース	高い	遅い	中	7z/xzアーカイブ
LZ4	圧縮率を犠牲に極限の速度を確保	低い	極めて速い	極めて速い(4GB/s)	リアルタイム/カーネル
LZW	明示的な辞書テーブル(スライディングウィンドウではない)	中	速い	速い	GIF/TIFF
ZSTD	LZ77変種+FSE+辞書プリセット	高い	速い	極めて速い	現代の汎用用途

進化のトレンドから見ると、現代のアルゴリズム（ZSTD、Brotli）は高い圧縮率を保ちながら速度を大幅に向上させ、徐々に DEFLATE に代わって新世代の標準となりつつあります。しかし LZ77 のコア思想——スライディングウィンドウによる辞書参照——は変わらず、すべての変種はこの基礎の上に築かれています。

シナリオ	推奨アルゴリズム	理由	圧縮率参照
ファイルアーカイブ	LZMA(xz)	圧縮率最優先、速度は度外視	70%–85%
汎用圧縮	ZSTD	圧縮率・速度の両立	60%–80%
リアルタイム転送	LZ4	解凍速度4GB/s、遅延が極めて小さい	50%–65%
Web転送	DEFLATE/GZIP	互換性が最も良く、すべてのブラウザーが対応	50%–70%
画像形式	DEFLATE(PNG)	可逆圧縮、グラフィック系に適する	50%–75%
メモリ上のデータ	LZ4	CPU負荷が低く、高頻度の圧縮に適する	50%–65%

PNG 形式における DEFLATE の具体的な応用については、PNG 圧縮原理詳解を参照してください。可逆圧縮と非可逆圧縮の違いについては、可逆圧縮 vs 非可逆圧縮：コアの違いを参照してください。

五、よくある質問FAQ

Q1：LZ77アルゴリズムとは？

LZ77 はスライディングウィンドウベースの辞書圧縮アルゴリズムで、Lempel と Ziv が 1977 年に提案しました。コア思想は：これまで処理したデータを辞書とし、重複コンテンツに遭遇したら (distance, length, next_char) の三元グループで元データを置き換えることです。distance は後方参照距離、length はマッチ長、next_char はマッチ後の次の 1 文字を表します。LZ77 は DEFLATE（ZIP/GZIP/PNG）のコア構成要素であり、LZSS/LZMA/LZ4 などの現代アルゴリズムの祖先でもあります。

Q2：LZ77のスライディングウィンドウとは？

スライディングウィンドウは LZ77 のコアデータ構造で、検索バッファ（処理済みの履歴データ）と先読みバッファ（処理待ちのデータ）に分かれます。エンコード時には先読みバッファから一節を取り、検索バッファ内で最長マッチを探します。典型的なウィンドウサイズは 32KB（DEFLATE 標準）で、ウィンドウが大きいほどマッチ確率は上がりますが、メモリ消費も増えます。ウィンドウサイズは最大後方参照距離 distance の上限を決めます。

Q3：LZ77 と LZ78 の違いは？

LZ77 はスライディングウィンドウを暗黙の辞書として使い、マッチした内容は直接履歴データを参照し、辞書を別途保存しません；LZ78 は明示的な辞書テーブルを使い、すでに見た文字列に番号を付けて辞書項目として保存し、エンコード時には辞書インデックスを出力します。LZ77 は局所的な反復のあるデータ（テキストなど）に向き、LZ78 は全局的な反復のあるデータに向きます。実務では LZ77 の後継（DEFLATE/LZMA/LZ4）が LZ78 の後継（LZW）よりはるかに普及しています。

Q4：LZ77、LZMA、LZ4 のうち圧縮率が最も高いのは？

圧縮率の順は：LZMA > LZ77（DEFLATE）> LZ4。LZMA はより大きなウィンドウ（デフォルト 8MB）、より優れたマッチアルゴリズムとレンジエンコードにより圧縮率が最も高い一方、速度は最も遅い；DEFLATE は 32KB ウィンドウ + Huffman で圧縮率・速度ともに中程度；LZ4 は圧縮率を犠牲にして極限の速度を狙い、圧縮率は最も低いが解凍速度は 4GB/s に達します。選定はシナリオ次第：アーカイブには LZMA、汎用には DEFLATE/ZSTD、リアルタイムには LZ4。

まとめ

LZ77 は辞書圧縮アルゴリズムの祖で、コア原理は「スライディングウィンドウ＋三元グループ参照」です：履歴データを暗黙の辞書とし、重複コンテンツに遭遇したら (distance, length, next_char) の三元グループを出力します。素の LZ77 は短いテキストでは膨張することがありますが、Huffman エンコードと組み合わせたもの（DEFLATE）が ZIP/GZIP/PNG の標準圧縮方式となりました。現代の変種では、LZMA は極限の圧縮率を、LZ4 は極限の速度を、ZSTD は両方のバランスを追求しています。

LZ77 を理解するうえでの重要ポイントは 3 つ：1）スライディングウィンドウがマッチ範囲を決める（DEFLATE 32KB、LZMA 8MB）、2）三元グループが基本のエンコード単元（後方参照＋長さ＋次の文字）、3）マッチ検索戦略が性能を決める（ハッシュチェーンが最速、接尾辞木が最強）。LZ77 + Huffman の混合エンコードは、現代の可逆圧縮の黄金基準です。