圧縮アルゴリズム Deep Dive — LZ77, Huffman, Arithmetic, ANS, Zstandard, Brotli 完全理解 (2025)

TL;DR

• 可逆圧縮はほぼ必ず 2 段構成: (1) Dictionary ベースの重複除去 (LZ77 系 — 反復バイトを back-reference で置換)、(2) Entropy coding (Huffman/Arithmetic/ANS — よく出る記号に短いコード)。
• LZ77 (1977): Sliding Window 内で反復を探し (offset, length, next_char) を出力。すべての modern compressor の起源。
• Huffman coding: 頻度ベースの prefix-free 符号。Deflate/gzip のエントロピー段。
• Arithmetic coding: Huffman より良い比率だが 遅い。30 年間、特許と性能の問題で限定用途。
• ANS (Asymmetric Numeral Systems)、Jarek Duda 2009: Arithmetic の品質 + Huffman の速度。Zstd、LZFSE、AV1 が採用。この 10 年の静かな革命。
• Deflate (1993, RFC 1951): LZ77 + Huffman。gzip、PNG、ZIP の基盤。
• LZ4 (2011): 圧縮率を犠牲にし 極限の速度 (GB/s)。Snappy と競合、RocksDB 等に組み込み。
• Zstandard (2016, Yann Collet): LZ77 + FSE (ANS)。gzip より 3 倍速く比率も良い。Dictionary training で小さなメッセージも効率圧縮。
• Brotli (2015, Google): Zstd と並ぶ競合。Web トラフィック最適化、静的 Dictionary 内蔵。
• 実務の選択: 速度 -> LZ4、汎用 -> Zstd、Web 静的 -> Brotli、レガシー -> gzip、小さなメッセージ多数 -> Zstd + Dictionary。

1. 圧縮の基本

1.1 なぜ圧縮するのか

• ディスク: ストレージコスト削減。
• ネットワーク: 帯域削減、レイテンシ短縮。
• メモリ: RAM 効率向上。
• バックアップ/アーカイブ: 長期保管。

2025 年、データは爆発的に増えており圧縮の重要性はむしろ増している。CPU は余っているが I/O とネットワークがボトルネック。

1.2 Lossless と Lossy

Lossless (本稿):

• 原本を完全復元。
• テキスト、コード、DB、実行ファイル。
• gzip、zstd、LZ4、Brotli。

Lossy:

• 情報の一部を失う (品質 vs 比率のトレードオフ)。
• 画像 (JPEG)、音声 (MP3)、動画 (H.264)。
• 本稿の範囲外。

1.3 Shannon の限界

情報理論 (Claude Shannon, 1948) によれば、任意のデータに圧縮の 理論的下限 が存在する。エントロピー:

p_i は記号 i の確率。単位は bit/symbol。

英文のエントロピーは約 1.5 bit/char。8-bit ASCII で保存されたテキストは理論上 5 倍以上圧縮 可能。現実の圧縮器は限界に近づくが到達はできない。

1.4 2 段戦略

現代の可逆圧縮器はほぼ 2 段 を組み合わせる:

1. Dictionary / LZ: "ABCDEF...ABCDEF" のような反復を back-reference で置換。構造的冗長性 を除去。
2. Entropy coding: 残ったバイトの 統計的偏り を活用。頻出文字に短符号、稀文字に長符号。

2 段は独立に発展しており、どの LZ とどの Entropy を組み合わせるかで異なる compressor になる。

2. LZ77 — すべての起源

2.1 アイデア

Lempel と Ziv の 1977 年論文。「反復されたシーケンスを以前の位置参照で置換する」。

入力: ABABABAB

A          -> "A" (literal)
B          -> "B" (literal)
AB         -> "位置 -2 から 2 バイトコピー"
AB         -> "位置 -2 から 2 バイトコピー"

出力:

(0, 0, A)
(0, 0, B)
(2, 2, _)
(2, 2, _)

各トークン (offset, length, next_char)。

2.2 Sliding Window

実装では 直近 N バイトの窓 だけを検索する。

[search buffer (N bytes)] [lookahead buffer (M bytes)] [未処理データ]

