ファイルを圧縮したのに、ほとんど小さくならない。
ところが、別のファイルは10分の1になった。同じ操作で、なぜこんなに差が出るのでしょうか。
先に結論：圧縮は、データの特徴に合うかが大切
- ランレングス法：同じ値の連続を「値と長さ」にまとめる。
- ハフマン法：よく出る記号に短い符号を割り当て、全体のビット数を減らす。
- 必ず縮むわけではない：連続が短い、すでに圧縮されている、付加情報が多いといった条件では、大きくなる場合もある。
どちらも元のデータに戻せる可逆圧縮です。今回はユウキの「同じ圧縮ボタンなのに」事件から、何を手掛かりに縮めるのかと、実際のビット数を追ってみましょう。
写真はほぼ据え置き、白黒プリントは10分の1
夜10時。ユウキは部活の写真200枚と、スキャンした練習メニューを圧縮しました。
写真は100MBから98MB。白黒のプリントは20MBから2MBになりました。
ユウキ「同じボタン押しただけなんだけど」
Sandy「ちょおおおおおお待ちぃ！」
ユウキ「……いま『お』をまとめた？」
Sandy「今日のテーマが先に漏れてもうたわ。同じものが続くとこ、まとめられるやろ」
これは架空の物語で、容量も学習用の例です。実際の縮み方は、ファイル形式、保存状態、圧縮方式などで変わります。
方法 | 利用する特徴 | 注目すること |
|---|---|---|
ランレングス法 | 同じ値が連続している | どれくらい長く続くか |
ハフマン法 | 記号ごとに出現回数が違う | 何が何回出るか。連続している必要はない |
白黒画像なら必ずよく縮む、写真なら必ず縮まない、という規則ではありません。
ランレングス法とは？同じ値の連続を「値と長さ」にする
同じ値が連続する区間を、ランといいます。ランレングス法は、その区間を値と長さの組で表します。
たとえば20マスの白黒データが、白7個・黒3個・白10個と続いていたとしましょう。各マスを一つずつ書かず、「白7、黒3、白10」と表せます。
今回の規則では1組5ビット。20ビットのデータ本体を15ビットに表せます。
ただし、文字で短く見えるだけでは、データ量が減ったかどうかは分かりません。値と個数を、何ビットで表すのかを先に決める必要があります。
20ビットが15ビットになる計算
今回は説明用に、次の規則を決めます。
- 元データは、白を0、黒を1として1マス1ビットで表す。
- 圧縮後は、1組を「色1ビット＋個数4ビット」で表す。
- 個数は1〜15を使い、0は使わない。
白7なら「0 0111」、黒3なら「1 0011」、白10なら「0 1010」です。空白は説明用で、各組は5ビットです。
計算は、ランの数を数える→1組のビット数を求める→掛けるの順です。
- 白7・黒3・白10なので、ランは3個。
- 1組は色1ビット＋個数4ビット＝5ビット。
- 圧縮後は3×5＝15ビット。元は20×1＝20ビット。
圧縮後÷圧縮前×100で圧縮率を求めるなら、15÷20×100＝75％。元の75％の量になり、減った割合は25％です。計算では方式を共有するための情報やファイルの付加情報を除いています。
個数4ビットでは15までなので、白が20個続く場合は、この規則では「白15、白5」と分けます。ランレングス法のすべての実装が、同じビット配分を使うわけではありません。
同じ20マスでも、白黒が交互だと増える
白・黒・白・黒……と交互なら、長さ1のランが20個できます。
同じ方式でも、連続が短いと元より大きくなることがあります。
同じ規則で計算すると、20組×5ビット＝100ビット。元の20ビットの5倍です。
ユウキ「圧縮したのに、増えてる！」
Sandy「値だけやったとこに、毎回『1個』の情報も足しとるからな」
ランレングス法は、同じ値が長く続くデータに向いています。白い背景が多い白黒画像などは候補ですが、スキャンのノイズや細かな模様で効き方は変わります。
ハフマン法とは？よく出る記号に短い符号を使う
連続していなくても、ある記号が多く現れることがあります。ハフマン法は、こうした出現頻度を使って符号の長さを決めます。
次の100文字を考えましょう。実際のかな文字の保存方式を示すのではなく、4種類の記号を使った説明用のデータです。
記号 | 出現回数 |
|---|---|
あ | 55 |
い | 25 |
う | 12 |
え | 8 |
4種類を同じ長さで表す固定長符号なら、00・01・10・11の2ビットずつを使えます。合計100文字で200ビットです。
一方、よく出る「あ」に1ビットの短い符号を割り当てれば、その分を減らせそうです。ただし、短い符号を思い付きで付けると、区切りが分からなくなるおそれがあります。そこで、ハフマン木を作ります。
ハフマン木の作り方：小さい二つを結び、和を戻す
いちばん小さい二つの重みを結び、和を新しい重みとして戻す。これを木が一つになるまで繰り返します。
最小の二つを結んで和を戻し、根からの0と1で符号を読み取ります。
手順1：小さい二つを選んで木を作る
ここでいう重みは、その記号やグループの出現回数です。
回 | 選ぶ前の重み | 結ぶ二つ | 結んだ後に残る重み |
|---|---|---|---|
1 | 8・12・25・55 | 8＋12＝20 | 20・25・55 |
2 | 20・25・55 | 20＋25＝45 | 45・55 |
3 | 45・55 | 45＋55＝100 | 100 |
結んでできた和も、次の「小さい二つ」の候補に戻します。 元の記号の回数だけを見て結び続けるのではありません。
手順2：完成した木をたどって符号を読む
枝へ0と1を付け、根から記号までたどったビット列を符号にします。図では、左の枝を0、右の枝を1としています。通る枝が1本なら1ビット、3本なら3ビットです。
記号 | 符号 | 符号長 |
|---|---|---|
あ | 0 | 1ビット |
い | 10 | 2ビット |
う | 110 | 3ビット |
え | 111 | 3ビット |
左右を入れ替えれば、0と1の並びは変わります。同じ重みが並ぶ場合には、結ぶ順番の選択肢も生まれます。正しくハフマン法を適用した木なら、与えられた頻度に対する符号列の合計ビット数は同じ最小値になります。
ただし、これだけで「あらゆる圧縮方式の中で最小」と言えるわけではありません。ここでは、記号ごとに二進の語頭符号を割り当てる範囲を扱っています。
語頭条件とは？区切りなしで読める理由
ハフマン符号には、どの符号も、ほかの符号の先頭部分になっていないという性質があります。これが語頭条件、またはプレフィックス条件です。
「あ＝0」に対し、ほかの符号はすべて1で始まります。「い＝10」は110や111の先頭ではありません。木では、記号をすべて葉に置き、途中の節には置かない形に対応します。
語頭条件を満たす符号なら、先頭から区切りを確定できます。
たとえば0101110110は、頭から次のように読めます。
0｜10｜111｜0｜110 → あ・い・え・あ・う
0を読んだ時点で「あ」が確定し、次の位置からまた読めます。区切り記号を保存しなくても、同じ符号表があれば復号できるのです。
曖昧になる反例は、実際に二通り読んで確かめる
仮に「あ＝0、い＝01、う＝1」と決めると、01は「い」にも「あ・う」にも読めます。これでは元の記号列が一つに決まりません。
まずは、ハフマン符号は語頭条件を満たすので、先頭から順に区切れると押さえましょう。
- 発展：「語頭条件を満たさない」と「復号できない」は同じ？
同じではありません。「あ＝0、う＝01」の二つだけなら、語頭条件は満たしませんが、記号列全体を見れば一意に復号できます。ただし、最初の0だけを読んだ時点では「あ」か「う」の途中かが確定しません。語頭条件は、区切りを先頭から即座に確定できる十分な条件です。
Sandy「『なんか頭がかぶっとる』だけやなく、実際に二通り読めるかまで確かめるんや」
合計ビット数と平均符号長：回数を掛けて足す
符号の長さは1・2・3・3ビットです。これを単純に平均すると2.25ビットですが、今回の100文字の平均にはなりません。短い符号の「あ」が55回も出てくるからです。
符号長の単純平均ではなく、出現回数で重みを付けます。付加情報は除いた計算です。
記号 | 回数 | 符号長 | 必要なビット数 |
|---|---|---|---|
あ | 55 | 1 | 55 |
い | 25 | 2 | 50 |
う | 12 | 3 | 36 |
え | 8 | 3 | 24 |
合計 | 100 | — | 165 |
合計は55×1＋25×2＋12×3＋8×3＝165ビット。平均符号長は165÷100＝1.65ビット／記号です。
1文字が1.65ビットになるわけではありません。 各記号の符号長は1・2・3ビットという整数ですが、100文字全体で平均すると1.65になる、という意味です。
固定長の200ビットと比べ、符号列だけの圧縮率は165÷200×100＝82.5％になります。
符号表や木の情報も数えよう
受信側は、どの符号がどの記号に対応するかを知る必要があります。今回のようにデータごとに符号を決める方式では、木や符号表などの情報も伝えることになります。実際の形式では、元の文字数や終端、バイト境界の調整なども必要です。
したがって、165ビットは圧縮ファイル全体のサイズではありません。短いデータでは付加情報が効き、圧縮前より大きくなる場合もあります。
一方、あらかじめ符号表を共有する方式などもあるため、「ハフマン法では毎回必ず表そのものを添付する」とは限りません。
圧縮済みの写真が縮みにくい理由
最初の事件へ戻りましょう。白黒データには同じ値の長い連続があり、写真はすでに圧縮されたJPEGだった——そんな条件なら、縮み方の差を理解できます。
ただし、実際の圧縮ソフトが、この例のランレングス法だけを使っているわけではありません。たとえばDEFLATEは、繰り返す文字列を扱う方式とハフマン符号を組み合わせています。
JPEGなどの圧縮済みデータは、さらに同じような圧縮を重ねても減らせる余地が小さいことが多く、付加情報で増える場合もあります。これは「非可逆だから」だけではなく、可逆圧縮済みのファイルでも起こります。
また、記号の出現回数に偏りがなくても、並び方に規則があれば別の方式で縮められる場合があります。 010101……は0と1の回数が同じでも、反復しています。今回のランレングス法で増えたからといって、すべての圧縮方式で増えるとは限りません。
ユウキ「『圧縮できるか』じゃなくて、『この方式が何を利用するか』なんだね」
Sandy「せや。連続、頻度、繰り返し。得意な見方がちゃうんや」
練習：ランの数と、符号長を数えよう
以下はこの記事のオリジナル学習例です。実際の共通テスト問題ではありません。付加情報は含めません。
問1：白8・黒8・白4の20マスを、色1ビット＋個数4ビットで表すと何ビット？
ランは3個なので3×5＝15ビットです。元の20ビットに対する比率は75％。白と黒の総数ではなく、連続した区間の数を数えます。
問2：先ほどの符号で「あいあうえ」を表すと何ビット？
0｜10｜0｜110｜111なので、1＋2＋1＋3＋3＝10ビットです。符号列は0100110111になります。
問3：固定長2ビットと、今回のハフマン符号で100文字を比べたい。何が必要？
それぞれの記号の出現回数が必要です。同じ4種類でも、回数が違えば符号列の合計は変わります。ファイル全体を比べるなら、符号表などの付加情報も条件に含めます。
まとめ：書き方の工夫には、得意なデータがある
ユウキは、写真の再圧縮で2MBだけ減らすために、長く待っていたことに気付きました。今回は写真の再圧縮を省き、よく縮むプリントを圧縮して送ることにします。
写真100MB＋プリント2MBなら合計102MB。両方を圧縮した98MB＋2MBの100MBより送信量は多いため、全体の待ち時間が必ず短くなるとは限りません。圧縮の処理時間と、送信量を両方見て判断するのが大切です。
- ランレングス法は、同じ値の連続を値と長さで表す。
- ハフマン法は、頻度に応じて短い符号と長い符号を使い分ける。
- ビット数は、規則を決めてから計算する。平均符号長は回数で重みを付ける。
- 圧縮は必ず小さくなるわけではない。方式とデータの組合せを見る。
仕組みをコードでも確かめたい人は、短い文字列を圧縮して復号するプログラムから試してみましょう。制作を通して学びたい人は、プログラミングスクールSandboxもご覧ください。
