圧縮アルゴリズムを理解する

今回は、ソフトウェアの圧縮アルゴリズムについて話してみたい。

社内プロジェクトのデプロイプロセスを改善する仕事を担当した。大容量のビルド成果物をS3へアップロードする構成だったため、ビルドフォルダーのサイズがアップロード時間とストレージコストに直結することを実感した。そこから自然に「どうすれば効率よく圧縮してアップロードできるだろうか」という疑問が生まれた。

いざ圧縮について調べると、zip、gzip、zstd、bzip2、xzなど、想像以上に多くの種類があった。名前はよく似ているのに、何が違い、どのような場面で何を選べばよいのかを一度に理解できる資料はなかなか見つからなかった。（圧縮ならどれも同じようなものだと思っていたが、世界は広く、圧縮方法も多かった。）

そこでこの機会に、各圧縮形式の原理と特徴を比較し、筆者がなぜ特定の方式を選んだのかを整理してみる。

可逆圧縮とは何か

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

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

その中でも、辞書ベース（Dictionary-Based）方式は可逆圧縮で最も広く使われるアルゴリズム群の一つだ。ここでいう辞書とは言葉の意味を調べる辞書ではなく、以前に現れたデータ片を短いコードへ対応付ける参照テーブルを指す。Abraham LempelとJacob Zivが1977年の論文 "A Universal Algorithm for Sequential Data Compression"（IEEE Transactions on Information Theory）で提案したLZ77と、翌1978年に発表したLZ78がこの系譜の始祖だ。二人の姓から一文字ずつ取って「LZ」と呼ばれる。以後に登場した辞書ベース圧縮アルゴリズムのほぼすべて、DEFLATE、LZMA、LZ4、Zstdなどは、この二つにルーツを持つ。（圧縮アルゴリズムの系図の大半が、この二人へ収束すると言っても大げさではない。）

簡単な例で考えてみよう。テキストに「Linux」という単語が100回現れるなら、最初の登場時に辞書へ登録し、それ以降は「辞書の1番目」という短い参照、つまりポインターに置き換える。「Linux」は5バイトだが、ポインターはそれより少ないバイトで表せるため、全体のサイズが小さくなる。

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

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

LZ77は明示的な辞書を別に作らず、入力ストリームの一定範囲そのものを辞書として使う。この範囲をスライディングウィンドウと呼ぶ。データの処理中にウィンドウが一つずつ前へ移動することから付いた名前だ。（アルゴリズム問題でもよく見かける言葉だ。）

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

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

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

たとえば、"banana_banana"という文字列をLZ77で圧縮するとしよう。二つ目の"banana"に到達した時点で、アルゴリズムは実質的に 「7文字戻って6文字をそのままコピーせよ」 と指示する。6バイトの文字列を、わずか二つの数値で表現できる。

この方式の要点は、辞書を別途保存したり送信したりする必要がないことだ。デコーダーは展開を進めながら検索バッファを自然に再構築するため、辞書はデータそのものへ暗黙的に組み込まれている。ただし、その代わりに展開は常にデータの先頭から順番に進めなければならない。原理上、途中の任意位置から展開を始めることはできない。

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

LZ78：明示的な辞書方式

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

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

LZ78で最も有名な派生がLZW（Lempel-Ziv-Welch）だ。Terry WelchがLZ78を改良して1984年に発表し、GIF画像形式とUnixのcompressユーティリティ（.Z拡張子）で使われた。（かつてLZWは特許紛争の中心にもなり、この出来事はPNG形式誕生のきっかけの一つとなった。）

現代の圧縮アルゴリズムはどちらの子孫か

興味深いことに、現在使われている主流の圧縮アルゴリズムは、ほぼすべてLZ77系の子孫だ。

StorerとSzymanskiが1982年に発表したLZSSはLZ77の改良版で、1ビットのフラグを導入し、各出力が「リテラル、つまり元の文字」なのか「長さと距離の組」なのかを区別した。一致が短すぎて参照のほうが損になる場合は、そのまま元の文字を出力できる。

