情報の勉強高校 情報Ⅰ

第2章 コミュニケーションと情報デザイン

データの圧縮(可逆・非可逆・ランレングス・ハフマン符号)

写真や動画はそのままでは大きすぎるので、表し方を工夫して小さくします。このページでは、圧縮と展開てんかい、圧縮率あっしゅくりつ、同じものが続く長さを記録するランレングス圧縮、よく出る文字を短くするハフマン符号(木の作り方と平均ビット数)、可逆圧縮かぎゃくあっしゅくと非可逆圧縮ひかぎゃくあっしゅくの違いと身近な形式を、図と動く部品で確かめます。

説明

1. 圧縮:意味を変えずに、データを小さくする

写真や動画をたくさん保存すると、スマホや SD カードがすぐにいっぱいになります。送るのにも時間がかかります。そこで、データの表し方を工夫して、ビット数を減らすことを圧縮と呼びます。圧縮したデータを元の形に戻すことを展開(解凍かいとう)と呼びます。

どれだけ縮んだかは圧縮率で表します。このページでは、圧縮率=圧縮後の大きさ÷圧縮前の大きさ×100(%)とします。100 が 40 になれば 40% で、小さいほどよく縮んだことになります。

圧縮と展開元のデータ100圧縮40展開元に戻る100圧縮率 = 40 ÷ 100 = 40%圧縮率=圧縮後の大きさ÷圧縮前の大きさ×100(%)。小さいほどよく縮んでいます。(本によっては「減った割合」を圧縮率と呼ぶこともあるので、問題文の決まりを確かめます。)

圧縮率=圧縮後÷圧縮前×100(%)。小さいほどよく縮んでいる。

2. ランレングス圧縮:続く数を数える

「AAAAABBBCC」は、「A が5個、B が3個、C が2個」と言えば伝わります。このように、同じものが続く固まり(ラン)の長さを記録する方法をランレングス圧縮(ランレングス符号化ふごうか)と呼びます。

展開するときは、「A5」を「AAAAA」のように並べ直すだけで、元とまったく同じに戻ります。

ランレングス:同じものが続いたら「何が・何個」で書くAAAAABBBCC10文字A5B3C26文字10文字が6文字になりました(圧縮率 60%)。「A5」を「AAAAA」に戻せば、元と同じ文字列に戻ります。同じものが長く続くほどよく縮みます。

3. ランレングスが向くもの・向かないもの

白黒の画像(ファクスの文書など)は、白い画素がそが長く続くので、ランレングスでよく縮みます。ここでは、1つのかたまりを「色1ビット(白0・黒1)+個数4ビット」の5ビットで表すことにします。

ところが、白と黒がこまかく入れ替わる画像では、固まりの数が増えて、かえって元より長くなります。普通の文章も同じ文字があまり続かないので、ランレングスには向きません。どの圧縮方法も、データの性質に合うときによく縮みます。

白黒の画像:1つのかたまりを「色1ビット+個数4ビット」で白が続く行→ 白12 黒4そのまま 16ビット → ランレングス 2×5=10ビット短くなった白黒が入れ替わる行→ 白1 黒1 白1 黒1 …(16個の固まり)そのまま 16ビット → ランレングス 16×5=80ビットかえって長くなった!

4. ハフマン符号:よく出る文字を短く

A・B・C・D の4種類の文字なら、普通は1文字を2ビット(00・01・10・11)で表します(固定長)。でも、A がとても多く、D がとても少ないなら、よく出る文字に短い符号、あまり出ない文字に長い符号を付けたほうが、全体は短くなります。

その符号の作り方がハフマン符号化です。①文字ごとの出てくる回数を数える、②回数の一番少ない2つをまとめて1つにする(回数は合計)、③1つになるまでくり返す、④できた木の枝に左 0・右 1 を書き、上から文字までたどった 0 と 1 を符号にします。

ハフマン符号:少ない2つから順にまとめて木を作る1. D(2)と C(3)をまとめて 52. B(5)と DC(5)をまとめて 103. A(10)と BDC(10)をまとめて 2001A10回01B5回01D2回C3回51020左へ 0、右へ 1A(10回)0B(5回)10C(3回)111D(2回)110

5. 平均のビット数と、区切らなくても読めるしくみ

符号の長さ × 回数を合計すると、全体のビット数が出ます。上の例では、固定長の40ビットが 35ビットになり、1文字当たり平均 1.75 ビットです。

ハフマン符号は、どの符号も、ほかの符号の頭の部分になっていません(例えば 0 で始まる符号は A だけ)。そのため、区切りの記号がなくても、前から読めば1通りに区切れます。ただし、受け取る側も符号表(どの文字がどの符号か)を知っている必要があり、その表を一緒に送る分だけ、実際の圧縮率は少し悪くなります。

どれだけ短くなったか(20文字のとき)文字回数固定長(2ビット)ハフマン符号ビット数A1000(10×2=20)010×1=10B501(5×2=10)105×2=10C310(3×2=6)1113×3=9D211(2×2=4)1102×3=6固定長:20×2=40ビット ハフマン符号:35ビット1文字の平均 35÷20=1.75ビット、圧縮率 35÷40=87.5%区切りがなくても読める:0110111… は 0|110|111… と、前から1通りに区切れる

