令和2年度10月 データベーススペシャリスト 午前Ⅰ 問2

文字の符号化と加重平均

符号語を連結したときの読み取り方と、出現回数に偏りがあるデータの平均について調べてみよう。

この問題で問われていること

文字ごとのビット列をつなぐとき、区切りの判断と全体の長さを、それぞれどのように検討できるだろうか。

文字の符号化と加重平均

文字ごとのビット列をつなぐとき、区切りの判断と全体の長さを、それぞれどのように検討できるだろうか。

確認ポイント

• 固定長符号と可変長符号では、文字の区切りを読み取る手順がどう違うか。
• 自分で簡単な符号表を作り、異なる文字列が同じビット列になる例を探せるか。
• 短い文字列を幾つか試すことと、任意の文字列について一意に復号できることを確かめることには、どのような違いがあるか。 単純平均と加重平均の違いを調べ、100文字のメッセージを想定した総ビット数の数え方と対応付けられるか。

正解

ウ

解説

添付の公式解答表では，午前Ⅰの問2の正解はウ。一意に復号できることと，ビット列が最も短くなることの両方が必要です。アとイは，同じビット列に複数の文字列が対応するので条件を満たさない。ウとエは一意に復号できる。各文字の出現頻度と符号長の積を合計すると，ウは平均1.7ビット／文字，エは平均2ビット／文字となるため，ウが最も短い。

添付の公式解答表では，午前Ⅰの問2の正解はウ。一意に復号できることと，ビット列が最も短くなることの両方が必要です。アとイは，同じビット列に複数の文字列が対応するので条件を満たさない。ウとエは一意に復号できる。各文字の出現頻度と符号長の積を合計すると，ウは平均1.7ビット／文字，エは平均2ビット／文字となるため，ウが最も短い。

選択肢ア

誤り。ビット列00は，cともaaとも解釈できる。同様に11は，dともbbとも解釈できるので，一意に復号できない。

選択肢イ

誤り。ビット列010は，ac（0・10）ともba（01・0）とも解釈できるので，一意に復号できない。

選択肢ウ（正解）

正しい。どの符号語も他の符号語の先頭部分になっていないので，一意に復号できる。平均符号長は0.5×1＋0.3×2＋0.1×3＋0.1×3＝1.7ビット／文字で，エより短い。

選択肢エ

誤り。全て2ビットの異なる符号なので，一意に復号できる。ただし，平均符号長は2ビット／文字で，ウの1.7ビット／文字より長い。

学習のポイント

文字ごとのビット列をつなぐとき、区切りの判断と全体の長さを、それぞれどのように検討できるだろうか。