おなじ ことばが なんども 出てくる 文を、みじかく したいと します。「あいうえおあいうえお」なら、「あいうえお」と かいて、「5もじ もどって 5もじ うつす」と しじを そえれば よさそうです。

この しじを よめば、もとの 文が ぜんぶ もどります。もどせる のは、ちぢめかたが「もどしかたまで きまった かきかた」だからです。ファイルの ちぢめかたも、これと おなじ かんがえです。

では、ほんとうの ZIPは、どんな しじを かいて いるのでしょう。

FLACの仕様は、FLACを「情報を失わずに」音のデータを小さくする形式だと説明しています［1］。ZIPなどで使われるDEFLATEも、展開すれば元のデータが返る可逆の方式です［3］。

戻せる理由は、縮め方が「情報を捨てる」ものではなく、「書き方を変える」ものだからです。たとえば「ABCDEFABCDEF」という文字の並びを、「ABCDEF」と書き、続けて「6文字戻って6文字写す」という指示を添えれば、元の12文字が組み立て直せます。これは説明のための例で、実際の形式の書き方とは少し違います。

では実際のZIPは、どんな指示を書いているのでしょうか。

可逆圧縮は、データを別の書き方に置きかえて短くし、展開時に元の並びを完全に復元する方式だ。FLACの仕様は、FLACが「情報を失うことなく」音のデータの保存容量を減らす形式だと定義している［1］。ZIPやgzipが使うDEFLATEも同じく可逆である［3］。

縮めるときに捨てるものがない以上、戻す側は、縮める側の手順を逆にたどればよい。説明用の例として、「ABCDEFABCDEF」を「ABCDEF」と「6文字戻って6文字写す」の指示に置きかえると、12文字が復元できる。実際の形式は指示の持ち方が異なるが、考え方は同じだ。では実際のDEFLATEは、どういう指示を書いているのか。

ZIPなどで つかわれる しくみ（DEFLATE）は、ほぼ その とおりの ことを して います。おなじ ことばが まえに 出て いれば、もう いちど かくかわりに、「なんもじ もどって、なんもじ うつす」という しじを かきます［3］。

もどす ときは、この しじに であうたびに、さきに できあがった 文の うしろを のぞいて、その ぶぶんを うつします。きめられた しじどおりに うつすと、もとの 文に もどせます。

ただし うつせる はんいには かぎりが あります。もどれるのは 32Kバイトまで、うつせるのは 258バイトまでです［3］。

さて、ことばには、よく 出る ものと、あまり 出ない ものが あります。この ちがいも、ちぢめるのに つかえるでしょうか。

DEFLATEは、LZ77という方法とハフマン符号を組み合わせています。縮めるときには、前に出てきた文字列と同じ並びを見つけて、「<長さ, 戻る距離>」という組の指示に置きかえます［3］。

戻すときは、写すだけ

展開するときは、その指示に出会うたびに、出力の距離ぶん後ろへ戻り、そこから長さぶんを写して出力の最後に足していきます［3］。すでに組み立てた部分を見て写すだけなので、判断が入り込む余地がありません。

ただし、戻れる距離は最大32Kバイト、写せる長さは最大258バイトという決まりがあります［3］。ずっと遠くの同じ文字列までは参照できません。

前に出た並びを指示に置きかえる方法のほかに、出てくる回数の差を使う方法もあります。次の章がその話です。

DEFLATEは、LZ77とハフマン符号を組み合わせる。LZ77の部分では、重複した文字列を「<長さ，後方への距離>」という対のポインタで表す［3］。

展開側は、このポインタに出会うと、出力ストリームを距離のバイト数だけさかのぼり、そこから長さのバイト数をコピーして出力に連ねる［3］。コピーは、すでに復元した位置から始まる。写した文字を続けて使う場合もある。だから復号は、先頭から順に、読んで写すだけの処理になる。

これには条件がある。距離は最大32Kバイト、長さは最大258バイトで［3］、この窓より遠い重複は指示にできない。縮め方の工夫は、窓の外の同じ並びには働かない。一方、もう1つの要素であるハフマン符号は、記号の出る回数のちがいを使う。それがどう生まれたのかが次の章だ。

「あ」が たくさん 出て くる 文では、「あ」を みじかい 合図で あらわし、ほとんど 出ない もじを ながい 合図で あらわすと、ぜんたいは みじかく なります。これが ハフマンふごうの かんがえです［4］。

