SC情報処理安全確保支援士試験 午前Ⅰ

平成22年度秋期 情報処理安全確保支援士 午前Ⅰ 問2

問題文と選択肢を読んで答えを考えてから、下の「正解と解説を見る」で確認しましょう。

問題

a、b、c、dの4文字からなるメッセージを符号化してビット列にする方法として表のア〜エの4通りを考えた。この表はa、b、c、dの各1文字を符号化するときのビット列を表している。メッセージ中でのa、b、c、dの出現頻度は、それぞれ50%、30%、10%、10%であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって、ビット列の長さが最も短くなるものはどれか。
文字a,b,c,dを0と1のビット列に符号化する,ア〜エ4通りの対応表。
文字a,b,c,dを0と1のビット列に符号化する,ア〜エ4通りの対応表。

選択肢

  1. ア
    a=0、b=1、c=00、d=11
  2. イ
    a=0、b=01、c=10、d=11
  3. ウ
    a=0、b=10、c=110、d=111
  4. エ
    a=00、b=01、c=10、d=11
解き方のヒントを見る

符号化と復号

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

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

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

符号化と復号

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

確認ポイント

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

正解

ウ

解説

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

正答

正解はウです。ウは a=0、b=10、c=110、d=111 で、どの符号も別の符号の先頭部分になっていないため(接頭符号)、ビット列を先頭から読むだけで一意に区切って復号できる。ビット列の長さの最小化は、出現頻度で重み付けした平均符号長で比べる。ウの平均符号長は 0.5×1 + 0.3×2 + 0.1×3 + 0.1×3 = 0.5 + 0.6 + 0.3 + 0.3 = 1.7 ビットであり、固定長のエ(2ビット)より短い。

誤答の理由

ア:a=0、b=1、c=00、d=11 は一意に復号できない。ビット列「00」は c とも aa とも、「11」は d とも bb とも解釈でき、復号結果が一つに定まらないためです。

イ:a=0、b=01、c=10、d=11 は一意に復号できない。例えばビット列「010」は、a と c の連結(0+10)とも、b と a の連結(01+0)とも解釈できるためです。

エ:a=00、b=01、c=10、d=11 はすべて2ビットの固定長であり、一意に復号できる。しかし平均符号長は 2 ビットで、ウの 1.7 ビットより長いため、長さが最も短い符号ではありません。

整理

接頭符号(どの符号も別の符号の先頭部分にならない符号)は一意に復号できる。出現頻度の高い文字に短い符号を割り当てると平均符号長が短くなり、この考え方がハフマン符号の基本です。

選択肢ア

一意に復号できない。「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ビットより長い。

学習のポイント

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

解説を確認したら、演習モードや同じ分野の類題で理解を定着させましょう。

出典:独立行政法人 情報処理推進機構(IPA)平成22年度秋期 情報処理安全確保支援士試験 午前Ⅰ 問2(公式資料:問題冊子(PDF) / 解答例)

関連する過去問一覧

IPA Advancedは非公式の学習サイトです。解説にはAIによる補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。運営・編集方針