問72
頻出度★★☆
図に示すように，文字列の各文字を置換表に従って置き換える処理を考える。このような置換えを行った結果が“0110001010”であったとき，置換え前の文字列はどれか。 文字の置換表
| 文字 | 置換え後の2進表示 |
|---|---|
| A | 0 |
| B | 10 |
| C | 11 |
置換例
| 文字 | A | B | A | B | C | A | B | A |
|---|---|---|---|---|---|---|---|---|
| 置換表で置き換えた結果 | 0 | 10 | 0 | 10 | 11 | 0 | 10 | 0 |
置き換えた最終結果 010010110100
平成24年度 秋期 ITパスポート試験 問72
テクノロジ系基礎理論 › 情報に関する理論
この問題の解説と、これまでの解答の記録です。
解説
問 72
不正解ア
ABBAAABB を置換表で符号化すると 0+10+10+0+0+0+10+10 = 010100001010 となり 12 ビットです。与件は 10 ビットなので長さからして合いません。ビット列を先頭から照合しても、1 ビット目 (0) と 2 ビット目 (1) までは一致しますが 3 ビット目で食い違います (与件は 1、ア は 0)。文字で言えば 2 文字目が C ではなく B になっているためです。
- イ
正解 置換表は A→0、B→10、C→11 です。1 で始まる符号は必ず 2 ビット、0 は必ず 1 ビットなので、ビット列は先頭から順に「0 なら 1 文字ぶん、1 なら 2 ビットまとめて」と読むだけで一意に元の文字へ戻せます。与件の「0110001010」を先頭から区切ると、0 → A、11 → C、0 → A、0 → A、0 → A、10 → B、10 → B となり、区切り方は 0 / 11 / 0 / 0 / 0 / 10 / 10 の 7 個です。並べると ACAAABB となり、選択肢 イ が正解です。逆に イ を符号化して検算しても、0+11+0+0+0+10+10 = 0110001010 と与件にぴったり一致します (合計 10 ビット)。
不正解ウ
ACABB を符号化すると 0+11+0+10+10 = 01101010 で 8 ビットにしかならず、与件の 10 ビットより 2 ビット足りません。正解 ACAAABB と比べると、C の後ろに続く A が 3 個ではなく 1 個しかなく、A 2 文字ぶん (0 が 2 個) を読み落とした形になっています。
不正解エ
CAAABB を符号化すると 11+0+0+0+10+10 = 110001010 で 9 ビットとなり、与件より 1 ビット短くなります。与件は先頭が 0、つまり最初の文字が A であるのに、エ は先頭の A を落としていきなり C から始めてしまっています (与件の先頭 1 文字ぶん 0 = A が欠落)。
ここがポイント
- A→0 / B→10 / C→11 のように、どの符号も他の符号の先頭部分にならない符号 (語頭条件を満たす符号) は、区切り記号がなくてもビット列を先頭から一意に復号できる。
- 復号は先頭から貪欲に読むだけでよい。0 が来たら 1 ビットで A、1 が来たら 2 ビットまとめて読み 10 なら B・11 なら C とし、最後に全体のビット数が与件と一致するかで検算する。
用語