この かんがえを 見つけたのは、アメリカの 学生 ハフマンだと つたえられて います［4］。1951ねん、MITで、ファノ先生の じゅぎょうの 宿題でした。「いちばん むだの ない 二しんの ふごうを 見つけなさい」という もんだいです。

ハフマンは、なかなか とけず、あきらめかけた そうです。そのとき、出る 回数の じゅんに ならべた 木の 絵を おもいついた、と つたえられて います［4］。

さて、ZIPは 文字の はなしでした。音は、どうやって ちぢめるのでしょう。

よく出る記号には短い符号を、まれな記号には長い符号を割り当てるのが、ハフマン符号です［4］。全体の長さが短くなるのに、割り当ての表をたどれば元に戻る可逆の符号です。

授業の課題が、きっかけだったと伝えられる

1951年、アメリカのMITで、ロバート・ファノ教授の情報理論の授業を受けていた学生のハフマンは、期末試験を受けるか、学期末のレポートを書くかを選べたと伝えられています［4］。レポートの課題は、最も効率のよい二進符号を見つけることでした。

ハフマンは、どの符号が最適かを証明できず、あきらめて試験勉強を始める寸前だったといいます。そこで、出現頻度の順にならべた二分木を使う案を思いつき、最適だと示したと伝えられています［4］。この逸話は雑誌記事を引用した二次的な説明で、細部は話によって少し違う可能性があります。

文章を縮める話はここまでです。音は、文字とはちがう縮め方をします。

ハフマン符号は、記号の出現頻度に応じて、頻出の記号に短い符号、まれな記号に長い符号を割り当てる可逆の符号だ［4］。

この符号の誕生には逸話がある。1951年、MITのロバート・M・ファノの情報理論の授業で、デイビッド・A・ハフマンらは、期末試験か学期末レポートを選べた。レポートの課題は最も効率のよい二進符号を見つけることで、ハフマンは最適な符号を証明できず、あきらめて試験勉強に移る寸前に、頻度順の二分木を思いついたと伝えられる［4］。出典は、1991年の雑誌記事を引いたWikipediaの記述なので、細部は話によって違う可能性がある。

成果は1952年9月の論文「A Method for the Construction of Minimum-Redundancy Codes」で、Proceedings of the IRE 40(9)の1098〜1101ページに載った［8］。木を頻度の低い記号の側から組み立てると最適になる［4］。なお、記号の種類が2の累乗個で、すべて同じ頻度なら、固定長の符号より短くする余地はない。この「偏りがあって初めて縮む」という考え方は、6章で数え上げの議論として戻ってくる。では、音のデータでは、どこに規則性を見つけるのか。

音は、数の ならびで あらわせます。ところが、音の 数は、となりどうしで にた 大きさに なりやすい もの です。そこで FLACは、まず「つぎの 数は、このくらいだろう」と よそうします。

そして、本当の 数と よそうの ずれだけを かきます。よそうが 当たれば、ずれは 小さい 数なので、みじかく かけます［1］。

この ずれを みじかく かくために、小さい 数ほど みじかく なる かきかた（Riceふごう）も つかいます［1］。

では、この ずれだけを 見て、もとの 音に もどせるのでしょうか。

FLACは、音のデータを小さなブロックに分けて、ブロックごとに別々に符号化します［2］。ステレオの音では、左右の音を「中央（左右の平均）」と「差（左から右を引いたもの）」に置きかえる方法も、選べる方式の1つとして用意されています［2］。

予想して、ずれだけを書く

各ブロックでは、まず音の並びを関数で近似し、つまり予想します。そして、実際の値と予想の差（残差）だけを書きます。予想がうまく当たれば、残差は元の値より少ないビット数で書けます［1］。

予想の作り方には、係数を保存しない固定予測器（次数0〜4の5種類）と、最大32個の係数を持つ線形予測があります［1］。線形予測は係数を保存する手間がかかりますが、複雑な音にも効きます。

残差の書き方には、小さい値ほど短くなるRice符号を使います［1］。

音そのものの数字が大きくても、予想が当たればずれは小さくなる、という点が、この方法の要です。では、戻すときは何をするのでしょう。

FLACは、音声をブロックに分け、ブロックごとに独立して符号化する。ステレオでは、左右をmid＝（L＋R）／2、side＝L−Rに変換する方式も選べる。常に使われるわけではない［2］。

