ITパスポート 2012年 秋期 問72

文字の置換表（可変長ビット列）の復元【ITパスポート 解説】

正解の理由

解法ステップ

1. 置換表を確認する：
   A → 0、B → 10、C → 11
2. 与えられたビット列を左から順に読む（"0110001010"）。
3. 次のルールで取り出す：
   • 先頭ビットが 0 のときは A（0 は A に対応）を確定して1ビット分を切る。
   • 先頭ビットが 1 のときは次の1ビットも見て、"10" なら B、"11" なら C を確定して2ビット分を切る。
4. 上記を繰り返すと、読み取り結果は次の通り：
   • 0 → A（残り "110001010"）
   • 11 → C（残り "0001010"）
   • 0 → A（残り "001010"）
   • 0 → A（残り "01010"）
   • 0 → A（残り "1010"）
   • 10 → B（残り "10"）
   • 10 → B（残り ""）
5. したがって元の文字列は A C A A A B B、すなわち ACAAABB（選択肢イ）。

選択肢別の誤答解説

• ア: ABBAAABB
  エンコード：0 10 10 0 0 0 10 10 → 010100001010（12ビット）
  与えられた 0110001010（10ビット）と異なるため誤り。
• イ: ACAAABB ← 正解
  エンコード：0 11 0 0 0 10 10 → 0110001010（10ビット）
  与えられたビット列と一致するため正解。
• ウ: ACABB
  エンコード：0 11 0 10 10 → 01101010（8ビット）
  長さも内容も一致しないため誤り。
• エ: CAAABB
  エンコード：11 0 0 0 10 10 → 110001010（9ビット）
  長さが異なり一致しないため誤り。

よくある誤解

1. 「0 を '10' の一部と考えてもよい」と誤解する。
   • 置換表がプレフィックスになっていなければ混乱しますが、今回は A=0 が他のコードの先頭ではないため、0 は単独で A と確定できます。よって左から最短で決めてよいです。
2. 右から読む・右端で区切ろうとするミス。
   • ここでは左から順に読むのが自然で確実です（与えられている置換表の符号が左から読んで決められるため）。右から読むと解釈が変わり誤答になります。
3. 「全て同じ長さでグループ化すればよい」と考える。
   • 符号が可変長なので固定長で区切ると誤りになります。必ず置換表を参照して可変長で切り分けます。

補足コラム

• プレフィックスコード（prefix-free code）：ある符号が別の符号の先頭になっていないコード集合のこと。例：{0, 10, 11} はプレフィックスコード。プレフィックスであることで「左から最短一致」で一意にデコードできます。
• ハフマン符号（Huffman coding）：可変長でよく使われる圧縮方法の一つで、文字の出現頻度に応じてプレフィックスコードを作ります。今回の問題はハフマン符号そのものではありませんが、可変長符号の性質理解に役立ちます。

mapping = {'0':'A', '10':'B', '11':'C'}
s = "0110001010"
i = 0
result = []
while i < len(s):
    if s[i] == '0':
        result.append('A'); i += 1
    else:
        # s[i] == '1' のときは2ビット読む
        result.append('B' if s[i+1] == '0' else 'C')
        i += 2
print(''.join(result))  # ACAAABB

FAQ