LZ77とLZ78の違い

今回は、LZ77とLZ78がどう違うのかについて話してみたい。

zip、gzip、zstdのような圧縮ツールを使いながら、その中の辞書式圧縮がどう動くのか気になっていた開発者に向けた記事だ。最後まで読めば、二つのアルゴリズムが辞書を扱う方法の違いと、今日の主流の圧縮ツールがどちらの系統から来ているのかを説明できる。

ビルド成果物をどの形式で圧縮するか比べていくと、結局この二つのアルゴリズムまでさかのぼることになる。

辞書ベース圧縮

可逆圧縮（Lossless Compression）は、元のデータを完全に復元できる圧縮方式だ。画像や音声で使われる非可逆圧縮（Lossy Compression）とは異なり、展開後のデータは元データと1ビットも違わない。ソースコードやビルド成果物のようにデータ整合性が重要な場合は、必ず可逆圧縮を使う必要がある。

可逆圧縮の中心的な考え方は、データに存在する統計的な冗長性を利用することだ。繰り返されるパターンを短い表現に置き換えれば、全体のサイズを減らせる。

その中でも、辞書ベース（Dictionary-Based）方式は可逆圧縮で広く使われるアルゴリズム群だ。ここでいう辞書とは、前に見たデータをもう一度指し示せるようにしておく仕組みだ。その仕組みが通ってきたデータそのものなのか、別に積み上げたリストなのかが、LZ77とLZ78を分ける。Jacob ZivとAbraham Lempelが1977年にIEEE Transactions on Information Theoryで発表した論文で提案したLZ77と、二人が翌1978年に続けて発表した論文のLZ78がこの系譜の始祖だ。二人の姓から一文字ずつ取って「LZ」と呼ばれる。以後に登場した辞書ベース圧縮アルゴリズム（DEFLATE、LZMA、LZ4、Zstdなど）は、この二つにルーツを持つ。

簡単な例で考えてみよう。「Linux」という単語が100回繰り返されるなら、2回目からは原文の代わりに「前に見たあの断片」を指す短い参照を書く。参照が原文より短ければ、全体のサイズが小さくなる。

では、LZ77とLZ78は具体的に何が違うのだろうか。

LZ77：スライディングウィンドウ方式

LZ77は明示的な辞書を別に作らず、入力ストリームの一定範囲そのものを辞書として使う。この範囲をスライディングウィンドウと呼ぶ。処理した分だけウィンドウが前へずれていくことから付いた名前だ。

ウィンドウは二つの領域に分かれる。

• 検索バッファ（Search Buffer）：すでに処理された直前までのデータ。辞書の役割を担う。
• ルックアヘッドバッファ（Look-ahead Buffer）：まだ処理されておらず、これから圧縮するデータ。

アルゴリズムは、ルックアヘッドバッファの先頭部分が検索バッファのどこかに現れたことがあるかを探す。同じパターンが見つかると、その一致を（距離、長さ、次の文字）というタプルで符号化する。距離は一致の開始位置まで何文字戻るかを、長さは一致が何文字続くかを表す。元の論文は最初の値をバッファ内の位置として記し、今の実装は同じ情報を距離として記す。

たとえば、"banana_banana"という文字列をこの記事の後半に載せた学習用エンコーダーで圧縮すると、LZ77のトークンが五つ出る。(0,0,b) (0,0,a) (0,0,n) (2,3,_) (7,5,a)だ。最初の三つは初めて見る文字なので、一致なしで次の文字だけを持つ。二つ目の"banana"は最後のトークン(7,5,a)一つで処理される。「7文字戻って5文字をコピーし、aを付けよ」という意味だ。6文字すべてをコピーしないのは、このエンコーダーが入力の最後の文字を常に次の文字の位置に残すからだ。

(2,3,_)では、長さ3が距離2より長い。デコーダーはbanまで書いた状態で2文字前のaからコピーを始め、3文字目をコピーするときには今書いたばかりのaをもう一度読む。そのためanaが出て、_が付く。1文字ずつ追うと次のようになる。

RFC 1951も同じ動作を明記している。直前の2バイトがX、Yのとき、<length = 5, distance = 2>はX,Y,X,Y,Xを追加する。辞書がそのまま今復元したデータだからこそ成り立つ。

この方式では、辞書を別途保存したり送信したりしない。 デコーダーは展開を進めながら検索バッファを自ら再構築するため、辞書はデータそのものへ暗黙的に組み込まれている。参照は前のデータを指すので、展開は基本的に先頭から順番に進む。ただし、参照が届く範囲はウィンドウまでだ。RFC 1951はDEFLATEの参照を最大32Kバイト前までに制限している。zlibのZ_FULL_FLUSHは圧縮状態をリセットし、前の圧縮データが壊れた場合やランダムアクセスが必要な場合に、その地点から展開をやり直せるようにする。zlib.hは、頻繁に使いすぎると圧縮率が大きく落ちると警告している。