各ステップ: lookahead の先頭が search buffer のどこに現れたか探す -> 最長 match を選ぶ -> (offset, length, next_char) 出力 -> length + 1 だけ進める。

2.3 LZSS (1982)

LZ77 の改良: match が短すぎると back-reference の方が損。LZSS は flag bit でリテラルか参照かを区別し、3 バイト以上のみ参照にする。ほとんどの modern compressor は LZSS の派生。

2.4 LZ78 と LZW

LZ78: Sliding Window の代わりに 明示的 Dictionary を構築。LZW (Welch, 1984) は派生で GIF、Unix compress、旧 PDF で使われた。現在はほぼ廃れ、LZ77 系が支配。

2.5 Back-reference の効率

1 MB の反復テキスト:

• Raw: 1 MB。
• LZ77 (window 32 KB): 先頭 ~32 KB 以降はすべて "32 KB 戻って長さ ..." の参照。数バイトで表現。
• 結果: 約 32 KB + メタデータ。

32 倍圧縮。原理は「反復を指す」の一言。

2.6 Hash ベースの Matching

各位置での最長 match 検索がボトルネック。解決策: hash chain。3 バイト prefix にハッシュを計算し、同じハッシュの過去位置を連結リストで繋ぐ。候補を高速に取得。

速度 vs 圧縮率:

• Chain を長く: 候補増 -> 長い match -> 良い比率 -> 遅い。
• 短く: 速いが比率低下。

これが gzip -1 と gzip -9 の差。

3. Huffman Coding

3.1 アイデア

David Huffman (1952 年、MIT 院生の課題)。「よく出る記号に短い符号、稀な記号に長い符号」。

頻度例:

a: 40%
b: 20%
c: 15%
d: 15%
e: 10%

固定 3-bit だと 3 bit/symbol。Huffman:

a -> 0     (1 bit)
b -> 10    (2 bits)
c -> 110   (3 bits)
d -> 1110  (4 bits)
e -> 1111  (4 bits)

平均: 0.4x1 + 0.2x2 + 0.15x3 + 0.15x4 + 0.10x4 = 2.25 bit/symbol。25% 削減。

3.2 Prefix-free の性質

どの符号も他の符号の接頭辞にならない (例: 0, 10, 110)。区切り子なしで連続デコード可能。

01001101110 -> 0 10 0 110 1110 -> a b a c d

3.3 Huffman Tree

二分木で各記号にパスを割り当て。葉が記号、パスが符号 (左=0、右=1)、頻出記号は 短いパス。

3.4 Tree 構築

1. すべての記号を頻度順の優先キューに投入。
2. 最小 2 ノードを取り出し、頻度の和を持つ親ノードに統合。
3. 親をキューに戻す。
4. 1 つになるまで繰り返し。

O(n log n)。貪欲だが 最適な prefix-free 符号 であることが証明されている。

3.5 Canonical Huffman

同じ頻度でも木の形は複数ある。Canonical form は符号長だけを保存し規則的に割り当てる -> メタデータが小さい。Deflate と現代の圧縮器の大半で採用。

3.6 限界

Huffman の限界:

• 最低 1 bit/symbol。確率 50% を超えても削れない。
• 確率 90% の記号には理想的には 0.15 bit 欲しいが Huffman は 1 bit -> 85% の損失。

この限界を Arithmetic coding と ANS が乗り越える。

4. Arithmetic Coding

4.1 アイデア

「メッセージ全体を 1 つの実数 で表す」。任意分布に対して理論限界に近づける。

4.2 例

アルファベット a (50%), b (25%), c (25%)。"abc" を区間 [0, 1) から符号化。

1. 'a' 入力: 区間 = [0, 0.5)。
2. 'b' 入力: 区間 = [0.25, 0.375)。
3. 'c' 入力: 区間 = [0.34375, 0.375)。

この区間内の 任意の実数 を出力 (例: 0.35、2 進 01011010)。Decoder は同じ確率分布で逆算。

4.3 効率

各記号が正確に -log2(p) bit を占有。Shannon エントロピー限界に接近。Huffman は整数 bit、Arithmetic は実数 bit。

4.4 なぜ限定的か

