平成28年度春期 データベーススペシャリスト 午前Ⅰ 問2

比較の前に前提条件を確かめる手順

複数の方式を比べる問題では、まず各方式が問題の求める前提を満たしているかを一つずつ確認し、満たすものだけを比較対象に残すという順序で考えると、判断の根拠が整理しやすくなります。

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

この問題で着目すべきは、数値の大小を比べる前に、各方式が受け取った側で元の情報を取り違えずに戻せるかという前提を、自分の手で具体的に試して確かめる姿勢を持てるかという点です。

視点

方式同士を比べるとき、評価の尺度が複数あるなら、どれが最低限満たすべき条件で、どれが優劣を比べるための尺度なのかを先に区別しておくと混乱しにくくなります。前提を満たさない方式は、他の尺度でどれほど有利に見えても比較の対象にはなりません。前提を確かめるには、短い入力例を自分で作り、変換と逆変換を手作業でたどる方法が有効です。

確認ポイント

• 各方式について短い入力例を自分で作り、変換した結果を実際に書き出してみたか
• 書き出した結果を区切りを知らない立場で先頭から読み戻し、別の読み方が生じないか試したか
• 前提の確認が済む前に、長さや効率などの数値の比較へ進んでしまっていないか

正解

ウ

解説

一意に復号できないア・イを除き、一意復号可能なウとエの平均符号長を比べます。ウは1.7ビット/文字、エは2.0ビット/文字なので、正答はウです。

一意復号できない方式の除外

アでは、ビット列00が「a、a」（0、0）とも「c」（00）とも読めます。イでは、ビット列010が「b、a」（01、0）とも「a、c」（0、10）とも読めます。同じビット列に複数のメッセージが対応するので、ア・イは一意に復号できません。

接頭語条件の位置付け

ウはどの符号語も他の符号語の先頭部分になっていない（接頭語条件を満たす）ため、先頭から読むだけで区切りが決まり、一意に復号できます。エは全て2ビットの固定長なので、2ビットずつ区切れば一意に復号できます。ただし、接頭語条件は即時に復号できるための十分条件です。満たさない符号でも一意に復号できる場合があるので、ア・イについては上の具体例で復号不能と判断しています。

平均符号長の比較

平均符号長は「出現確率×符号長」の合計です。ウは0.5×1ビット＋0.3×2ビット＋0.1×3ビット＋0.1×3ビット＝1.7ビット/文字、エは0.5×2ビット＋0.3×2ビット＋0.1×2ビット＋0.1×2ビット＝2.0ビット/文字です。参考までに、アは1.2ビット/文字、イは1.5ビット/文字とウより短くなりますが、一意に復号できないため条件を満たしません。したがって、条件を満たして最も短いのはウです。

選択肢ア

これは不正解だよ。アはa=0、b=1、c=00、d=11で、平均符号長は0.5×1＋0.3×1＋0.1×2＋0.1×2＝1.2ビット/文字と4方式で最も短いよ。でもビット列00は「a,a」とも「c」とも読めるし、11も「b,b」と「d」の両方に読めるんだ。元のメッセージを一意に復号できないので、条件を満たさないよ。

選択肢イ

これは不正解だよ。イはa=0、b=01、c=10、d=11で、平均符号長は0.5×1＋0.3×2＋0.1×2＋0.1×2＝1.5ビット/文字だよ。でもビット列010は「b(01),a(0)」とも「a(0),c(10)」とも区切れるんだ。同じビット列に複数のメッセージが対応して一意に復号できないので、条件を満たさないよ。

選択肢ウ（正解）

これは正解だよ。ウはa=0、b=10、c=110、d=111で、どの符号語も他の符号語の先頭部分になっていない（接頭語条件を満たす）から、先頭から読めば区切りが一つに決まって一意に復号できるよ。平均符号長は0.5×1＋0.3×2＋0.1×3＋0.1×3＝1.7ビット/文字で、一意に復号できるエの2.0ビット/文字より短いんだ。

選択肢エ

これは不正解だよ。エは全ての文字が2ビットの固定長符号だから、2ビットずつ区切れば一意に復号できるよ。でも平均符号長は0.5×2＋0.3×2＋0.1×2＋0.1×2＝2.0ビット/文字で、出現頻度の高いaにも2ビット使っているんだ。ウの1.7ビット/文字より長いので、「最も短くなるもの」には当たらないよ。

学習のポイント

一意復号可能性の判定（接頭語条件は十分条件）と、出現頻度による加重平均符号長の計算