ウィンドウサイズと圧縮率には直接的なトレードオフがある。ウィンドウが大きければ遠く離れたパターンも参照できるため圧縮率は高くなりやすいが、メモリ使用量が増え、調べる候補も多くなるので一致検索もたいてい遅くなる。

LZ78：明示的な辞書方式

LZ78はLZ77と異なり、圧縮を進めながら明示的な辞書を構築する。スライディングウィンドウはない。代わりに、以前見たパターンをインデックス付きの辞書項目として保存し、同じパターンが再び現れたらインデックスへ置き換える。

LZ78が出力する単位は、（辞書インデックス、次の文字）というタグだ。エンコーダーは辞書内で最長一致する項目を探し、そのインデックスと一致を崩した次の文字を組み合わせて出力する。そして 「今一致した項目＋新しい文字」 を新たな辞書項目として追加する。こうして辞書が段階的に成長していく。

同じ"banana_banana"をLZ78で圧縮すると、トークンが八つ出て、辞書には項目が七つ積み上がる。トークンは(0,b) (0,a) (0,n) (2,n) (2,_) (1,a) (3,a) (7,)で、辞書は1:b 2:a 3:n 4:an 5:a_ 6:ba 7:naだ。二つ目の"banana"は、ba、na、naを作る三つのトークンに分かれる。LZ77がトークン一つで済ませた部分だ。LZ78の辞書項目は一度に一文字ずつしか長くならないので、同じ単語を何度も見ないと長い項目はできない。最後の(7,)は、入力が終わって次の文字がない場合だ。このエンコーダーはトークンをビットに詰めないので、トークン数で圧縮率を比べることはできない。

二つのトークン列は下のコードで再現できる。2026-10-08にmacOS 26.6.2、Node v24.16.0でファイルに保存し、node lz.mjsで実行した結果だ。

// LZ77: (거리, 길이, 다음 문자). 가장 긴 일치를 고르고, 겹친 복사를 허용한다
function lz77(s, win = 4096) {
  const out = []
  let i = 0
  while (i < s.length) {
    let best = { d: 0, l: 0 }
    for (let j = Math.max(0, i - win); j < i; j++) {
      let l = 0
      // 입력의 마지막 글자는 매치에 넣지 않고 다음 문자로 남긴다
      while (i + l < s.length - 1 && s[j + l] === s[i + l]) l++
      if (l > best.l) best = { d: i - j, l }
    }
    out.push([best.d, best.l, s[i + best.l]])
    i += best.l + 1
  }
  return out
}
 
// LZ78: (사전 인덱스, 다음 문자). 인덱스 0 은 빈 문자열이다
function lz78(s) {
  const dict = new Map()
  const out = []
  let w = ''
  for (let i = 0; i < s.length; i++) {
    const c = s[i]
    if (dict.has(w + c)) {
      if (i < s.length - 1) { w += c; continue }
      out.push([dict.get(w + c), '']) // 입력이 끝나 다음 문자가 없다
      break
    }
    out.push([w ? dict.get(w) : 0, c])
    dict.set(w + c, dict.size + 1)
    w = ''
  }
  return { out, dict: [...dict.keys()] }
}
 
// 두 디코더 모두 토큰만 받는다. 사전은 전달받지 않는다
function unlz77(tokens) {
  let o = ''
  for (const [d, l, c] of tokens) {
    for (let k = 0; k < l; k++) o += o[o.length - d] // 방금 쓴 글자도 다시 읽는다
    o += c
  }
  return o
}
function unlz78(tokens) {
  const dict = ['']
  let o = ''
  for (const [i, c] of tokens) {
    const entry = dict[i] + c
    o += entry
    dict.push(entry) // 인코더와 같은 순서로 사전을 다시 쌓는다
  }
  return o
}
 
const s = 'banana_banana'
const a = lz77(s)
const b = lz78(s)
console.log('LZ77', a.map(([d, l, c]) => `(${d},${l},${c})`).join(' '), unlz77(a) === s)
console.log('LZ78', b.out.map(([i, c]) => `(${i},${c})`).join(' '), unlz78(b.out) === s)
console.log('사전', b.dict.map((e, k) => `${k + 1}:${e}`).join(' '))

LZ77 (0,0,b) (0,0,a) (0,0,n) (2,3,_) (7,5,a) true
LZ78 (0,b) (0,a) (0,n) (2,n) (2,_) (1,a) (3,a) (7,) true
사전 1:b 2:a 3:n 4:an 5:a_ 6:ba 7:na