各ブロックは、関数で近似（予測）され、実際の値との差（残差）だけが書かれる。予測が有効なら、残差は元の信号より少ないビット数で表せる［1］。予測器には、係数を保存しない固定予測器（次数0〜4の5種類）と、最大32個の係数とシフトを持つ線形予測がある。線形予測は係数の保存に手間がかかるが、複雑な音に効く［1］。

残差の符号化にはRice符号（Golomb符号の一種）を使う。残差は先に非負へ畳まれ、Rice parameterで上位と下位に分けられる。上位は「0の個数＋1」のunary、下位はそのまま二進数で書く。仕様の例では、parameter 3で畳んだ後の値38（0b100110）は、上位が0b100（＝4）で00001、下位が0b110となり、0b00001110と書かれる［1］。小さい値ほど短い符号になる。このしくみがうまく働くのは、予測が当たって残差が小さくなる音に限られる。では、残差から元の値を戻す手順はどうなっているか。

もどす ときは、ずれを よみとって、よそうの 数に たします。たすだけで、もとの 数が でて きます［1］。

そのために、よそうは、もどす がわでも おなじ けいさんで つくれる ように なって います。ちぢめる ときと おなじ やりかたで よそうを つくって、ずれを たすからです。

では、もどした 音が ほんとうに 同じか、どうやって たしかめるのでしょう。FLACには、「しるし」が ついて います。ちぢめる まえの 音の MD5（エムディーファイブ）という しるしが ファイルの 中に 入って います［1］。もどした 音から おなじ しるしが 作れれば、ただしく もどせたか たしかめる てがかりに なります。

FLACを再生するとき（復号）は、残差を読み取り、各サンプルに予想を足して元の値に戻します［1］。予想は、復号する側でも同じ計算で作れます。仕様では、固定予測器の場合、残差を復号した後に予測値を足していくと説明されています［1］。足し算だけで戻るのは、縮める側が予想を引いた分を、戻す側がそのまま足し直すからです。線形予測では、予想を作る係数が保存されているので、その係数を使います［1］。

戻した音が同じかを、確かめる印

FLACのSTREAMINFOという部分には、符号化する前の音のデータのMD5（データから作る短い指紋のような値）が入っています。復号した結果から計算した値と比べれば、正しく戻ったかが確かめられます［1］。各フレームには、16ビットのCRCという、誤り検出用の値も付いています［1］。

そのため、MD5やCRCの値を比べて、戻したデータに違いがないかを確かめられます。

FLACの復号は、縮める手順の逆である。固定予測器の場合、残差を復号し、各サンプルに予測値を加えて元の値を得る［1］。予測値は復号側でも同じ計算で再現できるので、加算だけで元の値に戻る。線形予測では、予測に使う係数が保存されており、復号側はその係数を読んで同じ計算をする［1］。

戻った結果は検証できる。STREAMINFOには符号化前の音データのMD5が入っており、デコーダが誤りの有無を判定するのに使える。各フレームには16ビットのCRC（誤り検出符号）も付く［1］。

「戻る」ことを、仕組みの上でも、確かめる手段の上でも保証している点が、可逆圧縮の信頼性を支える。ただし、MD5やCRCは偶然の壊れを見つけるための符号で、設計上の誤りまで見つけるものではない。そもそも、なぜここまで厳密に戻せる形式でなければならないのか。逆に、どんなデータでも縮められれば、もっと便利ではないのか。この問いに数え上げが答える。

3ビットの ならびは、「000」から「111」まで、8とおり あります。2ビットの ならびは、4とおりしか ありません。

8とおりの ファイルを、4とおりの 短い ファイルに ぜんぶ わりあてると、どこかで おなじ 短い ファイルに なる ものが 出ます。それでは、もどす ときに、どちらの ファイルか わかりません［5］。

だから、どんな ファイルでも ちぢめる やりかたは、つくれません。ぜんぜん きまりの ない でたらめな ならびは、ふつう ちぢめにくい ものです。やりかたに よっては、すこし ながく なる ことも あります［6］。

音には 音の、文章には 文章の きまりが あります。その きまりに あわせて、ちがう やりかたが 作られて きたのです。

