データ圧縮の仕組み入門 - ハフマン符号・LZ77・gzip/Brotli/Zstandard

ファイルを ZIP にすると小さくなり、Web ページは gzip や br で転送量を減らして届きます。ではなぜデータは縮むのか、そしてなぜどんなデータでも縮むわけではないのか。この記事では、冗長性とエントロピーという原理から、ハフマン符号や LZ77 といった中核アルゴリズム、gzip・Brotli・Zstandard など実世界のフォーマット、HTTP コンテンツ圧縮の実務までを、RFC と原論文に沿って整理します。バイト表現そのものについては文字コードと UTF-8 の記事が前段になります。

なぜデータは圧縮できるのか

圧縮できる根拠は冗長性（redundancy）です。多くのデータには、出現頻度の偏り・繰り返し・知覚上重要でない情報といった「無駄」が含まれており、そこを突くと同じ情報をより短く表せます。逆に言えば、冗長性がまったく無いデータは縮みません。

理論的な下限を与えるのが、Claude E. Shannon が 1948 年の論文「A Mathematical Theory of Communication」（Bell System Technical Journal）で導入したエントロピーです。各シンボルの出現確率を p_i とすると、1シンボルあたりの平均情報量は次式で表されます。

シャノンのエントロピー

H = -Σ p_i log2 p_i   （単位: ビット/シンボル）

この H が「1シンボルあたり平均で何ビット必要か」の理論的下限です。情報量の単位である「ビット(bit)」もこの論文に由来します。出現確率が偏っているほど H は小さくなり、縮む余地が大きい、という関係になります。

最も素朴な圧縮の例がランレングス符号化（RLE）です。同じ値の連続を「値と回数」に置き換えます。

RLE の最小例

AAAAABBBCCD  ->  5A 3B 2C 1D

連続が多いデータには効きますが、連続の少ないデータではむしろ増えることもあります。ここに「万能な圧縮は存在しない」という後述の限界が既に顔を出しています。

可逆圧縮と非可逆圧縮

圧縮は大きく2種類に分かれます。

可逆圧縮（lossless）: 復元すると元のデータと完全に一致します。テキスト・実行ファイル・ZIP・PNG など、1ビットも失えない用途に使います。
非可逆圧縮（lossy）: 知覚上重要でない情報をあえて捨てて高い圧縮率を得ます。JPEG・MP3・動画など、人間の目や耳が細部を区別しにくい対象に向きます。

以降の3〜5章は可逆圧縮の話、7章で非可逆圧縮を扱います。

エントロピー符号化: ハフマン・算術・ANS

エントロピー符号化は、頻出するシンボルに短い符号を、まれなシンボルに長い符号を割り当てて全体を縮める手法です。

ハフマン符号は David A. Huffman が 1952 年の論文「A Method for the Construction of Minimum-Redundancy Codes」で示しました。生成される符号は前置符号（prefix code, 語頭符号）、つまりどの符号も他の符号の先頭になっていないため、区切り記号なしで一意に復号できます。各シンボルの確率が固定なら、ハフマン符号の平均符号長は最小（最適）になります。木の作り方は「最小の2ノードを併合」を繰り返すだけです。

ハフマン木構築の擬似コード

# 各シンボルを頻度付きで最小ヒープに入れる
heap = min_heap(全シンボルを (頻度, ノード) として)
 
while heap のノードが 2 個以上:
    a = heap から最小を取り出す
    b = heap から最小を取り出す
    親 = 新ノード(頻度 = a.頻度 + b.頻度, 左 = a, 右 = b)
    heap へ 親 を挿入
 
root = heap の唯一のノード
# root から左枝を 0、右枝を 1 とたどり、各葉までの経路が符号

算術符号（arithmetic coding）は、メッセージ全体を区間 [0, 1) の中の1つの数値区間へ写像します。シンボルを読むたびに区間を確率に応じて狭めていき、最終的な区間を表す1つの数を出力します。ハフマンが「1シンボル＝整数ビット」に縛られるのに対し、算術符号はエントロピー限界にほぼ到達できます。実用的な有限精度化は Rissanen(1976) と Pasco(1976) によるもので、概念の源流は Peter Elias にさかのぼります。レンジコーダ（G.N.N. Martin, 1979）はその派生です。