二つの方式が分かれるところ

コードの二つのデコーダーはトークンだけを受け取る。つまり、LZ78も辞書を送らない。デコーダーはトークンを読みながらエンコーダーと同じ順序で項目を追加するので、同じ辞書が再び積み上がる。辞書を送信しない点は二つのアルゴリズムの共通点であり、両者が分かれるのは古い内容を忘れる方法だ。LZ77のウィンドウは前へ進みながら古いデータを自然に忘れる。LZ78の辞書は放っておくと大きくなり続ける。元の論文は決まった長さのブロックが終わるたびに辞書を丸ごと空にし、実際の実装は辞書の大きさに上限を設けて、いっぱいになると凍結するか、空にするか、一部の項目を再利用する。

LZ78で最も有名な派生がLZW（Lempel-Ziv-Welch）だ。Terry WelchがLZ78を改良して1984年に発表し、GIF画像形式とUnixのcompressユーティリティ（.Z拡張子）で使われた。どちらの実装も辞書に上限を設けた。GIF89a仕様はコードを最大12ビット（最大値4095）に抑え、辞書を初期状態に戻すClear codeを別に用意している。ncompressのmanページによれば、compressはコード長が-bの上限（既定値16ビット）に達した後は圧縮率を監視し、圧縮率が下がると辞書を捨てて最初から積み直す。

二つの論文は、それぞれのモデルで漸近的最適性を示した。1977年の論文は、LZ77の圧縮率が情報源を事前に知って設計した符号の下限に一様に近づく（"uniformly approaches the lower bounds"）ことを示し、1978年の論文は個別系列（individual sequence）を対象に、LZ78のincremental parsingが漸近的に最適であることを示した。モデルが異なるので、この結果だけで両者を比べることはできない。

LZ77系の子孫

では、現代の圧縮アルゴリズムはどちらから続いているのだろうか。現在使われている主流の圧縮アルゴリズムは、大半がLZ77系の子孫だ。

StorerとSzymanskiの1982年の論文から続くLZSSはLZ77の派生だ。一致が短すぎてポインターが元のデータより長くなる場合は、ポインターの代わりにリテラル（元の文字）をそのまま出す。

DEFLATEはPhil KatzがPKZIP 2のために設計し、1996年にRFC 1951として仕様がまとめられた。RFC 1951はDEFLATEを、LZ77とハフマン符号化（頻度の高いシンボルへ短いビット列を割り当てるエントロピー符号）の組み合わせだと書いている。出力はリテラルと（長さ, 距離）の組が混ざった列で、リテラルと一致の長さを一つのアルファベット（0〜285）にまとめて、一つのハフマン符号で区別する。大半のZIPプログラムが既定で使う圧縮方式、GZIP、PNGはいずれもこのDEFLATEを使う。つまり、日常的に扱う.zip、.gz、.pngファイルの大半はLZ77の直系子孫だ。

LZ77側が主流になった理由を一つに絞ることはできないが、仕様自身が掲げた点の一つは特許だ。RFC 1951は、LZ77の変形にも特許が取られたものが多いと書きつつ、DEFLATE形式は特許にかからない方法で容易に実装できると明記している。PNG仕様は冒頭でPNGを、特許のないGIFの代替形式として紹介する。GIFは先に見たLZWを使う形式だ。

その後に登場したLZMA（7-Zip、XZ）、LZ4、Zstdも、LZ77のスライディングウィンドウの考え方から出発した。LZMAとZstdは一致検索とエントロピー符号化をともに発展させ、LZ4はエントロピー符号化をまったく使わず、バイト単位の形式で速度を選んだ。LZ78系は、LZWの形でGIFのような形式の中に残っている。

おわりに

LZ77とLZ78は、繰り返されるパターンを短い参照に置き換えるという同じアイデアから出発した。どちらも辞書を送らずデコーダーが積み直すが、参照が指す先がすでに通ったデータの位置なのか、別に積み上げた辞書の番号なのかで分かれ、古いものを忘れる方法も違った。DEFLATEを経てLZMA、LZ4、Zstdへと続く主流の圧縮ツールはLZ77側の子孫であり、LZ78側はLZWの形でGIFのような形式に残った。

この系譜が実際の形式選びでどのような違いにつながるのか、つまりZIP、GZIP、ZSTD、XZの速度と圧縮率を比較し、ビルド成果物に何を選ぶかは圧縮アルゴリズムを理解するで扱う。

次に.zipや.gzファイルを展開するとき、その中で「何文字戻って何文字コピーせよ」という指示がやり取りされていることを一度思い出してもらえたらうれしい。