どこまで縮むか

友だちに、この15文字をそのまま送りたいとします。

コンピュータは0と1しか送れません。出てくる文字は4種類なので、1文字を2ビット（0か1を2つ並べたもの）で表せば足ります。A=00、B=01、C=10、D=11と決めれば、15文字で30ビットです。

でも、Aは8回も出てきます。Dは1回だけです。同じ長さを割り当てるのは、もったいない気がしませんか。

では、どう割り当てれば一番短くなるのでしょうか。1952年にハフマンが見つけた手順は、拍子抜けするほど単純です。いま残っている中でいちばん少ない2つを選んで、1つに束ねる。これをくり返すだけです。

束ねるたびに、その2つの上に新しい節ができます。枝の左へ行くと0、右へ行くと1です。

木のてっぺんから文字までたどって、左の枝で0、右の枝で1と書き取ります。これがその文字の符号語（0と1の列）です。

8回出てくるAはたった1ビット。1回しか出ないDは3ビット。よく出る文字ほど短くなっています。

30ビットが25ビットになりました。順番を入れ替えたわけでも、文字を捨てたわけでもありません。割り当てる長さを変えただけで、元どおりに戻せるまま短くなります。

文章の中身によって縮み方がまるで変わります。5つのボタンを順に押してみてください。

工夫なし（全部同じ長さ） ハフマン符号 エントロピー（これ以上は縮まないという限界）

緑の線は「この文章は、どんなにうまい方法を使っても1文字あたりこれより短くはできません」という線です。文字の出方の偏りだけから計算できます。これをエントロピーといいます。

ハフマン符号はこの線にかなり近づきます。ただし、ぴったりには届きません。理由ははっきりしていて、1文字に割り当てられるのが1ビット、2ビット、3ビットという整数だけだからです。9割の確率で出てくる文字を知らせるのに本当に必要なのは0.15ビットですが、ハフマン符号ではどうしても1ビット使ってしまいます。「2種類だけ」のボタンを押すと、この差がはっきり見えます。

短くしても、元に戻せなければ意味がありません。上の符号表でこの文章を0と1の列に直し、それをもう一度文章に戻してみます。

—

符号語は「どれも他の符号語の先頭になっていない」ように作られています（これを接頭辞条件といいます）。だから区切り記号がなくても、先頭から読むだけで切れ目が分かります。

Wordのファイルを1つ、下の枠に放り込んでみてください。拡張子が .docx .xlsx .pptx のどれかなら何でもかまいません。中に何が入っているかを表示します。

先頭の2バイトは 50 4B、文字にすると PK です。ZIPを作ったPhil Katzのイニシャルが、いまも全部のZIPファイルの先頭に残っています。

そして中からは word/document.xml（本文）、word/styles.xml（書式）、docProps/core.xml（作った人や日付）が出てきます。Wordのファイルは、XMLという文字だけの書類を何枚もZIPで固めた箱です。Excelも、PowerPointも同じです。

「明日、太陽が東から昇ります」と言われても、何も知らされた気がしません。「明日、雪が降ります」が9月の新潟で言われたら、思わず聞き返します。めったに起きないことが起きたと知らされたときほど、受け取ったものは大きいのです。この「受け取ったものの大きさ」を数にしたのが情報量です。

確率 p で起きることが起きたと知らせるには、log₂(1/p) ビット必要です。確率2分の1なら1ビット、確率8分の1なら3ビット。そして文章1文字あたりの情報量を平均したものが、STEP2で引いた緑の線、エントロピーです。

1948年にシャノンが示したのは、次のことでした。どんな方法で符号化しても、平均の長さをエントロピーより短くはできない。圧縮ソフトの性能競争は、この天井にどこまで近づけるかの勝負になります。

STEP2で「でたらめな文字列」を試すと、ほとんど縮みませんでした。偏りがなければエントロピーは最大になり、天井が下りてこないからです。縮むかどうかは圧縮ソフトの腕前ではなく、元のデータの偏りで決まります。

ハフマン符号は1文字に整数ビットしか割り当てられません。本当は0.01ビットで済む文字にも1ビットを使ってしまい、天井に届きません。

そこで、1文字ずつ区切るのをやめます。算術符号化は、文章全体を0から1までの数直線上のたった1つの点として表します。文字を読むたびに、その文字の確率の分だけ区間を狭めていく。最後に残った区間の中の1点を送れば、それが文章全体の符号語です。区切らないので、0.01ビットという端数もそのまま持ち越せます。

この算術符号化を、いまの言語モデル（ChatGPTの仲間）と組み合わせて、どこまで天井に迫れるか。さらには天井そのものを下げられないか。それが、この研究室でいま進めている情報源符号化の研究です。

次の語の予測がどういうものかは、単語カード箱で実際に動かせます。そこで作った予測の良し悪しが、そのままこのページの圧縮率につながっています。

← 前に触るとよいのは、いま挙げた 次の語の引き方 です。次に進む → なら どこまで直せるか へ。こちらは余分を削って短くしましたが、あちらはわざと余分を足して、途中で0と1が変わっても元に戻せるようにします。削る側と足す側で、扱っているものはどちらも同じ「余分」です。