問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
テクノロジ系基礎理論 › 情報に関する理論
This question's explanation and your answers so far.
解説
問 72
Incorrectア
Encoding ABBAAABB with the substitution table gives 0+10+10+0+0+0+10+10 = 010100001010, which is 12 bits. The given string is 10 bits, so the lengths do not match in the first place. Even comparing the bit strings from the front, the 1st bit (0) and the 2nd bit (1) match, but the 3rd bit differs (the given string has 1, while ア has 0). In terms of characters, this is because the 2nd character is B instead of C.
- イ
正解 The substitution table is A→0, B→10, C→11. A code that starts with 1 is always 2 bits, and 0 is always 1 bit, so you can uniquely restore the original characters just by reading the bit string from the front: “if it is 0, take 1 bit as one character; if it is 1, read 2 bits together.” Splitting the given “0110001010” from the front gives 0 → A, 11 → C, 0 → A, 0 → A, 0 → A, 10 → B, 10 → B, so the split is 0 / 11 / 0 / 0 / 0 / 10 / 10, seven pieces in all. Putting them together gives ACAAABB, so choice イ is correct. Checking in reverse by encoding イ also gives 0+11+0+0+0+10+10 = 0110001010, exactly matching the given bit string (10 bits in total).
Incorrectウ
Encoding ACABB gives 0+11+0+10+10 = 01101010, which is only 8 bits, 2 bits short of the given 10 bits. Compared with the correct answer ACAAABB, there is only one A after the C instead of three, so two characters’ worth of A (two 0s) have been missed.
Incorrectエ
Encoding CAAABB gives 11+0+0+0+10+10 = 110001010, which is 9 bits, one bit shorter than the given string. The given string starts with 0, meaning the first character is A, but エ drops that leading A and starts directly with C (the leading 0 = A, worth one character, is missing).
ここがポイント
- With codes like A→0 / B→10 / C→11, where no code forms the beginning of another code (a code satisfying the prefix condition), a bit string can be decoded uniquely from the front even without separators.
- Decoding only requires reading greedily from the front: when 0 comes, take 1 bit as A; when 1 comes, read 2 bits together, taking 10 as B and 11 as C. Finally, check your answer by seeing whether the total number of bits matches the given string.
用語