全体のビット数=(回数×符号の長さ)の合計。平均=全体÷文字数。

6. 可逆圧縮と非可逆圧縮

ランレングスやハフマン符号のように、展開すると元と完全に同じに戻る圧縮を可逆圧縮と呼びます。文書やプログラムは1ビットでも違うと困るので、可逆圧縮(ZIP など)を使います。

写真・音楽・動画では、人の目や耳では気づきにくい細かい部分を捨てて、もっと小さくする非可逆圧縮がよく使われます(JPEG、MP3 など)。元には完全に戻りませんが、ずっと小さくなります。どこまで捨てるか(画質や音質)は、設定で選べることが多いです。

可逆圧縮と非可逆圧縮可逆圧縮・展開すると、元と完全に同じ・1ビットでも違うと困る物に例ZIP(文書・プログラム)PNG・GIF(画像)FLAC(音声)非可逆圧縮・人が気づきにくい細かい所を捨てる・元には完全には戻らない・よく縮む例JPEG(写真)MP3・AAC(音声)H.264 など(動画)非可逆圧縮で保存し直すたびに、少しずつ画質や音質が落ちることがあります。

ひとことで言うと圧縮は表し方の工夫で小さくすること。元に戻る可逆と、細部を捨てる非可逆がある。

例題

例題1 白黒の行をランレングスで

16画素の行「白白白白白白白白白白黒黒黒白白白」を、1つのかたまりを「色1ビット(白0・黒1)+個数4ビット」で表すランレングスで符号にしましょう。何ビットになり、圧縮率は何%ですか(元は1画素1ビット)。

例題2 ハフマン符号で何ビット?

16文字の文字列に、A が8回、B が4回、C が2回、D が2回出てきます。ハフマン符号で表すと何ビットになりますか。固定長(1文字2ビット)と比べた圧縮率も求めましょう。

練習

1
次のうち、展開すると元のデータと完全に同じに戻る「可逆圧縮」が必要なものはどれですか。
2
「WWWWWWBBWWWW」を、「文字+続く個数」のランレングスで表したものはどれですか。
3
800KB のファイルを圧縮したら 200KB になりました。圧縮率(圧縮後÷圧縮前×100)は何%ですか。
4
ハフマン符号で A=0、B=10、C=111、D=110 と決めました。ビット列「0101110110」を文字に戻したものはどれですか。
5
10文字の文字列に A が6回、B が2回、C が1回、D が1回出てきます。ハフマン符号で表すと全体は何ビットですか。

さわってみよう

ランレングス:絵を変えて長さを比べる

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 です。

問1
空欄 ア に入る数を答えよ。
問2
A さんが作ったハフマン符号で30日分を表すと、全体は何ビットになるか。
問3
固定長の2ビットと比べたときの圧縮率(ハフマン符号のビット数÷固定長のビット数×100)として最も近いものを選べ。
問4
この方法についての説明として最も適当なものを選べ。

この単元が出た過去問の解説

ちょっと寄り道:豆知識・こぼれ話

試験に出るとはかぎりませんが、知っていると情報がもっと面白くなる話です。

ハフマン符号は、学生のレポートから生まれた

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 が共同で作成)

わからなかったら、ここへもどる

あわせて読む

次はこれ

先生・おうちの方へ

つまずきやすい所:①圧縮率の定義(圧縮後÷圧縮前か、減った割合か)が本によって違うこと。問題文の定義に必ず従うよう伝えてください。②ハフマン木で、まとめた固まりも次の比べる対象に入れ忘れる。③ランレングスの符号の決まり(色・個数の順、個数のビット数)が問題ごとに違うこと。

ハフマン符号について:同じ回数の組がある場合、まとめ方や左右の付け方によって符号そのものは変わりますが、全体のビット数(平均符号長)は同じ最小値になります。このページと部品は「回数が同じなら先に出てきたもの(先にできた固まり)を先にまとめる、小さい方を左(0)」で作っています。実際には符号表を相手に伝える必要があり、その分の大きさも考えると、短いデータでは圧縮率が悪くなります。

数値について:ハフマン符号の全体のビット数・平均・圧縮率と、ランレングスの例は verify/c2-assyuku.py で計算し直しています。形式の例(ZIP・PNG・GIF・FLAC は可逆、JPEG・MP3・AAC・H.264 は非可逆)は、それぞれの一般的な使い方での分類です。

学習指導要領との関係:解説 (2)ア(ア) では、デジタル化で蓄積ちくせき・編集・圧縮・転送がしやすくなること、可逆圧縮と非可逆圧縮で実際に圧縮・展開して特性の違いをつかむことが挙げられています。研修用教材では、ランレングス法、ハフマン法と圧縮率の計算が扱われています。共通テストでは、データの持ち方を変えてビット数を比べる考え方が問われています。

学習指導要領:情報Ⅰ (2)ア(ア) / 参考:高等学校学習指導要領(平成30年告示)解説 情報編 情報Ⅰ (2)ア(ア)、文部科学省「高等学校情報科『情報Ⅰ』教員研修用教材」第2章 学習6「デジタルにするということ」(圧縮)