DE-S08｜情報Ⅰ 対策問題

正答

1

この問題のポイント

ハフマン法（頻度に応じた可変長符号） を問う問題です。「よく出るものほど短く」という圧縮の発想を理解しましょう。

解説

文字をビット列に置き換えるとき、全文字に同じ長さの符号を使う方式を固定長符号、文字によって長さを変える方式を可変長符号と呼びます。4種類の文字なら固定長では1文字2ビット(2²=4通り)必要です。

ハフマン法は可変長符号の代表で、出現頻度の高いデータに短い符号、頻度の低いデータに長い符号を割り当てます。この問題ならA(50%)に最短の符号、D(5%)に最長の符号を与えます。よく使う文字が短くなるので、文章全体の平均符号長が固定長より短くなり、データ量を削減できます。元に完全に戻せる可逆圧縮です。

身近な例で言えば、モールス信号が英語で最頻出の「E」に最短の符号(トン1つ)を割り当てているのと同じ発想です。「よく出るものほど短く」が圧縮の基本原理だと押さえましょう。

共通テストでは、この考え方を選ばせる問題に加えて、「平均符号長 = Σ(頻度×符号長)を計算し、固定長と比べて何%節約できたか」まで計算させる問題が出題されています。原理と計算の両方を準備しておきましょう。

選択肢の確認

1．○ 頻度が最も高いAを最短、最も低いDを最長にするのがハフマン法の割り当て。
2．× 全文字同じ長さは固定長符号。平均符号長が縮まず圧縮にならない。
3．× 逆の割り当てでは、よく出るAが長い符号になり、固定長よりかえって長くなる。
4．× アルファベット順は頻度と無関係で、圧縮効果が得られる保証がない。

ここだけは覚えよう

ハフマン法=頻度が高いほど短い符号を割り当てる可逆圧縮 — 平均符号長を短くしてデータ量を減らす。