LZ78とは何か？辞書生成型可逆圧縮アルゴリズムの基本と実装ポイント

2025年11月22日 最終更新日時 : 2025年11月22日 エバープレイ編集部

LZ78とは — 辞書生成型の可逆圧縮アルゴリズム

LZ78（エルゼット・セブンティエイト）は、1978年に Abraham Lempel と Jacob Ziv によって提案された可逆（可逆的）な辞書ベース圧縮アルゴリズムです。逐次的に出現する「新しい語（フレーズ）」を辞書に追加していき、出力は既存辞書のインデックスと新しい文字の組で表現されます。LZ78 は、LZ77 と並ぶ Lempel–Ziv ファミリーの代表的手法の一つであり、後に発展した LZW（Welch による改良）など多くの派生手法の基礎になりました。

歴史的背景と位置づけ

  • 1977年の LZ77（Lempel & Ziv）提案に続き、1978年に LZ78 が発表されました（“Compression of Individual Sequences via Variable-Rate Coding”, IEEE Trans. Inf. Theory, 1978）。
  • LZ78 は「入力データから逐次辞書を生成する」方式で、LZ77 が「過去の窓から一致を参照する」方式と対照的です。
  • LZ78 の考え方は、その後の LZW（Welch, 1984）のように実用化され、多くの圧縮方式に影響を与えました。例えば LZW は GIF 画像形式で広く使われました（特許問題もありました）。

基本アイデア（直感）

LZ78 のエンコーダは、現在までに見たことのあるフレーズ（文字列）を辞書に登録し、入力を処理するごとに「既知のフレーズのインデックス」と「次の1文字」を出力します。辞書はエンコード中に自動的に拡張されるため、事前に固定辞書を持つ必要はありません。デコーダは同じ手順で辞書を再構築できるため、出力列から元のデータを正確に復元できます。

アルゴリズムの動作（エンコード）

代表的な処理の流れを簡潔に示します。

初期：辞書に空列（インデックス0）を用意
入力の先頭から現在位置を p とする
while (まだ入力が残っている) {
  w = 最長の辞書内フレーズが入力の位置pにマッチする文字列
  c = 次の1文字（wの直後にある文字、存在しない場合は EOF 記号）
  出力：(index(w), c)
  辞書に新エントリ：w + c を追加（新しいインデックス）
  p を w の長さ + 1 だけ進める
}

ここで index(w) は辞書中の w のインデックス（w が空文字列の場合は 0）です。出力は通常、(index, character) のペア列としてビット列に詰めて記録します。

デコード手順

デコーダはエンコーダと同じ初期辞書（空列のみ）から開始し、受け取った各ペア (i, c) を順に処理します。i が指す辞書エントリを取り出して w とし、出力に w + c を追記します。そして辞書に w + c を新規エントリとして追加します。これを繰り返すことで元のデータ列を復元できます。

簡単な例（ステップ実演）

入力: "a b a a b a b a"（空白は読みやすさのため）

  • 開始：辞書 = {0: ""}
  • 最初の文字 a：w = ""（辞書にない）、c = 'a' → 出力 (0,'a')、辞書追加 "a"→1
  • 次は b：w = ""、c='b' → 出力 (0,'b')、辞書追加 "b"→2
  • 次は "a a" の先頭：w='a'（インデックス1）、c='a' → 出力 (1,'a')、辞書追加 "aa"→3
  • 次は 'b'：w='b'（2）、c='a' → 出力 (2,'a')、辞書追加 "ba"→4
  • 続けて 'b','a'... と処理

このように「既知のフレーズを参照して次の1文字を付ける」ことを繰り返し、辞書を拡張していきます。

LZW との違い（派生・比較）

  • LZW（Welch, 1984）は LZ78 を改良し、出力を「(index)」のみのコード列に変換する方式です。LZW は最初にすべての単一記号を辞書に登録しておき、以後は辞書インデックスだけを出力します。これにより (index, char) ペアをビット単位で効率良くパックできる利点があります。
  • LZ77 は「過去のバッファ（スライディングウィンドウ）」からの距離と長さで参照する方式で、LZ78 の辞書生成方式とは根本的に異なります。ただし双方とも「再帰的に構築される辞書的構造」を使う点で共通しています。

