ITパスポート試験 ITパスポート 2012年 (平成24年 秋期) 問72: 図に示すように,文字列の各文字を置換表に従って置き換える処理を考える。このような置換えを行った結果が"0110001010"であったとき,置換え前の文字列はどれ

問題本文

図に示すように,文字列の各文字を置換表に従って置き換える処理を考える。このような置換えを行った結果が"0110001010"であったとき,置換え前の文字列はどれか。 文字の置換表 置換例: A,B,A,B,C,A,B,A → 0,10,0,10,11,0,10,0 → 最終結果"010010110100"

選択肢

• ア.ABBAABB
• イ.ACAAABB
• ウ.ACABB
• エ.CAAABB

正解

イ. ACAAABB

解説

正解はイ(ACAAABB).置換表でA=0,B=10,C=11(プレフィックスコード).「0110001010」を左から順に解析:0=A,1次に1だから11=C,次は0=A,次は0=A,次は0=A,次は10=B,次は10=B.合計でA・C・A・A・A・B・B=ACAAABB(7文字).プレフィックスコード(どの符号も他の符号の先頭にならない)なので一意に復号できる性質を利用する.ハフマン符号の考え方の基本問題で,文字列の長さは「0は1文字,1で始まれば10か11の2文字」で計算する.用語の本質的な定義と典型的な対比語を押さえる重要論点.

選択肢ごとの解説

• ア.ABBAABBは復号結果と一致しない.A=0,B=10で組み立てると0,10,10,0,0,10,10=01010001010だが,設問の0110001010とはビット列が異なる.正しい復号結果はACAAABBで,この組合せは置換結果から導けない別の文字列.
• イ.正解.ACAAABBは置換表に従ってビット列に変換するとA=0,C=11,A=0,A=0,A=0,B=10,B=10で,連結すると0110001010となり設問の結果と完全に一致する.プレフィックスコードの一意復号で導ける正しい元の文字列となる.
• ウ.ACABBの組合せでビット列に変換するとA=0,C=11,A=0,B=10,B=10で連結すると01101010で8ビットしかなく,設問の10ビット(0110001010)に足りない.復号結果として長さも内容も一致しないため不正解の組合せ.
• エ.CAAABBの組合せでビット列に変換するとC=11,A=0,A=0,A=0,B=10,B=10で連結すると110001010(9ビット)で先頭が1.設問のビット列は0で始まる0110001010のため先頭から異なり,この組合せは復号結果と一致しない.