1993年、Phil KatzはLZSSにハフマン符号化、つまり頻度の高いシンボルへ短いビット列を割り当てるエントロピー符号を組み合わせてDEFLATEを作った。ZIP、GZIP、PNGはいずれもDEFLATEを使う。つまり、日常的に扱う.zip、.gz、.pngファイルはすべてLZ77の直系子孫だ。

その後に登場したLZMA（7-Zip、XZ）、LZ4、Zstdも、LZ77のスライディングウィンドウを出発点とし、一致検索のデータ構造やエントロピー符号化を進化させてきた。一方、LZ78系はLZWを最後に、主流の舞台からほぼ退いたと見てよい。

理論上、二つのアルゴリズムは 「データ全体を展開する場合」 に同等の能力を持つことが証明されている。それでもLZ77が生き残った理由は、辞書をデータへ組み込む設計が、実装と拡張の両面でより柔軟だったからだ。スライディングウィンドウの大きさ、一致検索アルゴリズム、後段のエントロピーコーダーなどを自由に組み合わせられ、時代の要求に合わせて進化する余地があった。

圧縮性能を評価するときは、圧縮率、つまりどれだけ小さくなるかと、圧縮速度、つまりどれだけ早く終わるかという二つの軸を考える。一般に、高い圧縮率を求めるほど多くの計算が必要になり、圧縮時間も長くなる。この二つの折り合いをどこにつけるかが、現実的な圧縮戦略の要点だ。

それでは、さまざまな圧縮形式を順番に比較してみよう。

ZIP

ZIPはPhil Katzが1989年に作ったファイル形式で、内部では一般にDEFLATEアルゴリズム、LZ77とHuffman codingの組み合わせを使って圧縮する。重要なのは、ZIPが「圧縮アルゴリズム」そのものではなく「ファイル形式、つまりコンテナ」だという点だ。ZIPという器の中にDEFLATEなどのアルゴリズムで圧縮したデータが入る。

ZIPの特徴は、各ファイルを個別に圧縮することだ。これは非ソリッドアーカイブ（Non-solid Archive）と呼ばれ、アーカイブ内の特定ファイルだけを取り出せる。一方でファイル間の重複データを利用できないため、後述するtar.gzより圧縮率が低くなる場合がある。

Windows、macOS、Linuxなど大半のOSが追加ソフトウェアなしで標準対応しているため、クロスプラットフォーム互換性が重要な場合には最も無難な選択だ。

GZIP（GNU Zip）

GZIPもZIPと同様、内部ではDEFLATEアルゴリズムを使う。同じアルゴリズムなのに、なぜ別の形式があるのだろうか。ZIPは複数ファイルを一つのアーカイブへ収めるコンテナの役割まで担うが、GZIPは単一ファイル、または単一ストリームの圧縮に特化している。

複数のファイルやディレクトリをGZIPで圧縮するには、先にTARで一つのアーカイブへまとめ、その後GZIPで圧縮する。この二段階の処理によって.tar.gz、または.tgzファイルが生まれる。

GZIPのファイル構造はRFC 1952で定められており、かなり単純だ。固定10バイトのヘッダー、元のファイル名やコメントなどを含められる拡張ヘッダー、DEFLATE圧縮データ、そしてCRC-32チェックサムと元サイズを持つ8バイトのトレーラーで構成される。CRC-32は展開後のデータが元データと一致するかを検証する仕組みだ。GZIPはDEFLATEストリームを包む軽量なラッパーだと言える。

DEFLATE内部のスライディングウィンドウは最大32KBだ。このサイズはGZIPの圧縮率の上限を左右する。32KBより離れたパターンは参照できないからだ。また、GZIPは1から9までの圧縮レベルを指定できる。レベル1は高速だが圧縮率が低く、およそ60%で、レベル9は遅い代わりに最大およそ75%の圧縮率を達成する。既定値のレベル6は速度と圧縮率のバランスを取った値だ。

Unix/Linux環境では、ソースコード配布、ログファイル圧縮、ソフトウェアパッケージなどで標準のように使われている。WebサーバーのHTTP圧縮でもContent-Encoding: gzipとして今なお広く使われているが、この用途では徐々にBrotliへ置き換わりつつある。

