平成22年度秋期 ITサービスマネージャ 午前Ⅰ 問2

符号化と復号

符号を連結したときの読み取り方と、出現頻度を考慮した長さの比較を準備する。

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

固定長符号・可変長符号・平均符号長を調べ、復号の可否と長さをそれぞれどう検討するか考えてみよう。

符号化と復号

固定長符号・可変長符号・平均符号長を調べ、復号の可否と長さをそれぞれどう検討するか考えてみよう。

確認ポイント

• 固定長符号と可変長符号では、連結したビット列の区切りをどのように判断するか。
• 異なる文字列が同じビット列になる例を作れるか。また、短い文字列だけを試す方法にはどんな限界があるか。
• 各文字の符号長を単純に平均する場合と、出現頻度を考慮する場合では、比較結果がどう変わり得るか。

正解

ウ

解説

添付の公式解答表では，問2の正解はウ。まず，一つのビット列が複数の文字列に復号されないことを確認する。アとイは異なる文字列が同じビット列になるため，条件を満たさない。ウはどの符号も別の符号の先頭部分にならず，エは固定長なので，いずれも一意に復号できる。次に，出現頻度で重み付けした平均符号長を比較する。ウは1.7ビット／文字，エは2ビット／文字となるので，ウが最も短い。

添付の公式解答表では，問2の正解はウ。まず，一つのビット列が複数の文字列に復号されないことを確認する。アとイは異なる文字列が同じビット列になるため，条件を満たさない。ウはどの符号も別の符号の先頭部分にならず，エは固定長なので，いずれも一意に復号できる。次に，出現頻度で重み付けした平均符号長を比較する。ウは1.7ビット／文字，エは2ビット／文字となるので，ウが最も短い。

選択肢ア

一意に復号できない。「00」はcともaaとも解釈でき，「11」はdともbbとも解釈できる。

選択肢イ

一意に復号できない。例えば「010」は，aとcの連結（0＋10）とも，bとaの連結（01＋0）とも解釈できる。

選択肢ウ（正解）

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

選択肢エ

すべて2ビットなので，2ビットずつ区切れば一意に復号できる。ただし，1文字当たりの平均符号長は2ビットで，ウの1.7ビットより長い。

学習のポイント

固定長符号・可変長符号・平均符号長を調べ、復号の可否と長さをそれぞれどう検討するか考えてみよう。