非対称数系（ANS）は Jarek Duda が 2009 年に提出しました（arXiv:0902.0271）。ハフマン並みの速度で算術符号並みの圧縮率をねらう手法で、tANS/rANS などの変種があり、後述の Zstandard の FSE などで採用されています。

辞書式圧縮: LZ77 / LZ78 / LZW

エントロピー符号化が「シンボル単位の頻度の偏り」を突くのに対し、辞書式圧縮（LZ 系）は「過去に出た並びの繰り返し」を突きます。

LZ77（別名LZ1）は Jacob Ziv と Abraham Lempel が 1977 年に発表しました。直近の入力をスライディングウィンドウとして保持し、これから出力する並びが窓の中に既出なら「どれだけ前の、どれだけの長さか」という後方参照 <距離, 長さ> に置き換えます。辞書は暗黙で、過去の入力そのものが辞書の役割を果たします。

LZ77 の後方参照イメージ

入力: abcabcabc
出力: a, b, c, <距離=3, 長さ=6>
     ("abc" を出したあと、3 文字前から 6 文字ぶんコピーで残りを復元)

一致を高速に探すには「直近の並びからハッシュで候補位置を引く」実装がよく使われます（ハッシュテーブルの記事が背景になります）。

LZ78（別名LZ2）は同じ Ziv と Lempel が 1978 年に発表した方式で、こちらは明示的な辞書を少しずつ構築していきます。LZWは Terry Welch が 1984 年に LZ78 を実装改良し、出力を固定長コードにしたものです。GIF・TIFF・Unix の compress で使われました。かつて Unisys の LZW 特許が GIF まわりで問題化し、後に失効しましたが、正確な失効日は要確認レベルなので深追いしません。

要点を整理すると、LZ77 は過去の入力を窓として参照し（辞書は暗黙）、LZ78・LZW は明示辞書にエントリを追加していく、という違いになります。

実世界の可逆フォーマット

実用フォーマットの多くは「LZ 系で繰り返しを潰し、その出力をエントロピー符号化で詰める」という二段構えです。

DEFLATE: RFC 1951（1996 年）。定義どおり「LZ77 + ハフマン符号」の組み合わせです。
gzip ファイル形式: RFC 1952（1996 年）。DEFLATE に CRC-32 とヘッダを付けたものです。
zlib: RFC 1950（1996 年）。DEFLATE に Adler-32 を付けたストリーム形式です。
PNG: 圧縮に zlib/DEFLATE を採用しています（RFC 2083 / W3C PNG 仕様）。
Brotli: RFC 7932（Google, J. Alakuijala と Z. Szabadka, 2016 年）。静的辞書 + LZ77 + ハフマン + コンテキストモデリング（文脈に応じた確率モデル）で、Web 配信向けに gzip より高い圧縮率をねらいます。
Zstandard（zstd）: RFC 8878（Meta/Facebook, Yann Collet ほか, 2021 年, Informational）。エントロピー段に FSE（ANS の一種）とハフマンを併用します。辞書学習（--train）に対応し、HTTP のコンテンツコーディング zstd とメディアタイプ application/zstd を登録済みで、速度と圧縮率のバランスが良好です。
bzip2: Julian Seward 製。BWT（Burrows–Wheeler 変換）+ MTF（move-to-front）+ ハフマンという構成で、gzip より高圧縮ですが低速です。
xz / LZMA / LZMA2: Igor Pavlov（7-Zip 作者）による LZMA が基盤。LZ 系 + レンジコーダ + 高度なコンテキストモデルで、高圧縮・低速の代表です。
LZ4 / Snappy: LZ4 は Yann Collet による高速・低圧縮の LZ77 系、Snappy は Google 製の高速・そこそこ圧縮のライブラリで、いずれも速度優先です。