ZSTD（Zstandard）

ZSTDはMeta、旧FacebookのYann Colletが開発し、2016年にオープンソースとして公開した圧縮アルゴリズムだ。GZIPと同程度の圧縮率を維持しながら、圧縮と展開が圧倒的に速いことが最大の強みだ。

ZSTDの内部処理は大きく三段階に分かれる。まずLZ77系のマッチファインダー（Match Finder）が入力から繰り返しパターンを探す。次に、その一致情報、リテラル、一致長、オフセットをシーケンスとして符号化する。最後にシーケンスをエントロピー符号化で圧縮する。ここではGZIPのハフマン符号化だけでなく、**FSE（Finite State Entropy）**という方式を使う。FSEはANS（Asymmetric Numeral Systems）理論に基づくエントロピーコーダーで、ハフマン符号化と算術符号化（Arithmetic Coding）の長所を組み合わせたものだ。ハフマン符号化はシンボルごとに整数ビットしか割り当てられないが、FSEは分数ビットに相当する確率を表現でき、理論上の最適値へ近づける。（名前は大げさだが、要点は「同じデータをより少ないビットで表す賢い方法」と考えればよい。）

マッチファインダーの戦略も圧縮レベルによって変わる。低レベルの1〜4では単純なハッシュテーブルで高速に検索し、中間の5〜12では複数候補を比較してより良い一致を選ぶLazy方式を使う。高レベルの13〜22では二分木と動的計画法を用いて、最適に近い一致を探す。1から22まで細かく調整できるため、リアルタイム転送には低レベル、アーカイブには高レベルという柔軟な運用ができる。

Silesia Corpusベンチマークでは、ZSTDの既定レベル3は圧縮約300MB/s、展開約1,200MB/sだ。一方、GZIPの既定レベル6は圧縮約34MB/s、展開約380MB/sにとどまる。圧縮は約8倍、展開は約3倍速い一方、圧縮率もZSTDの3.17がGZIPの3.09をわずかに上回る。 この数値を見ると、ZSTDがトレードオフをどう改善したかが直感的に分かる。

採用も急速に広がっている。Linuxカーネルのモジュール圧縮やファイルシステムの透過圧縮で使われ、Arch Linux、Fedora、Debian、Ubuntuなど主要ディストリビューションがパッケージ圧縮の標準形式に採用した。2025年2月にリリースされたv1.5.7からは、最大4スレッドのマルチスレッド圧縮が既定で有効になり、シングルスレッドのGZIPとの実質的な速度差はさらに広がった。AWSも内部サービスをgzipからzstdへ切り替え、S3ストレージを約30%削減したと説明している。

BZIP2

BZIP2は複数段階の変換を経てデータを圧縮する。中心となるパイプラインは次のとおりだ。

1. RLE（Run-Length Encoding）：最初のデータに連続する繰り返しを減らす
2. BWT（Burrows-Wheeler Transform）：データを圧縮しやすい形へ並べ替える
3. MTF（Move-to-Front Transform）：BWTの出力を数値列へ変換する
4. RLE：MTF結果の繰り返しをもう一度減らす
5. Huffman Coding：最後に頻度ベースの符号化を行う

GZIPより高い圧縮率を得られるが、圧縮も展開も遅い。高い圧縮率が必要で、速度の優先度が低いアーカイブ用途に使われてきた。

ただし、最後のリリースは2019年のv1.0.8で、活発な開発はほぼ止まっている。圧縮率と速度の両面でZSTDがBZIP2を上回るベンチマークが増え、新規プロジェクトではZSTDが選ばれることが多い。

XZ

XZはLZMA2を使う圧縮形式だ。LZMA（Lempel-Ziv-Markov chain Algorithm）はIgor Pavlovが開発し、LZ77ベースの辞書圧縮と範囲符号化（Range Encoding）を組み合わせている。LZMA2は単純な「LZMAの改良版」というより、LZMAストリームを包むコンテナ形式に近い。マルチスレッド圧縮・展開と、圧縮しにくいデータを効率よく扱う仕組みが加わっている。