実装上の注意点・データ構造

辞書の管理は性能に直結します。典型的には次のような構造が用いられます。

  • トライ（prefix tree）：フレーズ検索に適しており、最長一致検索が効率よく行える。
  • ハッシュ表：ハッシュによるフレーズの登録・検索で高速化。メモリと衝突処理が課題。
  • 配列ベース：インデックスからフレーズを再構築する際に使う（デコーダ側）。

メモリ使用量は辞書の大きさに比例して増えるため、実装では辞書サイズの上限を設けたり、一定サイズを越えたらリセット（辞書のクリア）するなどの対策を取ることが多いです。また、ビット詰め（可変長コード）や語幅の拡張（初めは 9bit、満杯で 10bit に拡張、など）といった実装上の工夫も一般的です。

性能と理論的性質

  • LZ78（および LZ77）は、統計が未知のソースに対しても漸近的にエントロピー率に収束する「普遍性（universal）」を持つことが示されています（stationary ergodic sources に対して）。
  • 実用上の圧縮率はデータの種類（反復性、自己相似性、語彙の広さ）に大きく依存します。短いデータでは辞書オーバーヘッドが目立ち、長いデータでより有利になります。
  • 計算量は適切なデータ構造を使えば入力長に対してほぼ線形（平均的な O(n)）です。ただし最悪時のメモリ使用量は辞書に依存して大きくなり得ます。

利点・欠点（実用面）

  • 利点：
    • ストリーミング処理が可能（逐次辞書構築）でデコーダは出力を見ながら同じ辞書を再構築できる。
    • 事前の統計モデルが不要で適応的に動作する。
    • シンプルで理解しやすく、多くの派生や最適化が存在する。
  • 欠点：
    • 辞書サイズ・メモリ管理の課題。長い入力で辞書が巨大になる可能性。
    • 短い入力や高エントロピーデータでは圧縮効果が低い／オーバーヘッドが大きい。
    • エラー耐性が低く、ビット反転などで同期が崩れると再同期が難しい（フォーマット設計で対処が必要）。

実務での利用例・派生技術

  • LZW（LZ78 に影響を受けた派生）は GIF、UNIX compress（歴史的に）などで使われました（特許問題に注意）。
  • LZ ベースの手法は多数派生し、例えば LZSS、DEFLATE（LZ77 と Huffman の組合せ）、LZMA（Lempel–Ziv–Markov）など現代の多くの圧縮形式の基礎的アイデアとなっていますが、DEFLATE は LZ77 ベースです。
  • 組み込み用途や教科書的実装として LZ78 系の実装が教育・研究でよく使われます。

実装上のヒント（実用メモ）

  • 可変長コードを使う場合はビット詰めルールを明確に定義する（語幅の増加、リセット時の同期など）。
  • 辞書サイズ制限（最大エントリ数）とリセット戦略を決める。フラッシュやメモリが限られる環境では必須。
  • 辞書登録のキー（親インデックス＋文字）を効率よく管理するためにハッシュやコンパクトトライを活用する。
  • データの特性に応じて前処理（バイト→シンボルの分割やランレングス符号化）を組み合わせると圧縮性能が向上する場合がある。

まとめ

LZ78 は「動的に辞書を構築する」シンプルかつ強力な可逆圧縮アルゴリズムです。エンコーダとデコーダが同じ手順で辞書を再現することで元のデータを復元でき、普遍的な圧縮手法として理論的にも実用的にも重要な位置を占めます。実装では辞書管理・メモリ制御・ビットパッキングなどの細部が性能を左右します。LZ78 の基本概念を理解することは、現代の多数の LZ 系圧縮技術（LZW、LZSS、LZMA 等）を理解・実装する上で非常に役立ちます。

参考文献

カテゴリー
IT
前の記事
This Heat徹底解説：代表作『This Heat』『Deceit』を軸にしたレコード選びと聴きどころNew!!
2025年11月22日
次の記事
筋肉少女帯の魅力を徹底解剖：歌詞世界・音楽性・演劇的ライブと入門ガイドNew!!
2025年11月22日