平成24年度 秋期 ITパスポート試験 問72 解説 文字列の置換処理

置換表に従って、与えられた2進数文字列 0110001010 を左から順に切り出し、文字に変換します。

A = 0 B = 10 C = 11

この表に基づき、文字列 0110001010 を先頭から確認します。

1. 0 は A です。
2. 次の 11 は C です。
3. 次の 0 は A です。
4. 次の 0 は A です。
5. 次の 10 は B です。
6. 次の 10 は B です。 これらをつなげると ACAAABB となります。

可変長符号という考え方

この問題で使われているのは、文字ごとに割り当てる符号の長さが異なる「可変長符号」という考え方です。Aは1ビット、BとCは2ビットで表現されています。

通常の固定長符号（例えば、すべての文字を8ビットで表すASCIIコードなど）とは異なり、出現頻度の高い文字に短い符号を割り当てることで、データ全体を圧縮できるという特徴があります。

復号のプロセス

復号（符号化されたデータをもとのデータに戻すこと）を行う際は、左から順に符号を読み取り、それが置換表のどのパターンに一致するかを判断します。

今回の例で言えば、先頭の 0 を読んだ瞬間に、A（0）なのかB（10）なのかC（11）なのかを判断しなければなりません。もしAが 0 で始まり、Bが 01 で始まるようなルールであれば、次に 1 が来るか 0 が来るかを見るまで確定できません。このように、符号の先頭部分だけを見てもどの文字か区別できないような組み合わせを作らないように注意する必要があります。

コンピュータのデータ圧縮と符号化

この問題の背後には、ハフマン符号などの「データ圧縮アルゴリズム」の基礎となる考え方があります。コンピュータの世界では、情報を効率よく保存・転送するために、あらかじめ決めたルールに基づいてデータを短いビット列に置き換える処理が不可欠です。

例えば、Webサイトで見かける画像形式や動画形式の多くは、この可変長符号の応用や、より複雑な数学的処理を組み合わせることでファイルサイズを小さくしています。ITパスポート試験では、このような具体的な変換作業を通じて、コンピュータが情報を「どのように表現し、どのように処理しているか」という基礎的な論理思考力を問うています。

参考リンク

• 【ITパスポート】計算問題の解説（可変長符号）
• ハフマン符号で圧縮の仕組みを理解する
• 情報理論における符号化定理（可変長符号の定義）