問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 个字符成了 B 而不是 C。
- イ
正解 置换表为 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 只有 1 个而不是 3 个，相当于漏读了 2 个 A（2 个 0）。
错误エ
把 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；最后再用整体的比特数是否与题给一致来验算。
用語