• 速度: 浮動小数または高精度整数演算。Huffman の 2-5 倍遅い。
• 特許: IBM の複数特許が数十年使用を制限 (2000 年代に期限切れ)。
• 複雑さ: 実装困難、バグを生みやすい。

30 年間、「より良い方法はあるが実用的ではない」という位置づけ。H.264、JPEG 2000 で利用。

4.5 Range Coding

Arithmetic coding の派生。整数演算を使い特許を回避。LZMA (7zip) で使用。

5. ANS — ゲームチェンジャー

5.1 背景

2009 年、ポーランドの数学者 Jarek Duda が新エントロピー符号 ANS (Asymmetric Numeral Systems) を提案。メーリングリストと論文で静かに公開。のちに 「Arithmetic の品質 + Huffman の速度」 と評価され急速に採用。

5.2 アイデア

「1 つの大きな整数」にメッセージ全体を符号化。ただし標準レジスタ演算で。Arithmetic coding のように動くが 浮動小数なし、除算ほぼなし。代わりに Finite State Machine として表現。

5.3 Finite State Entropy (FSE)

ANS の実用派生。Zstd 作者の Yann Collet が実装。

• 各記号に 次の状態 を割り当て。
• 符号化: 記号入力 -> 状態遷移 -> 一部の bit を出力。
• 復号: 逆方向。

状態機械は 事前計算テーブル -> 実行時は lookup + shift のみ -> 非常に高速。

5.4 tANS と rANS

• tANS (table-based ANS): 状態遷移テーブル。高速だがテーブルがメモリを食う。
• rANS (range-ANS): 範囲ベース。テーブルなし、やや遅いが柔軟。

Zstd の FSE は tANS。Facebook の一部内部ツールは rANS。

5.5 性能

「欠点のないアップグレード」。なぜもっと早くなかったのか疑問。

5.6 採用

ANS ベースの compressor:

• Zstandard (2016): FSE を使用。最も広く普及。
• LZFSE (Apple, 2015): LZ + FSE、iOS/macOS 標準。
• AV1 video codec: エントロピー段に ANS。
• oodle: 商用ゲーム圧縮。
• Brotli: 一部で採用。

2015 年以降の新しい圧縮器における 事実上の標準エントロピー符号。

6. Deflate — gzip のエンジン

6.1 概要

Phil Katz の 1993 年作。PKZIP で利用、RFC 1951 (1996) として標準化。LZ77 + Huffman。最も広く使われる圧縮フォーマット: gzip, ZIP, PNG, Content-Encoding: gzip。30 年以上の標準。

6.2 構造

圧縮データ = block のシーケンス。各 block:

• Header: block 種別 (stored, fixed Huffman, dynamic Huffman)。
• Huffman tree (dynamic のみ)。
• Compressed data: LZ77 トークンを Huffman で符号化。

6.3 LZ77 段

• Window: 32 KB。
• Match length: 3-258 バイト。
• Offset: 1-32768。

各 match は (length, distance) ペア、リテラルは 0-255 の文字コード。

6.4 Huffman 段

2 本の Huffman tree:

• Literal/length tree: literal (0-255) と length 符号 (257-285)。
• Distance tree: offset 符号 (0-29)。

長さと距離は log スケールの bucket にマップ。小さな値は正確に、大きな値は extra bits で表現。

6.5 レベル

gzip -1 ~ gzip -9:

• -1: lazy match、短い hash chain。
• -9: 長い hash chain、best match 探索。

Time/space トレードオフ。比率差 ~20% / 速度差 5-10 倍。

6.6 性能

• 圧縮: ~50 MB/s (単一コア)。
• 解凍: ~300 MB/s。
• 比率: テキストで 3-5 倍。

30 年前のアルゴリズムだが依然有用。とはいえ現代の zstd/brotli がより優秀。

7. LZ4 — 極限の速度

7.1 哲学

Yann Collet の 2011 年作。「圧縮率を犠牲にして速度を極大化」。

7.2 設計

• Entropy coding なし: LZ77 のみ。
• シンプルなフォーマット: byte 境界、bit 操作なし。
• Hash table: 単純ハッシュ、1 回の lookup のみ。
• 最小 match: 4 バイト。

7.3 速度

• 圧縮: 500-800 MB/s (単一コア)。
• 解凍: 2-5 GB/s (単一コア)。
• 比率: テキストで 2-2.5 倍 (gzip の半分)。