nビットのファイルは2のn乗通りあります。たとえば3ビットなら8通りです。それより短いファイルの種類は、2ビットなら4通りしかありません。8通りを4通りの短いファイルに割り当てると、必ず同じ出力になる入力ができて、戻せなくなります。これは「鳩の巣原理」の考え方です［5］。

長さ0から2ビットまでを全部足しても、1＋2＋4＝7通りで、3ビットの8通りには足りません。長さ0〜n−1ビットをすべて足せば2のn乗−1通りで、いつも元より1つ少なくなります。

縮まないデータもある

そのため、可逆圧縮は、あらゆるデータを小さくはできません。一部のデータは、少なくとも1記号は長くなります［6］。規則性（冗長性）のない、でたらめなデータは、一般に縮めにくく、方法によっては少し長くなります。だから音声や文章、画像ごとに、それぞれの規則性に合わせた方法が作られました。

シャノンは1948年の論文で、情報の量（エントロピー）を定めました。そこから、可逆圧縮には、これ以上縮められない限界があると分かっています［7］。ただしこれは「平均で」「記号が同じ確率で独立に出てくる情報源」という条件つきの話で、個々のファイルの限界ではありません。

nビットのファイルは2ⁿ通りある。nビットより短いファイルは、長さ0〜n−1ビットの合計で2ⁿ−1通りにしかならない。たとえば3ビットは8通りで、2ビットは4通りだ。8通りを4通りに割り当てれば、同じ出力に行きつく入力が必ず出て、復号できなくなる（鳩の巣原理）［5］。したがって、あらゆるデータを縮める可逆圧縮は存在せず、一部のデータは少なくとも1記号長くなる［6］。

縮むかどうかは、データの規則性（冗長性）で決まる。ランダムで規則性のないデータは、一般に縮めにくく、方法によっては少し長くなる。これが、音声・文章・画像ごとに、それぞれの規則性に合わせた方式が作られた理由である［6］。FLACの予測は音の連続性に、DEFLATEの参照は文字列の繰り返しに、ハフマン符号は出現頻度の偏りに、それぞれ頼る。

限界の下限を与えたのが、シャノンが1948年の論文「A Mathematical Theory of Communication」で定めたエントロピーである。N個の記号をNH(X)ビット未満に圧縮すると、ほぼ確実に情報が失われる［7］。ただしこれは、記号が独立同分布の情報源の平均についての結論で、個々のファイルの限界ではない。ハフマン符号などは、この限界に近づく実用的な方法として位置づけられる［7］。

かみと えんぴつを よういします。すきな 文を 1つ かいて、おなじ ならびが 2かい 出る ところを さがします。

2かいめの ところを、「なんもじ もどって、なんもじ うつす」という しじに かきかえます。つぎに、ともだちか おうちの 人に、その かみだけを わたして、もとの 文に もどして もらいます。

もどせたら、せいこうです。つぎは、おなじ ことばが ほとんど 出ない 文でも ためして みましょう。ちぢめられる ところが すくないと 気づくはずです。

紙と鉛筆で、「縮める」と「戻す」を往復してみましょう。自分で短い文を1つ作り、同じ並びが2回以上出る場所を探します。

2回目以降を「何文字戻って、何文字写す」という指示に書きかえて、指示だけを残した紙を友だちや家族に渡し、元の文を組み立て直してもらいます。うまく戻せたら、仕組みがつかめた証拠です。

次に、同じ言葉がほとんど出ない文でも試します。指示に置きかえられる場所が少ないので、あまり縮まないはずです。同じ並びがあるほど縮めやすいことを、自分の手で確かめられます。

手で試すなら、紙の上でLZ77風の往復を行う。好きな歌詞や短文を書き、同じ並びの2回目以降を「何文字戻って何文字写す」の指示に置きかえる。指示だけを別の人に渡し、元の文が復元できるか確かめる。繰り返しの少ない文で同じことをして、置きかえられる箇所の少なさを比べると、規則性の有無と縮みやすさの関係が実感できる。

原典に当たるなら、DEFLATEはRFC 1951、FLACはRFC 9639が公開されている。どちらも英語の仕様書なので、英語が読める人向けの案内になるが、復号の手順が書かれており、このメモで見た「戻す手順」を本文で確かめられる［3］［1］。FLACの設計の流れは、xiph.orgの説明ページも読みやすい［2］。ハフマンの原論文は1952年のProceedings of the IREにある［4］。