この記事で扱う形式の中では、最も高い圧縮率を誇る。その代わり圧縮速度は非常に遅く、メモリ使用量も大きい。保存容量の削減を最優先するアーカイブに向いている。

しかし2024年3月、XZの中核ライブラリxz-utilsでバックドアが発見される深刻なサプライチェーン事件、CVE-2024-3094が起きた。2年にわたるソーシャルエンジニアリング攻撃でメンテナー権限が奪われ、CVSS 10.0という最高深刻度が付いた。主要ディストリビューションは直ちに安全なバージョンへロールバックしたが、この事件はオープンソースのサプライチェーンセキュリティに強い警鐘を鳴らした。（XZ自体の技術的価値は変わらないが、ツール選定ではこの背景も知っておきたい。）

TAR

TAR（Tape Archive）は、それ自体が圧縮アルゴリズムではない。複数のファイルとディレクトリを一つのアーカイブファイルへまとめるツール兼形式だ。名前のとおり、もともとは磁気テープへのバックアップ用に作られた。テープは順次アクセスする媒体なので、データを連続して並べる構造が自然だった。

TARの内部構造は意外に単純だ。すべてのデータを512バイトのブロック単位で扱う。各ファイルの前には512バイトのヘッダーブロックがあり、ファイル名、最大100バイト、ファイルモード、所有者UID/GID、サイズ、更新時刻、チェックサムなどのメタデータが入る。ファイルデータはヘッダーに続き、512バイトの倍数になるようパディングされる。アーカイブの終端は二つの512バイトゼロブロックで示す。現代の多くのTAR実装はPOSIXの**UStar（Unix Standard TAR）**形式に従い、最大256バイトの長いファイル名と追加メタデータフィールドを扱える。

重要なのは、TARが権限、所有者、タイムスタンプ、シンボリックリンクなどのUnixファイルシステムメタデータをそのまま保存することだ。ZIPではUnix固有のメタデータを完全に保持できない場合があるため、サーバー環境へのデプロイにはTARのほうが適していることが多い。

TARだけではサイズは小さくならない。ヘッダーとパディングによって、むしろ元より少し大きくなることもある。実際の圧縮はGZIP、BZIP2、XZ、ZSTDなどと組み合わせて行う。.tar.gz、.tar.bz2、.tar.xz、.tar.zstという拡張子が存在するのはそのためだ。TARが「まとめる」役割を、圧縮ツールが「小さくする」役割を担う。これは「一つのことをうまくやれ」というUnix哲学の典型例だ。

Unix/Linux環境では標準的なアーカイブ手段だが、Windowsでは7-Zipなどの追加ソフトウェアが必要になる場合がある。

Brotliも知っておこう

フロントエンド開発者なら、Brotliも押さえておく必要がある。BrotliはGoogleが開発した圧縮アルゴリズムで、2015年にHTTPストリーム圧縮仕様Content-Encoding: brとして標準化された。

主要ブラウザーはすべてHTTPS環境で対応し、世界での対応率は96%以上だ。GZIPより約15〜25%高い圧縮率を示し、特にJavaScript、CSS、HTMLのようなテキストベースの静的ファイルに効果的だ。Cloudflareをはじめとする主要CDNで標準の圧縮方式として採用され、現代のWeb最適化は「Brotli優先、GZIPフォールバック」と整理できる。

ビルド成果物をS3へ置いてCDNから配信する構成なら、静的ファイルをあらかじめBrotliで圧縮することでネットワーク転送を大きく最適化できる。（当時のプロジェクトではすぐ導入できるほどの材料がなかったが、開発者として知っておき、後で再検討する価値はある。）

tar.gzがZIPより高い圧縮率を得られる理由

これは**ソリッドアーカイブ（Solid Archive）と非ソリッドアーカイブ（Non-solid Archive）**の違いから生じる。