CPU がディスクやネットワークより速い環境に最適。

7.4 使われる場所

• RocksDB, Cassandra: ディスク保存圧縮。
• Zstandard: 低レベルで LZ4 ライクなモード。
• MongoDB: スナップショット、ジャーナル。
• Kernel: Linux の一部圧縮経路。
• Kafka: 一部構成。

「リアルタイム圧縮が必要だが CPU 予算が限られる」場所。

7.5 LZ4 HC

High Compression 派生。より遅いが比率が良い。それでも zstd より速く圧縮率は低い。

7.6 Snappy

Google の類似圧縮器 (2011)。非常に高速で比率低め、LevelDB、BigTable、HBase で使用。LZ4 の方がやや速くやや圧縮するので大抵 LZ4 が勝つ。

8. Zstandard — 汎用の王

8.1 背景

Facebook の Yann Collet (LZ4 と同じ作者)、2016 年発表。目標「gzip より 3 倍速く、よりよく圧縮」。

8.2 構成

• LZ77 形式 match: 2+ バイト、大きな window (既定 8 MB)。
• Entropy coding: literals に FSE (ANS ベース)、一部で literal 分布に Huffman。
• Frame format: チャンク単位、ストリーミング向け。

8.3 Dictionary 機能

Killer feature: pre-trained Dictionary。

