第2章 コミュニケーションと情報デザイン
データの圧縮(可逆・非可逆・ランレングス・ハフマン符号)
写真や動画はそのままでは大きすぎるので、表し方を工夫して小さくします。このページでは、圧縮と展開、圧縮率、同じものが続く長さを記録するランレングス圧縮、よく出る文字を短くするハフマン符号(木の作り方と平均ビット数)、可逆圧縮と非可逆圧縮の違いと身近な形式を、図と動く部品で確かめます。
説明
1. 圧縮:意味を変えずに、データを小さくする
写真や動画をたくさん保存すると、スマホや SD カードがすぐにいっぱいになります。送るのにも時間がかかります。そこで、データの表し方を工夫して、ビット数を減らすことを圧縮と呼びます。圧縮したデータを元の形に戻すことを展開(解凍)と呼びます。
どれだけ縮んだかは圧縮率で表します。このページでは、圧縮率=圧縮後の大きさ÷圧縮前の大きさ×100(%)とします。100 が 40 になれば 40% で、小さいほどよく縮んだことになります。
データをしまう所・送るもの



圧縮率=圧縮後÷圧縮前×100(%)。小さいほどよく縮んでいる。
2. ランレングス圧縮:続く数を数える
「AAAAABBBCC」は、「A が5個、B が3個、C が2個」と言えば伝わります。このように、同じものが続く固まり(ラン)の長さを記録する方法をランレングス圧縮(ランレングス符号化)と呼びます。
展開するときは、「A5」を「AAAAA」のように並べ直すだけで、元とまったく同じに戻ります。
3. ランレングスが向くもの・向かないもの
白黒の画像(ファクスの文書など)は、白い画素が長く続くので、ランレングスでよく縮みます。ここでは、1つのかたまりを「色1ビット(白0・黒1)+個数4ビット」の5ビットで表すことにします。
ところが、白と黒がこまかく入れ替わる画像では、固まりの数が増えて、かえって元より長くなります。普通の文章も同じ文字があまり続かないので、ランレングスには向きません。どの圧縮方法も、データの性質に合うときによく縮みます。
4. ハフマン符号:よく出る文字を短く
A・B・C・D の4種類の文字なら、普通は1文字を2ビット(00・01・10・11)で表します(固定長)。でも、A がとても多く、D がとても少ないなら、よく出る文字に短い符号、あまり出ない文字に長い符号を付けたほうが、全体は短くなります。
その符号の作り方がハフマン符号化です。①文字ごとの出てくる回数を数える、②回数の一番少ない2つをまとめて1つにする(回数は合計)、③1つになるまでくり返す、④できた木の枝に左 0・右 1 を書き、上から文字までたどった 0 と 1 を符号にします。
5. 平均のビット数と、区切らなくても読めるしくみ
符号の長さ × 回数を合計すると、全体のビット数が出ます。上の例では、固定長の40ビットが 35ビットになり、1文字当たり平均 1.75 ビットです。
ハフマン符号は、どの符号も、ほかの符号の頭の部分になっていません(例えば 0 で始まる符号は A だけ)。そのため、区切りの記号がなくても、前から読めば1通りに区切れます。ただし、受け取る側も符号表(どの文字がどの符号か)を知っている必要があり、その表を一緒に送る分だけ、実際の圧縮率は少し悪くなります。
全体のビット数=(回数×符号の長さ)の合計。平均=全体÷文字数。
6. 可逆圧縮と非可逆圧縮
ランレングスやハフマン符号のように、展開すると元と完全に同じに戻る圧縮を可逆圧縮と呼びます。文書やプログラムは1ビットでも違うと困るので、可逆圧縮(ZIP など)を使います。
写真・音楽・動画では、人の目や耳では気づきにくい細かい部分を捨てて、もっと小さくする非可逆圧縮がよく使われます(JPEG、MP3 など)。元には完全に戻りませんが、ずっと小さくなります。どこまで捨てるか(画質や音質)は、設定で選べることが多いです。
ひとことで言うと圧縮は表し方の工夫で小さくすること。元に戻る可逆と、細部を捨てる非可逆がある。
例題
例題1 白黒の行をランレングスで
16画素の行「白白白白白白白白白白黒黒黒白白白」を、1つのかたまりを「色1ビット(白0・黒1)+個数4ビット」で表すランレングスで符号にしましょう。何ビットになり、圧縮率は何%ですか(元は1画素1ビット)。
- 固まりに分けます:白10、黒3、白3 の3つ。
- 符号:白10 → 0 1010、黒3 → 1 0011、白3 → 0 0011。3つ × 5ビット = 15ビット。
- 元は 16ビットなので、圧縮率は 15÷16×100 = 93.75%。あまり縮みませんでした。白がもっと長く続く行ほど、よく縮みます。
例題2 ハフマン符号で何ビット?
16文字の文字列に、A が8回、B が4回、C が2回、D が2回出てきます。ハフマン符号で表すと何ビットになりますか。固定長(1文字2ビット)と比べた圧縮率も求めましょう。
- 少ない2つをまとめる:C(2)と D(2)で 4。次に B(4)とそれで 8。最後に A(8)とそれで 16。
- 左 0・右 1 で符号を付けると、A=0、B=10、C=110、D=111。
- 全体:8×1+4×2+2×3+2×3=28ビット。固定長は 16×2=32ビットなので、圧縮率は 28÷32×100=87.5%。
練習
さわってみよう
ランレングス:絵を変えて長さを比べる
6×6 のマス目を押して白と黒を変えると、固まりの符号と全体のビット数、圧縮率が変わります。マス目は1行目の左から右へ、続けて2行目…と1列につなげて読みます。「真っ白」「四角のわく」「市松もよう」で、元の36ビットより短くなるか長くなるかを予想してから押してみましょう。
同じ色が長く続くほど短くなり、こまかく入れ替わると元より長くなります。データの性質によって、向いている圧縮方法が違います。
ハフマン符号:木を作る
文字列を選び、「2つま止める」を押して、回数の少ない2つから順にまとめていきます。最後まで行くと、木と符号表、全体のビット数が出ます。どの文字が一番短い符号になるか、予想してから進めましょう。
回数のかたよりが大きいほどよく縮み、回数がほぼ同じなら固定長とあまり変わりません。同じ回数の組が複数あると、作り方によって符号は変わることがありますが、全体のビット数は同じになります。
やってみよう(共通テスト形式)
このサイトで作った問題です(過去の試験問題ではありません)。
気象部の A さんは、11月の30日間の天気を毎日「晴・曇・雨・雪」の4種類で記録した。回数は、晴 15日、曇 8日、雨 5日、雪 2日だった。この記録を、0 と 1 でできるだけ短く表したい。
A さん:4種類なので、1日を2ビット(晴 00、曇 01、雨 10、雪 11)で表せば、30日分は ア ビットです。
先生:晴が多いから、ハフマン符号にすると短くできるよ。回数の少ない2つから順にまとめて木を作ってみよう。
A さん:できました。晴=0、曇=11、雨=101、雪=100 です。
この単元が出た過去問の解説
ちょっと寄り道:豆知識・こぼれ話
試験に出るとはかぎりませんが、知っていると情報がもっと面白くなる話です。
ハフマン符号は、学生のレポートから生まれた
1951年、アメリカのマサチューセッツ工科大学(MIT)の大学院生デビッド・ハフマンは、情報理論の授業を取っていました。先生のロバート・ファノは、「期末試験を受けるか、レポートを書くか」を選ばせました。レポートの課題は「一番効率のよい2進数の符号の作り方」でした。それまでに知られていた方法(シャノン・ファノ符号)は、いつも最も短くなるとは限りませんでした。
ハフマンは、試験勉強に切りかえようとしたころに、出る回数の少ない文字から2つずつまとめて木を作る方法を思いつき、それが最も短くなることを証明しました。1952年に論文として発表されたこの方法は、今も ZIP や PNG、JPEG の中で使われています。
参考:D. A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes”, Proceedings of the IRE, 1952/いきさつは G. Stix による紹介記事(Scientific American, 1991年9月)、A. Moffat, “Huffman Coding”, ACM Computing Surveys, 2019 による/ZIP・PNG で使う Deflate 形式は RFC 1951
ファクスは、白と黒の「続く長さ」を送っている
白黒のファクスは、紙を細い横の線に分け、1行ずつ「白が何個続き、次に黒が何個続くか」という長さを送っています。このページのランレングス圧縮と同じ考え方です。
国際電気通信連合(ITU-T)の勧告 T.4 では、基本の方式として、この長さに、よく出る長さほど短い符号を割り当てる「修正ハフマン符号」を使うと決めています。つまりファクスは、ランレングスとハフマン符号を組み合わせているのです(前の行との違いを使って、さらに縮める方式も決められています)。この基本の方式では、どの行も白から数え始める決まりなので、黒から始まる行は「白が0個」から送ります。
参考:ITU-T 勧告 T.4(グループ3ファクシミリ装置の標準化)
JPEG は、もともと「会の名前」
写真でおなじみの JPEG(ジェイペグ)は、Joint Photographic Experts Group の頭文字です。元は、画像の規格を作った専門家の集まりの名前でした。
この会は、ISO・IEC と、電話の規格を決める CCITT(今の ITU-T)が合同で作ったもので、1992年に写真などの静止画像の圧縮方式の規格(ITU-T T.81。ISO/IEC 10918-1 も同じ内容)をまとめました。会の名前が、そのまま画像の形式の呼び名として広まったのです。動画の MPEG(エムペグ)も、Moving Picture Experts Group という会の名前から来ています。
参考:ITU-T 勧告 T.81(1992年9月承認。ISO/IEC 10918-1 と同じ内容。CCITT 第8研究委員会と ISO/IEC の JPEG が共同で作成)
わからなかったら、ここへもどる
- ビットとバイト、情報量(nビットで何通り)
- 小学算数・中学数学「割合(百分率)・平均」準備中
先生・おうちの方へ
つまずきやすい所:①圧縮率の定義(圧縮後÷圧縮前か、減った割合か)が本によって違うこと。問題文の定義に必ず従うよう伝えてください。②ハフマン木で、まとめた固まりも次の比べる対象に入れ忘れる。③ランレングスの符号の決まり(色・個数の順、個数のビット数)が問題ごとに違うこと。
ハフマン符号について:同じ回数の組がある場合、まとめ方や左右の付け方によって符号そのものは変わりますが、全体のビット数(平均符号長)は同じ最小値になります。このページと部品は「回数が同じなら先に出てきたもの(先にできた固まり)を先にまとめる、小さい方を左(0)」で作っています。実際には符号表を相手に伝える必要があり、その分の大きさも考えると、短いデータでは圧縮率が悪くなります。
数値について:ハフマン符号の全体のビット数・平均・圧縮率と、ランレングスの例は verify/c2-assyuku.py で計算し直しています。形式の例(ZIP・PNG・GIF・FLAC は可逆、JPEG・MP3・AAC・H.264 は非可逆)は、それぞれの一般的な使い方での分類です。
学習指導要領との関係:解説 (2)ア(ア) では、デジタル化で蓄積・編集・圧縮・転送がしやすくなること、可逆圧縮と非可逆圧縮で実際に圧縮・展開して特性の違いをつかむことが挙げられています。研修用教材では、ランレングス法、ハフマン法と圧縮率の計算が扱われています。共通テストでは、データの持ち方を変えてビット数を比べる考え方が問われています。
学習指導要領:情報Ⅰ (2)ア(ア) / 参考:高等学校学習指導要領(平成30年告示)解説 情報編 情報Ⅰ (2)ア(ア)、文部科学省「高等学校情報科『情報Ⅰ』教員研修用教材」第2章 学習6「デジタルにするということ」(圧縮)