用途別におおまかな位置づけを整理すると、次の表のようになります。圧縮率や速度の具体的な数値は入力・レベル・実装に強く依存するため、ここでは傾向のみを示します（詳細は計算量の記事の観点で、時間と結果のトレードオフとして捉えると分かりやすいです）。

方式	中核技術	傾向（速度/圧縮率）	主な用途
gzip/DEFLATE	LZ77 + ハフマン	中速・中圧縮	Web 配信・汎用
zstd	LZ + FSE/ハフマン	高速・中〜高圧縮	汎用・ログ・DB
Brotli	静的辞書 + LZ77 + ハフマン	中速・高圧縮	Web 静的配信
bzip2	BWT + MTF + ハフマン	低速・高圧縮	アーカイブ
xz/LZMA	LZ + レンジコーダ	低速・最高圧縮寄り	配布物・バックアップ
LZ4/Snappy	LZ77 系	最速・低圧縮	メモリ内・ストリーム

CLI ではレベル指定で速度と圧縮率のバランスを変えられます（数値が大きいほど高圧縮・低速の傾向）。

代表的な CLI 例

gzip -9 -k file.txt                    # 高圧縮・元ファイル保持
zstd -19 file.txt                      # zstd 高レベル
zstd --train samples/* -o dict.zstd    # 小さいファイル群向けに辞書学習
brotli -q 11 file.txt                  # Brotli 最高品質
xz -9 file.txt                         # LZMA 高圧縮
bzip2 -9 file.txt                      # BWT 系高圧縮

HTTP コンテンツ圧縮の実務

Web ではレスポンス本文を圧縮して転送量を減らします。方式はリクエストの Accept-Encoding とレスポンスの Content-Encoding でネゴシエートし、代表値は gzip / deflate / br（Brotli）/ zstd です。

HTTP コンテンツ圧縮のネゴシエーション

# リクエスト
Accept-Encoding: gzip, deflate, br, zstd
 
# レスポンス
Content-Encoding: br
Vary: Accept-Encoding

キャッシュ整合のため、圧縮方式で内容が変わることを示す Vary: Accept-Encoding を返すのが実務標準です（RFC 9110/9111, MDN）。これを忘れると、CDN が別方式のクライアントへ誤った表現を配ってしまう恐れがあります（Cache-Control と CDN の記事や、圧縮の要否を左右するHTTP ステータスコードの記事も参照）。

対応状況をおおまかに言うと、gzip/deflate はほぼ全ブラウザ、br は主要ブラウザが対応（Chrome/Firefox は HTTPS の安全なオリジンでのみ br を広告）、zstd は比較的新しく Chrome 123（2024 年）で zstd の広告を開始しました。最新の対応状況は caniuse 等で要確認です。

WARNING

HTTP の deflate は本来 zlib 形式（RFC 1950）を指しますが、歴史的に一部サーバが生 DEFLATE（RFC 1951）を返して互換問題を起こしました。実務では deflate を避け、gzip/br/zstd を使うのが無難です。

非可逆圧縮の仕組み（画像・音声・動画）

非可逆圧縮は「人間が気づきにくい情報を捨てる」ことで、可逆では届かない圧縮率を実現します。

JPEGは画像を 8x8 のブロックに分け、各ブロックに DCT（離散コサイン変換）を適用して周波数成分へ変換し、人間の目が鈍感な高周波成分を粗く量子化してからエントロピー符号化します。量子化の粗さが「画質」に相当します。この「有限のビットに丸めて情報を落とす」構図は、浮動小数点（IEEE 754）の記事の丸め誤差と対比すると理解しやすいです。

MP3/AACは音響心理モデルを使い、大きな音の陰でマスキングされて知覚されない成分を除去します。動画（H.264/H.265/AV1）は概観のみですが、世代が進むほど同じ画質で必要ビットレートが下がる傾向があります（具体的な数値は条件依存のため断定しません）。

圧縮の限界: すべては縮められない

最後に原理的な限界です。どんな可逆圧縮アルゴリズムでも、必ず縮まない（あるいは増える）入力が存在します。理由は鳩の巣原理（counting argument）です。長さ N ビットの出力は高々 2^N 通りしかなく、それより多くの入力を一対一（単射）で写すことはできません。したがって「あらゆるファイルを縮める可逆圧縮」は数学的に不可能です。

鳩の巣原理による限界

N ビットの出力パターン数 = 2^N（有限）
「N ビット未満へ縮む入力」が「縮まない入力」を伴わずに存在することはない
=> 2^N < 2^M を単射で写すのは不可能（M は N より大きいビット長）

冗長性の無いランダムなデータは、どんな可逆圧縮でも実質縮みません。各アルゴリズムは特定の冗長性パターンを突いているだけで、そのパターンが無ければ効きません。二重圧縮（圧縮済みをもう一度圧縮）が効かないのも同じ理由で、圧縮後の出力は既にランダムに近く、突くべき冗長性が残っていないからです。

まとめ - 場面別にどれを選ぶか

原理: 圧縮は冗長性を突く行為で、エントロピー H = -Σ p_i log2 p_i が可逆圧縮の下限を与えます。冗長性が無ければ縮みません。
可逆の中核: LZ 系で繰り返しを潰し、ハフマン・算術・ANS などのエントロピー符号化で詰める二段構えが定番です。
速度優先: LZ4/Snappy。メモリ内やストリームで低遅延が要る場面。
バランス: gzip/DEFLATE と zstd。汎用・ログ・Web 配信で扱いやすい。
圧縮率優先: bzip2・xz/LZMA・高レベルの Brotli。保存や配布で転送量を最優先する場面。
Web 配信: br や zstd を優先し、deflate は避け、Vary: Accept-Encoding を忘れない。
非可逆: 画像・音声・動画は知覚上不要な成分を捨てて高圧縮。ただし元へは戻りません。

参考リンク

Shannon, A Mathematical Theory of Communication (1948) — https://en.wikipedia.org/wiki/A_Mathematical_Theory_of_Communication
Huffman (1952) の紹介 — https://en.wikipedia.org/wiki/Huffman_coding
RFC 1951 DEFLATE — https://www.rfc-editor.org/info/rfc1951
RFC 1952 gzip — https://www.rfc-editor.org/info/rfc1952
RFC 7932 Brotli — https://www.rfc-editor.org/info/rfc7932
RFC 8878 Zstandard — https://www.rfc-editor.org/info/rfc8878
MDN Accept-Encoding — https://developer.mozilla.org/en-US/docs/Web/HTTP/Reference/Headers/Accept-Encoding

データ圧縮の仕組み入門 - ハフマン符号・LZ77・gzip/Brotli/Zstandard

なぜデータは圧縮できるのか

可逆圧縮と非可逆圧縮

エントロピー符号化: ハフマン・算術・ANS

辞書式圧縮: LZ77 / LZ78 / LZW

実世界の可逆フォーマット

HTTP コンテンツ圧縮の実務

非可逆圧縮の仕組み（画像・音声・動画）

圧縮の限界: すべては縮められない

まとめ - 場面別にどれを選ぶか

参考リンク

ロードバランシングのアルゴリズム入門 - ラウンドロビンから最少コネクション・P2Cまで

ブルームフィルタとは - 少ないメモリで「たぶん在る・確実に無い」を判定する確率的データ構造

コンシステントハッシュ法とは - 分散システムでノードを増減してもキャッシュが崩れない仕組み

なぜデータは圧縮できるのか

可逆圧縮と非可逆圧縮

エントロピー符号化: ハフマン・算術・ANS

辞書式圧縮: LZ77 / LZ78 / LZW

実世界の可逆フォーマット

HTTP コンテンツ圧縮の実務

非可逆圧縮の仕組み（画像・音声・動画）

圧縮の限界: すべては縮められない

まとめ - 場面別にどれを選ぶか

参考リンク

関連記事

ロードバランシングのアルゴリズム入門 - ラウンドロビンから最少コネクション・P2Cまで

ブルームフィルタとは - 少ないメモリで「たぶん在る・確実に無い」を判定する確率的データ構造

コンシステントハッシュ法とは - 分散システムでノードを増減してもキャッシュが崩れない仕組み