# 100 個の JSON サンプルから Dictionary を学習
zstd --train samples/*.json -o dict.bin

# Dictionary を用いて圧縮
zstd -D dict.bin input.json -o output.zst

# Dictionary を用いて解凍
zstd -D dict.bin -d output.zst -o input.json

効果: 小さなメッセージ (数百バイト) で 10-100 倍の圧縮率改善。通常の圧縮器は小さな payload に弱いが Zstd + Dictionary で克服。Kafka、小さな HTTP API、チャットに最適。

8.4 Long-range モード

zstd --long: 遠く離れた match まで検索 (GB 単位の window)。バックアップ、ディスクイメージに効果的。

8.5 圧縮レベル

zstd -1 (fast) ~ zstd -22 (max):

• -1: ~500 MB/s、比率 2x。LZ4 と競合。
• -3 (既定): ~200 MB/s、比率 3x。
• -9: ~50 MB/s、比率 3.5x。
• -19: ~10 MB/s、比率 4.2x。
• -22: ~1 MB/s、比率 4.5x。

8.6 解凍速度

2-3 GB/s (単一コア)。圧縮レベルに無関係、常に高速 — これが最大の強み。

8.7 採用

• Linux カーネル 圧縮 (zstd オプション)。
• Btrfs, ZFS ファイルシステム。
• Arch Linux パッケージ (リポジトリ全体が zstd)。
• Kafka, RocksDB 等現代システム。
• Facebook のインフラ全域。

事実上の新標準。

8.8 コード複雑さ

Zstd のソースは ~25,000 行 C、gzip は ~5,000 行。複雑さ vs 性能のトレードオフだが 単一バイナリ、外部依存なし でポート容易。

9. Brotli — Google の選択

9.1 背景

Google の Jyrki Alakuijala 他、2015 年発表。HTTP/2 コンテンツ圧縮用。

特徴:

• 静的 Dictionary 内蔵: 120 KB の英語/HTML/CSS/JS トークン。
• Context modeling: literal 周辺の context を考慮しよりよい Huffman tree。
• 長い back-reference: 2 MB window。

9.2 圧縮率

Zstd と同程度の比率で やや遅い。HTML/CSS/JS に最適化、Web コンテンツでは内蔵 Dictionary のおかげで Zstd よりやや良い。

9.3 解凍

~400 MB/s。Zstd よりやや遅いが十分。

9.4 使われる場所

主に Web:

• HTTP Content-Encoding: br — Chrome、Firefox 共にサポート。
• WOFF2 (Web Open Font Format 2)。
• Android APK。
• Cloudflare のエッジ圧縮。

汎用システムでは zstd が主。

9.5 Brotli vs Zstd (Web)

10 MB HTML + CSS + JS
gzip (-9):   2.5 MB
brotli (11): 1.8 MB  (gzip より 28% 小)
zstd (19):   1.9 MB

Web では Brotli が静的 Dictionary により僅差で優位。

10. LZMA / 7z

10.1 背景

Igor Pavlov の LZMA (Lempel-Ziv-Markov chain-Algorithm)。7-zip の既定、1998 年から。

10.2 特徴

• 巨大 window: 最大 4 GB。遠い match も発見。
• Arithmetic coding (range coder): Huffman より良い比率。
• Markov モデル: literal 周辺の context で条件付き確率を改善。
• 実装が非常に複雑。

10.3 性能

• 圧縮: 非常に遅い (数 MB/s)。
• 解凍: 数十 MB/s。
• 比率: 非常に良い。Zstd より 5-15% 小さい。

10.4 使われる場所

• 7-zip: GUI 圧縮ツール。
• xz (.tar.xz)。
• Arch Linux (以前は xz、現在 zstd に移行中)。
• Debian パッケージの一部。

「極限の圧縮率が必要で時間がある」場合。バックアップ、配布ファイル。

10.5 なぜ zstd が置き換えるのか

Zstd: 比率は少し劣るが はるかに高速。Arch の xz -> zstd 移行報告では「インストール時間 50% 短縮、パッケージサイズ 20% 増加」。ユーザー視点でネットポジティブ。

11. 比較表

11.1 圧縮率

テキスト入力 (10 MB Linux kernel source):

11.2 用途別の推奨

• リアルタイム / 高速 I/O: LZ4。
• 汎用ファイル圧縮: Zstd -3。
• バックアップ/アーカイブ: Zstd -19 または xz。
• Web コンテンツ: Brotli (フォールバック gzip)。
• 小さなメッセージ多数: Zstd + Dictionary。
• DB / ストレージエンジン: ホットは LZ4、スペース優先は Zstd。

12. SIMD 加速

12.1 機会

圧縮は逐次処理だが多くの部分で SIMD が効く:

1. Hash 計算: 複数位置を一度に。
2. Match 検索: 長い byte 比較。
3. Huffman 復号: 並列 lookup。
4. Entropy 復号: ANS state 更新。

12.2 現代の実装

• Zstd: SSE2/AVX2 対応。SIMD で literal コピーを加速。
• LZ4: 構造が単純で SIMD 活用は少ないが、長コピーは memcpy (内部 SIMD)。
• libdeflate: zlib の代替実装。SIMD 加速で zlib より 2-3 倍速い gzip。

12.3 帯域の限界

多くの場合 メモリ帯域 が実質ボトルネック。SIMD で CPU を減らしても L3/DRAM の帯域が飽和。数 GB/s を超えるとハードウェアの限界。

12.4 ハードウェア圧縮

• Intel QAT (Quick Assist): CPU 内蔵の Deflate アクセラレータ、100 GB/s 級。
• NVIDIA GPU: cuDNN の一部、一部 DB エンジン。
• SmartNIC: ネットワークカードで圧縮/解凍。

大規模サービス (Facebook, Google) が活用。

13. Dictionary Training

13.1 なぜ必要か

通常の圧縮器は入力内の重複のみを探す。100 バイトの JSON には内部重複がほぼないため圧縮されない。

{"name":"Alice","age":30}

このメッセージはメタデータのオーバーヘッドで むしろ大きくなる こともある。

13.2 Dictionary の役割

似た JSON を数百個見ると 共通パターン が多い: "name":、"age": 等のキーが繰り返し出現。Dictionary = 「これらの共通トークンを事前に入れた参照資料」。圧縮時に参照を Dictionary に向ければ非常に短い符号になる。

13.3 学習プロセス

zstd --train samples/*.json --maxdict=110K -o dict

1. サンプルファイルを読み込む。
2. 最もよく出る部分文字列 を統計的に抽出。
3. 上位を Dictionary に含める。
4. Dictionary ファイルを出力。

13.4 使い方

zstd -D dict input.json -o output.zst

Dictionary ファイルは encoder と decoder の両方 が保持する必要がある。共有が必要。

13.5 性能

• 通常 JSON 100 バイト: zstd で 90 バイト (10% 減)。
• Dictionary 利用 (10 KB の Dictionary、1000 JSON 学習): 30 バイト (70% 減)。

7 倍差。大量の小さなメッセージ転送で必須。

13.6 ユースケース

• Kafka: メッセージ毎の小さな payload。Dictionary で 50-80% 削減。
• HTTP API: 応答 payload の構造が定まっている。Dictionary 学習可能。
• Protobuf メッセージ: スキーマ特化 Dictionary。
• NoSQL KV: 似たキー-値ペア。

Facebook はこの手法で petabyte 規模の保存コストを削減。

14. 実戦例

14.1 HTTP サーバー

Accept-Encoding: gzip, br, zstd

Response:
Content-Encoding: zstd

Nginx:

http {
    zstd on;
    zstd_comp_level 3;
    zstd_types text/html text/css application/javascript application/json;
}

(zstd モジュールが必要。既定 Nginx は gzip。) 静的ファイル はビルド時に事前圧縮 (.br, .gz ファイル) -> ランタイム CPU を節約。

14.2 Kafka

compression.type=zstd

Producer がバッチを圧縮。既定 3 レベルでテキストメッセージが 3-5 倍 削減。Broker は圧縮バッチを そのまま保存・転送 -> CPU 効率が高い。

14.3 Kubernetes コンテナイメージ

OCI イメージレイヤーは通常 gzip。zstd に移行中:

docker build --compression=zstd .

Pull 時間 30-50% 短縮。大きなイメージ (ML モデル) に有効。

14.4 バックアップ

tar -cf - /data | zstd -19 --long > backup.tar.zst

--long で大 window を使い、ファイル間の重複も除去。Rsync + zstd は従来の gzip 組み合わせより 10-30% 速く小さい。

14.5 DB

RocksDB:

options.compression = kZstdCompression;
options.bottommost_compression = kZstdCompression;
options.compression_opts.level = 3;

L0-L4 は LZ4 (速い)、L5-L6 は zstd (高圧縮)。Tiered compression。

ClickHouse:

CREATE TABLE events (
    ...
) ENGINE = MergeTree
SETTINGS
    index_granularity = 8192;

ALTER TABLE events MODIFY COLUMN data CODEC(ZSTD(3));

カラム別に異なる codec。

15. 現代のトレンド

15.1 Asymmetric Speed

Decode >> Encode の速度不均衡を活用: 1 度圧縮、数千回解凍 (Web、CDN、画像)。Encoder に時間投資 して decoder を速く。Brotli -11、zstd -19。

15.2 Hardware Acceleration

• Intel QAT (サーバー CPU)。
• NVIDIA decompression engines (Ampere+)。
• AWS Nitro カードの一部。

大規模サービスの主要投資領域。

15.3 ML ベース

Google DeepMind の実験: LLM ベースの圧縮。モデルが「次のトークンを予測」し差分だけ保存。画像/テキストで 5-10 倍圧縮。ただし遅く GPU が必要 — 実用的ではない。特殊用途 (genome, 科学データ) で関心。

15.4 Lossy Text?

「多少の誤りを許容する」テキスト圧縮の研究中。自然言語の情報理論限界は 1-1.5 bit/char だが LLM が下げる可能性。学術段階。

15.5 次世代 entropy coder?

ANS から 10 年。Pelican、rANS 変種などが実験中。ただし ANS が十分に良く、主流交代はしばらく来そうにない。

16. よくある質問

Q: すでに圧縮されたファイルをもう一度圧縮すると?

A: 効果ほぼなし。JPEG、MP3、ZIP、既に gzip されたファイル等。通常 1% 未満の節約、むしろ大きくなることもある (メタデータ)。

Q: Solid 圧縮 vs ファイル別圧縮?

A: Solid (全体を 1 つの stream): ファイル間の重複を活用、比率が良い。欠点: 1 つ取り出すのに全体解凍。ファイル別: 独立、random access が速い。欠点: 共有重複の損失。ZIP はファイル別、tar.gz / tar.zst / 7z は solid。

Q: 最大効率の組み合わせは?

A: LZMA / zstd --long どちらも GB 規模の window で大ファイル間の重複を活用。

Q: 暗号化との組み合わせは?

A: 圧縮 -> 暗号化 の順。逆は暗号化済みデータがランダムなので圧縮不可。注意: CRIME/BREACH のような長さベース攻撃。HTTPS で機微データ + 圧縮が混在すると危険。

Q: Streaming サポート?

A: Zstd、Brotli、gzip すべて streaming API あり。入力を一度に持たなくても圧縮可能。

17. 1 枚まとめ

+------------------------------------------------------+
|          Compression Cheat Sheet                     |
+------------------------------------------------------+
| 基本原理:                                            |
|   2 段: LZ (重複除去) + Entropy (統計)               |
|                                                      |
| LZ ファミリー:                                       |
|   LZ77 (Sliding Window, back-reference)              |
|   LZSS (最小 match 長)                               |
|   LZ78/LZW (明示 Dictionary, 非推奨)                 |
|                                                      |
| Entropy Coding:                                      |
|   Huffman (1952): 整数 bit, 高速                     |
|   Arithmetic (1970s): 実数 bit, 低速, 特許           |
|   ANS/FSE (2009): Arithmetic 品質 + Huffman 速度     |
|                                                      |
| 主要アルゴリズム:                                    |
|   Deflate (1993): LZ77 + Huffman                     |
|   LZ4 (2011): LZ77 のみ, 超高速                      |
|   Zstandard (2016): LZ77 + FSE                       |
|   Brotli (2015): 静的 Dictionary + context           |
|   LZMA (1998): LZ77 + Markov + Range                 |
|                                                      |
| 速度 vs 比率:                                        |
|   LZ4/Snappy: 高速, 低比率                           |
|   gzip -1: 高速, 中                                  |
|   zstd -3: バランス (既定推奨)                       |
|   gzip -9: 低速, 良比率                              |
|   zstd -19: 低速, より良い比率                       |
|   brotli -11: 低速, Web 最適                         |
|   xz -9: 非常に低速, 最良比率                        |
|                                                      |
| 用途別:                                              |
|   リアルタイム: LZ4                                  |
|   汎用: zstd -3                                      |
|   バックアップ: zstd -19 または xz                   |
|   Web: brotli                                        |
|   小メッセージ: zstd + Dictionary                    |
|                                                      |
| Dictionary Training:                                 |
|   zstd --train                                       |
|   小メッセージで 10-100 倍改善                       |
|   Kafka, HTTP API, NoSQL に有効                      |
|                                                      |
| 加速:                                                |
|   SIMD (libdeflate, zstd)                            |
|   ハードウェア (Intel QAT)                           |
|   GPU                                                |
|                                                      |
| 注意:                                                |
|   圧縮済みのものは再圧縮不可                         |
|   暗号化の前に圧縮                                   |
|   CRIME/BREACH 注意 (HTTPS)                          |
+------------------------------------------------------+

18. クイズ

19. 学習リソース

論文:

• Lempel & Ziv, "A Universal Algorithm for Sequential Data Compression" (1977).
• Huffman, "A Method for the Construction of Minimum-Redundancy Codes" (1952).
• Duda, "Asymmetric Numeral Systems" (2009).
• Yann Collet の Zstd 関連ブログ。

書籍:

• "Introduction to Data Compression" — Khalid Sayood.
• "Managing Gigabytes" — Witten, Moffat, Bell.

ブログ:

• https://fastcompression.blogspot.com — Yann Collet (LZ4, Zstd 作者)。
• https://www.righto.com/2019/07/shanghaied-by-zsr.html — 圧縮アルゴリズムブログ。

ツール:

• zstd, gzip, xz, brotli CLI。
• lzbench: 各種 compressor ベンチマーク。
• squash benchmark (https://quixdb.github.io/squash-benchmark)。

ソース:

• Facebook/zstd GitHub。
• LZ4 GitHub。
• Brotli GitHub。

この記事が役に立ったら、以下の関連記事もどうぞ:

• "SIMD / AVX / NEON Deep Dive" — 圧縮加速に使われる技術。
• "RocksDB と LSM-Tree" — LZ4/zstd を使う DB エンジン。
• "CDN と Edge Caching" — Web 圧縮のデプロイ。
• "Binary Serialization (Protobuf/Thrift/Avro)" — 事前圧縮されたデータフォーマット。