きっかけ
2026年5月2日現在，私はセキュリティ・キャンプ2026ネクストへの応募に向けて,応募課題を進めています．
応募課題の中に自ら技術的な疑問を設定して，解答するものがあり，「せっかくやるなら普段使ってるけど，あまり仕組みを理解してないものを調査したら楽しいのではないか」という気持ちで「zip圧縮化の仕組み」を調査することに決めました．
ZIPファイル圧縮の方式（Deflateアルゴリズム）
ZIPファイルの最も標準的な圧縮アルゴリズムは「Deflate」です．これは，「辞書式アルゴリズム」で文字列の繰り返しパターンを圧縮したのちに，その結果に「ハフマン符号化」を行うことで圧縮を行います．
辞書式圧縮 (LZ77 / LZSSベース)
辞書式圧縮には，「LZ○○」といった形で様々な派生アルゴリズムがあります．大本はLampelとZivが1977年に発案した「LZ77」で，それにStorerとSzymanskiが改良を加えた「LZSS」が主流となっています．
具体的には，「LZ77」では，文字列の繰り返し圧縮するために(一致する文字パターンの参照部最後尾からのオフセット，文字列の繰り返しが一致する長さ，そのパターンに一致しなくなる最初の文字)を結果として出力していたところを，一致した場合はLZ77と同様の出力，一致しない場合はそのままの文字を出力し1ビットのフラグで区別します．これによって，不必要な情報を省略しています．
当然，圧縮データの構造次第で1ビットのフラグは無駄な冗長になるため，必ずしも優れているわけではない．
以下にアルゴリズムの動作例（LZ77）を示す．
まず，今回扱う文字列は次の通りである．
「あ，あ，い，あ，あ，い，あ，あ，う，え，あ，う」
また，参照部と複合部を次のように定義する．
- 参照部（探索バッファ：Search buffer）：すでに圧縮を終えた部分（有限長）
今回は{}で表現 - 符号部（先行読み込みバッファ：Lookahead buffer）：これから圧縮しようとする部分（有限長）
今回は[]で表現
ステップ１
状態：「[]{あ}，あ，い，あ，あ，い，あ，あ，う，え，あ，う」
出力：(0, 0, あ)
最初なので符号部は{あ}で，一致しなくなる文字も「あ」です．参照部[]は空なので出力は(0, 0, あ)となります．
ステップ２
状態：「[あ]，{あ，い}，あ，あ，い，あ，あ，う，え，あ，う」
出力：(0, 0, あ),(1, 1, い)
符号部は{あ，い}です．このとき，一致しなくなる文字は「い」です．
参照部は[あ]で，一致する文字列も[あ]です．オフセットは１，一致する文字列の長さも１となり，出力は(1, 1, い)
ステップ３
状態：「[あ，あ，い]，{あ，あ，い，あ}，あ，う，え，あ，う」
出力：(0, 0, あ),(1, 1, い),(3, 3, あ)
符号部は{あ，あ，い，あ}です．このとき，一致しなくなる文字は「あ」です．
参照部は[あ，あ，い]で，一致する文字列は[あ，あ，い]なので，オフセットは3，一致する文字列の長さは3となり，出力は(3, 3, あ)です．
ステップ４
状態：「[あ，あ，い，あ，あ，い，あ]，{あ，う}，え，あ，う」
出力：(0, 0, あ),(1, 1, い),(3, 3, あ),(1, 1, う)
符号部は{あ，う}です．このとき，一致しなくなる文字はなく，終了です．
参照部は[あ，あ，い，あ，あ，い，あ]で，一致する文字列は[あ]なので，オフセットは1，一致する文字列の長さは1となり，出力は(1, 1, う)です．
また，一致する文字列が複数ある場合（今回だとオフセットで１，３，４，６，７に[あ]が含まれる），最も近いものを選ぶことが多いです．
ステップ５
状態：「[あ，あ，い，あ，あ，い，あ，あ，う]，{え}，あ，う」
出力：(0, 0, あ),(1, 1, い),(3, 3, あ),(1, 1, う),(0, 0, え)
符号部は{え}です．このとき，一致する文字はないので，オフセット0，一致する文字列は0となり，出力は(0, 0, え)です．
ステップ６
状態：「[あ，あ，い，あ，あ，い，あ，あ，う，え]，{あ，う}」
出力：(0, 0, あ),(1, 1, い),(3, 3, あ),(1, 1, う),(0, 0, え),(3, 2, EOF)
符号部は{あ，う}です．このとき，一致しなくなる文字はなく，終了（EOF：End Of File）です．
参照部は[あ，あ，い，あ，あ，い，あ，あ，う，え]で，一致する文字列は[あ，う]なので，オフセットは3，一致する文字列の長さは2となり，出力は(3, 2, EOF)です．
EOFには，文字データとしてあり得ない256を入れたり，ヘッダに文字列の長さを記録しておき，そもそも書かない？（何かしらは入れた方がいいと思うが）といったことをするそうです．
LZSS
ここで，最終的な出力「(0, 0, あ),(1, 1, い),(3, 3, あ),(1, 1, う),(0, 0, え),(3, 2, EOF)」を見ると効率の悪い部分に気づくと思います．(0, 0, あ)と(0, 0, え)です．これらは一致する文字列がなかった時の出力ですが，一致しないのであれば必ず一致する文字列の長さは0,0なのでわざわざ2bit情報を使っています．
そこで，一致する場合とそうでない場合を1bitのフラグで分けたものがLZSSとなります．
ハフマン符号
辞書圧縮形式で変換されたデータに対して，さらにデータサイズを削減します．
このデータサイズの削減に用いられるのが，ハフマン符号です．
このハフマン符号はコンパクト符号という特徴があり，コンパクト符号とは，情報源記号に一個づつ一意復号可能な符号化を行うとき，平均符号長を最小とする符号のことです．
つまり，ハフマン符号を用いることで情報源記号の平均データサイズを最小化し，一意に複合できる符号化が行えるということです．
なぜ平均符号長最小といえるのか？
ここで情報理論を習っていない皆さんは一つ疑問に思うことがあると思います．それは，「平均符号長を最小する符号であるということは，平均符号長の最小って分かっているの？」です．
結論，平均符号長は，その情報源エントロピー以下にはならないという定理が示されています．つまり，この情報源エントロピーが下限の役割を示しています．
定理
情報源 $S$ を一意復号可能な2元符号に符号化したとき，平均符号長 $L$ は以下の条件を満たす．
$$L \ge H_{1}(S)$$
ここで，$L$ は平均符号長（$L := \sum_{i=1}^{M} l_{i} p_{i}$）であり，$H_{1}(S)$ は一次エントロピー（$H_{1}(S) := -\sum_{i=1}^{M} p_{i} \log_{2} p_{i}$）である．
詳しい，証明は以下に記します．興味があったら読んでください．
平均符号長の下限の証明
1．補助定理の証明
以下の条件を満たす任意の非負の数 $q_{1}, q_{2}, \dots, q_{M}$ を考える．
$$\sum_{i=1}^{M} q_{i} \le 1$$
このとき，以下の不等式が成立する．
$$-\sum_{i=1}^{M} p_{i} \log_{2} q_{i} \ge -\sum_{i=1}^{M} p_{i} \log_{2} p_{i} = H_{1}(S)$$
【証明】
両辺の差を $D$ とおく．
$$D := -\sum_{i=1}^{M} p_{i} \log_{2} q_{i} + \sum_{i=1}^{M} p_{i} \log_{2} p_{i}$$
$$D = -\sum_{i=1}^{M} p_{i} \log_{2} \frac{q_{i}}{p_{i}}$$
対数の底を変換する．
$$D = -\sum_{i=1}^{M} \frac{p_{i}}{\ln 2} \ln \frac{q_{i}}{p_{i}}$$
任意の $x \ge 0$ について $\ln x \le x - 1$ となる性質を利用する．
$$D \ge \sum_{i=1}^{M} \frac{p_{i}}{\ln 2} \left(1 - \frac{q_{i}}{p_{i}}\right)$$
$$D \ge \frac{1}{\ln 2} \left(1 - \sum_{i=1}^{M} q_{i}\right) \ge 0$$
前提条件 $\sum_{i=1}^{M} q_{i} \le 1$ より，$D \ge 0$ が成立する．
（等号成立は $q_{i} = p_{i}$ のとき）
2．平均符号長がエントロピー以下にはならないことの証明
情報源 $S$ の符号において，$q_{i} := 2^{-l_{i}}$ とおく．
各符号語の長さ $l_{1}, l_{2}, \dots, l_{M}$ はクラフトの不等式（マクミランの不等式）を満たすため，以下の式が成立する．
$$\sum_{i=1}^{M} q_{i} \le 1$$
これにより補助定理が適用できるため，以下の不等式が成り立つ．
$$-\sum_{i=1}^{M} p_{i} \log_{2} q_{i} \ge -\sum_{i=1}^{M} p_{i} \log_{2} p_{i} = H_{1}(S)$$
ここで $l_{i} = -\log_{2} q_{i}$ であるため，平均符号長 $L$ の式に代入する．
$$L = \sum_{i=1}^{M} l_{i} p_{i} = -\sum_{i=1}^{M} p_{i} \log_{2} q_{i} \ge H_{1}(S)$$
以上により，$L \ge H_{1}(S)$ が証明される．
（等号成立は $p_{i} = 2^{-l_{i}}$ のとき）
圧縮は保証されるのか？
結論として，可逆圧縮アルゴリズムがあらゆるデータを必ず圧縮できるという保証はありません．これは，数学の「鳩の巣原理」を用いて証明することができます．
「鳩の巣原理」とは，「4つの巣に5羽の鳩を入れる場合，少なくとも1つの巣には2羽以上の鳩がいる．」という考え方です．ここで重要なのでこの考えでは，どこの巣に何羽の鳩がいるかを特定できていないということです．
これをN個のデータ圧縮に置き換えると，「N-1個の圧縮後データ(巣)に対して，N個の圧縮前データ(鳩)を割り当てようとすると，少なくとも一つの圧縮後データに，2つ以上の圧縮前データが入る．」ことになります．
「少なくとも一つの圧縮後データに，2つ以上の圧縮前データが入る．」と主張できるということは，同時にどこに圧縮前データがあるかわからない，追跡できないことを示しています．この時点で可逆圧縮でなくなり，また，追跡するために冗長性を持たせるならかえって，ファイルサイズが大きくなります．
数学的な原理を用いず直感的な説明をするなら，「どんな場合でも可逆圧縮可能であれば，いつかは1bitのデータに圧縮されますが，1bitだけで表現できるパターンは2通りであり，膨大な種類あるデータを2通りで表現できわけないよね」といった感じです．
誤り訂正は行われるのか？
ZIPファイル自体は「誤り訂正（Error Correction）」を行わず，「誤り検出（Error Detection）」のみを実施します．これは，ZIPが開発された当時の「役割分担」の思想が背景にあります．データ転送中の誤り訂正はTCP/IPなどのネットワーク層が，保存時の誤り訂正はハードウェア層が担います．そのため，ZIPフォーマット自体が誤り訂正アルゴリズムを持つことは，不要な二重処理とみなされ，このような設計がとられたらしいです（ZIP設計者が計算コストを優先した説や構造上必要としなかった説等々諸説あり）．
また，一方でデータの破損がないかの完全性については，CRC-32(巡回調査検査)により誤り検出を行っています．ファイル全体から生成多項式を用いて計算した32ビットの「CRC値」を付与し，展開時に一致しない場合は破損データとして，展開を注視します．
ZIPファイル以外の圧縮形式との違いは何か？
ZIP形式以外の圧縮化形式として7Z形式，TAR形式をよく見ると思う．
ここでは，これら２つの形式とZIP形式の違いについてまとめる．
まず，おおまかな違いとしては次の表のとおりである．
| ファイル形式 | アルゴリズム | 圧縮速度 | 圧縮の特徴 |
|---|---|---|---|
| ZIP | Deflate | 早い | |
| 7Z | LZMA | 遅い | 最高クラス |
| TAR | Deflate | 早い | ZIPと比較すると高い |
7Z形式との違い
7Z形式では，ZIP形式とは異なるアルゴリズム（LZMA）を用いる．このアルゴリズムを説明すると本記事と同程度のコンテンツ量になるため，詳しい説明は避ける（また，調査次第投稿します）．
大まかな説明としては，Deflateより大きさサイズの辞書と文脈を確率モデルとして学習しながら圧縮を行う．
つまり，メモリを最大限使用して，最大限圧縮する方法です．
TAR形式との違い
ZIPファイルと使っているアルゴリズム（Deflate）は同じ．大きな違いとして，ZIPファイルはファイルごとに圧縮を行うのに対して，TARはファイルをまとめて圧縮を行う．そのため，辞書の使いまわしが効く分，基本的にはTAR形式の方が圧縮率は高くなる．
一方で，まとめて圧縮を行うということは，１つのファイルで完全性が保証されなければ他のファイルも取り出せなくなってしまうことになる．この完全性に対する信頼度の違いでZIP形式とは使い分けができるといえる．
まとめ
ZIPファイルは，LZSSとハフマン符号を組み合わせることで，パターンの繰り返しを省き，より短い符号化表現を行います．一方で，情報理論の観点からすべてのファイルを圧縮することは保証されていません．また，役割分担の思想で誤り訂正は実施されず，CRC-32による誤り検出を行うことで完全性を担保しようとします．
参考文献
以下，この記事の執筆にあたって参考にさせていただいた文献です．