tar.gzは、TARですべてのファイルを一つの連続データストリームへまとめた後、GZIPがストリーム全体を一度に圧縮する。そのため、ファイルをまたぐ重複データを認識して利用できる。これがソリッドアーカイブ方式だ。ビルドフォルダーに構造の似たJavaScriptバンドルが数十個あれば、ファイルAに現れたパターンをファイルBで再び参照できる。ファイルごとに独立したヘッダー、チェックサム、目次（Table of Contents）を持つ必要もないため、メタデータのオーバーヘッドも減る。

一方、ZIPはファイルごとに独立して圧縮する非ソリッド方式なので、ファイル間の重複を利用できない。ファイルAとBに同じコードブロックがあっても、別々のDEFLATEストリームは互いの存在を知らない。一般にtar.gzがZIPより5〜15%高い圧縮率を得るのはこのためだ。似た構造のファイルが大量に入るビルド成果物ほど差は大きくなる。

ただし、ソリッドアーカイブにも明確な欠点がある。

• 特定のファイルを一つだけ取り出す場合でも、そのファイルより前にあるデータをすべて先に展開しなければならないことがある。全ファイルが一つのストリームでつながっており、中間へ直接移動できないからだ。ZIPは個別ファイルへランダムアクセスできるため、特定ファイルを頻繁に取り出す用途ではZIPのほうが適している場合がある。
• アーカイブの一部が壊れると、破損箇所以降のすべてのデータを復旧できなくなる可能性がある。非ソリッド方式なら壊れた一ファイルだけを失い、残りを救える場合がある。

2026年追記

2024年にはtar.gzを選んだ。今ならどうするか

当時tar.gzを選んだ理由は、互換性と安定性だった。S3へアップロードした後にさまざまな環境で展開する必要があったため、ほぼどこでも使えるtar.gzが安全な選択だった。

しかし同じ状況に今もう一度直面したなら、**tar.zst（TAR + ZSTD）**を真剣に検討する。先ほどのベンチマーク値を思い出してほしい。

GZIP既定レベルの圧縮速度は34MB/sだが、ZSTD既定レベルは300MB/sだ。2GBのビルドフォルダーなら、単純計算でGZIPは約60秒、ZSTDは約7秒で圧縮を終える。ZSTD v1.5.7以降に既定で有効となった最大4スレッドのマルチスレッド処理まで考慮すれば、体感差はさらに大きい。CI/CDパイプラインでは、この差がデプロイのたびに積み重なるため無視できない。

# tar.zst 생성 (멀티스레드 자동 활용)
tar --zstd -cf archive.tar.zst directory/
 
# 또는 압축 레벨 지정 (-T0은 사용 가능한 모든 코어 활용)
tar -cf archive.tar.zst -I 'zstd -3 -T0' directory/

圧縮率でもZSTDはGZIPと同等か、それ以上だ。「速度のために圧縮率を諦める」というトレードオフは事実上なく、速いうえに成果物も小さい。

ただし受信側の環境でzstdを展開できるかは必ず確認しなければならない。主要Linuxディストリビューションにはすでに含まれ、macOSでもHomebrewのbrew install zstdで簡単にインストールできる。一方、レガシーシステムや最小構成の環境では追加インストールが必要な場合があるため、チームが使う全環境を事前に点検することが重要だ。互換性が最優先なら、今でもtar.gzが最も無難な選択だ。

一覧で比較する

おわりに

圧縮を掘り下げる前は、正直「ただzipでまとめればよいのでは」と思っていた。しかし2GBを超えるビルドフォルダーを実際に扱うと、どのアルゴリズムを選ぶかによってアップロード時間とコストが大きく変わることを実感した。

それぞれの圧縮形式には異なる設計思想とトレードオフがある。ZIPの互換性、GZIPの汎用性、ZSTDの速度、XZの圧縮率まで、どれか一つを「最高」と断定することはできない。適した選択はプロジェクトの状況によって変わる。

普段何気なく使う道具の原理を調べておけば、次に似た問題へ出会ったとき、よりよい判断ができる。この文章が圧縮アルゴリズムを選ぶ誰かの小さな手がかりになればうれしい。