問題
四つのアルファベットa〜dから成るテキストがあり、各アルファベットは2ビットの固定長2進符号で符号化されている。このテキストにおける各アルファベットの出現確率を調べたところ、表のとおりであった。
各アルファベットの符号を表のような可変長2進符号に変換する場合、符号化されたテキストの、変換前に対する変換後のビット列の長さの比は、およそ幾つか。
アルファベット 出現確率 可変長2進符号 a 40% 0 b 30% 10 c 20% 110 d 10% 111 ア：0.75 イ：0.85 ウ：0.90 エ：0.95
結論
答えは「エ：0.95」です。
解き方
ステップ1：変換前（固定長）の合計ビット数を出す
問題文には「各アルファベットは2ビットの固定長」とある。
つまり、a、b、c、d、どの文字が来てもすべて「2ビット」を使う。
テキスト全体が100文字だとすると、合計のビット数は下記となる。
- 100文字 × 2ビット ＝ 200ビット
これが「変換前の長さ」。
ステップ2：変換後（可変長）の合計ビット数を出す
次に、表のルールに従って変換した後の長さを計算する。
100文字の文章の中で、それぞれの文字が何文字出てくるかは「出現確率」をそのまま「文字数」に置き換えることができる。
-
a: 100文字中 40文字 × 1ビット（符号
0） ＝ 40ビット -
b: 100文字中 30文字 × 2ビット（符号
10） ＝ 60ビット -
c: 100文字中 20文字 × 3ビット（符号
110） ＝ 60ビット -
d: 100文字中 10文字 × 3ビット（符号
111） ＝ 30ビット
これをすべて足し合わせる。
- 40 ＋ 60 ＋ 60 ＋ 30 ＝ 190ビット
これが「変換後の長さ」。
よく出る文字（a）のビット数を短くしたことで、全体のデータ量が少し圧縮されている。
ステップ3：変換前と変換後の比率を計算する
最後に、問題で問われている「変換前に対する変換後の比」を求める。
- 変換後の長さ ÷ 変換前の長さ
- 190ビット ÷ 200ビット ＝ 0.95
したがって、正解は エ（0.95） となる。
別解：平均符号長で解く
100文字と仮定しなくても、出現確率から「1文字あたりの平均ビット数」を求めれば解ける。
- 平均符号長 ＝ 0.4×1 ＋ 0.3×2 ＋ 0.2×3 ＋ 0.1×3 ＝ 1.9ビット
- 固定長は2ビットなので、1.9 ÷ 2 ＝ 0.95
この方法なら、文字数を置く手間が省けて試験でも時間を短縮できる。
まとめ
今回のように「よく出る文字には短い符号を、あまり出ない文字には長い符号を割り当てる」のが、可変長符号によるデータ圧縮の基本的な考え方で、出現確率から最適な符号を作る方法をハフマン符号化と呼ぶ。
ZIPファイルの圧縮では、「同じ文字列の繰り返しを短い記述に置き換える」処理と、このハフマン符号化による「よく出る記号ほど短いビット列にする」処理を組み合わせている。
